Cantor's theorem: Difference between revisions

Revision as of 04:25, 18 April 2021

Revision as of 06:26, 17 June 2021

Line 13:

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

{{quoteboxmath theorem|quotename=<p>'''Theorem (Cantor).''' |math_statement=Let <math>f</math> be a map from set <math>A</math> to its power set <math>\mathcal{P}(A)</math>. Then <math>f : A \to \mathcal{P}(A)</math> is not [[surjective]]. As a consequence, <math>\mathrmoperatorname{card}(A) < \mathrmoperatorname{card}(\mathcal{P}(A))</math> holds for any set <math>A</math>.</p>}}

<p>'''Proof.'''{{math proof| Consider the set <math> B=\{x \in A \, | \,mid x \notin f(x)\}</math>. Suppose to the contrary that <math>f</math> is surjective. Then there exists <math>\xi\in A</math> such that <math>f(\xi)=B</math>. But by construction, <math>\xi \in B \iff \xi \notin f(\xi)= B </math>. This is a contradiction. Thus, <math>f</math> cannot be surjective. On the other hand, <math>g : A \to \mathcal{P}(A)</math> defined by <math>x \mapsto \{x\}</math> is an injective map. Consequently, we must have <math>\mathrmoperatorname{card}(A) < \mathrmoperatorname{card}(\mathcal{P}(A))</math>.<math>\ \blacksquare</math></p>|qalign=left[[Q.E.D.]]}}

By definition of cardinality, we have <math>\mathrm{card}(X) < \mathrm{card}(Y)</math> for any two sets <math>X</math> and <math>Y</math> if and only if there is an [[injective function]] but no [[Bijective Function|bijective function]] from <math>X</math> to {{nowrap|<math>Y</math>.}} It suffices to show that there is no surjection from <math>X</math> to <math>Y</math>. This is the heart of Cantor's theorem: there is no surjective function from any set <math>A</math> to its power set. To establish this, it is enough to show that no function ''f'' that maps elements in <math>A</math> to subsets of <math>A</math> can reach every possible subset, i.e., we just need to demonstrate the existence of a subset of <math>A</math> that is not equal to <math>f(x)</math> for any <math>x</math> ∈ <math>A</math>. (Recall that each <math>f(x)</math> is a subset of <math>A</math>.) Such a subset is given by the following construction, sometimes called the [[Cantor's diagonal argument|Cantor diagonal set]] of <math>f</math>:<ref name="Dasgupta2013">{{cite book|author=Abhijit Dasgupta|title=Set Theory: With an Introduction to Real Point Sets|year=2013|publisher=[[Springer Science & Business Media]]|isbn=978-1-4614-8854-5|pages=362–363}}</ref><ref name="Paulson1992">{{cite book|author=Lawrence Paulson|title=Set Theory as a Computational Logic |url=https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-271.pdf|year=1992|publisher=University of Cambridge Computer Laboratory|page=14}}</ref>

:<math>B=\{x\in A \,|\,mid x\not\in f(x)\}.</math>

This means, by definition, that for all ''x''&nbsp;∈&nbsp;''A'', ''x''&nbsp;∈&nbsp;''B'' if and only if ''x''&nbsp;∉&nbsp;''f''(''x''). For all ''x'' the sets ''B'' and ''f''(''x'') cannot be the same because ''B'' was constructed from elements of ''A'' whose [[Image (mathematics)|images]] (under ''f'') did not include themselves. More specifically, consider any ''x''&nbsp;∈&nbsp;''A'', then either ''x''&nbsp;∈&nbsp;''f''(''x'') or ''x''&nbsp;∉&nbsp;''f''(''x''). In the former case, ''f''(''x'') cannot equal ''B'' because ''x''&nbsp;∈&nbsp;''f''(''x'') by assumption and ''x''&nbsp;∉&nbsp;''B'' by the construction of ''B''. In the latter case, ''f''(''x'') cannot equal ''B'' because ''x''&nbsp;∉&nbsp;''f''(''x'') by assumption and ''x''&nbsp;∈&nbsp;''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]]:

:<math>\begin{aligned}

:<math>\begin{aligned}\xi \in f(\xi) &\iff \xi \in B && \text{(by assumption that }f(\xi)=B\text{)}; \\

\xi\in B &\iff \xi\notin f(\xi) && \text{(by definition of }B\text{)}.
\end{aligned}</math>

Therefore, by [[reductio ad absurdum]], the assumption must be false.<ref name="Priest2002"/> 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.