Cantor's theorem: Difference between revisions

Revision as of 07:08, 17 June 2021

Revision as of 17:18, 11 July 2021

Line 4:

{{SpecialChars}}

In elementary [[set theory]], '''Cantor's theorem''' is a fundamental result which states that, for any [[Set (mathematics)|set]] <math>A</math>, the set of all [[subset]]s of <math>A</math> (the [[power set]] of <math>A</math>, denoted by <math>\mathcal{P}(A)</math>) has a strictly greater [[cardinality]] than <math>A</math> itself. For [[finite set]]s, 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 <math>n</math> members has a total of <math>2^n</math> subsets, so that if <math>\operatorname{\rm card}(A) = n,</math> then <math>\operatorname{\rm card}(\mathcal{P}(A)) = 2^n</math>, and the theorem holds because <math>2^n > n</math> for all [[non-negative integers]].

Much more significant is Cantor's discovery of an argument that is applicable to any set, which showed that the theorem holds for [[infinite set|infinite]] sets, countable or uncountable, as well as finite ones. As a particularly important consequence, the power set of the set of [[natural number]]s, a [[countably infinite]] set with cardinality {{math|1=ℵ₀ = card('''N''')}}, is [[uncountable set|uncountably infinite]] and has the same size as the set of [[real number]]s, a cardinality larger than that of the set of natural numbers that is often referred to as the [[cardinality of the continuum]]: {{math|1=𝔠 = card(ℝ'''R''') = card(𝒫('''N'''))}}. The relationship between these cardinal numbers is often expressed symbolically by the equality and inequality <math>\mathfrak{c} = 2^{\aleph_0} > \aleph_0</math>.

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").

Line 16:

{{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>\operatorname{card}(A) < \operatorname{card}(\mathcal{P}(A))</math>. [[Q.E.D.]]}}

By definition of cardinality, we have <math>\mathrmoperatorname{card}(X) < \mathrmoperatorname{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>