Infinity: The Cardinality of the Continuum

Before reading this post, make sure you have read Infinity: The First Transfinite Cardinal, and Infinity: Countable Sets.

In the previous posts of this series, it was established that the sets of natural numbers, integers, rational numbers, and even algebraic numbers have an equivalent cardinality: aleph-zero. However, not all real numbers fall under the umbrella of algebraic numbers. All of the numbers that are real but non-algebraic are irrational, and are specifically known as transcendental. Numbers such as e and π are transcendental.

To determine the cardinality of the real numbers, this problem can be again simplified to a problem involving ordered n-tuplets. This is done by considering the construction of an arbitrary real number. The general real number has a finite whole number part, followed by an infinite decimal expansion. For example, the real number π has a whole number part of 3, and a decimal expansion of .14159265... It is simpler to just ignore the whole number part, and focus on the real numbers on the interval (0,1). All of these are defined uniquely (almost, as we will see below) by their infinite decimal expansion. Therefore, each of these numbers is defined by an ordered n-tuplet, with n being infinite, and of the form

(a1,a2,a3...)

Since all values in this sequence are place values, each must be 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9. However, no clarity is lost if these real numbers are converted to binary, and each number still as a unique infinite decimal expansion, this time only incorporating 1's and 0's. We have the just simplified the problem to determining whether the set of all infinite sequences consisting of 1's and 0's is countable, i.e. whether it has a cardinality of aleph-zero.

Georg Cantor was the first to devise this method, and through infinite binary sequences found a very elegant way to find the cardinality of the real numbers, through proof by contradiction. It is called the diagonal argument. To understand this argument, consider all possible infinite binary sequences as making up a set, called S. Each element Sn is then an infinite binary sequence. If the cardinality of the real numbers is aleph-zero, then each element in the set can be numbered Sn, with n being a natural number. The first few elements of the set are shown below:



The actual ordering of this set is arbitrary, since if the cardinality of S is aleph-zero, all sequences with be covered eventually. For the next part of the proof, consider a sequence Sx, which is constructed by taking the nth element of each Sn and reversing it, i.e. 0 becomes 1, and 1 becomes 0. This is illustrated below:



The nth element of every nth sequence is bolded, and for each bolded element, the opposite one is placed in the sequence Sx. The resulting sequence is clearly an infinite binary sequence, and therefore is a member of the set S. However, by definition, it is different from any sequence in the set (S1,S2,S3...) because for any sequence Sn, with n a natural number, the nth element of the sequence is different from that of Sx. Therefore, assigning a natural number to each infinite binary sequence does not cover all such sequences, and the function from the natural numbers to S is not a bijection. Therefore, the set S has a cardinality greater then aleph-zero. Sets with cardinalities greater than aleph-zero are also known as uncountable.

When extending this back to our real number problem, there are a few slight glitches in this system, one of which being that an infinite binary decimal expansion such as .001111... with infinite 1's is actually equal to another, namely .010000... Therefore, each real number does not quite have a unique decimal expansion. However, this problem can be resolved.

Only numbers with terminating decimal expansions can be expressed in the two ways shown above, and in binary, the only such numbers are those whose denominators involve only a power of 2. For example, 1/2=.1000...=.0111..., and 5/8=.101000...=.100111... These numbers can be collected into a set of their own, called A, the first few members of which are {1/2, 1/4, 3/4, 1/8, 3/8,...}.

This is a subset of the rational numbers, and therefore has cardinality aleph-zero. The set of infinite binary sequences with infinite 0's or infinite 1's (which starts {.1000...,.0111...,.01000...,.00111...,...}) merely has two elements for each element of set A, and still has a cardinality of aleph-zero. (just as the sets {1,2,3...} and {1,-1,2,-2...} have the same cardinality, even though there are two elements in the latter whose absolute values correspond to the former) Because of this, a bijection can be set up between them, corresponding .1000... to 1/2, .0111... to 1/4, and so on. Adding this to the original set S, one finds that each real number on (0,1) now corresponds to a single unique infinite binary sequence.

Clearly, the cardinality of the entire set of real numbers must be greater than or equal to that of the real numbers on (0,1), and so we have now proved that

The cardinality of the real numbers, known as the cardinality of the continuum and denoted by , is strictly greater then the cardinality of the natural numbers, aleph-zero. In other words

> ℵ₀

More number systems still remain, including the complex numbers. However, it is fairly easy to see that the complex numbers still have the cardinality of the continuum, as any complex number can be defined uniquely as an ordered pair of two real numbers (a,b). Also, through a similar method that was used for integral ordered n-tuplets that is not detailed here, it can be proved that sets of ordered n-tuplets of real numbers or of complex numbers both have the cardinality of the continuum. This result also seems intuitively correct from previous examinations of ordered n-tuplets.

Using Cantor's diagonal argument, it was established that the cardinality of the set of real numbers was greater than that of natural numbers, in other words that there is no bijection between them. However, it has not been found exactly what this cardinality of the continuum actually is, or how to relate these quantities to each other in any way.

In order to accomplish this, one must first understand the concept of a power set. A power set is denoted P(S), where S is any ordinary set. Every set has a corresponding power set, and the above statement says that the power set of S is called P(S).

To construct the power set for any set S, take each unique combination of the elements in S, and put it into its own set. Then compile all of these sets and place them within another set. This is the power set, P(S). For example, the set {1,2,3} includes eight unique combinations of the elements contained within it, namely: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, and {1,2,3}. (the first of these is included as a choice of zero elements from the set) All of these are then included in a larger set, yielding {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}. In conclusion:

P({1,2,3})={{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

If one compares the cardinality of these two sets, where each subset of the latter is a single element, it is easy to see that they are 3 and 8, respectively. One also notices that 2^3=8. This is no coincidence. The total number of combinations of n elements is (2^n)-1, and when one adds the empty set to this total, 2^n. Expressed in formula form, with the cardinality of a set S written as |S|:



Applying this knowledge to what we know about the set of natural numbers, it is easy to identify the set of all real numbers as the set of combinations of natural numbers, using the technique of binary sequences that was used previously. Combinations of natural numbers can be interpreted at the decimal expansion of real numbers through binary sets. For example, one can draw the combination {1,4,7} from the set of natural numbers {1,2,3...} and take it to mean .1100111000... which is a decimal sequence in which the binary expansions of 1 4, and 7 are joined, and then followed by zeros. There are also infinite subsets of the natural numbers, such as the even numbers {2,4,6...}, which will provide an infinite decimal expansion. This is not a precise mathematical way of doing this, but it serves as an intuitive glimpse into the cardinality of the continuum.

One can also choose the first element of the subset to represent the whole number part, which is always a finite natural number for all positive reals. Using this method, every real number can be generated from a subset (finite or infinite) of the natural numbers, and the real set is the power set of the natural numbers. This proves that



In other words, the cardinality of the continuum is two to the power of aleph-zero. But how can one even comprehend arithmetic operations with cardinal numbers, and infinite ones at that? What other properties does aleph-zero have? The answers can be defined through sets, and are discussed in the next post.

Sources: http://en.wikipedia.org/wiki/Cardinality_of_the_continuum, http://en.wikipedia.org/wiki/Cantor's_diagonal_argument