# constructing well ordered sets

A set $A$ well-orderable if there is a well-ordering on $A$. For example, the empty set  $\varnothing$, is well-orderable, the well-ordering itself is $\varnothing$. Similarly, any singleton has $\varnothing$ as the unique well-ordering, and is therefore well-orderable. More generally, every finite set  is well-orderable. To construct a well-ordering 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!$ well-orderings on the set (since every well-ordering is a linear ordering  ).

By the axiom of choice  , every set is well-orderable. However, this does not provide us with an explicit way to construct the well-order. For example, how does one well-order $\mathbb{R}$, the set of real numbers? Nevertheless, given two well-ordered sets $(A,<_{A}),(B,<_{B})$, one can explicitly construct well-orderings on the following sets, without AC.

###### Proposition 1.

$A\cup B$ is well-orderable.

###### Proof.

We may assume $A\cap B=\varnothing$, since $A\cap B=A\cap(A-B)$, and any subset of an well-ordered set is well-ordered. 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 well-ordered set. ∎

###### Proposition 2.

$A\times B$ is well-orderable.

###### Proof.

We may assume that $A,B$ are both non-empty, since the empty set is well-orderable. 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 well-ordering on $A\times B$. ∎

Remarks.

Title constructing well ordered sets ConstructingWellOrderedSets 2013-03-22 18:49:12 2013-03-22 18:49:12 CWoo (3771) CWoo (3771) 9 CWoo (3771) Example msc 03E25 msc 06A05 well-orderable Hebrew lexicographic ordering