Content deleted Content added
Tags: Reverted references removed |
→When A is countably infinite: Added "Indeed," to the beginning of a sentence so that the sentence does not start with a mathematical symbol, as is often accepted as bad style. I think this does not change the meaning of the sentence |
||
| (One intermediate revision by one other user not shown) | |||
Line 18:
{{math proof| <math> B=\{x \in A \mid x \notin f(x)\}</math> exists via the [[axiom schema 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> From ''for all'' <math>x</math> ''in'' <math>A \ [ x \in B \iff x \notin f(x) ]</math> , we deduce <math>\xi \in B \iff \xi \notin f(\xi) </math> via [[universal instantiation]]. <br> The previous deduction yields a contradiction of the form <math>\varphi \Leftrightarrow \lnot \varphi</math>, since <math>f(\xi)=B</math>. <br> Therefore, <math>f</math> is not surjective, via [[reductio ad absurdum]]. <br> We know [[injective function|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> such that <math>g(x) = \{x\}</math>. <br> Consequently, <math>\operatorname{card}(A) < \operatorname{card}(\mathcal{P}(A))</math>. ∎}}
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>. Recalling 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>
Line 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:
| |||