Cantor's theorem: Difference between revisions

Revision as of 20:08, 24 April 2024

Revision as of 08:04, 14 May 2024

Line 16:

{{math theorem|name=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>\operatorname{card}(A) < \operatorname{card}(\mathcal{P}(A))</math> holds for any set <math>A</math>.}}

{{math proof| ConsiderLet the<math> A </math> be any arbitrary set. <br> Let <math>f</math> be a map from <math>A</math> to its power set, <math>\mathcal{P}(A)</math>. <br> <math> B=\{x \in A \mid x \notin f(x)\}</math> exists via the [[axiom schema of specification]]. <br> SupposeBy todefinition, the<math> contraryB that\subseteq A </math> and <math> B \in \mathcal{P}(A) </math> since for all <math> x </math>, <math> x \in B </math> implies <math> x \in A </math>. <br> Assume <math> f </math> is surjective. <br> Then there exists a <math>\xi \in A</math> such that <math>f(\xi)=B</math>. <br> But by construction,If <math>\xi \in B \iff \xi \notin f(\xi)= B </math>., then This<math> is\xi a\in contradiction. Thus,B </math>f. </mathbr> cannotThe beprevious surjective.line is a contradiction Onof the other[[logical hand,form|form]] <math>g\lnot : A\varphi \toRightarrow \mathcal{P}varphi</math>, since <math>f(A\xi)=B</math>. defined<br> byTherefore, <math>x \mapsto \{x\}f</math> iscannot anbe injective mapsurjective. <br> Consequently, we must have <math>\operatorname{card}(A) < \operatorname{card}(\mathcal{P}(A))</math>. [[Q.E.D.]]}}

By definition of cardinality, we have <math>\operatorname{card}(X) < \operatorname{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> {{nowrap|to <math>Y</math>.}} It suffices to show that there is no surjection from <math>X</math> {{nowrap|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 <math>f</math> 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 \in 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>