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

一、对角线方法

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

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

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

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

证明过程 : N ≠ R \rm N \not=R N​=R , 自然数集与实数集不存在一一对应 ;

证明的方法是 反证法 ;

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

N \rm N N 可以进行一一枚举出来 , f ( 1 ) , f ( 2 ) , ⋯   , f ( n ) \rm f(1) , f(2) , \cdots , f(n) f(1),f(2),⋯,f(n) ,

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

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

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

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

f ( 1 ) = 0. a 11 a 12 a 13 a 14 ⋯ \rm f(1) = 0.a_{11}a_{12}a_{13}a_{14}\cdots f(1)=0.a11​a12​a13​a14​⋯ ,

f ( 2 ) = 0. a 21 a 22 a 23 a 24 ⋯ \rm f(2) = 0.a_{21}a_{22}a_{23}a_{24}\cdots f(2)=0.a21​a22​a23​a24​⋯

⋮ \vdots ⋮

f ( n ) = 0. a n 1 a n 2 a n 3 a n 4 ⋯ a n n \rm f(n) = 0.a_{n1}a_{n2}a_{n3}a_{n4}\cdots a_{nn} f(n)=0.an1​an2​an3​an4​⋯ann​

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

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

对角线上的值 a 11 , a 22 , ⋯   , a n n a_{11} , a_{22} , \cdots , a_{nn} a11​,a22​,⋯,ann​ ,

根据对角线上的值设计一个实数 b = b 1 b 2 b 3 ⋯ b n b = b_1b_2b_3\cdots b_n b=b1​b2​b3​⋯bn​

选择 b 1 b_1 b1​ 一定不等于 a 11 a_{11} a11​ ,

选择 b 2 b_2 b2​ 一定不等于 a 22 a_{22} a22​ ,

选择 b n b_n bn​ 一定不等于 a n n a_{nn} ann​ ;

如果 自然数集 N \rm N N 与 实数集 R \rm R R 是一一对应 , 那么 一定可以找到一个自然数 k \rm k k , 与实数 b = b 1 b 2 b 3 ⋯ b n b = b_1b_2b_3\cdots b_n b=b1​b2​b3​⋯bn​ 一一对应 ;

实数 b = b 1 b 2 b 3 ⋯ b n b = b_1b_2b_3\cdots b_n b=b1​b2​b3​⋯bn​ , 一定等于某个自然数 k \rm k k 对应的 f ( k ) \rm f(k) f(k) ;

现在得到了一个 矛盾 , 设计过程中 b k \rm b_k bk​ 肯定不等于 a k k \rm a_{kk} akk​ , 而 f ( k ) \rm f(k) f(k) 的第 k \rm k k 个数值一定是 a k k \rm a_{kk} akk​ , 因此这两个值 b = b 1 b 2 b 3 ⋯ b n b = b_1b_2b_3\cdots b_n b=b1​b2​b3​⋯bn​ 与 f ( k ) \rm f(k) f(k) 不可能相等 ;

三、对角线方法意义

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

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