In mathematical

_{1}), ''f''(''x''_{2}), ..., in this order. The intersection of each row ''x'' and column ''y'' records a true/false bit whether ''x'' ∈ ''y''. Given the order chosen for the row and column labels, the main diagonal ''D'' of this table thus records whether ''x'' ∈ ''f''(''x'') for each ''x'' ∈ ''A''. The set ''B'' constructed in the previous paragraphs coincides with the row labels for the subset of entries on this main diagonal ''D'' where the table records that ''x'' ∈ ''f''(''x'') is false. Each column records the values of the indicator function of the set corresponding to the column. The indicator function of ''B'' coincides with the logically negated (swap "true" and "false") entries of the main diagonal. Thus the indicator function of ''B'' does not agree with any column in at least one entry. Consequently, no column represents ''B''.
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.

power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...

𝒫(N) contains all sets of natural numbers, and so it contains this set ''B'' as an element. If the mapping is bijective, ''B'' must be paired off with some natural number, say ''b''. However, this causes a problem. If ''b'' is in ''B'', then ''b'' is selfish because it is in the corresponding set, which contradicts the definition of ''B''. If ''b'' is not in ''B'', then it is non-selfish and it should instead be a member of ''B''. Therefore, no such element ''b'' which maps to ''B'' can exist.
Since there is no natural number which can be paired with ''B'', we have contradicted our original supposition, that there is a bijection between N and 𝒫(N).
Note that the set ''B'' may be empty. This would mean that every natural number ''x'' maps to a subset 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 𝒫(N), so the mapping still does not cover 𝒫(N).
Through this

_{''U''} leads to the contradiction:
:$R\_U\; \backslash in\; R\_U\; \backslash iff\; R\_U\; \backslash notin\; R\_U.$
This argument is known as _{''U''}∈''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 ''R''_{''A''} above, which in turn entailed that
:$R\_U\; \backslash in\; R\_U\; \backslash iff\; (R\_U\; \backslash in\; U\; \backslash wedge\; R\_U\; \backslash notin\; R\_U).$
Had we used

set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...

, Cantor's theorem is a fundamental result which states that, for any set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...

$A$, the set of all subsets of $A,$ the power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...

of $A,$ has a strictly greater cardinality than $A$ itself.
For finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...

s, Cantor's theorem can be seen to be true by simple enumeration
An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration (fo ...

of the number of subsets. Counting the empty set as a subset, a set with $n$ elements has a total of $2^n$ subsets, and the theorem holds because $2^n\; >\; n$ for all non-negative integers
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...

.
Much more significant is Cantor's discovery of an argument that is applicable to any set, and shows that the theorem holds for infinite
Infinite may refer to:
Mathematics
* Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
*Infinite (group), a South Korean boy band
*''Infinite'' (EP), debut EP of American m ...

sets also. As a consequence, the cardinality of the real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...

s, which is the same as that of the power set of the integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...

s, is strictly larger than the cardinality of the integers; see Cardinality of the continuum for details.
The theorem is named for German mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...

Georg Cantor
Georg Ferdinand Ludwig Philipp Cantor ( , ; – January 6, 1918) was a German mathematician. He played a pivotal role in the creation of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of ...

, 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
The philosophy of mathematics is the branch of philosophy that studies the assumptions, foundations, and implications of mathematics. It aims to understand the nature and methods of mathematics, and find out the place of mathematics in peop ...

. 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
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. T ...

(colloquially, "there's no largest infinity").
Proof

Cantor's argument is elegant and remarkably simple. The complete proof is presented below, with detailed explanations to follow. By definition of cardinality, we have $\backslash operatorname(X)\; <\; \backslash operatorname(Y)$ for any two sets $X$ and $Y$ if and only if there is an injective function but nobijective function
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...

from $X$ to It suffices to show that there is no surjection from $X$ to $Y$. This is the heart of Cantor's theorem: there is no surjective function from any set $A$ to its power set. To establish this, it is enough to show that no function ''f'' that maps elements in $A$ to subsets of $A$ can reach every possible subset, i.e., we just need to demonstrate the existence of a subset of $A$ that is not equal to $f(x)$ for any $x$ ∈ $A$. (Recall that each $f(x)$ is a subset of $A$.) Such a subset is given by the following construction, sometimes called the Cantor diagonal set of $f$:
:$B=\backslash .$
This means, by definition, that for all ''x'' ∈ ''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
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...

(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''.
Equivalently, and slightly more formally, we just proved that the existence of ξ ∈ ''A'' such that ''f''(ξ) = ''B'' implies the following contradiction
In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...

:
:$\backslash begin\; \backslash xi\backslash notin\; f(\backslash xi)\; \&\backslash iff\; \backslash xi\backslash in\; B\; \&\&\; \backslash textB\backslash text;\; \backslash \backslash \; \backslash xi\; \backslash in\; B\; \&\backslash iff\; \backslash xi\; \backslash in\; f(\backslash xi)\; \&\&\; \backslash textf(\backslash xi)=B\backslash text;\; \backslash \backslash \; \backslash end$
Therefore, by reductio ad absurdum
In logic, (Latin for "reduction to absurdity"), also known as (Latin for "argument to absurdity") or ''apagogical arguments'', is the form of argument that attempts to establish a claim by showing that the opposite scenario would lead to absu ...

, the assumption must be false. Thus there is no ξ ∈ ''A'' such that ''f''(ξ) = ''B''; in other words, ''B'' is not in the image of ''f'' and ''f'' does not map to every element of the power set of ''A'', i.e., ''f'' is not surjective.
Finally, to complete the proof, we need to exhibit an injective function from ''A'' to its power set. Finding such a function is trivial: just map ''x'' to the singleton set . The argument is now complete, and we have established the strict inequality for any set ''A'' that card(''A'') < card(𝒫(''A'')).
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
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...

, 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'' cannot be onto.
Because of the double occurrence of ''x'' in the expression "''x'' ∉ ''f''(''x'')", this is a diagonal argument A diagonal argument, in mathematics, is a technique employed in the proofs of the following theorems:
*Cantor's diagonal argument (the earliest)
*Cantor's theorem
* Russell's paradox
*Diagonal lemma
** Gödel's first incompleteness theorem
**Tarski ...

. 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 ''x'' from ''A'' = , in this order. ''A'' is assumed to admit a linear order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...

so that such table can be constructed. Each column of the table is labelled by a unique ''y'' from the power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...

of ''A''; the columns are ordered by the argument to ''f'', i.e. the column labels are ''f''(''x''Lawrence Paulson
Lawrence Charles Paulson (born 1955) is an American computer scientist. He is a Professor of Computational Logic at the University of Cambridge Computer Laboratory and a Fellow of Clare College, Cambridge.
Education
Paulson graduated from the ...

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.
When ''A'' is countably infinite

Let us examine the proof for the specific case when $A$ is countably infinite.Without loss of generality
''Without loss of generality'' (often abbreviated to WOLOG, WLOG or w.l.o.g.; less commonly stated as ''without any loss of generality'' or ''with no loss of generality'') is a frequently used expression in mathematics. The term is used to indicat ...

, we may take , the set of natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...

s.
Suppose that N is equinumerous
In mathematics, two sets or classes ''A'' and ''B'' are equinumerous if there exists a one-to-one correspondence (or bijection) between them, that is, if there exists a function from ''A'' to ''B'' such that for every element ''y'' of ''B'', the ...

with its power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...

𝒫(N). Let us see a sample of what 𝒫(N) looks like:
:$\backslash mathcal(\backslash mathbb)=\backslash .$
𝒫(N) contains infinite subsets of N, e.g. the set of all even numbers , as well as the empty set.
Now that we have an idea of what the elements of 𝒫(N) look like, let us attempt to pair off each element of N with each element of 𝒫(N) to show that these infinite sets are equinumerous. In other words, we will attempt to pair off each element of N with an element from the infinite set 𝒫(N), so that no element from either infinite set remains unpaired. Such an attempt to pair elements would look like this:
:$\backslash mathbb\backslash begin\; 1\; \&\; \backslash longleftrightarrow\; \&\; \backslash \backslash \backslash \; 2\; \&\; \backslash longleftrightarrow\; \&\; \backslash \; \backslash \backslash \; 3\; \&\; \backslash longleftrightarrow\; \&\; \backslash \; \backslash \backslash \; 4\; \&\; \backslash longleftrightarrow\; \&\; \backslash \; \backslash \backslash \; \backslash vdots\; \&\; \backslash vdots\; \&\; \backslash vdots\; \backslash end\backslash mathcal(\backslash mathbb).$
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 , 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 , 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
In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...

we seek. Let ''B'' be the set of ''all'' non-selfish natural numbers. By definition, the proof by contradiction
In logic and mathematics, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Proof by contradiction is also known ...

we have proven that the cardinality of N and 𝒫(N) cannot be equal. We also know that the cardinality of 𝒫(N) cannot be less than the cardinality of N because 𝒫(N) contains all singleton
Singleton may refer to:
Sciences, technology Mathematics
* Singleton (mathematics), a set with exactly one element
* Singleton field, used in conformal field theory Computing
* Singleton pattern, a design pattern that allows only one instance ...

s, by definition, and these singletons form a "copy" of N inside of 𝒫(N). Therefore, only one possibility remains, and that is that the cardinality of 𝒫(N) is strictly greater than the cardinality of N, proving Cantor's theorem.
Related paradoxes

Cantor's theorem and its proof are closely related to twoparadoxes of set theory
This article contains a discussion of paradoxes of set theory. As with most mathematical paradoxes, they generally reveal surprising and counter-intuitive mathematical results, rather than actual logical contradictions within modern axiomatic set t ...

.
Cantor's paradox
In set theory, Cantor's paradox states that there is no set of all cardinalities. This is derived from the theorem that there is no greatest cardinal number. In informal terms, the paradox is that the collection of all possible "infinite sizes" is ...

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 set theory, a universal set is a set which contains all objects, including itself. In set theory as usually formulated, it can be proven in multiple ways that a universal set does not exist. However, some non-standard variants of set theory inc ...

$V$. 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 $,\; \backslash mathcal(X),\; >\; ,\; X,$ for any set $X$. On the other hand, all elements of $\backslash mathcal(V)$ are sets, and thus contained in $V$, therefore $,\; \backslash mathcal(V),\; \backslash leq\; ,\; V,$.
Another paradox can be derived from the proof of Cantor's theorem by instantiating the function ''f'' with the identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...

; this turns Cantor's diagonal set into what is sometimes called the ''Russell set'' of a given set ''A'':
:$R\_A=\backslash left\backslash .$
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 ''R''Russell's paradox
In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox discovered by the British philosopher and mathematician Bertrand Russell in 1901. Russell's paradox shows that every set theory that contains ...

. As a point of subtlety, the version of Russell's paradox we have presented here is actually a theorem of Zermelo
Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic se ...

; we can conclude from the contradiction obtained that we must reject the hypothesis that ''R''unrestricted comprehension
In many popular versions of axiomatic set theory, the axiom schema of specification, also known as the axiom schema of separation, subset axiom scheme or axiom schema of restricted comprehension is an axiom schema. Essentially, it says that any ...

(as in Frege
Friedrich Ludwig Gottlob Frege (; ; 8 November 1848 – 26 July 1925) was a German philosopher, logician, and mathematician. He was a mathematics professor at the University of Jena, and is understood by many to be the father of analytic ph ...

's system for instance) by defining the Russell set simply as $R=\backslash left\backslash $, then the axiom system itself would have entailed the contradiction, with no further hypotheses needed.
Despite the syntactical similarities between the Russell set (in either variant) and the Cantor diagonal set, Alonzo Church
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer scien ...

emphasized that Russell's paradox is independent of considerations of cardinality and its underlying notions like one-to-one correspondence.
History

Cantor gave essentially this proof in a paper published in 1891 "Über eine elementare Frage der Mannigfaltigkeitslehre",, also in ''Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts'', E. Zermelo, 1932. where thediagonal argument A diagonal argument, in mathematics, is a technique employed in the proofs of the following theorems:
*Cantor's diagonal argument (the earliest)
*Cantor's theorem
* Russell's paradox
*Diagonal lemma
** Gödel's first incompleteness theorem
**Tarski ...

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. 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
Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ...

has a very similar proof in '' Principles of Mathematics'' (1903, section 348), where he shows that there are more propositional function In propositional calculus, a propositional function or a predicate is a sentence expressed in a way that would assume the value of true or false, except that within the sentence there is a variable (''x'') that is not defined or specified (thus be ...

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 Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic se ...

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 (sometimes denoted by Z-), as set out in a seminal paper in 1908 by Ernst Zermelo, is the ancestor of modern Zermelo–Fraenkel set theory (ZF) and its extensions, such as von Neumann–Bernays–Gödel set theory (NBG). It be ...

.
Generalizations

Cantor's theorem has been generalized to anycategory
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
* Category of being
* ''Categories'' (Aristotle)
* Category (Kant)
* Categories (Peirce) ...

with products
Product may refer to:
Business
* Product (business), an item that serves as a solution to a specific consumer problem.
* Product (project management), a deliverable or set of deliverables that contribute to a business solution
Mathematics
* Produ ...

.
See also

*Schröder–Bernstein theorem In set theory, the Schröder–Bernstein theorem states that, if there exist injective functions and between the sets and , then there exists a bijective function .
In terms of the cardinality of the two sets, this classically implies that if ...

*Cantor's first uncountability proof
Cantor's first set theory article contains Georg Cantor's first theorems of transfinite set theory, which studies infinite sets and their properties. One of these theorems is his "revolutionary discovery" that the set of all real numbers is unco ...

* Controversy over Cantor's theory
References

* Halmos, Paul, '' Naive Set Theory''. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted bySpringer-Verlag
Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.
Originally founded in 1842 ...

, New York, 1974. (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. (Paperback edition).
*
External links

* * {{Mathematical logic 1891 introductions 1891 in science Set theory Theorems in the foundations of mathematics Cardinal numbers Georg Cantor