Non-Denumerably Infinite Sets | Research & Encyclopedia Articles

Non-Denumerably Infinite Sets

The German mathematician Georg Cantor (1845-1918), who laid the foundation of modernset theory, utilized the idea of "one-to-one correspondence" as a way of "counting" the members of a set. Thus he defined a finite set as either the empty set or a set whose members can be placed in one-to-one correspondence with the set {1, 2, 3, ... , n} where n is some positive integer. An infinite set, then, was defined as a set that was not finite. Many of Cantor's most interesting and sometimes provocative results concerned his theory of infinite sets. These he broke into two types, the denumerably infinite and the non-denumerably infinite sets. The denumerably (or countably) infinite sets are sets whose members can be placed in one-to-one correspondence with the infinite set {1, 2, 3,...} of positive integers. The even integers {2, 4, 6,...} are denumerably infinite since we can correspond 2 with 1, 4 with 2, 6 with 3, ... , and so on. On the other hand, non-demumerably (or uncountably) infinite sets were those which could not be placed in one-to-one correspondence with the positive integers. Cantor produced a clever argument to show that, for example, the real numbers in the interval [0,1] were non-denumerably infinite. He used an indirect proof, assuming that a one-to-one correspondence between the real numbers in [0,1] and the positive integers could be made and then showing that this assumption led to a contradiction. Since any real number in [0,1] can be written as an infinite decimal, Cantor set up the following "alleged" one-to-one correspondence: 1 corresponds to 0.a₁₁a₁₂a₁₃ ... , 2 corresponds to 0.a₂₁a₂₂a₂₃ ... , 3 corresponds to 0.a₃₁a₃₂a₃₃ ... , and, in general, n corresponds to 0.a_n1a_n2a_n3 ... , and so on. Then Cantor showed how to come up with a real number in [0,1] that had been left out of this correspondence. His number had the form 0.b₁b₂b₃ ... b_n ... ; where a₁₁ is not equal to b₁, a₂₂ is not equal to b₂, a₃₃ is not equal to b₃, and, in general, a_nn is not equal to b_n. Since this number cannot be equal to any of the numbers given in the correspondence, it follows that such a correspondence cannot be made.

In a sense, Cantor was saying that the interval [0,1] has "more" elements than the set of positive integers; but "more" can be a very tricky and misleading concept when dealing with infinite sets. For example, the set {1, 2, 3, ... } "seems" to have "more" elements than the set {2, 4, 6,...}; in fact "maybe" twice as many.

Yet we showed above that these two sets can be placed in one-to-one correspondence. To get around this seeming paradox, Cantor defined the concept of cardinality for sets. The empty set would have cardinality 0, and a finite set with n elements would have a cardinality of n. Thus for a finite set, the cardinality is just the number of elements in the set. So any two finite sets with the same number of elements have the same cardinality, and clearly any two finite sets with the same cardinality can be placed in one-to-one correspondence with each other. But what about infinite sets? Since we cannot meaningfully talk about the "number" of elements in an infinite set, Cantor simply carried over the one-to-one correspondence idea and said that any two infinite sets which can be placed in one-to-one correspondence with each other have the same cardinality. He also introduced the symbol ₀, read "aleph-null" for the cardinality of the positive integers. ( is the first letter of the Hebrew alphabet.) Therefore, {2, 4, 6,...} has cardinality ₀, as does any other set that can be placed in one-to-one correspondence with the positive integers. Sets with cardinality ₀ are the denumerable (countable) sets. To the cardinality of the set [0,1] Cantor gave the symbol C, for "continuum" since any interval of real numbers has no "gaps" or "holes." He also showed that the set of all real numbers can be placed in one-to-one correspondence with the interval [0,1], and, therefore, also has cardinality C. In fact, any interval of real numbers has cardinality C, as does any square and its interior, as does the entire Cartesian plane. Thus all of these sets are non-denumerably infinite, whereas, the sets with cardinality ₀ are denumerably infinite.

Cantor defined an order relation for cardinality as follows: The cardinality of a set T is greater than the cardinaltiy of a set S if and only if S can be placed in one-to-one correspondence with a subset of T but T cannot be placed in one-to-one correspondence with a subset of S. Thus the cardinality C is greater than the cardinality ₀. It is natural to ask if there are sets with cardinality greater than C. To answer this question, Cantor considered the "power" set of a given set, i.e., the set of all subsets of S. For example, the set {1, 2, 3} has the following subsets: the empty set, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. (The empty set is a subset of every set and a set is always considered to be a subset of itself.) Note that the power set of {1, 2, 3} has 8 = 2³ elements. In general a finite set with n elements will have a power set with 2ⁿ elements, hence the term "power" set. Clearly, the cardinality of the power set of any finite set will always be greater than the cardinality of the set itself, and Cantor was able to show that this is also true for infinite sets. Therefore, we may conclude that the cardinality of the power set of any set with cardinality C will be greater than C. This cardinality is sometimes designated by 2^C. In this way, Cantor was able to generate an infinite number of so-called "transfinite" cardinal numbers. One of the most famous questions of set theory is whether or not there is a transfinite cardinal number between ₀ and C. Cantor thought not, and his statement of this fact became known as "thecontinuum hypothesis." In 1938, the great mathematical logician Kurt Gödel (1906-1978) showed that no contradiction would arise if the continuum hypothesis were added to the axioms of conventional Zermelo-Fraenkel set theory; but in 1963, Paul Cohen (1934-) showed that no contradiction would arise if the negation of the continuum hypothesis were added to those axioms. These two results taken together showed that, within conventional Zermelo-Fraenkel set theory, the continuum hypothesis is undecidable.