Cantor's theorem: Difference between revisions

Revision as of 08:12, 14 May 2024

Latest revision as of 00:55, 8 December 2024

(19 intermediate revisions by 10 users not shown)

Line 10:

Much more significant is Cantor's discovery of an argument that is applicable to any set, and shows that the theorem holds for [[infinite set|infinite]] sets also. As a consequence, the cardinality of the [[real number]]s, which is the same as that of the power set of the [[integer]]s, is strictly larger than the cardinality of the integers; see [[Cardinality of the continuum]] for details.

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

==Proof==

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| Consider the set <math> B=\{x \in A \mid x \notin f(x)\}</math>. exists Suppose tovia the contrary[[axiom thatschema of specification]], and <math> B \in \mathcal{P}(A) </math> because <math> B \subseteq 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> ButFrom by&nbsp;''for all'' <math>x</math> ''in'' <math>A \ [ x \in B \iff x \notin f(x) ]</math> construction, we deduce &nbsp;<math>\xi \in B \iff \xi \notin f(\xi)= B </math> &nbsp;via [[universal instantiation]]. <br> ThisThe isprevious deduction yields a contradiction of the form <math>\varphi \Leftrightarrow \lnot \varphi</math>, since <math>f(\xi)=B</math>. <br> ThusTherefore, <math>f</math> cannotis benot surjective, via [[reductio ad absurdum]]. <br> OnWe theknow other[[injective handfunction|injective maps]] from <math>A</math> to <math>\mathcal{P}(A)</math> exist. For example, a function <math>g : A \to \mathcal{P}(A)</math> definedsuch bythat <math>g(x) \mapsto= \{x\}</math> is an injective map. <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>. (RecallRecalling that each <math>f(x)</math> is a subset of <math>A</math>.), Suchsuch 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>

Line 38:

Another way to think of the proof is that <math>B</math>, empty or non-empty, is always in the power set of <math>A</math>. For <math>f</math> to be [[Surjective function|onto]], some element of <math>A</math> must map to <math>B</math>. But that leads to a contradiction: no element of <math>B</math> can map to <math>B</math> because that would contradict the criterion of membership in <math>B</math>, thus the element mapping to <math>B</math> must not be an element of <math>B</math> meaning that it satisfies the criterion for membership in <math>B</math>, another contradiction. So the assumption that an element of <math>A</math> maps to <math>B</math> must be false; and <math>f</math> cannot be onto.

Because of the double occurrence of <math>x</math> in the expression "<math>x\in f(x)</math>", this is a [[Cantor's diagonal argument|diagonal argument]]. For a countable (or finite) set, the argument of the proof given above can be illustrated by constructing a table in which

Because of the double occurrence of <math>x</math> in the expression "<math>x\in f(x)</math>", this is a [[Cantor's diagonal argument|diagonal 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 <math>x</math> from <math>A=\{x_1 ,x_2 , \ldots \}</math>, in this order. <math>A</math> is assumed to admit a [[Total order|linear order]] so that such table can be constructed. Each column of the table is labelled by a unique <math>y</math> from the [[power set]] of <math>A</math>; the columns are ordered by the argument to <math>f</math>, i.e. the column labels are <math>f(x_1),f(x_2)</math>, ..., in this order. The intersection of each row <math>x</math> and column <math>y</math> records a true/false bit whether <math>x\in y</math>. Given the order chosen for the row and column labels, the main diagonal <math>D</math> of this table thus records whether <math>x\in f(x)</math> for each <math>x\in A</math>. The set <math>B</math> constructed in the previous paragraphs coincides with the row labels for the subset of entries on this main diagonal <math>D</math> where the table records that <math>x\in f(x)</math> is false.<ref name="Priest2002">{{cite book|author=Graham Priest|title=Beyond the Limits of Thought|year=2002|publisher=Oxford University Press|isbn=978-0-19-925405-7|pages=118–119}}<!--note that the page numbers differ between the OUP and CUP editions of Priest's book!--></ref> Each column records the values of the [[indicator function]] of the set corresponding to the column. The indicator function of <math>B</math> coincides with the [[logical negation|logically negated]] (swap "true" and "false") entries of the main diagonal. Thus the indicator function of <math>B</math> does not agree with any column in at least one entry. Consequently, no column represents <math>B</math>.

# each row is labelled by a unique <math>x</math> from <math>A=\{x_1 ,x_2 , \ldots \}</math>, in this order. <math>A</math> is assumed to admit a [[Total order|linear order]] so that such table can be constructed.

# each column of the table is labelled by a unique <math>y</math> from the [[power set]] of <math>A</math>; the columns are ordered by the argument to <math>f</math>, i.e. the column labels are <math>f(x_1),f(x_2)</math>, ..., in this order.

# the intersection of each row <math>x</math> and column <math>y</math> records a true/false bit whether <math>x\in y</math>.

Given the order chosen for the row and column labels, the main diagonal <math>D</math> of this table thus records whether <math>x\in f(x)</math> for each <math>x\in A</math>. One such table will be the following:

<math display="block">\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}</math>

Because of the double occurrence of <math>x</math> in the expression "<math>x\in f(x)</math>", this is a [[Cantor's diagonal argument|diagonal 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 <math>x</math> from <math>A=\{x_1 ,x_2 , \ldots \}</math>, in this order. <math>A</math> is assumed to admit a [[Total order|linear order]] so that such table can be constructed. Each column of the table is labelled by a unique <math>y</math> from the [[power set]] of <math>A</math>; the columns are ordered by the argument to <math>f</math>, i.e. the column labels are <math>f(x_1),f(x_2)</math>, ..., in this order. The intersection of each row <math>x</math> and column <math>y</math> records a true/false bit whether <math>x\in y</math>. Given the order chosen for the row and column labels, the main diagonal <math>D</math> of this table thus records whether <math>x\in f(x)</math> for each <math>x\in A</math>. The set <math>B</math> constructed in the previous paragraphs coincides with the row labels for the subset of entries on this main diagonal <math>D</math> (which in above example, coloured red) where the table records that <math>x\in f(x)</math> is false.<ref name="Priest2002">{{cite book|author=Graham Priest|title=Beyond the Limits of Thought|year=2002|publisher=Oxford University Press|isbn=978-0-19-925405-7|pages=118–119}}<!--note that the page numbers differ between the OUP and CUP editions of Priest's book!--></ref> Each columnrow records the values of the [[indicator function]] of the set corresponding to the column. The indicator function of <math>B</math> coincides with the [[logical negation|logically negated]] (swap "true" and "false") entries of the main diagonal. Thus the indicator function of <math>B</math> does not agree with any column in at least one entry. Consequently, no column represents <math>B</math>.

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. [[Lawrence Paulson]] noted in 1992 that [[Otter (theorem prover)|Otter]] could not do it, whereas [[Isabelle (proof assistant)|Isabelle]] could, albeit with a certain amount of direction in terms of tactics that might perhaps be considered cheating.<ref name="Paulson1992"/>

Line 49 ⟶ 63:

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

Indeed, <math>\mathcal{P}(\mathbb{N})</math> contains infinite subsets of <math>\mathbb{N}</math>, e.g. the set of all positive even numbers <math>\{2, 4, 6,\ldots\}=\{2k:k\in \mathbb{N}\}</math>, along with the [[empty set]] <math>\varnothing</math>.

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