Movatterモバイル変換

[0]ホーム

Jump to content

Cantor's theorem

Edit links

From Wikipedia, the free encyclopedia

Every set is smaller than its power set

For other theorems bearing Cantor's name, seeCantor's theorem (disambiguation).

The cardinality of the set {x,y,z}, is three, while there are eight elements in its power set (3 < 2³ = 8), hereordered byinclusion.

This article containsspecial characters. Without properrendering support, you may seequestion marks, boxes, or other symbols.

In mathematicalset theory,Cantor's theorem is a fundamental result which states that, for anyset $A {\displaystyle A}$ , the set of allsubsets of $A, {\displaystyle A,}$ known as thepower set of $A, {\displaystyle A,}$ has a strictly greatercardinality than $A {\displaystyle A}$ itself.

Forfinite sets, Cantor's theorem can be seen to be true by simpleenumeration of the number of subsets. Counting theempty set as a subset, a set with $n {\displaystyle n}$ elements has a total of $2^{n}$ subsets, and the theorem holds because $2^{n}>n$ for allnon-negative integers.

Much more significant is Cantor's discovery of an argument that is applicable to any set, and shows that the theorem holds forinfinite sets also. As a consequence, the cardinality of thereal numbers, which is the same as that of the power set of theintegers, is strictly larger than the cardinality of the integers; seeCardinality of the continuum for details.

The theorem is named forGeorg Cantor, who first stated and proved it at the end of the 19th century. Cantor's theorem had immediate and important consequences for thephilosophy 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 largestcardinal number (colloquially, "there's no largest infinity").

Proof

[edit]

Cantor's argument is elegant and remarkably simple. The complete proof is presented below, with detailed explanations to follow.

Theorem (Cantor)—Let $f {\displaystyle f}$ be a map from set $A {\displaystyle A}$ to its power set ${\mathcal {P}}(A)$ . Then $f:A\to {\mathcal {P}}(A)$ is notsurjective. As a consequence, $\operatorname {card} (A)<\operatorname {card} ({\mathcal {P}}(A))$ holds for any set $A {\displaystyle A}$ .

Proof

$B=\{x\in A\mid x\notin f(x)\}$ exists via theaxiom schema of specification, and $B\in {\mathcal {P}}(A)$ because $B\subseteq A$ .
Assume $f {\displaystyle f}$ is surjective.
Then there exists a $\xi \in A$ such that $f(\xi )=B$ .
From for all $x {\displaystyle x}$ in $A\ [x\in B\iff x\notin f(x)]$ , we deduce $\xi \in B\iff \xi \notin f(\xi )$ viauniversal instantiation.
The previous deduction yields a contradiction of the form $\varphi \Leftrightarrow \lnot \varphi$ , since $f(\xi )=B$ .
Therefore, $f {\displaystyle f}$ is not surjective, viareductio ad absurdum.
We knowinjective maps from $A {\displaystyle A}$ to ${\mathcal {P}}(A)$ exist. For example, a function $g:A\to {\mathcal {P}}(A)$ such that $g(x)=\{x\}$ .
Consequently, $\operatorname {card} (A)<\operatorname {card} ({\mathcal {P}}(A))$ . ∎

By definition of cardinality, we have $\operatorname {card} (X)<\operatorname {card} (Y)$ for any two sets $X {\displaystyle X}$ and $Y {\displaystyle Y}$ if and only if there is aninjective function but nobijective function from $X {\displaystyle X}$ to $Y {\displaystyle Y}$ . It suffices to show that there is no surjection from $X {\displaystyle X}$ to $Y {\displaystyle Y}$ . This is the heart of Cantor's theorem: there is no surjective function from any set $A {\displaystyle A}$ to its power set. To establish this, it is enough to show that no function $f {\displaystyle f}$ (that maps elements in $A {\displaystyle A}$ to subsets of $A {\displaystyle A}$ ) can reach every possible subset, i.e., we just need to demonstrate the existence of a subset of $A {\displaystyle A}$ that is not equal to $f(x)$ for any $x\in A$ . Recalling that each $f(x)$ is a subset of $A {\displaystyle A}$ , such a subset is given by the following construction, sometimes called theCantor diagonal set of $f {\displaystyle f}$ :^[1]^[2]

B=\{x\in A\mid x\not \in f(x)\}.

This means, by definition, that for all $x\in A$ , $x\in B$ if and only if $x\notin f(x)$ . For all $x {\displaystyle x}$ the sets $B {\displaystyle B}$ and $f(x)$ cannot be equal because $B {\displaystyle B}$ was constructed from elements of $A {\displaystyle A}$ whoseimages under $f {\displaystyle f}$ did not include themselves. For all $x\in A$ either $x\in f(x)$ or $x\notin f(x)$ . If $x\in f(x)$ then $f(x)$ cannot equal $B {\displaystyle B}$ because $x\in f(x)$ by assumption and $x\notin B$ by definition. If $x\notin f(x)$ then $f(x)$ cannot equal $B {\displaystyle B}$ because $x\notin f(x)$ by assumption and $x\in B$ by the definition of $B {\displaystyle B}$ .

Equivalently, and slightly more formally, we have just proved that the existence of $\xi \in A$ such that $f(\xi )=B$ implies the followingcontradiction:

{\begin{aligned}\xi \in B&\iff \xi \notin f(\xi )&&{\text{(by definition of }}B{\text{)}};\\\xi \in B&\iff \xi \in f(\xi )&&{\text{(by assumption that }}f(\xi )=B{\text{)}}.\\\end{aligned}}

Therefore, byreductio ad absurdum, the assumption must be false.^[3] Thus there is no $\xi \in A$ such that $f(\xi )=B$ ; in other words, $B {\displaystyle B}$ is not in the image of $f {\displaystyle f}$ and $f {\displaystyle f}$ does not map onto every element of the power set of $A {\displaystyle A}$ , i.e., $f {\displaystyle f}$ is not surjective.

Finally, to complete the proof, we need to exhibit an injective function from $A {\displaystyle A}$ to its power set. Finding such a function is trivial: just map $x {\displaystyle x}$ to the singleton set $\{x\}$ . The argument is now complete, and we have established the strict inequality for any set $A {\displaystyle A}$ that $\operatorname {card} (A)<\operatorname {card} ({\mathcal {P}}(A))$ .

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

Because of the double occurrence of $x {\displaystyle x}$ in the expression " $x\in f(x)$ ", this is adiagonal 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 $x {\displaystyle x}$ from $A=\{x_{1},x_{2},\ldots \}$ , in this order. $A {\displaystyle A}$ is assumed to admit alinear order so that such table can be constructed.
each column of the table is labelled by a unique $y {\displaystyle y}$ from thepower set of $A {\displaystyle A}$ ; the columns are ordered by the argument to $f {\displaystyle f}$ , i.e. the column labels are $f(x_{1}),f(x_{2})$ , ..., in this order.
the intersection of each row $x {\displaystyle x}$ and column $y {\displaystyle y}$ records a true/false bit whether $x\in y$ .

Given the order chosen for the row and column labels, the main diagonal $D {\displaystyle D}$ of this table thus records whether $x\in f(x)$ for each $x\in A$ . One such table will be the following: ${\begin{array}{cccccc}&f(x_{1})&f(x_{2})&f(x_{3})&f(x_{4})&\cdots \\\hline x_{1}&{\color {red}T}&T&F&T&\cdots \\x_{2}&T&{\color {red}F}&F&F&\cdots \\x_{3}&F&F&{\color {red}T}&T&\cdots \\x_{4}&F&T&T&{\color {red}T}&\cdots \\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \end{array}}$ The set $B {\displaystyle B}$ constructed in the previous paragraphs coincides with the row labels for the subset of entries on this main diagonal $D {\displaystyle D}$ (which in above example, coloured red) where the table records that $x\in f(x)$ is false.^[3] Each row records the values of theindicator function of the set corresponding to the column. The indicator function of $B {\displaystyle B}$ coincides with thelogically negated (swap "true" and "false") entries of the main diagonal. Thus the indicator function of $B {\displaystyle B}$ does not agree with any column in at least one entry. Consequently, no column represents $B {\displaystyle B}$ .

Despite the simplicity of the above proof, it is rather difficult for anautomated theorem prover to produce it. The main difficulty lies in an automated discovery of the Cantor diagonal set.Lawrence Paulson noted in 1992 thatOtter could not do it, whereasIsabelle could, albeit with a certain amount of direction in terms of tactics that might perhaps be considered cheating.^[2]

WhenA is countably infinite

[edit]

Let us examine the proof for the specific case when $A {\displaystyle A}$ iscountably infinite.Without loss of generality, we may take $A=\mathbb {N} =\{1,2,3,\ldots \}$ , the set ofnatural numbers.

Suppose that $\mathbb {N}$ isequinumerous with itspower set ${\mathcal {P}}(\mathbb {N} )$ . Let us see a sample of what ${\mathcal {P}}(\mathbb {N} )$ looks like:

{\mathcal {P}}(\mathbb {N} )=\{\varnothing ,\{1,2\},\{1,2,3\},\{4\},\{1,5\},\{3,4,6\},\{2,4,6,\dots \},\dots \}.

Indeed, ${\mathcal {P}}(\mathbb {N} )$ contains infinite subsets of $\mathbb {N}$ , e.g. the set of all positive even numbers $\{2,4,6,\ldots \}=\{2k:k\in \mathbb {N} \}$ , along with theempty set $\varnothing$ .

Now that we have an idea of what the elements of ${\mathcal {P}}(\mathbb {N} )$ are, let us attempt to pair off eachelement of $\mathbb {N}$ with each element of ${\mathcal {P}}(\mathbb {N} )$ to show that these infinite sets are equinumerous. In other words, we will attempt to pair off each element of $\mathbb {N}$ with an element from the infinite set ${\mathcal {P}}(\mathbb {N} )$ , so that no element from either infinite set remains unpaired. Such an attempt to pair elements would look like this:

\mathbb {N} {\begin{Bmatrix}1&\longleftrightarrow &\{4,5\}\\2&\longleftrightarrow &\{1,2,3\}\\3&\longleftrightarrow &\{4,5,6\}\\4&\longleftrightarrow &\{1,3,5\}\\\vdots &\vdots &\vdots \end{Bmatrix}}{\mathcal {P}}(\mathbb {N} ).

Given such a pairing, some natural numbers are paired withsubsets 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 numbersselfish. Other natural numbers are paired withsubsets 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 numbersnon-selfish. Likewise, 3 and 4 are non-selfish.

Using this idea, let us build a special set of natural numbers. This set will provide thecontradiction we seek. Let $B {\displaystyle B}$ be the set ofall non-selfish natural numbers. By definition, thepower set ${\mathcal {P}}(\mathbb {N} )$ contains all sets of natural numbers, and so it contains this set $B {\displaystyle B}$ as an element. If the mapping is bijective, $B {\displaystyle B}$ must be paired off with some natural number, say $b {\displaystyle b}$ . However, this causes a problem. If $b {\displaystyle b}$ is in $B {\displaystyle B}$ , then $b {\displaystyle b}$ is selfish because it is in the corresponding set, which contradicts the definition of $B {\displaystyle B}$ . If $b {\displaystyle b}$ is not in $B {\displaystyle B}$ , then it is non-selfish and it should instead be a member of $B {\displaystyle B}$ . Therefore, no such element $b {\displaystyle b}$ which maps to $B {\displaystyle B}$ can exist.

Since there is no natural number which can be paired with $B {\displaystyle B}$ , we have contradicted our original supposition, that there is abijection between $\mathbb {N}$ and ${\mathcal {P}}(\mathbb {N} )$ .

Note that the set $B {\displaystyle B}$ may be empty. This would mean that every natural number $x {\displaystyle x}$ maps to a subset of natural numbers that contains $x {\displaystyle 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 ${\mathcal {P}}(\mathbb {N} )$ , so the mapping still does not cover ${\mathcal {P}}(\mathbb {N} )$ .

Through thisproof by contradiction we have proven that thecardinality of $\mathbb {N}$ and ${\mathcal {P}}(\mathbb {N} )$ cannot be equal. We also know that thecardinality of ${\mathcal {P}}(\mathbb {N} )$ cannot be less than thecardinality of $\mathbb {N}$ because ${\mathcal {P}}(\mathbb {N} )$ contains allsingletons, by definition, and these singletons form a "copy" of $\mathbb {N}$ inside of ${\mathcal {P}}(\mathbb {N} )$ . Therefore, only one possibility remains, and that is that thecardinality of ${\mathcal {P}}(\mathbb {N} )$ is strictly greater than thecardinality of $\mathbb {N}$ , proving Cantor's theorem.

Related paradoxes

[edit]

Cantor's theorem and its proof are closely related to twoparadoxes 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, theuniversal set $V {\displaystyle 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 $|{\mathcal {P}}(X)|>|X|$ for any set $X {\displaystyle X}$ . On the other hand, all elements of ${\mathcal {P}}(V)$ are sets, and thus contained in $V {\displaystyle V}$ , therefore $|{\mathcal {P}}(V)|\leq |V|$ .^[1]

Another paradox can be derived from the proof of Cantor's theorem by instantiating the functionf with theidentity function; this turns Cantor's diagonal set into what is sometimes called theRussell set of a given setA:^[1]

R_{A}=\left\{\,x\in A:x\not \in x\,\right\}.

The proof of Cantor's theorem is straightforwardly adapted to show that assuming a set of all setsU exists, then considering its Russell setR_U leads to the contradiction:

R_{U}\in R_{U}\iff R_{U}\notin R_{U}.

This argument is known asRussell's paradox.^[1] As a point of subtlety, the version of Russell's paradox we have presented here is actually a theorem ofZermelo;^[4] we can conclude from the contradiction obtained that we must reject the hypothesis thatR_U∈U, thus disproving the existence of a set containing all sets. This was possible because we have usedrestricted comprehension (as featured inZFC) in the definition ofR_A above, which in turn entailed that

R_{U}\in R_{U}\iff (R_{U}\in U\wedge R_{U}\notin R_{U}).

Had we usedunrestricted comprehension (as inFrege's system for instance) by defining the Russell set simply as $R=\left\{\,x:x\not \in x\,\right\}$ , 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]

History

[edit]

Cantor gave essentially this proof in a paper published in 1891 "Über eine elementare Frage der Mannigfaltigkeitslehre",^[6] where thediagonal argument for the uncountability of thereals also first appears (he hadearlier 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 iff is a function defined onX whose values are 2-valued functions onX, then the 2-valued functionG(x) = 1 −f(x)(x) is not in the range off.

Bertrand Russell has a very similar proof inPrinciples of Mathematics (1903, section 348), where he shows that there are morepropositional 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 ofx. Then "not-phi-x(x)," i.e. "phi-x does not hold ofx" is a propositional function not contained in this correlation; for it is true or false ofx according as phi-x is false or true ofx, and therefore it differs from phi-x for every value ofx." 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. SeeZermelo set theory.

Generalizations

[edit]

Lawvere's fixed-point theorem provides for a broad generalization of Cantor's theorem to anycategory withfinite products in the following way:^[8] let ${\mathcal {C}}$ be such a category, and let $1 {\displaystyle 1}$ be a terminal object in ${\mathcal {C}}$ . Suppose that $Y {\displaystyle Y}$ is an object in ${\mathcal {C}}$ and that there exists an endomorphism $\alpha :Y\to Y$ that does not have any fixed points; that is, there is no morphism $y:1\to Y$ that satisfies $\alpha \circ y=y$ . Then there is no object $T {\displaystyle T}$ of ${\mathcal {C}}$ such that a morphism $f:T\times T\to Y$ can parameterize all morphisms $T\to Y$ . In other words, for every object $T {\displaystyle T}$ and every morphism $f:T\times T\to Y$ , an attempt to write maps $T\to Y$ as maps of the form $f(-,x):T\to Y$ must leave out at least one map $T\to Y$ .

References

[edit]

^^a ^b ^c ^dAbhijit Dasgupta (2013).Set Theory: With an Introduction to Real Point Sets.Springer Science & Business Media. pp. 362–363.ISBN 978-1-4614-8854-5.
^^a ^bLawrence Paulson (1992).Set Theory as a Computational Logic(PDF). University of Cambridge Computer Laboratory. p. 14.
^^a ^bGraham Priest (2002).Beyond the Limits of Thought. Oxford University Press. pp. 118–119.ISBN 978-0-19-925405-7.
^^a ^bHeinz-Dieter Ebbinghaus (2007).Ernst Zermelo: An Approach to His Life and Work. Springer Science & Business Media. pp. 86–87.ISBN 978-3-540-49553-6.
^Church, A. [1974] "Set theory with a universal set." inProceedings of the Tarski Symposium. Proceedings of Symposia in Pure Mathematics XXV, ed. L. Henkin, Providence RI, Second printing with additions 1979, pp. 297−308.ISBN 978-0-8218-7360-1. Also published inInternational Logic Review 15 pp. 11−23.
^Cantor, Georg (1891),"Über eine elementare Frage der Mannigfaltigskeitslehre",Jahresbericht der Deutschen Mathematiker-Vereinigung (in German),1:75–78, also inGeorg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, E. Zermelo, 1932.
^A. Kanamori, "The Empty Set, the Singleton, and the Ordered Pair", p.276. Bulletin of Symbolic Logic vol. 9, no. 3, (2003). Accessed 21 August 2023.
^F. William Lawvere; Stephen H. Schanuel (2009).Conceptual Mathematics: A First Introduction to Categories. Cambridge University Press. Session 29.ISBN 978-0-521-89485-2.

Halmos, Paul,Naive Set Theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted bySpringer-Verlag, New York, 1974.ISBN 0-387-90092-6 (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011.ISBN 978-1-61427-131-4 (Paperback edition).
Jech, Thomas (2002),Set Theory, Springer Monographs in Mathematics (3rd millennium ed.), Springer,ISBN 3-540-44085-2

External links

[edit]

"Cantor theorem",Encyclopedia of Mathematics,EMS Press, 2001 [1994]
Weisstein, Eric W."Cantor's Theorem".MathWorld.

v t e Metalogic andmetamathematics
Cantor's theorem Entscheidungsproblem Church–Turing thesis Consistency Effective method Foundations of mathematics of geometry Gödel's completeness theorem Gödel's incompleteness theorems Soundness Completeness Decidability Interpretation Löwenheim–Skolem theorem Metatheorem Satisfiability Independence Type–token distinction Use–mention distinction

v t e Set theory
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy projective Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo

Mathematical logic

General

Theorems (list)
and paradoxes

Logics

Traditional	Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram
Propositional	Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞
Predicate	First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus

Set theory

Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities
Types ofsets	Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann
Maps and cardinality	Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary
Set theories	Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive