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.

•

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
1. (a)
  
  $(A\cup B,<_{(A,B)})\cong\alpha+\beta$ , provided that $A\cap B=\varnothing$ ,
2. (b)
  
  $(A\times B,<_{A\times B})\cong\alpha\cdot\beta$ ,
where $\cong$ denotes order isomorphism between well-ordered sets.
•

One would hope that for well-ordered sets $A, B$ , the set $B^{A}$ is well-orderable 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$ well-ordered, 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:
1. (a)
  
  the well-ordering principle,
2. (b)
  
  if $A, B$ are well-orderable, so is $B^{A}$ ,
3. (c)
  
  if $A$ is well-orderable, so is $P(A)$ , the powerset of $A$ .

Title	constructing well ordered sets
Canonical name	ConstructingWellOrderedSets
Date of creation	2013-03-22 18:49:12
Last modified on	2013-03-22 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	well-orderable
Defines	Hebrew lexicographic ordering