In the previous page, we have seen how different infinite sets can be said to have different numbers of elements in them. No matter how you arrange the real numbers, you can't match every one of them with a different integer.
If the order of the objects in a set is allowed to matter, there is a way that two infinite sets having the same size from the viewpoint of cardinality can still be said to differ in size. Let us take the set of positive integers, ordered in the normal fashion:
1, 2, 3, 4, 5, 6, 7, ...
Now, suppose we take the 1 away from the start of the set, and tack it on to the end, like this:
2, 3, 4, 5, 6, 7, 8, ... 1
Then, if the order of elements in the sets are fixed, the second set could be said to be the bigger one, because as you pair the numbers in the first set with the numbers one greater in the second set, you never reach the extra number 1 at the end.
Amazingly enough, this isn't just playing with numbers: it happens to be relevant to the understanding of infinity, and can give us new information about the cardinality of numbers, the topic of the previous page.
In the dictionary, you can see lists of the cardinal numbers, which are one, two, three, four, and so on, and the ordinal numbers, which are first, second, third, fourth, and so on. There is one ordinal number for each cardinal number, and one cardinal number for each ordinal number.
In set theory, in addition to the transfinite cardinals such as aleph-one and c, which we met on the previous page, there are also transfinite ordinals. However, the transfinite ordinals are not isomorphic (essentially equivalent, having the same structure) to the transfinite cardinals, but represent something very different. A transfinite ordinal stands for the number of elements in a set where the order of its elements are fixed, like the example illustrated above.
In mathematics, a set is defined as being well-ordered if every subset of it has a smallest member. It doesn't matter if they all have a largest member or not. The contents of the set don't even have to be numbers, since the order relation that allows you to say that one element is smaller than another can be any relationship you choose to define, as long as it behaves the way the conventional ordering of numbers behaves.
Different ways to arrange the integers such that they are still well-ordered are known as order types. The ordinary way to list the positive integers (in every case, when a list of the positive integers is shown, the order relation between the integers for that particular ordering is that "less than" is defined to mean "earlier in the list") is:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11...
If we then make a conventional list of the non-negative integers, we get:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10...
and we can pair the numbers in the two lists with each other, including every element in each, in order. This means both lists have the same arrangement as we are considering them here, the same order type. This order type is denoted by lower-case Greek omega (ω).
Suppose we listed the non-negative numbers this way:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10..., 0
If we tried matching the numbers in this list, in order, to the numbers in our previous list, we would find that the number 0 at the end of this list would never get matched. Thus, this list has the order type denoted as
(ω, 1)
which can also be written as ω+1, and it is a different order type from ω. Note that the order type didn't change when we added the zero to the beginning of our list, so there is no such order type as (1, ω). This is a general rule for order types: a lesser order type gets swallowed up in a greater order type that follows it. That is true, though, only when the difference is qualitative rather than purely quantitative: thus, ω swallows a preceding 1, but (ω, 1) doesn't swallow a preceding ω. An order type is not swallowed when it is followed by a multiple of itself plus a lesser order type, but it is swallowed by a power of itself or anything greater.
Note that the positive integers are also order types, but for finite sets the order type and the cardinality are always noted by the same integer. You can only play the interesting games of going off to infinity in different places in a list of items when that list is itself infinite, of course.
Suppose we now try to include the negative numbers in our list.
..., -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5...
This list is not well-ordered. If we take the list as a whole, or any subset of the form "all the numbers less than N" for some N, since there is no largest positive integer, there is also no smallest negative integer, and such these subsets don't have a smallest member.
However, we can easily make it well ordered; either by an arrangement that pairs off its elements with the natural numbers:
0, -1, 1, -2, 2, -3, 3...
or this way:
0, 1, 2, 3, 4, 5..., -1, -2, -3, -4, -5...
This arrangement has the order type (ω, ω), which is also known as 2ω.
It is also possible to arrange the positive integers in an order type called ω times ω:
1, 3, 5, 7, 9, 11, 13, 15, 17... 2, 6, 10, 14, 18, 22, 26, 30, 34... 4, 12, 20, 28, 36, 44, 52, 60, 68... 8, 24, 40, 56, 72, 88, 104, 120, 136... 16, 48, 80, 112, 144, 176... ...
Here, we first have all the odd positive integers, followed by the ones divisible by 2 but not by 4, followed by the ones divisible by 4 but not by 8, followed by the ones divisible by 8 but not by 16, and so on.
The positive rational numbers can also be arranged fairly easily with this order type:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11... 1/2, 3/2, 5/2, 7/2, 9/2, 11/2, 13/2, 15/2... 1/3, 2/3, 4/3, 5/3, 7/3, 8/3, 10/3, 11/3... 1/4, 3/4, 5/4, 7/4, 9/4, 11/4, 13/4, 15/4... 1/5, 2/5, 3/5, 4/5, 6/5, 7/5, 8/5, 9/5... ...
Since each of the infinity of subsequences in the ω2 order type consists of a set of numbers with cardinality ℵ0, each of those sets could be rearranged to have the order type ω2 itself. So it is also possible to have the order type ω3, and so on.
If one arranges the integers such that a first group has the order type ω, a second group has the order type ω-squared, a third group has the order type ω-cubed, and so on, then, since a lesser order type is swallowed up by a greater one following it, we have constructed an order type that is a well-defined version of ω raised to the ω power.
One can then arrange the integers so that there is a group with the order type ω, a second group with the order type ω^ω, a third group with the order type ω^ω^ω, and so on. This order type is called ϵ0, being represented by a lowercase Greek epsilon with zero as a subscript.
We have been constructing larger and larger order types, but I have not presented the formal definition of when one order type is larger than another. The rule is this: a segment of a well-ordered set is defined as all the elements less than any particular element (rather than just any piece of the set), and it can be proven that the order type of a segment of a set is always less than the order type of the set itself, among other things.
The order types denoted by epsilon with various subscripts have the interesting property that the list of order types below them has their own order type.
Even the very large and complicated order type ϵ0 still only places the members of a set with cardinality ℵ0 in a well-ordered arrangement. Is there a well-ordering of a set with the cardinality of the continuum? This is an unsolved problem in mathematics.
However, it is known that the number of fundamentally different well-orderings of the integers is ℵ1. (For even a single order type, such as ω, the number of different ways the integers themselves can be rearranged is, of course, the cardinality of the continuum. Thus, since that is equal to or greater than ℵ1, its product with ℵ1 is itself as well.) Since this gives us a real example of a set with that cardinality, just as the real numbers are a real example of a set with the cardinality of the continuum, this would seem to be an entry point for determining whether the continuum hypothesis is true or not. However, it so far has only tantalized mathematicians; the answer has not been found.
The proof that there are more than ℵ0 well-orderings of the integers (or any set with ℵ0 elements) is based on the trick we used to produce the order types ω^ω and ϵ0.
Let us suppose we had a list of all the well-orderings of the integers and it was countable. We know that list can't have a greatest element in it, because we can always derive the order type (type, 1) from the order type type. A continuously-increasing infinite sequence of order types can therefore be produced from our list, without changing the order of its elements, simply by taking the first element, and then advancing through the elements of the list, and taking only those elements which are larger than the last element we took.
Since the integers can be ordered in the order type ω times ω, we can certainly order them so that they are in the type corresponding to all these types, one after the other (by taking each of the pieces in the ω times ω order, and re-ordering it to match the corresponding type in our increasing sequence). But since this is a continuously increasing sequence, with no largest member, any member in that sequence is smaller than those which follow it. Hence, the overall order type of the sequence we have now created is larger than that of any of the ones on our list.
This is an important point, since it shows that order types such as ω times ω and ϵ0 actually exist, ruling out a simple fallacy in the proof. To be able to do this with any arbitrary sequence of order types whose cardinality is ℵ0, we need to know that we can compare any two order types, and this, too, is clear from what we have seen about order types so far, although I will not attempt to prove this point here.
Thus, as in the diagonal proof, we create a list which we hope has all the order types in it, and we find that it cannot possibly have them all.
One of the consequences of the formal definition of when one order type is less than another given above is that if the order type of one well-ordered set is less than that of another set, there must be some segment of the set with the larger order-type that has the same order-type as the set with the smaller order-type.
This surprising fact allows it to be proven that there can be no intermediate cardinalities between that of the list of order-types of the integers and ℵ0, the cardinality of the integers themselves.
It is because a smaller ordinal is gobbled up by a larger ordinal following it, and because a well-ordered arrangement can't include an ellipsis pointing left, it isn't possible to produce obvious and trivial cases where a well-ordering has an infinitely complicated description, variable at an infinite number of places and therefore obviously gives rise to a class of well-orderings with the cardinality of the continuum. Thus, ω, ω^5, ω^6, ω^11... is identical to ω, ω^2, ω^3... or ω^ω, by the first rule; and ω^ω, ...ω^11, ω^6, ω^5, ω is not a well ordering if the ω^N for finite N items following the ω^ω don't have some finite upper bound for N. On the other hand, the well-orderings we can form all seem to be describable by finite strings, hence having ℵ0 cardinality.
Since the 'trick' used to produce ω^ω and ϵ0 has, so far, only introduced a new symbol whenever we have used it, and a Gödel-numbering can handle an infinite (ℵ0, that is) alphabet of symbols, the proof that there are aleph-one order-types applicable to the integers, instead of, like the diagonal proof, making it obvious why the cardinality of the set involved is greater (an integer has a description with a finite number of elements; a real number has a description with ℵ0 elements) is maddening and frustrating. Even before the diagonal proof, our notation for the real numbers meant that in a sense the whole vista of the real numbers was spread out before us. After the proof that there are more than ℵ0 well-orderings of the integers, however, we still have no glimpse of any systematic sequence of these orderings that is easily seen (that is, is accessible constructively) to be larger than ℵ0. And thus, the continuum problem remains unsolved.
Incidentally, if we could solve the continuum problem by placing the reals in a one-to-one correspondence with the set of well-orderings of the integers, since these well-orderings are themselves well-ordered, that would also produce a well-ordering of the reals. (This doesn't mean the two problems are equivalent.)
There are some maddeningly non-constructible sets that we know to have the cardinality of the continuum as well. Try to construct a set of numbers within [0,1) such that it contains 0, all its other members are irrational, and every real number is the sum of one of its members and a rational number, but cannot be expressed as the sum of any other of its members and a rational number.
The problem of constructing a set of numbers within [0,1) such that it contains 0, all its other members are not terminating decimals, and every real number is the sum of one of its members and a terminating decimal, but not of any other one of its members and a terminating decimal is essentially equivalent, since the rationals, although not the reals, can easily be given this kind of a basis within [0,1).
The following image shows the steps in the construction of a fractal which includes an infinite number of terminating binary decimals.
The non-terminating decimals which can also be considered to belong to this fractal are not well-ordered, and so this is a failed attempt to exhibit a well-ordering of a set with the cardinality of the continuum, another of the bizarre things that, were it possible, would remove an obstacle to accepting the Cantorian view of sets.
Essentially, this fractal consists of points at the following positions:
The next number after any terminating member of this set is always found by appending 01 to it at the end.
A well-ordered sequence has the property that any set of members in it contains a least member. It is necessary, but not sufficient, that any element in the sequence has a well-defined next element after it (or is the last element in the sequence) to be well-ordered.
The reason that condition is not sufficient is because one could have the elements in infinite sequences, each one well-ordered in itself, but arranged so that one could have a subset of the total such that it is impossible to find the least sequence in it.
The least terminating member of this set that follows, for example, .101010101... is not defined, since one can postpone replacing a trailing 101010101... by 110000000... to as late in the expansion as one wants.
This can be fixed, by not having the fractal process always repeat an infinite number of times. Instead, repeat the fractal in the first zone once, in the second zone twice, in the third zone three times, and so on - where the successive repetitions given are in the first zone of the next pattern, each succeeding zone getting one more. But that still does not result in a well-ordering of a set with the cardinality of the continuum, since now the fractal process only repeats infinitely often in an area of zero extent; the points are well-ordered, but they have only cardinality ℵ0.