Infinity: Uncountable Sets

This is the fifth post of the Infinity Series, beginning here. For all posts, see the Infinity Series Portal.

In previous posts, the idea of an "uncountable set" has arisen, namely a set that has a cardinality greater than that of the natural numbers. We have already revealed that the sets of real numbers and complex numbers are uncountable, specifically having a cardinality that is two to the power of aleph-zero, the cardinality of the natural numbers. However, there are other sets which have this cardinality, as well as sets with one greater than this.

First, sets with the cardinality of the continuum will be listed. The sets of real and complex numbers fit into this category, along with any interval of either of them. For example, the set of real numbers between 1 and 5 (inclusive or exclusive) will have the cardinality of the continuum.

A somewhat more interesting case is the Cantor set, a famous entity in mathematics. It is obtained geometrically by beginning with a solid line segment, (mathematically, this segment is the real numbers on [0,1]) and on each step removing the middle third of every existing line segment. This process is illustrated below.



The first seven steps in producing the Cantor Set. This process is repeated infinitely many times. It appears that the entire original line segment will eventually be removed after an infinite number of the above steps, and this is, in a way, true. During the first step 1/3 of the total bar is removed, followed by 1/9 of the total for each remaining segment on the second step, then 1/27 of the total for each remaining part on the third step, and so on. The sum of these removals is 1/3+2/9+4/27+... since there are 2^n segments on the nth step (the amount removed on second step equals 2*1/9=2/9, and on the third, 4*1/27=4/27). The above sequence sums, in the limit as n increases without bound, to 1. In other words, 100% of the original segment is taken away as the Cantor Set is constructed.

Despite the apparent paradox, it is clear that for any segment remaining at any step of the above process, it will have two endpoints that are untouched even after an infinite number of steps. This is because only the middle of all such segments are removed. The remaining points, which all become endpoints at some step, are the points of the Cantor Set. For example, the points 0 and 1 are never removed, along with 1/3, 2/3, 1/9, 2/9, 7/9, 8/9 and many others. The cardinality of this set can be discovered by expressing all its points in base-3 (ternary) decimal notation. In it, 1/3=.1=.02222..., 2/3=.2=.12222..., 1=.22222..., 7/9=.20222..., etc. Many of these numbers have two forms, i.e. 1/3=.1=.0222..., but it can be shown that the Cantor Set contains only points whose base-3 decimal representation has at least one form (out of the two) that consists of only 2's and 0's (a more full discussion is found here). If one took all of these decimals and changed all of the 2's into 1's, a set of binary sequences would be produced. The Cantor set has all base-3 points consisting of only 2's and 0's, but after the function, which is clearly a bijection, it is now the set of all binary sequences, which has previously been shown to have the cardinality of the continuum. The Cantor Set does as well.

Mathematically, this is remarkable. Even though the Cantor Set is an infinitesimal fraction of the line segment [0,1], it still has the cardinality of the continuum. Since no two points of the final Cantor Set are "adjacent" to each other, the Cantor Set is defined to have the property of being nowhere dense. Simply put, this means that any interval containing two points of the Cantor Set does not necessarily contain a third. In contrast, there are an infinite number of rational numbers between any two one could chose, and the set of rational numbers is therefore dense. The fact that such a "nowhere dense" set can have the cardinality of the continuum is also incredible, because all of the discrete sets (natural numbers, integers, etc.) that we have examined have not had this cardinality. These are clearly nowhere dense, as there are real numbers between any two natural numbers, or any two integers.

Another very interesting case is the cardinality of the set of continuous functions on the real numbers. To find this cardinality, it is useful to use a proof of trichotomous exclusion. Such a proof confirms that a set must have a cardinality greater than or equal to that of a certain set, and then proves that it must simultaneously satisfy the condition of having a cardinality less than or equal to that of the same set. Since one quantity cannot be less than and greater than another, the cardinality of the two sets must be equal.

To go about the above proof, it is useful to reevaluate the definition of a continuous function. The "local" definition is of most use here. It states that for any value x on a continuous function, there exists a sufficiently small ε such that f(x+ε) approximates f(x) to an arbitrary accuracy σ. In addition, as ε goes to 0, σ will as well, as point Q becomes a better and better approximation to point P. This is all summarized in the figure below.



Compare the above to the discontinuous function below, where the open circle on the curve represents a discontinuity, the true function value f(x) being located at point P. Even with ε miniscule, the approximation to f(x) never reaches the desired accuracy of σ.



Having defined what it means to be continuous, it is now possible to find the cardinality of the set of continuous functions. The key concept is that knowing the value of a continuous function on all rational numbers is enough to determine it uniquely, i.e. to find its value at any real number.

To see this, consider the value x from above to be a certain real number (for our purpose, make it irrational). This number can be approximated to an arbitrarily high accuracy with a rational number, e.g. π≈3.14159=314159/10000, etc. and therefore ε can be made as small as desired. In the limit as ε goes to 0, the approximation to f(x) becomes exact, and the function value is uniquely determined. Therefore, the knowledge of the value of a continuous function over the rational numbers is enough to determine it.

The main idea is that the above shows that the any specific continuous function needs no more than a countable set of real numbers to define it. The cardinality of the set of all continuous functions is therefore either equal to or less than that of the set of the countable sets of real numbers, or the power set of real numbers, (a power set is the set of all combinations of elements of a given set, discussed in an earlier post) whose cardinality is 2 to the power of the cardinality of all countable sets: aleph-zero. The set of continuous functions therefore has no more than the cardinality of the continuum.

To confirm that this is the cardinality, we must still prove that the set of continuous functions is uncountable. There is a very simple way of doing this. Take a subset of the continuous functions, the constant functions, for which f(x)=k, k being a real number. Clearly, if one defines a set of all constant functions, including every possibility of k, the set will be equivalent in cardinality to the real numbers: the cardinality of the continuum. However, the constant functions are a subset of all continuous functions, the true cardinality must be equal to or greater than this. Since we have already confirmed that it is no greater, and now it is known that the cardinality of the set is no less than that of the real numbers, it follows that the two must be equal.

In contrast, discontinuous functions cannot be pinned down without their value at each and every real number. For example, the discontinuous (piecewise) function that defines f(x) to be equal to 1 for all x except π, and at π for the value to be 12, no degree of accuracy in the rational numbers can confirm that f(π) will equal twelve. The best approximations will simply yield f(π)=1, as they "expect" the function to be continuous at π. More generally, some discontinuous function could potentially have a jump at any or every real number. Therefore, it takes a set of real numbers to uniquely determine such a function.

The total set of functions (including both continuous and discontinuous) on the real numbers is then the power set of the real numbers, with a cardinality greater than any yet discussed. It is 2 to the power of the cardinality of the continuum, which is also known as beth-two, the symbol of which is illustrated below.



This is the third member of what is called the beth sequence. Beth-zero is equal to aleph-zero, and each subsequent element of the sequence is defined recursively as 2 to the power of the previous one. Beth-one is equal to 2 to the power of aleph-zero, or the cardinality of the continuum, and so on. Equivalently, each element is the cardinality of the power set of the previous element. The distinctions between the aleph series and the beth series are revealed in a later post. The next post is on a new type of number.

Sources: http://en.wikipedia.org/wiki/Cantor_set, etc.