In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set , the set of all subsets of known as the power set of has a strictly greater cardinality than itself.
For finite sets, Cantor's theorem can be seen to be true by simple enumeration of the number of subsets. Counting the empty set as a subset, a set with elements has a total of subsets, and the theorem holds because for all non-negative integers.
Much more significant is Cantor's discovery of an argument that is applicable to any set, and shows that the theorem holds for infinite sets also. As a consequence, the cardinality of the real numbers, which is the same as that of the power set of the integers, is strictly larger than the cardinality of the integers; see Cardinality of the continuum for details.
The theorem is named for German mathematician Georg Cantor, who first stated and proved it at the end of the 19th century. Cantor's theorem had immediate and important consequences for the philosophy of mathematics. For instance, by iteratively taking the power set of an infinite set and applying Cantor's theorem, we obtain an endless hierarchy of infinite cardinals, each strictly larger than the one before it. Consequently, the theorem implies that there is no largest cardinal number (colloquially, "there's no largest infinity").
Cantor's argument is elegant and remarkably simple. The complete proof is presented below, with detailed explanations to follow.
Theorem (Cantor) — Let be a map from set to its power set . Then is not surjective. As a consequence, holds for any set .
exists via the axiom schema of specification, and because .
Assume is surjective.
Then there exists a such that .
From for allin , we deduce via universal instantiation.
The previous deduction yields a contradiction of the form , since .
Therefore, is not surjective, via reductio ad absurdum.
We know injective maps from to exist. For example, a function such that .
Consequently, . ∎
By definition of cardinality, we have for any two sets and if and only if there is an injective function but no bijective function from to . It suffices to show that there is no surjection from to . This is the heart of Cantor's theorem: there is no surjective function from any set to its power set. To establish this, it is enough to show that no function (that maps elements in to subsets of ) can reach every possible subset, i.e., we just need to demonstrate the existence of a subset of that is not equal to for any . Recalling that each is a subset of , such a subset is given by the following construction, sometimes called the Cantor diagonal set of : [1] [2]
This means, by definition, that for all , if and only if . For all the sets and cannot be equal because was constructed from elements of whose images under did not include themselves. For all either or . If then cannot equal because by assumption and by definition. If then cannot equal because by assumption and by the definition of .
Equivalently, and slightly more formally, we have just proved that the existence of such that implies the following contradiction:
Therefore, by reductio ad absurdum, the assumption must be false. [3] Thus there is no such that ; in other words, is not in the image of and does not map onto every element of the power set of , i.e., is not surjective.
Finally, to complete the proof, we need to exhibit an injective function from to its power set. Finding such a function is trivial: just map to the singleton set . The argument is now complete, and we have established the strict inequality for any set that .
Another way to think of the proof is that , empty or non-empty, is always in the power set of . For to be onto, some element of must map to . But that leads to a contradiction: no element of can map to because that would contradict the criterion of membership in , thus the element mapping to must not be an element of meaning that it satisfies the criterion for membership in , another contradiction. So the assumption that an element of maps to must be false; and cannot be onto.
Because of the double occurrence of in the expression "", this is a diagonal argument. For a countable (or finite) set, the argument of the proof given above can be illustrated by constructing a table in which each row is labelled by a unique from , in this order. is assumed to admit a linear order so that such table can be constructed. Each column of the table is labelled by a unique from the power set of ; the columns are ordered by the argument to , i.e. the column labels are , ..., in this order. The intersection of each row and column records a true/false bit whether . Given the order chosen for the row and column labels, the main diagonal of this table thus records whether for each . The set constructed in the previous paragraphs coincides with the row labels for the subset of entries on this main diagonal where the table records that is false. [3] Each column records the values of the indicator function of the set corresponding to the column. The indicator function of coincides with the logically negated (swap "true" and "false") entries of the main diagonal. Thus the indicator function of does not agree with any column in at least one entry. Consequently, no column represents .
Despite the simplicity of the above proof, it is rather difficult for an automated theorem prover to produce it. The main difficulty lies in an automated discovery of the Cantor diagonal set. Lawrence Paulson noted in 1992 that Otter could not do it, whereas Isabelle could, albeit with a certain amount of direction in terms of tactics that might perhaps be considered cheating. [2]
Let us examine the proof for the specific case when is countably infinite. Without loss of generality, we may take , the set of natural numbers.
Suppose that is equinumerous with its power set . Let us see a sample of what looks like:
contains infinite subsets of , e.g. the set of all positive even numbers , along with the empty set .
Now that we have an idea of what the elements of are, let us attempt to pair off each element of with each element of to show that these infinite sets are equinumerous. In other words, we will attempt to pair off each element of with an element from the infinite set , 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 subsets 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 subsets 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 be the set of all non-selfish natural numbers. By definition, the power set contains all sets of natural numbers, and so it contains this set as an element. If the mapping is bijective, must be paired off with some natural number, say . However, this causes a problem. If is in , then is selfish because it is in the corresponding set, which contradicts the definition of . If is not in , then it is non-selfish and it should instead be a member of . Therefore, no such element which maps to can exist.
Since there is no natural number which can be paired with , we have contradicted our original supposition, that there is a bijection between and .
Note that the set may be empty. This would mean that every natural number maps to a subset of natural numbers that contains . Then, every number maps to a nonempty set and no number maps to the empty set. But the empty set is a member of , so the mapping still does not cover .
Through this proof by contradiction we have proven that the cardinality of and cannot be equal. We also know that the cardinality of cannot be less than the cardinality of because contains all singletons, by definition, and these singletons form a "copy" of inside of . Therefore, only one possibility remains, and that is that the cardinality of is strictly greater than the cardinality of , proving Cantor's theorem.
Cantor's theorem and its proof are closely related to two paradoxes of set theory.
Cantor's paradox is the name given to a contradiction following from Cantor's theorem together with the assumption that there is a set containing all sets, the universal set . In order to distinguish this paradox from the next one discussed below, it is important to note what this contradiction is. By Cantor's theorem for any set . On the other hand, all elements of are sets, and thus contained in , therefore . [1]
Another paradox can be derived from the proof of Cantor's theorem by instantiating the function f with the identity function; this turns Cantor's diagonal set into what is sometimes called the Russell set of a given set A: [1]
The proof of Cantor's theorem is straightforwardly adapted to show that assuming a set of all sets U exists, then considering its Russell set RU leads to the contradiction:
This argument is known as Russell's paradox. [1] As a point of subtlety, the version of Russell's paradox we have presented here is actually a theorem of Zermelo; [4] we can conclude from the contradiction obtained that we must reject the hypothesis that RU∈U, thus disproving the existence of a set containing all sets. This was possible because we have used restricted comprehension (as featured in ZFC) in the definition of RA above, which in turn entailed that
Had we used unrestricted comprehension (as in Frege's system for instance) by defining the Russell set simply as , then the axiom system itself would have entailed the contradiction, with no further hypotheses needed. [4]
Despite the syntactical similarities between the Russell set (in either variant) and the Cantor diagonal set, Alonzo Church emphasized that Russell's paradox is independent of considerations of cardinality and its underlying notions like one-to-one correspondence. [5]
Cantor gave essentially this proof in a paper published in 1891 "Über eine elementare Frage der Mannigfaltigkeitslehre", [6] where the diagonal argument for the uncountability of the reals also first appears (he had earlier proved the uncountability of the reals by other methods). 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. [7] 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.
Bertrand Russell has a very similar proof in Principles of Mathematics (1903, section 348), where he shows that there are more propositional functions 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 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.
Lawvere's fixed-point theorem provides for a broad generalization of Cantor's theorem to any category with finite products in the following way: [8] let be such a category, and let be a terminal object in . Suppose that is an object in and that there exists an endomorphism that does not have any fixed points; that is, there is no morphism that satisfies . Then there is no object of such that a morphism can parameterize all morphisms . In other words, for every object and every morphism , an attempt to write maps as maps of the form must leave out at least one map .
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.
In mathematical logic, model theory is the study of the relationship between formal theories, and their models. The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be defined in a model of a theory, and the relationship of such definable sets to each other. As a separate discipline, model theory goes back to Alfred Tarski, who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by Saharon Shelah's stability theory.
In mathematics, a topological space is called separable if it contains a countable, dense subset; that is, there exists a sequence of elements of the space such that every nonempty open subset of the space contains at least one element of the sequence.
Cantor's diagonal argument is a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers – informally, that there are sets which in some sense contain more elements than there are positive integers. Such sets are now called uncountable sets, and the size of infinite sets is treated by the theory of cardinal numbers, which Cantor began.
In physics, engineering and mathematics, the Fourier transform (FT) is an integral transform that takes a function as input and outputs another function that describes the extent to which various frequencies are present in the original function. The output of the transform is a complex-valued function of frequency. The term Fourier transform refers to both this complex-valued function and the mathematical operation. When a distinction needs to be made, the output of the operation is sometimes called the frequency domain representation of the original function. The Fourier transform is analogous to decomposing the sound of a musical chord into the intensities of its constituent pitches.
In mathematics, a base (or basis; pl.: bases) for the topology τ of a topological space (X, τ) is a family of open subsets of X such that every open set of the topology is equal to the union of some sub-family of . For example, the set of all open intervals in the real number line is a basis for the Euclidean topology on because every open interval is an open set, and also every open subset of can be written as a union of some family of open intervals.
In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. Intuitively, forcing can be thought of as a technique to expand the set theoretical universe to a larger universe by introducing a new "generic" object .
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.
In mathematics, the adele ring of a global field is a central object of class field theory, a branch of algebraic number theory. It is the restricted product of all the completions of the global field and is an example of a self-dual topological ring.
In general topology, a branch of mathematics, a non-empty family A of subsets of a set is said to have the finite intersection property (FIP) if the intersection over any finite subcollection of is non-empty. It has the strong finite intersection property (SFIP) if the intersection over any finite subcollection of is infinite. Sets with the finite intersection property are also called centered systems and filter subbases.
In mathematics, the Fourier inversion theorem says that for many types of functions it is possible to recover a function from its Fourier transform. Intuitively it may be viewed as the statement that if we know all frequency and phase information about a wave then we may reconstruct the original wave precisely.
In mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.
In statistics and probability theory, a point process or point field is a collection of mathematical points randomly located on a mathematical space such as the real line or Euclidean space. Point processes can be used for spatial data analysis, which is of interest in such diverse disciplines as forestry, plant ecology, epidemiology, geography, seismology, materials science, astronomy, telecommunications, computational neuroscience, economics and others.
In mathematical logic, the theory of infinite sets was first developed by Georg Cantor. Although this work has become a thoroughly standard fixture of classical set theory, it has been criticized in several areas by mathematicians and philosophers.
Axiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "" and "" of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories.
In constructive mathematics, a collection is subcountable if there exists a partial surjection from the natural numbers onto it. This may be expressed as
In mathematics, specifically set theory, the Cartesian product of two sets A and B, denoted A × B, is the set of all ordered pairs (a, b) where a is in A and b is in B. In terms of set-builder notation, that is
In digital signal processing, multidimensional sampling is the process of converting a function of a multidimensional variable into a discrete collection of values of the function measured on a discrete set of points. This article presents the basic result due to Petersen and Middleton on conditions for perfectly reconstructing a wavenumber-limited function from its measurements on a discrete lattice of points. This result, also known as the Petersen–Middleton theorem, is a generalization of the Nyquist–Shannon sampling theorem for sampling one-dimensional band-limited functions to higher-dimensional Euclidean spaces.
In mathematics, a polyadic space is a topological space that is the image under a continuous function of a topological power of an Alexandroff one-point compactification of a discrete space.
In algebraic geometry, the problem of residual intersection asks the following: