My Infinity is Bigger than Yours


I have been reading a lot about numbers, Georg Cantor, and infinite set theory recently and thought I would share some of the more interesting things here. Mostly this concerns properties of the integers (whole numbers such as 0, 1, -1, 1032, …), the rationals (numbers that can be written as a/b, such as 1/2, 7/8, 22/7, …), and the irrational numbers, which are things like √2 or \pi which cannot be written as a/b. All these together make up the real numbers. Conventionally we write real numbers using decimal sequences so that 1.25 is a way of writing 5/4, but actually is a representation of the series 1 + 2/10 + 5/100. It is important to realize that our everyday number system is describing these things using a sequence of symbols which specify an additive series of rationals. Many rational numbers cannot be precisely written using this system. For example 1/3 is 0.33333…, where the 3 is repeating forever. What this means is that 1/3 is written as the limit of an infinite series, i.e.,

\frac{1}{3} = \sum_{i=1}^\infty\frac{3}{10^i}

It is worth noticing that in other number bases the fraction 1/3 can be exactly represented (e.g., as 0.2 in base 6).

So really all our numbers are created from the integers, combined with the concept of division, plus the concept of successive approximation using numerical series. Regarding the rational numbers such as a/b, these can all be written using the decimal system as A.B[C], where A is the whole number part, B is a unique digit sequence, and C is a digit sequence which repeats, for example C=142857 in the decimal representation of 1/7. As such, they have a finite description—the digit strings A, B, and C are of finite length, and the maximum length of C must be less than the denominator of the rational. Examples include 1/6 which is equal to 0.1[6] and 1/4 which is equal to 0.25[0] (and incidentally can also be represented as 0.24[9].)

The irrational numbers however must be written as D.E, where D is the whole number part and E is a digit string of infinite length. An infinite amount of information is needed to directly specify an irrational number when it is represented in the decimal form (or in binary, or in any other number base). Even though this is true, the sequence can still be generated by a rule, which in the case of √2 is the procedure for square-rooting an integer to obtain the actual digits (and is similar to long division.) Therefore any specific irrational number is an abstract mathematical concept which can be used to define a procedure for calculating its decimal representation in terms of a non-repeating infinite sequence. This decimal then represents a list of rationals that must be added to obtain the desired number, and all these rationals are themselves just built out of whole numbers that we think about in everyday life, but combined with the concept of dividing up into parts. You can see how this forms an interesting chain of abstraction which comes back to counting and dividing.

It is useful to consider the number line stretching from minus infinity to positive infinity with zero in the middle. In between each of the integers are an infinite number of rational numbers; between 0 and 1 there are 1/8, 1/4, 17/31, etc. For every pair of rational numbers it is always possible to pick another rational number that lies between them in the interval. Since any region of the number line can be divided up using the rationals to whatever extent you might desire, one might think that the rationals would fully suffice to represent all numbers directly. However Cantor and other mathematicians have shown that the rationals actually leave ‘holes’ and these are filled in with an infinity of irrational numbers which are needed to complete the ‘continuum’ of the number line. In order to think about this further requires exploring some infinite set theory.

As an introduction it is interesting to consider one of the ways that mathematicians define real numbers. Richard Dedekind created the concept of a cut which partitions the set of all rational numbers on the number line into two sets. The first set A contains all the rational numbers from minus infinity upwards which are less than a certain cut at x (the number to be defined). The second set B contains the rest of the rational numbers on up to positive infinity. Set A contains no largest element, because since x is not an element of A it will always be possible to find a larger rational number in A that is ever closer to x. The elements of A can get infinitesimally close to x but not reach it. If x is a rational number then it will be the smallest element in B, but if it is irrational then B will not have a smallest element in the same way that A has no largest element. The irrational number x is trapped between rational numbers above and below that come infinitesimally close to it. In this way Dedekind uses the set of rational numbers to define all real numbers including the irrationals. Once every number is defined as being equivalent to a pair of sets {A, B}, set theory can be used to place things like ordering, equality, and operations among the real numbers on a solid mathematical base.

For any set, a cardinal number can be defined which specifies the number of elements. For example, the cardinality of the set {apple, pair, orange} is 3. Cantor defined the aleph numbers to indicate the cardinality of infinite sets, where \aleph_0 is the size of the set of integers and represents what is called a countable (or denumerable) infinity. In order to compare the sizes of two sets one must pair off the elements of one set against the other, one by one. If there is a way of creating a one-to-one mapping between the elements of two sets then we can be sure that the sets have the same size. Ordinal numbers are numbers which are used to label the elements of a set when we care about the ordering. The smallest element is labeled 0, then after that 1, 2, 3, etc. Cantor introduced \omega to represent the first infinite ordinal which is a representation of all the ordinals that come before it. You can read a lot more about infinite ordinals and set ordering here.

Pairing off the elements of a set allows us to reach some interesting conclusions about the sizes of infinite sets. If one considers the set of natural numbers {1, 2, 3, …} and the set of integers {…, -3, -2, -1, 0, 1, 2, 3, …} it might seem that because the integers stretch out to infinity at both ends that there might be more of them. However by re-arranging the elements as {0, 1, -1, 2, -2, 3, -3, …} one can pair them off against the natural numbers and demonstrate that the sets are the same size. Surprisingly this is also true of the rational numbers. Even though there are an infinite number of rational numbers in any span of the number line, the set of all rationals can be ordered in a special way to pair it off against the natural numbers. An example ordering for the rationals between 0 and 1 might be {1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, …} which can be paired against {1, 2, 3, …}. Note that repeated representations like 2/4 = 1/2 are deleted. The cardinality of the sets of natural numbers, integers, and rational numbers are all equal to the countable infinity \aleph_0.

It might seem that there is only one quantity which is has the size of infinity. However Cantor showed that there is actually more than one type of infinity and some infinities are larger than others. If one tries to pair off the real numbers that form the number line continuum against the natural numbers or the rationals, it turns out not to be possible. There are actually more real numbers. Cantor proved this by using his famous diagonal proof. Let us suppose that there are as many real numbers as natural numbers and let us try to pair them off. We can use a decimal representation and write down real numbers in a list as follows:

1 — 0.13649832749832795864717358…
2 — 0.13286523865236587634584756…
3 — 0.98346587346587346583752555…
4 — 0.82359823659823598723598732…
5 — 0.42343319564308765347865755…
6 — 0.10567834165804351647045743…
7 — 0.03487652438752348766787824…

Since the list includes the irrational numbers, each entry has an infinite decimal representation. The list goes on forever and is supposed to exhaustively include every real number (between 0 and 1). If we consider the diagonal digits in the list which are highlighted here, we can form a new number which contains corresponding digits which are one greater than the digits of the diagonal (wrapping from 9 back to 0) which here would be the decimal number 0.2446496… It is evidently impossible for this number to be included in the list because no matter where you place it there is a contradictory digit, and therefore we have proved that the list cannot be complete. This is Cantor’s classical diagonal argument which shows that the infinity of the reals is greater than the infinity of the integers. This is known as an uncountable infinity.

In its original form Cantor’s proof was described in terms of binary strings containing only the digits 0 and 1. If we consider an infinitely tall binary tree we can come up with a visualization of the larger infinity. If we imagine a tree which starts from the root and branches into two, and then those branches split into two and this process of splitting repeats a countable infinity of times then the number of leaves at infinity has the same cardinality as the reals. Each path up from the root through the splitting of the tree defines one real number. From this we might guess that the cardinality of the reals is 2^{\aleph_0} and in fact that is what is found to be the case.

Cantor’s next aleph number, \aleph_1, is the cardinality of the set of all countable ordinal numbers, which to a rough approximation is the uncountable set which contains all possible ways to re-order a countable infinity of items. Cantor’s continuum hypothesis is the statement that there is no kind of infinity which lies in between \aleph_0 and \aleph_1 and that in fact \aleph_1 is equal to the cardinality of the reals, 2^{\aleph_0}. Kurt Gödel showed in 1940 that the continuum hypothesis was undecidable in the context of Zermelo–Fraenkel set theory, which means that it can neither be proven to be true nor false by reasoning from the axioms of the theory. We can go on generating further cardinal numbers \aleph_2, \aleph_3, \aleph_n, etc, but these cannot be shown to be actually larger than the cardinality of the reals. It is only when we get to \aleph_\omega, where \omega is the first infinite ordinal, that we can prove that we have a cardinal which is not equal to 2^{\aleph_0}.

Beth numbers are somewhat more accessible than aleph numbers. \beth_0 is the first beth number and is equal to \aleph_0. \beth_1 is then equal to 2^{\beth_0} and is the uncountable infinity of the reals. In general \beth_{\alpha+1} = 2^{\beth_\alpha}. The intuition behind these beth numbers is that they represent the sizes of power sets P(A), where P(A) means the set of all subsets of A. Therefore \beth_1 is the cardinality of the set of all subsets of the natural numbers P(N) and \beth_2 is the cardinality of the set of all subsets of the set of all subsets of the natural numbers P(P(N)). The generalized continuum hypothesis states that \beth_\alpha = \aleph_\alpha for all \alpha. The relations between these infinities are deeply connected to the axiom of choice which may be the subject of a future blog post. For a readable introduction to some of these things, I would recommend Gödel, Escher, Bach by Douglas Hofstadter.