【计算理论】可判定性 ( 对角线方法 | 证明自然数集 N 与实数集 R 不存在一一对应关系 )_如何证明r和n不等势

一、对角线方法

---

数学上使用 对角线方法 证明了一个很重要的数学命题 , 自然数集 与 实数集 不是一一对应的 ;

1874 年 G.Cantor 使用对角线方法证明了上述命题 , 代表人类彻底掌握了无穷的运算 , 是现代数学的开端 ;

( 1874 年之前的数学称为 古典数学 )

二、证明自然数集 N 与实数集 R 不存在一一对应关系

---

证明过程 : $\mathrm{N}\ne \mathrm{R}$ , 自然数集与实数集不存在一一对应 ;

证明的方法是 反证法 ;

假设 : 自然数集 $\mathrm{N}$ 与 实数集 $\mathrm{R}$ 之间 , 一定存在一一映射 ;

$\mathrm{N}$ 可以进行一一枚举出来 , $\mathrm{f}(1),\mathrm{f}(2),\cdots ,\mathrm{f}(\mathrm{n})$ ,

$\mathrm{f}(\mathrm{n})$ 对应的是实数 , 将其限制在 $[0,1]$ 区间内 ;

$[0,1]$ 之间的实数 , 与整个实数集 一定存在着一一对应关系的 ;

现在证明 自然数集 $\mathrm{N}$ 与 $[0,1]$ 区间内的实数 , 不可能存在一一对应 ;

$\mathrm{f}(\mathrm{n})$ 是一个 $[0,1]$ 区间内的实数 , 则可以写成

$\mathrm{f}(1)=0.{\mathrm{a}}_{11}{\mathrm{a}}_{12}{\mathrm{a}}_{13}{\mathrm{a}}_{14}\cdots$ ,

$\mathrm{f}(2)=0.{\mathrm{a}}_{21}{\mathrm{a}}_{22}{\mathrm{a}}_{23}{\mathrm{a}}_{24}\cdots$

$⋮$

$\mathrm{f}(\mathrm{n})=0.{\mathrm{a}}_{\mathrm{n}1}{\mathrm{a}}_{\mathrm{n}2}{\mathrm{a}}_{\mathrm{n}3}{\mathrm{a}}_{\mathrm{n}4}\cdots {\mathrm{a}}_{\mathrm{n}\mathrm{n}}$

其中 $a_{1k}$ 的值 ( $k=1,2,3,4,\cdots$ ) 是 $0,1,2,3,4,5,6,7,8,9$ 中的一个数字 ;

假设存在一个 $f$ 是一一映射 , 从自然数集 到 $[0,1]$ 区间内的实数 之间的映射 ,

对角线上的值 $a_{11},a_{22},\cdots ,a_{nn}$ ,

根据对角线上的值设计一个实数 $b=b_1{b}_2{b}_3\cdots b_n$

选择 $b_1$ 一定不等于 $a_{11}$ ,

选择 $b_2$ 一定不等于 $a_{22}$ ,

选择 $b_n$ 一定不等于 $a_{nn}$ ;

如果 自然数集 $\mathrm{N}$ 与 实数集 $\mathrm{R}$ 是一一对应 , 那么 一定可以找到一个自然数 $\mathrm{k}$ , 与实数 $b=b_1{b}_2{b}_3\cdots b_n$ 一一对应 ;

实数 $b=b_1{b}_2{b}_3\cdots b_n$ , 一定等于某个自然数 $\mathrm{k}$ 对应的 $\mathrm{f}(\mathrm{k})$ ;

现在得到了一个 矛盾 , 设计过程中 ${\mathrm{b}}_{\mathrm{k}}$ 肯定不等于 ${\mathrm{a}}_{\mathrm{k}\mathrm{k}}$ , 而 $\mathrm{f}(\mathrm{k})$ 的第 $\mathrm{k}$ 个数值一定是 ${\mathrm{a}}_{\mathrm{k}\mathrm{k}}$ , 因此这两个值 $b=b_1{b}_2{b}_3\cdots b_n$ 与 $\mathrm{f}(\mathrm{k})$ 不可能相等 ;

三、对角线方法意义

---

该证明的证明过程很简单 , 但是该证明在整个人类历史上是非常重要的一个证明 ;

它证明了 自然数的无穷 与 实数的无穷 是两种性质截然不同的无穷 ;