* Order Structures

Contents
Contents
 1.  Transfinite Recursion Theorem
   1.1.  Transfinite Recursion
   1.2.  Replacement Axioms
 2.  Continued on Page Three

(Continued.)

1. Transfinite Recursion Theorem We continue to study well-orders. Let (A,\leqslant) be a well-order structure.

By definition, A itself has a least element a _ 0. Then we cosider the least element of A\setminus\{a _ 0\}, which is a _ 1, and we can continue this process. For convenience we introduce the following notation:
\[ \downarrow a=\{x\mid x\leqslant a\},\quad \downarrow<a=\{x\mid x<a\}.\]
We call them the (strict) initial segment below a. For example, for the usual < relation on \mathbb N, \downarrow<n=\mathbb N _ {<n}=\{m\in\mathbb N\mid m<n\}. Now we have \downarrow< a _ 0=\varnothing and \downarrow< a _ 1=\{a _ 0\}, and so forth. To be precise, we prove the following transfinite induction principle.

With the idea above, consider the set A\setminus B. If B\subsetneq A then it is a nonempty set, and has a least element m. Hence if t<m then t must be an element of B, indicating \downarrow< m\subseteq B. Therefore m\in B, a contradiction. Thus B=A.□

1.1. Transfinite Recursion Assume now we want to define a mapping f on a set A that is well-ordered, in a way that f(a) is determined by all f(t) where t<a. Possibly this is realized by a mapping g such that f(a)=g(f| _ {\downarrow< a}). The domain of g is the set of mappings from an initial segment to a set B.
\[
B^{<A}=\{h\mid \exists t\in A\, (h:\operatorname{\downarrow<}t\to B)\}.
\]

However if we want to set f(a)=\{f(x)\mid x<a\}, the range of f| _ {\downarrow< a}, then we encounter difficulties since there is no mapping g that maps any set to its range. Such a mapping will have everything in its domain, which fails to be a set. Therefore we want g to be something G like a mapping but not actually a mapping. We allow ourselves a formula \varphi(x,y) as a substitue for a mapping:
\[G=\{(x,y)\mid \varphi(x,y)\}.\]

Since G is not a set, we should refer to \varphi instead of G.

Set \varphi(x,y) to be y=\operatorname{ran}(x), where \operatorname{ran}(x) is the range of x. By the theorem, there exists a unique mapping F on A such that F(a)=\operatorname{ran}(F| _ {\downarrow< a}) for all a\in A.

Set \varphi(x,y) to be the following formula:
\[
(x\in B^{<A}\wedge y=g(x))\vee(x\notin B^{<A}\wedge y=\varnothing).
\]

It clearly holds that for any f there is a unique y such that \varphi(f,y). By the theorem there is a unique mapping F on A such that for any a\in A we have either F| _ {\downarrow< a}\in B^{<A}\wedge F(a)=g(F| _ {\downarrow< a}) or F| _ {\downarrow< a}\notin B^{<A}\wedge F(a)=\varnothing. Since g:B^{<A}\to B, by transfinite induction it is not difficult to see that we have the first case for every a\in A.

(Specifically, suppose for any a\in\operatorname{\downarrow<} t it holds that F| _ {\downarrow< a}\in B^{<A}\wedge F(a)=g(F| _ {\downarrow< a}). Then we consider F(t). On the one hand F| _ {\downarrow< t}\in B^{<A} holds since F(a)=g(F| _ {\downarrow< a})\in B. On the other hand this excludes the second case so that F(t)=g(F| _ {\downarrow< t}). Hence the first case holds for \downarrow< t implies the first case holds for t. By transfinite induction, the first case holds for every a\in A.)

Thus we have the following theorem.

With the axioms so far, we cannot prove the transfinite recursion theorem. A new axiom is therefore added to our list.

1.2. Replacement Axioms We have known the range of a mapping f is a set, so for a set A the image f(A) is also a set. Now consider the case where F is not a mapping but still something like a mapping, so that F maps an element to another element uniquely. Naturally we infer from the behavior of F that F(A) is a set, which generalizes the property of a mapping, but it turns out that we are unable to prove it now.

We have known the set of all sets fails to exist, for it must contain too much elements to become a set but then leads to a contradiction. Intuitively F(A) is not too large to be a set since it is not larger than A, so it is reasonable to adopt an axiom which indicates F(A) is a set whenever A is a set. This is our 8\textsuperscript{th} axiom.

Again, in set theory we should not refer to F but a formula \varphi.

8. Replacement Axioms: Let \varphi(x,y) be a formula not containing B. It is an axiom that
   \begin{gather*}
   \forall A\quad[
   (\forall x\in A)\forall y _ 1\forall y _ 2\, (\varphi(x,y _ 1)=\varphi(x,y _ 2)\Rightarrow y _ 1=y _ 2)\\
   \implies \exists B\, \forall y(y\in B\Leftrightarrow (\exists x\in A)\varphi(x,y))
   ].
   \end{gather*}

It is allowed that \varphi is a formula containing other sets A _ 1,A _ 2,\dots,A _ n, but not B. Only some obvious assertion is needed at the beginning of the axiom.

A quick application: If A is a set, we take \varphi(x,y) to be y=\mathcal P(x) and then obtain \{\mathcal P(a)\mid a\in A\} is a set.

With the replacement axioms, we now prove the axioms adopted are not independent.

First we prove the subset axioms, which asserts the existence of a set \{x\in A\mid \varphi(x)\} given a formula \varphi(x). We set a new formula
\[\psi(x,y)=(y=x)\wedge(x\in A)\wedge\varphi(x).\]

Clearly \psi(x,y _ 1)=\psi(x,y _ 2)\Rightarrow y _ 1=y _ 2, so we can apply replacement axioms to obtain a set \{y\mid (\exists x\in A)\psi(x,y)\}, which is just \{x\in A\mid \varphi(x)\}.

Then we prove the pairing axiom. Suppose A,B are two sets. We set a formula
\[\psi(x,y)=(x=\varnothing\wedge y=A)\vee(x=\{\varnothing\}\wedge y=B).\]

This actually induces a mapping that maps \varnothing to A and \{\varnothing\} to B.

Hence we can apply the replacement axiom to obtain a set
\[\{y\mid (\exists x\in \{\varnothing,\{\varnothing\}\})\psi(x,y)\}=\{A,B\}.\square\]

Transfinite Recursion Theorem

We can now prove the transfinite recursion theorem.

Step 1.

We refer to a "partial mapping" as a mapping f with domain \downarrow a and for any x\in{\downarrow a}, \varphi(f| _ {\downarrow< x},f(x)) holds. Suppose f _ 1,f _ 2 are two partial mappings with domain \downarrow a _ 1 and \downarrow a _ 2 and suppose a _ 1\leqslant a _ 2. We can infer that they agree on the common domain, i.e., f _ 1(x)=f _ 2(x) for any x\leqslant a _ 1. Otherwise, there is a least x such that f _ 1(x)\neq f _ 2(x). Then the two mappings agree on \downarrow< x, indicating f _ 1(x)=f _ 2(x) by the assumption of \varphi.

Step 2.

The partial mappings form a linear ordered set under inclusion. Hence, we want to collect all of such mappings to form a set and take their union.

An element a\in A corresponds to a unique partial mapping, so we apply the replacement axiom. Formally, let \psi(a,f) be the formula: f is a mapping that is a partial mapping with domain \downarrow a. Step 1 shows that for any a\in A, \psi(a,f _ 1)=\psi(a,f _ 2)\Rightarrow f _ 1=f _ 2. By replacement axiom, there is a set \mathcal F consisting of mappings f such that (\exists a\in A)\psi(a,f).

Now we can take F=\bigcup\mathcal F. This F is a mapping: If xFy _ 1 and xFy _ 2, then there are two partial mappings f _ 1,f _ 2 such that f _ 1(x)=y _ 1 and f _ 2(x)=y _ 2. By step 1, y _ 1=y _ 2.

Step 3.

We verify F satisfies the recursion on its domain. Take an element x in its domain. We need to show \varphi(F| _ {\downarrow< x},F(x)). Since x is in the domain, it is also in the domain of some f\in \mathcal F, so \varphi(f| _ {\downarrow< x},f(x)).

Consider the mapping F| _ {\downarrow< x}. A pair (x',y) in it if and only if x'<x and y=\tilde f(x') for some \tilde f\in \mathcal F. By Step 1, f(x')=\tilde f(x'). Hence f| _ {\downarrow<x}=F| _ {\downarrow<x}.

Similarly, consider F(x). There is some f'\in \mathcal F such that F(x)= f'(x). Then f(x)=f'(x), so f(x)=F(x).

Since \varphi(f| _ {\downarrow< x},f(x)), we have \varphi(F| _ {\downarrow< x},F(x)).

Step 4.

We now show the domain of F is A. Otherwise, there is a least t\in A not in the domain. Then \downarrow<t is contained in the domain. We extend the mapping F| _ {\downarrow<t} by setting F(t) to the unique y such that \varphi(F| _ {\downarrow<t},y). We thus obtain a partial mapping, indicating t is in the domain.

We verify the uniqueness of F by transfinite induction. Let B be the set on which two such mappings F _ 1,F _ 2 agree, i.e., B=\{x\in A\mid F _ 1(x)=F _ 2(x)\}. It is easy to see that \downarrow<a\subseteq B implies a\in B.□

2. Continued on Page Three