Cantor's theorem
Encyclopedia
In elementary set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

, Cantor's theorem states that, for any set A, the set of all subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of A (the power set of A) has a strictly greater cardinality than A itself. For finite sets, Cantor's theorem can be seen to be true by a much simpler proof than that given below, since in addition to subsets of A with just one member, there are others as well, and since for all natural numbers n. But the theorem is true of infinite sets as well. In particular, the power set of a countably infinite set
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...

 is uncountably infinite
Uncountable set
In mathematics, an uncountable set is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger than that of the set of all natural numbers.-Characterizations:There...

. The theorem is named for German
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...

 mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....

 Georg Cantor
Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...

, who first stated and proved it.

Proof

Two sets are equinumerous
Equinumerosity
In mathematics, two sets are equinumerous if they have the same cardinality, i.e., if there exists a bijection f : A → B for sets A and B. This is usually denoted A \approx B \, or A \sim B....

 (have the same cardinality) if and only if there is a one-to-one correspondence between them. To establish Cantor's theorem it is enough to show that, for any given set A, no function f from A into , the power set of A, can be surjective
Surjective function
In mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...

, i.e. to show the existence of at least one subset of A that is not an element of the image
Image (mathematics)
In mathematics, an image is the subset of a function's codomain which is the output of the function on a subset of its domain. Precisely, evaluating the function at each element of a subset X of the domain produces a set called the image of X under or through the function...

 of A under f. Such a subset, , is given by the following construction:


This means, by definition, that for all x in A, x ∈ B if and only if x ∉ f(x). For all x the sets B and f(x) cannot be the same because B was constructed from elements of A whose images (under f) did not include themselves. More specifically, consider any x ∈ A, then either x ∈ f(x) or x ∉ f(x). In the former case, f(x) cannot equal B because x ∈ f(x) by assumption and x ∉ B by the construction of B. In the latter case, f(x) cannot equal B because x ∉ f(x) by assumption and x ∈ B by the construction of B.

Thus there is no x such that f(x) = B; in other words, B is not in the image of f. Because B is in the power set of A, the power set of A has a greater cardinality than A itself.

Another way to think of the proof is that B, empty or non-empty, is always in the power set of A. For f to be onto, some element of A must map to B. But that leads to a contradiction: no element of B can map to B because that would contradict the criterion of membership in B, thus the element mapping to B must not be an element of B meaning that it satisfies the criterion for membership in B, another contradiction. So the assumption that an element of A maps to B must be false; and f can not be onto.

Because of the double occurrence of x in the expression "xf(x)", this is a diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...

.

A detailed explanation of the proof when X is countably infinite

To get a handle on the proof, let's examine it for the specific case when X is countably infinite. Without loss of generality
Without loss of generality
Without loss of generality is a frequently used expression in mathematics...

, we may take X = N = {1, 2, 3,...}, the set of natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s.

Suppose that N is bijective with its power set P(N). Let us see a sample of what P(N) looks like:


P(N) contains infinite subsets of N, e.g. the set of all even numbers {2, 4, 6,...}, as well as the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

.

Now that we have a handle on what the elements of P(N) look like, let us attempt to pair off each element of N with each element of P(N) to show that these infinite sets are bijective. In other words, we will attempt to pair off each element of N with an element from the infinite set P(N), so that no element from either infinite set remains unpaired. Such an attempt to pair elements would look like this:


Given such a pairing, some natural numbers are paired with subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s that contain the very same number. For instance, in our example the number 2 is paired with the subset {1, 2, 3}, which contains 2 as a member. Let us call such numbers selfish. Other natural numbers are paired with subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s that do not contain them. For instance, in our example the number 1 is paired with the subset {4, 5}, which does not contain the number 1. Call these numbers non-selfish. Likewise, 3 and 4 are non-selfish.

Using this idea, let us build a special set of natural numbers. This set will provide the contradiction we seek. Let D be the set of all non-selfish natural numbers. By definition, the power set P(N) contains all sets of natural numbers, and so it contains this set D as an element. Therefore, D must be paired off with some natural number, say d. However, this causes a problem. If d is in D, then d is selfish because it is in the corresponding set. If d is selfish, then d cannot be a member of D, since D was defined to contain only non-selfish numbers. But if d is not a member of D, then d is non-selfish and must be contained in D, again by the definition of D.

This is a contradiction because the natural number d must be either in D or not in D, but neither of the two cases is possible. Therefore, there is no natural number which can be paired with D, and we have contradicted our original supposition, that there is a bijection
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...

 between N and P(N).

Note that the set D may be empty. This would mean that every natural number x maps to a set of natural numbers that contains x. Then, every number maps to a nonempty set and no number maps to the empty set. But the empty set is a member of P(N), so the mapping still does not cover P(N).

Through this proof by contradiction we have proven that the cardinality of N and P(N) cannot be equal. We also know that the cardinality of P(N) cannot be less than the cardinality of N because P(N) contains all singletons, by definition, and these singletons form a "copy" of N inside of P(N). Therefore, only one possibility remains, and that is the cardinality of P(N) is strictly greater than the cardinality of N, proving Cantor's theorem.

History

Cantor gave essentially this proof in a paper published in 1891 Über eine elementare Frage der Mannigfaltigkeitslehre, where the diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...

 for the uncountability of the reals
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

 also first appears (he had earlier proved the uncountability of the reals by other methods
Cantor's first uncountability proof
Georg Cantor's first uncountability proof demonstrates that the set of all real numbers is uncountable. This proof differs from the more familiar proof that uses his diagonal argument...

). The version of this argument he gave in that paper was phrased in terms of indicator functions on a set rather than subsets of a set. He showed that if f is a function defined on X whose values are 2-valued functions on X, then the 2-valued function G(x) = 1 − f(x)(x) is not in the range of f.

Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...

 has a very similar proof in Principles of Mathematics (1903, section 348), where he shows that that there are more propositional function
Propositional function
A propositional function in logic, is a statement expressed in a way that would assume the value of true or false, except that within the statement is a variable that is not defined or specified, which leaves the statement undetermined...

s than objects. "For suppose a correlation of all objects and some propositional functions to have been affected, and let phi-x be the correlate of x. Then "not-phi-x(x)," i.e. "phi-x does not hold of x" is a propositional function not contained in this correlation; for it is true or false of x according as phi-x is false or true of x, and therefore it differs from phi-x for every value of x." He attributes the idea behind the proof to Cantor.

Ernst Zermelo
Ernst Zermelo
Ernst Friedrich Ferdinand Zermelo was a German mathematician, whose work has major implications for the foundations of mathematics and hence on philosophy. He is known for his role in developing Zermelo–Fraenkel axiomatic set theory and his proof of the well-ordering theorem.-Life:He graduated...

 has a theorem (which he calls "Cantor's Theorem") that is identical to the form above in the paper that became the foundation of modern set theory ("Untersuchungen über die Grundlagen der Mengenlehre I"), published in 1908. See Zermelo set theory
Zermelo set theory
Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. It bears certain differences from its descendants, which are not always understood, and are frequently misquoted...

.

For one consequence of Cantor's theorem, see beth number
Beth number
In mathematics, the infinite cardinal numbers are represented by the Hebrew letter \aleph indexed with a subscript that runs over the ordinal numbers...

s.

See also

  • Controversy over Cantor's theory
    Controversy over Cantor's theory
    In mathematical logic, the theory of infinite sets was first developed by Georg Cantor. Although this work has found wide acceptance in the mathematics community, it has been criticized in several areas by mathematicians and philosophers....

  • Cantor–Bernstein–Schroeder theorem
    Cantor–Bernstein–Schroeder theorem
    In set theory, the Cantor–Bernstein–Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions and between the sets A and B, then there exists a bijective function...

  • Cantor's first uncountability proof
    Cantor's first uncountability proof
    Georg Cantor's first uncountability proof demonstrates that the set of all real numbers is uncountable. This proof differs from the more familiar proof that uses his diagonal argument...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK