Cantor's theorem: Difference between revisions

Revision as of 19:59, 24 April 2024

Revision as of 20:08, 24 April 2024

Line 49:

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

<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>, asalong well aswith the [[empty set]] <math>\varnothing</math>.

Now that we have an idea of what the elements of <math>\mathcal{P}(\mathbb{N})</math> look likeare, 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>

Line 57:

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.