You are here
Homeconstructing well ordered sets
Primary tabs
constructing well ordered sets
A set $A$ wellorderable if there is a wellordering on $A$. For example, the empty set $\varnothing$, is wellorderable, the wellordering itself is $\varnothing$. Similarly, any singleton has $\varnothing$ as the unique wellordering, and is therefore wellorderable. More generally, every finite set is wellorderable. To construct a wellordering on a finite set, pick any element from the set and designate the element to be the smallest element of the set. Then, pick an element from the remaining collection, and make this element the next smallest element. Keep doing this until every element has been picked and assigned. Obviously, this process will not go on forever. If there are $n$ elements in the set, there are $n!$ wellorderings on the set (since every wellordering is a linear ordering).
By the axiom of choice, every set is wellorderable. However, this does not provide us with an explicit way to construct the wellorder. For example, how does one wellorder $\mathbb{R}$, the set of real numbers? Nevertheless, given two wellordered sets $(A,<_{A}),(B,<_{B})$, one can explicitly construct wellorderings on the following sets, without AC.
Proposition 1.
$A\cup B$ is wellorderable.
Proof.
We may assume $A\cap B=\varnothing$, since $A\cap B=A\cap(AB)$, and any subset of an wellordered set is wellordered. Define a binary relation $<_{{(A,B)}}$ on $A\cup B$ as follows: for $x,y\in A\cup B$,
$x<_{{(A,B)}}y\quad\mbox{iff}\quad\left\{\begin{array}[]{ll}x,y\in A\mbox{ and % }x<_{A}y,\mbox{ or }\\ x,y\in B\mbox{ and }x<_{B}y,\mbox{ or }\\ x\in A\mbox{ and }y\in B.\end{array}\right.$ 
So $<_{{(A,B)}}$ is a (strict) linear ordering on $A\cup B$. Furthermore, $<_{{(A,B)}}$ extends both $<_{A}$ and $<_{B}$. If $X\subseteq A\cup B$, then the least element of $X$ with respect to $<_{{(A,B)}}$ is the least element of $X$ with respect to $<_{B}$ if $X\subseteq B$, or the least element of $X\cap A$ with respect to $<_{A}$, if $X\cap A\neq\varnothing$. Hence $(A\cup B,<_{{(A,B)}})$ is a wellordered set. ∎
Proposition 2.
$A\times B$ is wellorderable.
Proof.
We may assume that $A,B$ are both nonempty, since the empty set is wellorderable. Define $<_{{A\times B}}$ on $A\times B$ as follows:
$(x_{1},x_{2})<_{{A\times B}}(y_{1},y_{2})\quad\mbox{iff}\quad\left\{\begin{% array}[]{ll}y_{1}<_{B}y_{2},\mbox{ or }\\ y_{1}=y_{2}\mbox{ and }x_{1}<_{A}x_{2}.\end{array}\right.$ 
Again, it is easy to see that $<_{{A\times B}}$ is a strict linear ordering on $A\times B$. Next, let $X\subseteq A\times B$. Define $X[A]:=\{y\in B\mid(x,y)\in X\mbox{ for some }x\in A\}$. Let $b$ be the least element of $X[A]$. Define $X^{{1}}(b):=\{x\in A\mid(x,b)\in X\}$. Let $a$ be the least element of $X^{{1}}(b)$. Then $(a,b)\in X$. For any $(c,d)\in X$ distinct from $(a,b)$, since $d\in X[A]$, either $b<_{B}d$ or $b=d$. In the first case, $(a,b)<_{{A\times B}}(c,d)$. In the second case, $c\in X^{{1}}(b)$, either $a<_{B}c$ or $a=c$. In the first case, $(a,b)<_{{A\times B}}(c,d)$, and the second case is impossible for otherwise $(a,b)=(c,d)$. Therefore $<_{{A\times B}})$ is a wellordering on $A\times B$. ∎
Remarks.

The ordering constructed in Proposition 2 is called the Hebrew lexicographic ordering. It is similar to the usual lexicographic ordering, except that the second coordinates are ordered first before the first coordinates. The reason for choosing this ordering is to make the ordering on $A\times 2$ compatible with the ordering on $A\coprod A$, the disjoint union of $A$ with itself. Had we chosen the lexicographic ordering instead, on, say, $\omega\times 2$, then every initial segment of it would be finite, whereas the initial segment of $(0,1)$ on $\omega\coprod\omega=(\omega\times\{0\})\cup(\omega\times\{1\})$ is infinite.

The above constructions parallel the ordinal arithmetic: if $\alpha,\beta$ are ordinals such that $(A,<_{A})\cong\alpha$ and $(B,<_{B})\cong\beta$, then
(a) $(A\cup B,<_{{(A,B)}})\cong\alpha+\beta$, provided that $A\cap B=\varnothing$,
(b) $(A\times B,<_{{A\times B}})\cong\alpha\cdot\beta$,
where $\cong$ denotes order isomorphism between wellordered sets.

One would hope that for wellordered sets $A,B$, the set $B^{A}$ is wellorderable without resorting to AC. However, this is not possible, and the best one can do is the following: if $B$ is linearly ordered, and $A$ wellordered, then one can linearly order $B^{A}$ without AC:
Proof.
Let $C:=B^{A}$. For $f,g:A\to B$, let $[f,g]:=\{a\in A\mid f(a)<_{B}g(a)\}$. If $[f,g]\neq\varnothing$, it has a least element $\min[f,g]$. Define $<_{C}$ on $C$ as follows, for any $f,g\in C$:
$f<_{C}g\quad\mbox{iff}\quad[f,g]\neq\varnothing\mbox{ and }f(a)=g(a)\mbox{ for% all }a<_{A}\min[f,g].$ If $f\neq g$, then $[f,g]\cup[g,f]\neq\varnothing$ so that $f<_{C}g$ or $g<_{C}f$. To show that $<_{C}$ is transitive, suppose $f<_{C}g$ and $g<_{C}h$. Let $b=\min[f,g]$ and $c=\min[g,h]$. Then:

if $b\leq_{A}c$, then $f(b)<_{B}g(b)\leq_{B}h(b)$, which implies $[f,h]\neq\varnothing$ and $\min[f,h]\leq_{A}b$.

if $c<_{A}b$, then $f(c)=g(c)<_{B}h(c)$, which implies $[f,h]\neq\varnothing$ and $\min[f,h]\leq_{A}c$.
In either case, $\min[f,h]\leq_{A}\min(b,c)$. Now, suppose $a<\min[f,h]$. Then $f(a)=g(a)=h(a)$. As a result, $f<_{C}h$. ∎


In fact, it can be shown that the following are all equivalent to AC in ZF:
(a) the wellordering principle,
(b) if $A,B$ are wellorderable, so is $B^{A}$,
(c) if $A$ is wellorderable, so is $P(A)$, the powerset of $A$.
Mathematics Subject Classification
03E25 no label found06A05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections