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}](/latex?n=7e70fb8c24a83021c525033cb0d90402480f4ff88224309a36f3c2cfccc6f486)
can be made in terms of the default ordering
![\le](/latex?n=7a03384e6e8b85197651452d5bfaff72559b1af11aedb271b10f67c1c4e9154e)
, 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
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](/latex?n=e5f07b21cb1819f977378e404e0bd4d467f1f22aa23c2e0cb92985912aa8c796)
of pairs of natural numbers. We give an ordering
![(\sqsubseteq, \mathbb{N}_0\times\mathbb{N}_0)](/latex?n=a23bc2be607f52337173e0bc1037e2cc87e00d60576c7acefe2f256c7f49d8f8)
by
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](/latex?n=e5f07b21cb1819f977378e404e0bd4d467f1f22aa23c2e0cb92985912aa8c796)
. It is, in fact, an ordering (exercise).
This relation satisfies our two remaining axioms: The unique successor of a pair
![(a,b)](/latex?n=686d29dd27b7437ae8351191ff8087889edde918abed40d4af8e6a2bd362fb09)
is obviously
![(a,b+1)](/latex?n=8c0027883cf164843013d3bcb47de1b854547bad4bdec2e2656f8d97ee3bb370)
. To get the minimum of a set
![X\subseteq \mathbb{N}_0\times\mathbb{N}_0](/latex?n=35dd170dec10b9b4d0f346bbbf8c13781915262f48d642a9ecef269ad4b22c38)
, we first notice that
![\{a|(a,q)\in X\mbox{ for some }q\}\subseteq\mathbb{N}_0](/latex?n=b42f02696f777be4ea63e81430b001c72c1bab28171fd981cf9a77eada546297)
has a minimal element
![m](/latex?n=62c66a7a5dd70c3146618063c344e531e6d4b59e379808443ce962b3abd63c5a)
, as it is a subset of
![\mathbb{N}_0](/latex?n=bcd8b397219bdf5708f8b59a0d132e4ba6ad208f1942fb2610876434a9b98d08)
, and then
![\{q|(m,q)\in X\}\subseteq\mathbb{N}_0](/latex?n=a6a962a8636273f49806b497c3fa86cb57a8da0a1191fd72b70fd37d3ce4ad62)
also has a smallest element
![b](/latex?n=3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d)
, and then,
![(m,b)](/latex?n=29f61dd4a2de6e6482a51335f0b02221e32d17691566c673111a2c0b25db776b)
is a minimal element of
![X](/latex?n=4b68ab3847feda7d6c62c1fbcbeebfa35eab7351ed5e78f4ddadea5df64b8015)
. The "zero" of this ordering, that is, the smallest element, is obviously
![(0,0)](/latex?n=a2c508f756fd50443052e6d4dd608e8b9617507afac5be1bba5619787d3757f2)
.
A further example for a pair with no predecessor is
![(1,0)](/latex?n=5af86a98fe16ac5a884d32f7c7140e9da0fbba74614070c3839fa938e3ed8b78)
. Even though there are infinitely many pairs, namely
![(0,0), (0,1), (0,2), (0,3), \ldots](/latex?n=12a5e5d8c854da8fa8e65127dff13fa2410e42e7c2c00b41cd8df80d83a3a3ba)
smaller than
![(1,0)](/latex?n=5af86a98fe16ac5a884d32f7c7140e9da0fbba74614070c3839fa938e3ed8b78)
, none of them is the predecessor of
![(1,0)](/latex?n=5af86a98fe16ac5a884d32f7c7140e9da0fbba74614070c3839fa938e3ed8b78)
.
Now, keep in mind that we still want a generalization of the order of the natural numbers. We can embed
![(\le,\mathbb{N}_0)](/latex?n=c87d34a2335fd48378e67917d9e101b5f22349e76265a9098cd8ab888f0685c7)
into
![(\sqsubseteq,\mathbb{N}_0\times\mathbb{N}_0)](/latex?n=7fcfd48f87e587003d10c0e404d99efdd32795ea47cdb0086089681cc27d235c)
using the injective homomorphism
![n\rightarrow(0,n)](/latex?n=526590e77b91236a90ba9eb5382b9952c51d57c6a73b12f8970398401876d270)
. As mathematicians are lazy, we will now just identify the naturals by this homomorphism, that is, we will actually write
![n](/latex?n=1b16b1df538ba12dc3f97edbb85caa7050d46c148134290feba80f8236c83db9)
instead of
![(0,n)](/latex?n=f9c1735806fbf71b40fbe74fefaa863566b24b6aaf5b3ac4577167fab7dbc431)
. With this inclusion,
![(1,0)](/latex?n=5af86a98fe16ac5a884d32f7c7140e9da0fbba74614070c3839fa938e3ed8b78)
becomes the first element that is larger than all the "naturals". We will - for now - write
![\omega](/latex?n=11baa595827a4e0fd17af205816653eb40ea4c8410ba94a26118d3e60292d4e4)
for
![(1,0)](/latex?n=5af86a98fe16ac5a884d32f7c7140e9da0fbba74614070c3839fa938e3ed8b78)
, and
![\omega+n](/latex?n=8ac54c504b4ff1f5114c22a538e831229a742a85acff8bde29b340c5e043cbea)
for
![(1,n)](/latex?n=65a89010d70f0368bbd04888e6791c577a9457e53b1feb4c130d1e92dee794fc)
, and - to make it even more confusing -
![\omega\cdot m+n](/latex?n=060e166541253b2230b09652b98904922923a249bc4e0b8bfe630dbc06f5ccf5)
for
![(m,n)](/latex?n=f89ffcd30a342a08bdbbcb6c0992adb870db32d722e0a009931397ccb79feb02)
.
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:
However, what we cannot do yet is multiplying two of these new objects:
![\omega\cdot\omega](/latex?n=910c7a0a7a567040129a9f1aeb6a945f4523c9c18c1347e02fef4160fb08ed10)
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)](/latex?n=e149e1d3abcdf101c9aadcab5c18ed2e599a5d692f89d046a4f15f77b4f0a5c8)
,
![(2, 9, 7, 2, 55, 0, 0, 0, 0, \ldots)](/latex?n=b66feac8fbeaaf0e42bdb48970c6e4ad6c0a4fac7fbd9c303e2ca0aa89ae0ebc)
, etc., and apply the lexicographical order on their reversed sequences:
That is, we get for the largest index
![i](/latex?n=de7d1b721a1e0632b7cf04edf5032c8ecffa9f9a08492152b926f1a5a7e765d7)
such that
![a_i\neq b_i](/latex?n=4e7de5abf95e760e51b4ce215f8140fa1ea8775ad78adebb1880ec6fddfd9cc1)
, and use its order. Our former ordering of pairs can be embedded by
![(a,b)\rightarrow (b,a,0,0,0,\ldots)](/latex?n=4649235ebb090f30cf83d8ab471088e1dc88f66d27318801aaf63847551525cd)
.
Now,
![\omega=(0,1,0,0,0,\ldots)](/latex?n=5d02087b47a7114995caad87e69abbe4107ea800f1416ba656e06d9c440ac8cf)
, and
![\omega^2=(0,0,1,0,0,0,\ldots)](/latex?n=707fdf09dc2818f7fc3e7cf776433cbe05a3c8202f24c5972770a63c85fbfa3c)
, and generally,
![\omega^n=(\underbrace{0,\ldots,0}_{n\times},1,0,0,0,\ldots)](/latex?n=5d556fd62b11208552f9f126a9785775ba066f4d3d07649f2fbcaad09888d96d)
, and we can write a sequence
![(a_0,a_1,a_2,\ldots)](/latex?n=eeef19ee8614964aa8d83256beec0320b0795d6c26b86396304e136c8590100b)
as
![\ldots+\omega^3 a_3+\omega^2 a_2+\omega a_1+a_0](/latex?n=c4d57e1879b890ab442d99236a95efde3af8fd99e874918a86fd11aceccebf94)
.
This definition is only provisional: the actual definition is more complicated, especially, addition is not commutative,
![1+\omega\neq\omega+1](/latex?n=6e73849c1cf6ed5d69203a9b16e621e92431e3f0b4ccbdd9d9479c54b80501ea)
. 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.
Ordering relations like
![\sqsubseteq](/latex?n=737fea136a42ec19ca9f2cb5dedd15c769a97e8dc9f944f412a8d4520795f16c)
are called
well-orderings: A well-ordering
![(R,A)](/latex?n=2d33f505212e86b4b198a8998498c89cbc47d74361fbbe5052c1aacddeaecf6f)
on a set
![A](/latex?n=559aead08264d5795d3909718cdd05abd49572e84fe55590eef31a88a08fdffd)
is an ordering, for which every subset
![B\subseteq A](/latex?n=6075a21bddc3bcc943c6ac156c2920cd19aa9c9c789e9e00e31d73437e435666)
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)](/latex?n=2d33f505212e86b4b198a8998498c89cbc47d74361fbbe5052c1aacddeaecf6f)
be a well-ordering, and
![\vec{a}=a_1,a_2,\ldots](/latex?n=1bb076b6e231a0b8d464c0161c665d30114c338d2e1888f1bdea4bad14860a50)
be a strictly decreasing sequence of elements of
![A](/latex?n=559aead08264d5795d3909718cdd05abd49572e84fe55590eef31a88a08fdffd)
. Then
![\vec{a}](/latex?n=3c85b1c8ad08f3a7a36669c163737510d19089b05d72ea724b12aac16964c232)
is of finite length.
Proof: The set of sequence elements
![\{a_1,a_2,\ldots\}](/latex?n=f864f3128d623e066be103d429b7c0364056c651d2ec8e3c74fdfbd0afb530bf)
must have a smallest element. As
![\vec{a}](/latex?n=3c85b1c8ad08f3a7a36669c163737510d19089b05d72ea724b12aac16964c232)
is strictly decreasing, after reaching this element,
![\vec{a}](/latex?n=3c85b1c8ad08f3a7a36669c163737510d19089b05d72ea724b12aac16964c232)
must end immediately.
Interestingly, we can now find an ordering relation on well-orderings: Let
![(R,A)](/latex?n=2d33f505212e86b4b198a8998498c89cbc47d74361fbbe5052c1aacddeaecf6f)
and
![(S,B)](/latex?n=7bfb8c7514270d04df0978c7b6b9116a61cb96a82c39a8daec341a0c35947ca1)
be well-orderings, then there is either an injective homomorphism
![A\rightarrow B](/latex?n=79b5de12beb45d7ab4a3c911c595b5b1da739c10f765efc0124063cafb486691)
or an injective homomorphism
![B\rightarrow A](/latex?n=c5cfa17b2b7467695ab19d0d8cf8b77bcb1e54e586efbca6e61138e4e3d65f46)
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](/latex?n=737fea136a42ec19ca9f2cb5dedd15c769a97e8dc9f944f412a8d4520795f16c)
between well-orderings, where
![(R,A)\sqsubseteq(S,B)](/latex?n=c01058b172bac20d0a9033169f21b1badfe541a9e934e870a54abee2f4cf9893)
shall mean that there exisit an injective homomorphism
![A\rightarrow B](/latex?n=79b5de12beb45d7ab4a3c911c595b5b1da739c10f765efc0124063cafb486691)
. If we have
![(R,A)\sqsubseteq(S,B)](/latex?n=c01058b172bac20d0a9033169f21b1badfe541a9e934e870a54abee2f4cf9893)
and
![(S,B)\sqsubseteq(R,A)](/latex?n=8ff5e00f478a7d3297a54bc25033e49f9055d63129b22838a9b8fb662927934b)
, then the well-ordernigs are isomorphic, we write
![(R,A)\equiv(S,B)](/latex?n=75818164348cd248737963de37d836503a476094ebffeed305d4d8c4fba697c9)
for that.
The collection
![\mbox{OT}(W)=\{x|x\equiv W\}](/latex?n=e16c5903c3a20e91226f23ab26bab09de98b50dfa4c06ea4ad1c6e629c79515f)
contains all the well-orderings isomorphic to a well-ordering
![W](/latex?n=fcb5f40df9be6bae66c1d77a6c15968866a9e6cbd7314ca432b019d17392f6f4)
, and as it contains all the relevant structural information of the ordering, it is called the
ordering type of
![W](/latex?n=fcb5f40df9be6bae66c1d77a6c15968866a9e6cbd7314ca432b019d17392f6f4)
.
And now ... it gets complicated. We defined
![\mbox{OT}(W)](/latex?n=475fdcf3fe0ddfc2c569d2a9a6b770c5e5514ad2b70590e0b1e4c464bff2efb5)
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.