Cantor's theorem: Difference between revisions

Revision as of 19:46, 24 April 2024

Revision as of 19:59, 24 April 2024

Line 43:

==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|1=''>A'' = '''\mathbb{N'''} = \{{mset|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>

𝒫<math>\mathcal{P}('''\mathbb{N'''})</math> contains infinite subsets of '''<math>\mathbb{N'''}</math>, e.g. the set of all even numbers {2, 4, 6,...}, as well as the [[empty set]].

Now that we have an idea of what the elements of 𝒫<math>\mathcal{P}('''\mathbb{N'''})</math> look like, 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 ''B'' 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 ''B'' as an element. If the mapping is bijective, ''B'' must be paired off with some natural number, say ''b''. However, this causes a problem. If ''b'' is in ''B'', then ''b'' is selfish because it is in the corresponding set, which contradicts the definition of ''B''. If ''b'' is not in ''B'', then it is non-selfish and it should instead be a member of ''B''. Therefore, no such element ''b'' which maps to ''B'' can exist.

Since there is no natural number which can be paired with ''B'', 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 ''B'' may be empty. This would mean that every natural number ''x'' maps to a subset of natural numbers that contains ''x''. 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.

==Related paradoxes==