Franklin's Notes


Well-ordering

A well-ordering is a total order on a set with the property that every subset of the set contains a least element. That is, the set $A$ is well-ordered by $\leq$ iff, for every nonempty subset $A'\subset A$, there exists $a'\in A'$ such that $a'\leq a$ for all $a\in A'$.

Theorem 1. Assuming the Axiom of Choice , an ordered set $A$ is well-ordered if and only if $\omega^d$ cannot be embedded in $A$.

Proof. Clearly, if $f:\omega^d\to A$ is an embedding, then the image of $\omega^d$ under $f$ is a subset of $A$ with no least element. Thus, "only if" follows easily without requiring AC.

For the "if" part of the claim, we make use of the General Principle of Choice, which can be shown equivalent to AC . Suppose $A'\subset A$ is a subset of $A$ without a least element. Then let $Z$ be the set of finite subsets of $A'$, and define the set $f:Z\to 2^{A'}$ so that $f(B)$ is the set of elements of $A'$ less than all elements of $B$, for any $B\subset A'$. Let $Z'$ be the image of the set $Z$ under $f$, so that $f:Z\to Z'$. Finally, define a choice function $g:Z'\to A'$. Then, for any finite sequence of elements ${a_0,...,a_n}\subset A'$, the element $(g\circ f)({a_0,...,a_n})\in A'$ is an element less than all of them. Thus, if we let $a_0$ be an arbitrary element of $A'$, we may recursively define an infinite descending sequence of elements $a_n$ as follows: The existence of an infinite descending sequence of elements $...<a_2<a_1<a_0$ shows that $\omega^d$ can be embedded in $A$, as claimed. $\blacksquare$

Note that the above proof is an example of using AC to creatively make dependent choices in a non-obvious way.

Theorem 2. Suppose that $A$ is well-ordered by $\leq$ and $f:A\to A$ satisfies $x<y\implies f(x)<f(y)$ for all $x,y\in A$. Then $f(x)\geq x$ for all $x\in A$.

Proof. Suppose that $f:A\to A$ satisfies $x<y\implies f(x)<f(y)$ for all $x,y\in A$. Suppose for the sake of contradiction that there exists $x\in A$ such that $f(x)<x$. Then, letting $x_0=x$, we may define an infinite descending sequence recursively by letting $x_{n+1}=f(x_n)$, so that we have so that the set ${x_0,x_1,x_2,...}$ is a subset of $A$ without a smallest element, meaning that $A$ is not well-ordered after all. This is a contradiction, so we must have that $f(x)\geq x$ for all $x\in A$. $\blacksquare$

Theorem 3. Suppose that $A_1\subset A_2$ and $B$ are all well-ordered nonempty sets, and suppose that $f_1:A_1\to B$ is an order-isomorphism between $A_1$ and a proper initial segment of $B$, and $f_2:A_2\to B$ is an order-isomorphism between $A_2$ and a proper initial segment of $B$. Then $f_1\subset f_2$ - that is, $f_2$ extends $f_1$, or $f_1(x)=f_2(x)$ for all $x\in A_1$.

Proof. Let $f_1(A_1),f_2(A_1),f_2(A_2)$ denote the images of $A_1,A_1,A_2$ under $f_1,f_2,f_2$ respectively. First of all, since $f_1(A_1)$ and $f_2(A_1)$ are both initial segments of $B$, at least one of them must be a subset of the other. If $f_2(A_1)$ is a proper subset of $f_1(A_1)$, then the function $f_1^{-1}\circ f_2$ is an automorphism of $A_1$, but it satisfies $(f_1^{-1}\circ f_2)(x) < x$ for any $x$ in the preimage of $f_1(A_1)\backslash f_2(A_1)$, which contradicts the previous theorem. Suppose, on the other hand, that $f_1(A_1)$ is a proper subset of $f_2(A_1)$. Then, similarly, the function $f_2^{-1}\circ f_1$ is an automorphism of $A_1$, but it satisfies $(f_2^{-1}\circ f_1)(x)<x$ for any $x$ in the preimage of $f_2(A_1)\backslash f_1(A_1)$, again contradicting the previous theorem. Thus, we must have that $f_1(A_1)=f_2(A_1)$.

Now, since $f_1(A_1)=f_2(A_1)$, we have that $f_1^{-1}$ and $f_2^{-1}$ are both defined on this set. Suppose that $f_1(x)\ne f_2(x)$ for some $x\in A_1$. If $f_1(x)<f_2(x)$, then $(f_2^{-1}\circ f_1)(x)<x$ and $f_2^{-1}\circ f_1$ is an order-preserving function on $A_1$, which contradicts the previous theorem. On the other hand, if $f_2(x)<f_1(x)$ for some $x\in A_1$, then $(f_1^{-1}\circ f_2)(x)<x$, contradicting the previous theorem again. Thus, we must have that $f_1(x)=f_2(x)$ for all $x\in A_1$, and hence $f_1\subset f_2$. $\blacksquare$

Theorem 4. Suppose that $A$ and $B$ are two well-ordered sets. Then exactly one of the following cases holds:
1. $A$ is isomorphic to a proper initial segment of $B$
2. $B$ is isomorphic to a proper initial segment of $A$
3. $A$ and $B$ are isomorphic

Proof. Let's suppose that all $3$ of these statements are false, and derive a contradiction. First of all, $A$ must have some proper initial segment not isomorphic to a proper initial segment of $B$, for otherwise $A$ would be isomorphic to a proper initial segment of $B$ or to $B$ itself. By similar reasoning, $B$ must have some proper initial segment not isomorphic to a proper initial segment of $A$. Since the proper initial segments of $A$ and $B$ are well-ordered by inclusion, we may let $A'$ be the least proper initial segment of $A$ not isomorphic to a proper initial segment of $B$, and $B'$ be the least proper initial segment of $B$ not isomorphic to a proper initial segment of $A$.

Let $A'={x\in A:x<a'}$. By the definition of $A'$, for each $a<a'$, there exists an isomorphism $f_a$ from ${x\in A:x<a}$ to some initial segment of $B$, and by the previous theorem, $f_{a_1}\subset f_{a_2}$ for all $a_1<a_2$. This means that the function is also an isomorphism, between $A'$ and the union of ranges in $B$ of each of the functions $f_a$. But the union of proper initial segments of $B$ must be either an initial segment of $B$ or the set $B$ itself, since $B$ is well-ordered. This means that either $B$ is isomorphic to the proper initial segment $A'$ of $A$, contradicting our assumption that $(2)$ was false, or $A'$ is isomorphic to a proper initial segment of $B$, contradicting the definition of $A'$ as the least proper initial segment of $A$ not isomorphic to a proper initial segment of $B$.

Either way, we have the desired contradiction - thus, one of the statements $(1),(2),(3)$ must be true. Clearly no two of them can be true, because this would result in either $A$ or $B$ being isomorphic to a proper initial segment of itself, which would violate Theorem 2. $\blacksquare$

set-theory

order-theory

ordinals

back to home page