Bernhard Bolzano defined cardinality in his book Paradoxes of the Infinite (1851). The cardinality of a set is, roughly speaking, its size. Precisely, the cardinality of X is said to be less than or equal to that of Y if there is a function f from X to Y with the property that if x and x' are elements of X with f(x) = f(x') then x = x'. Such a function is said to be one to one or injective. Equivalently, the cardinality of X is said to be less than or equal to that of Y if there is a function f from Y to X with the property that if x is an element of X then there is an element y of Y with f(y) = x. Such a function is said to be onto or surjective. If the cardinality of X is less than or equal to Y and vice versa then X and Y are said to have the same cardinality and it can be proven that there is a bijective (i.e. both injective and surjective) function from X to Y. Such a function is also called a one-to-one correspondence. Accordingly, two finite sets have the same cardinality if and only if they have the same number of elements. Also, the set N of natural numbers {0,1,2,3,...} has the same cardinality as the set Z of integers {...,-3,-2,-1,0,1,2,3,...} because the function f(x) = (-1)^x multiplied by the greatest integer less than or equal to one-half x is a bijection from N to Z. Any set that has the same cardinality as N is said to be countable or denumerable.
Georg Cantor (1845-1918) built on Bolzano's work and rigorously proved most of the theorems that draw on cardinality. In 1874, Cantor proved that the set Q of rational numbers has the same cardinality as N by his "diagonalization method." First, the rational numbers are arranged as follows:
0/1, 1/1, -1/1, 2/1, -2/1, 3/1,
0/2, 1/2, -1/2, 2/2, -2/2, 3/2,...
0/3, 1/3, -1/3, 2/3, -2/3, 3/3,...
Next, a zigzagging line is drawn which touches (in order) 0/1, 1/1, 0/2, 0/3, 1/2, -1/1, 2/1, -1/2, 1/3, and so on. The function f which assigns to each natural number n the (n+1)st number of the above sequence is onto (i.e., for every rational number r there is a natural number n with f(n) = r). The function g which assigns to each natural number n the rational number n/1 is one to one. Hence Q has the same cardinality as N.
For any set X, Cantor denoted by 2^X the set of all subsets of X, because if X is a finite set, 2^X has as many elements as 2 to the power of the number of elements of X. Cantor proved that any set X is strictly smaller than 2^X. He reasoned thus: if f is a function from X to 2^X, then one can denote by Y the subset of X containing all elements x of X having the property "x is not an element of f(x)." Assuming that there is an element y in X with f(y) = Y results in a contradiction since by the very definition of Y, such a y cannot be in Y, but this implies that y is in Y. So f is not onto. Since f is arbitrary, this implies that there can be no bijection between X and 2^X. Cantor used this fact to show that the set R of real numbers is strictly larger than N by showing that R is bijective with the set 2^N. The same result can be demonstrated more easily as follows. Let f be a function from N to [0,1] (the set of real numbers between 0 and 1). Write the numbers f(0), f(1), f(2), f(3), and so on, in order and in binary form. For example, suppose
f(0) = 0.100101...
f(1) = 0.011100...
f(2) = 0.110001...
Let a(i) = the (i+1)st digit of f(i). Let x be the real number in [0,1] whose (i+ 1)st digit is equal to 1 minus a(i). In the example x = 0.001 ... By construction x is not in the image of f since if f(n) = x then the (n+1)st digit of f(n) is equal to one minus the (n+1)st digit of x, and this is a contradiction. Hence f cannot be onto. Since f is arbitrary, there are no onto functions from N to R.
Suppose that X is a set with cardinality strictly larger than that of N but smaller than or equal to that of R.
The continuum hypothesis is the assertion that the cardinality of X is equal to that of R. Cantor tried in vain to prove it. David Hilbert included it in his famous problem list at the beginning of the 20th century. In 1963, Paul Cohen of Stanford University proved that the continuum hypothesis is independent of the other well-accepted axioms of set theory (specifically, the Zermelo-Fraenkel axioms). In other words, it cannot be proved or disproved if one assumes only standard set theory.
Cantor's ideas were opposed by some prominent mathematicians of his time including Leopold Kronecker, Christian F. Klein, Jules-Henri Poincare, and Herman Weyl, who doubted the soundness of Cantor's arguments and disliked the apparent paradoxes that arose from them. Today Cantor's theories are widely accepted and have applications to most areas of mathematical research. David Hilbert has said, "No one shall expel us from the paradise which Cantor created for us," and Bertrand Russell has said that Cantor's work is "probably the greatest of which the age can boast."
This is the complete article, containing 922 words
(approx. 3 pages at 300 words per page).
