constructing well ordered sets
A set $A$ wellorderable if there is a wellordering on $A$. For example, the empty set^{} $\mathrm{\varnothing}$, is wellorderable, the wellordering itself is $\mathrm{\varnothing}$. Similarly, any singleton has $\mathrm{\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 $$, 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=\mathrm{\varnothing}$, since $A\cap B=A\cap (AB)$, and any subset of an wellordered set is wellordered. Define a binary relation^{} $$ on $A\cup B$ as follows: for $x,y\in A\cup B$,
$$ 
So $$ is a (strict) linear ordering on $A\cup B$. Furthermore, $$ extends both $$ and $$. If $X\subseteq A\cup B$, then the least element of $X$ with respect to $$ is the least element of $X$ with respect to $$ if $X\subseteq B$, or the least element of $X\cap A$ with respect to $$, if $X\cap A\ne \mathrm{\varnothing}$. Hence $$ 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 $$ on $A\times B$ as follows:
$$ 
Again, it is easy to see that $$ 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\text{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 $$ or $b=d$. In the first case, $$. In the second case, $c\in {X}^{1}(b)$, either $$ or $a=c$. In the first case, $$, and the second case is impossible for otherwise $(a,b)=(c,d)$. Therefore $$ 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 $$ and $$, then

(a)
$$, provided that $A\cap B=\mathrm{\varnothing}$,

(b)
$$,
where $\cong $ denotes order isomorphism between wellordered sets.

(a)

•
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 $$. If $[f,g]\ne \mathrm{\varnothing}$, it has a least element $\mathrm{min}[f,g]$. Define $$ on $C$ as follows, for any $f,g\in C$:
$$ If $f\ne g$, then $[f,g]\cup [g,f]\ne \mathrm{\varnothing}$ so that $$ or $$. To show that $$ is transitive^{}, suppose $$ and $$. Let $b=\mathrm{min}[f,g]$ and $c=\mathrm{min}[g,h]$. Then:

–
if $b{\le}_{A}c$, then $$, which implies $[f,h]\ne \mathrm{\varnothing}$ and $\mathrm{min}[f,h]{\le}_{A}b$.

–
if $$, then $$, which implies $[f,h]\ne \mathrm{\varnothing}$ and $\mathrm{min}[f,h]{\le}_{A}c$.
In either case, $\mathrm{min}[f,h]{\le}_{A}\mathrm{min}(b,c)$. Now, suppose $$. Then $f(a)=g(a)=h(a)$. As a result, $$. ∎

–

•
In fact, it can be shown that the following are all equivalent^{} to AC in ZF:
 (a)

(b)
if $A,B$ are wellorderable, so is ${B}^{A}$,

(c)
if $A$ is wellorderable, so is $P(A)$, the powerset of $A$.
Title  constructing well ordered sets 

Canonical name  ConstructingWellOrderedSets 
Date of creation  20130322 18:49:12 
Last modified on  20130322 18:49:12 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  9 
Author  CWoo (3771) 
Entry type  Example 
Classification  msc 03E25 
Classification  msc 06A05 
Defines  wellorderable 
Defines  Hebrew lexicographic ordering 