康托尔的对角线论证

康托尔的第一个对角线论证

下面的例子使用了两个最简单的无限集，即自然数集和正分数集。我们的想法是要证明这两个集合，N {displaystyle\mathbb {N}} 和 Q + {displaystyle \mathbb {Q^{+}}这两个集合都有相同的心数。} 具有相同的cardinality。

首先，分数被排列成一个数组，如下所示。

1 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 3 2 4 2 5 ⋯ 3 1 3 2 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 5 ⋯ 5 1 5 2 5 3 5 4 5 ⋯ ⋮ ⋮ ⋮ ⋮ {\\displaystyle {begin{array}{cccccccc}{tfrac {1}{1}&&{tfrac {1}{2}}&{tfrac {1}{3}}&{tfrac {1}{4}}&&{tfrac {1}{5}}&cdots\&&&&&&&&&\{tfrac {2}{1}&&{tfrac {2}{2}}&&{tfrac {2}{3}}&{tfrac {2}{4}}&{tfrac {2}{5}}&cdots {&&&&&&&&&\{tfrac {3}{1}&&{tfrac {3}{2}}&{tfrac {3}{3}}&{tfrac {3}{4}}&{tfrac {3}{5}}&cdots {&&&&&&&&&\\{tfrac {4}{1}&&{tfrac {4}{2}&&{tfrac {4}{3}&&{tfrac {4}{4}&&{tfrac {4}{5}}&。\ocdots\&&&&&&&&&\{tfrac {5}{1}}&{tfrac {5}{2}}&{tfrac {5}{3}}&&{tfrac {5}{4}}&{tfrac {5}{5}}&&cdots {5}{5}{5}}&&cdots {5}{5}{5}{5}}&&cdots {5}{5}{5}{5}{5}}&&cdots {5}{5}{5}{5}{5}}&&cdots {5}{5}{5}{5}}&&cdots {5}{5}{5}{5}&&cdots

接下来，如图所示，对这些数字进行计数。可以简化的分数就不做了。

1 1 ( 1 ) → 1 2 ( 2 ) 1 3 ( 5 ) → 1 4 ( 6 ) 1 5 ( 11 ) → ↙ ↙ 2 1 ( 3 ) 2 2 ( ⋅ ) 2 3 ( 7 ) 2 4 ( ⋅ ) 2 5 ⋯ ↓ ↙ 3 1 ( 4 ) 3 2 ( 8 ) 3 3 ( ⋅ )3 4 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 4 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ {displaystyle {begin{array}{lclclclc}{tfrac {1}{1}}\ _{\color {Blue}(1)}&{color {MidnightBlue}rightarrow }&{tfrac {1}{2}}\ _{color {Blue}(2)}&{tfrac {1}{3}\ _{color {Blue}(5)}&{color {MidnightBlue}rightarrow }&{tfrac {1}{4}} _{color {Blue}(6)}&{tfrac {1}{5}} _{color {Blue}(11)}&{fnTahomafs10bord0shad01cH00FFFF}{color {MidnightBlue}rightarrow }&{color {MidnightBlue}swarrow }&{color {MidnightBlue}\nearrow }&&{color {MidnightBlue}swarrow }&{color {MidnightBlue}nearrow }&{tfrac {2}{1}}\_{color {Blue}(3)}&&{tfrac {2}{2}}\ _{color {Blue}(\cdot )}&{tfrac {2}{3}}\ _{color {Blue}(7)}&{tfrac {2}{4}}\ _{color {Blue}(\cdot)}&&{tfrac {2}{5}}&cdots {{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\nearrow }&&{color {MidnightBlue}swarrow }&{color {MidnightBlue}nearrow }&&&&\{tfrac {3}{1}\ _{color {Blue}(4)}&&{tfrac {3}{2}}\ _{color {Blue}(8)}&{tfrac {3}{3}}\ _{color {Blue}(\cdot )}&{tfrac {3}{4}}&&{tfrac {3}{5}}&cdots }&{color {MidnightBlue}\swarrow }&{color {MidnightBlue}\nearrow }&&&&&&\\{fnTahomafs10bord0shad01cH00FFFF}and{tfrac {4}{1}}\ _{color {Blue}(9)}&{tfrac {4}{2}}\ _{color {Blue}(cdot )}&{tfrac {4}{3}&&{tfrac {4}{4}}&{tfrac {4}{5}}&cdots {{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\nearrow }&&&&&&&&\{tfrac {5}{1}\ _{color {Blue}(10)}&{tfrac {5}{2}}&{tfrac {5}{3}&{tfrac {5}{4}&&{tfrac {5}{5}}&&cdots \\vdots &&vdots &&vdots &&vdots &end{array}}。

这样一来，分数就被计算在内了。

1 2 3 4 5 6 7 8 9 10 11 ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 3 1 4 2 3 2 4 5 1 5 ⋯ {displaystyle {\begin{array}{cccccccccc}{color {Blue}1}&{color {Blue}2}&{color {Blue}3}&{color {Blue}4}&{color {Blue}5}&{color {Blue}6}&{color {Blue}7}&{color {Blue}8}&{color {Blue}9}&{color {Blue}10}&{color {Blue}11}&{color {Blue}cdots }/[3pt]{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{fnTahomafs10bord0shad01cH00FFFF}{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow}&{fnTahomafs10bord0shad01cH00FFFF}{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow}&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{tfrac {1}{2}}&2&3&。{tfrac {1}{3}}&{tfrac {1}{4}&{tfrac {2}{3}&{tfrac {3}{2}&4&5&{tfrac {1}{5}&cdots\end{array}}。

通过省略仍可简化的分数，有一种双射关系，将自然数的每个元素与分数的一个元素联系起来。

为了证明所有的自然数和分数都有相同的心数，需要添加元素0；在每个分数之后都要添加其负数。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 12 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯{displaystyle {begin{array}{cccccccccccc}{color {Blue}1}&{color {Blue}2}&{color {Blue}3}&{color {Blue}4}&{color {Blue}5}&{color {Blue}6}&{color {Blue}7}&{color {Blue}8}。{fnTahomafs10bord0shad01cH00FFFF}{color {Blue}8}&{color {Blue}9}&{color {Blue}10}&{color {Blue}11}&{color {Blue}12}&{color {Blue}13}&{color {Blue}14}&{color {Blue}15}&{color {Blue}cdots }\[3pt]{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow}&{fnTahomafs10bord0shad01cH00FFFF}{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow}&{fnTahomafs10bord0shad01cH00FFFF}{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color{MidnightBlue}\downarrow{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow {[3pt]0&1&1&{tfrac {1}{2}}&-{tfrac {1}{2}}&2&-2&3&-3&{tfrac {1}{3}&-{tfrac {1}{3}&{tfrac {1}{4}&-{tfrac {1}{4}&{tfrac {2}{3}&-{tfrac {2}{3}&cdots {end{array}}。

这样一来，就有了一个完整的双射，它将一个分数与每个自然数联系起来。换句话说：两个集合都有相同的cardinality。今天，比自然数集拥有相同数量元素的集合被称为可数。元素少于自然数的集合被称为至多可数。根据这个定义，有理数/分数的集合是可数的。

无限集往往具有违背直觉的特性。大卫-希尔伯特在一个被称为 "希尔伯特大饭店悖论 "的实验中展示了这一点。

实数

实数的集合与自然数的集合不具有相同的cardinality；实数比自然数多。上面概述的想法影响了他的证明。在1891年的文章中，康托尔考虑了所有二进制数字的无限序列的集合T（即每个数字都是0或1）。

他首先对以下定理进行了建设性的证明。

如果s₁ ，s₂ ，...，s_n ，...是T中任何元素的枚举，那么T中总有一个元素s对应于枚举中没有s_n 。

为了证明这一点，给定一个来自T的元素枚举，比如说

序列s是通过选择第1位数字作为s₁ 的第1位数字的补充（将0换成1，反之亦然），第2位数字作为s₂ 的第2位数字的补充，第3位数字作为s₃ 的第3位数字的补充，一般对于每个n，n^th 的数字作为s_n 的n^th 的补充。在这个例子中，这得到了。

根据结构，s与每个s_n ，因为它们的n^th 位数不同（在例子中强调）。因此，s不能出现在列举中。

基于这个定理，康托尔接着用矛盾证明法来证明：。

集合T是不可数的。

他假设T是可数的，以避免矛盾。在这种情况下，它的所有元素可以写成一个枚举s₁ , s₂ , ... , s_n , ... 。将前面的定理应用于这个枚举，会产生一个不属于该枚举的序列s。然而，s是T的一个元素，因此应该在枚举中。这与原来的假设相矛盾，所以T必须是不可数的。