language hipsters also have never used C, if they had they

On Infinity 6 - Well-Orderings
Tue, 13 Mar 2012 13:30:00 GMT

Be sure to read the former parts 1, 2, 3, 4 and especially part 5 about orderings, before you read this part.

There are a lot of people trying to tell about what mathematics or a more specific topic is actually about - and they are often right in some sense, looking at it from a certain perspective. However, mostly those perspectives are missing something. Therefore, I will not make the claim that talking about infinitary objects is talking about orderings. However, what I can say is that ordering relations play an important role.

For example, many important definitions on \mathbb{R} can be made in terms of the default ordering \le, like convergence and openness.

However, there is one sort of ordering relations which especially suits the purpose of describing connections between infinitary objects: the well-orderings. We will introduce this concept here.

In part 1, we gave axioms for natural numbers. These were

  • Every number has a unique successor
  • Every number except 0 has a predecessor
  • Every non-empty set has a smallest element
We now want to generalize these. To generalize something, the axioms must be loosened. Loosening the first axiom would lead to a structures mathematicians would call trees (yes, like the plant), but we do not want to discuss these here - we keep the axiom of unique successors. We have seen that the third axiom is useful in proofs. The property is called well-foundedness. We will also keep this one. So the only thing we can loosen is the second: We will allow additional elements which have no predecessor.

Now consider the set \mathbb{N}_0\times\mathbb{N}_0 of pairs of natural numbers. We give an ordering (\sqsubseteq, \mathbb{N}_0\times\mathbb{N}_0) by

(a,b)\sqsubseteq (c,d) :\Leftrightarrow \left\{\begin{array}{cl} b\le d & \mbox{for } a=c \\ a<c & \mbox{otherwise}\end{array}\right.

That is, we first sort by the left element, and then, if the left elements are equal, by the right element. This is called the lexicographical order on \mathbb{N}_0\times\mathbb{N}_0. It is, in fact, an ordering (exercise).

This relation satisfies our two remaining axioms: The unique successor of a pair (a,b) is obviously (a,b+1). To get the minimum of a set X\subseteq \mathbb{N}_0\times\mathbb{N}_0, we first notice that \{a|(a,q)\in X\mbox{ for some }q\}\subseteq\mathbb{N}_0 has a minimal element m, as it is a subset of \mathbb{N}_0, and  then \{q|(m,q)\in X\}\subseteq\mathbb{N}_0 also has a smallest element b, and then, (m,b) is a minimal element of X. The "zero" of this ordering, that is, the smallest element, is obviously (0,0).

A further example for a pair with no predecessor is (1,0). Even though there are infinitely many pairs, namely (0,0), (0,1), (0,2), (0,3), \ldots smaller than (1,0), none of them is the predecessor of (1,0).

Now, keep in mind that we still want a generalization of the order of the natural numbers. We can embed (\le,\mathbb{N}_0) into (\sqsubseteq,\mathbb{N}_0\times\mathbb{N}_0) using the injective homomorphism n\rightarrow(0,n). As mathematicians are lazy, we will now just identify the naturals by this homomorphism, that is, we will actually write n instead of (0,n). With this inclusion, (1,0) becomes the first element that is larger than all the "naturals". We will - for now - write \omega for (1,0), and \omega+n for (1,n), and - to make it even more confusing - \omega\cdot m+n for (m,n).




Source: Wikipedia

In fact, we can then do addition with these new objects, and multiplication with a new object and a natural, as we did with naturals - with distributive and associative laws:

(\omega m_1+n_1)+(\omega m_2+n_2)=\omega(m_1+m_2)+(n_1+n_2)
(\omega m+n)k=\omega mk+nk

However, what we cannot do yet is multiplying two of these new objects: \omega\cdot\omega is not defined yet. We can generalize the above concept by looking at infinite sequences of natural numbers, which end in a sequence of zeroes, that is, (1, 0, 0, 0, 0, 0, \ldots), (2, 9, 7, 2, 55, 0, 0, 0, 0, \ldots), etc., and apply the lexicographical order on their reversed sequences:

(a_1,a_2,\ldots) \sqsubseteq (b_1,b_2,\ldots) :\Leftrightarrow\left\{\begin{array}{cl} \mbox{true} & \mbox{for} \{j|a_j\neq b_j\}=\emptyset \\ a_i<b_i &\mbox{for }i=\max\{j|a_j\neq b_j\}\end{array}\right.

That is, we get for the largest index i such that a_i\neq b_i, and use its order. Our former ordering of pairs can be embedded by (a,b)\rightarrow (b,a,0,0,0,\ldots).

Now, \omega=(0,1,0,0,0,\ldots), and \omega^2=(0,0,1,0,0,0,\ldots), and generally, \omega^n=(\underbrace{0,\ldots,0}_{n\times},1,0,0,0,\ldots), and we can write a sequence (a_0,a_1,a_2,\ldots) as \ldots+\omega^3 a_3+\omega^2 a_2+\omega a_1+a_0. This definition is only provisional: the actual definition is more complicated, especially, addition is not commutative, 1+\omega\neq\omega+1. Our definition works well if we always have larger numbers on the left side of the addition, and we will silently ignore the fact that we did not define it for other cases.


Source:Wikipedia

Ordering relations like \sqsubseteq are called well-orderings: A well-ordering (R,A) on a set A is an ordering, for which every subset B\subseteq A has a smallest element.

As you have seen in the examples, with well-orderings we can get beyond the tower of natural numbers, into "transfinite" numbers. However, well-orderings have a surprising property, which makes them suitable for analysis of infinity:

Let (R,A) be a well-ordering, and \vec{a}=a_1,a_2,\ldots be a strictly decreasing sequence of elements of A. Then \vec{a} is of finite length.
Proof: The set of sequence elements \{a_1,a_2,\ldots\} must have a smallest element. As \vec{a} is strictly decreasing, after reaching this element, \vec{a} must end immediately.

Interestingly, we can now find an ordering relation on well-orderings: Let (R,A) and (S,B) be well-orderings, then there is either an injective homomorphism A\rightarrow B or an injective homomorphism B\rightarrow A or both, when they are isomorphic - as this is a bit harder to prove, we omit the proof.

So we can find a relation \sqsubseteq between well-orderings, where (R,A)\sqsubseteq(S,B) shall mean that there exisit an injective homomorphism A\rightarrow B. If we have (R,A)\sqsubseteq(S,B) and (S,B)\sqsubseteq(R,A), then the well-ordernigs are isomorphic, we write (R,A)\equiv(S,B) for that.

The collection \mbox{OT}(W)=\{x|x\equiv W\} contains all the well-orderings isomorphic to a well-ordering W, and as it contains all the relevant structural information of the ordering, it is called the ordering type of W.

And now ... it gets complicated. We defined \mbox{OT}(W) as a collection, but not as a set! The axioms of set theory require sets to obey some restrictions - and this collection does not do so. It is a so-called proper class, that is a collection which is too big to be a set. However, it is not necessary to understand the reasons right now, and so I will not give any. The important thing is that being proper classes makes ordering types pretty hard to handle, which is why mathematicians had to invent a different method. For every ordering type, they gave a representative, that is a well-ordering which is isomorphic to the others, but has an additional property that uniquely determines it. These representatives are called ordinal numbers.

While originally I wanted to discuss ordinal numbers in detail with this post, the post turns out to become longer than I expected. I think, for this time, the amount of new knowledge floating through my dear readers' brains is enough.