Editing Cantor's theorem (section)

==When ''A'' is countably infinite==
Let us examine the proof for the specific case when <math>A</math> is [[countably infinite]]. [[Without loss of generality]], we may take <math>A = \mathbb{N} = \{1,2,3,\ldots\}</math>, the set of [[natural number]]s.

Suppose that <math>\mathbb{N}</math> is [[equinumerous]] with its [[power set]] <math>\mathcal{P}(\mathbb{N})</math>. Let us see a sample of what <math>\mathcal{P}(\mathbb{N})</math> looks like:

:<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:

:<math>\mathbb{N}\begin{Bmatrix} 1 & \longleftrightarrow & \{4, 5\}\\ 2 & \longleftrightarrow & \{1, 2, 3\} \\ 3 & \longleftrightarrow & \{4, 5, 6\} \\ 4 & \longleftrightarrow & \{1, 3, 5\} \\ \vdots & \vdots & \vdots \end{Bmatrix}\mathcal{P}(\mathbb{N}).</math>

Given such a pairing, some natural numbers are paired with [[subset]]s that contain the very same number. For instance, in our example the number 2 is paired with the subset {1, 2, 3}, which contains 2 as a member. Let us call such numbers ''selfish''. Other natural numbers are paired with [[subset]]s that do not contain them. For instance, in our example the number 1 is paired with the subset {4, 5}, which does not contain the number 1. Call these numbers ''non-selfish''. Likewise, 3 and 4 are non-selfish.

Using this idea, let us build a special set of natural numbers. This set will provide the [[proof by contradiction|contradiction]] we seek. Let <math>B</math> be the set of ''all'' non-selfish natural numbers. By definition, the [[power set]] <math>\mathcal{P}(\mathbb{N})</math> contains all sets of natural numbers, and so it contains this set <math>B</math> as an element. If the mapping is bijective, <math>B</math> must be paired off with some natural number, say <math>b</math>. However, this causes a problem. If <math>b</math> is in <math>B</math>, then <math>b</math> is selfish because it is in the corresponding set, which contradicts the definition of <math>B</math>. If <math>b</math> is not in <math>B</math>, then it is non-selfish and it should instead be a member of <math>B</math>. Therefore, no such element <math>b</math> which maps to <math>B</math> can exist.

Since there is no natural number which can be paired with <math>B</math>, we have contradicted our original supposition, that there is a [[bijection]] between <math>\mathbb{N}</math> and <math>\mathcal{P}(\mathbb{N})</math>.

Note that the set <math>B</math> may be empty. This would mean that every natural number <math>x</math> maps to a subset of natural numbers that contains <math>x</math>. Then, every number maps to a nonempty set and no number maps to the empty set. But the empty set is a member of <math>\mathcal{P}(\mathbb{N})</math>, so the mapping still does not cover <math>\mathcal{P}(\mathbb{N})</math>.

Through this [[proof by contradiction]] we have proven that the [[cardinality]] of <math>\mathbb{N}</math> and <math>\mathcal{P}(\mathbb{N})</math> cannot be equal. We also know that the [[cardinality]] of <math>\mathcal{P}(\mathbb{N})</math> cannot be less than the [[cardinality]] of <math>\mathbb{N}</math> because <math>\mathcal{P}(\mathbb{N})</math> contains all [[singleton (mathematics)|singleton]]s, by definition, and these singletons form a "copy" of <math>\mathbb{N}</math> inside of <math>\mathcal{P}(\mathbb{N})</math>. Therefore, only one possibility remains, and that is that the [[cardinality]] of <math>\mathcal{P}(\mathbb{N})</math> is strictly greater than the [[cardinality]] of <math>\mathbb{N}</math>, proving Cantor's theorem.