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

文章目录

一、对角线方法
二、证明自然数集 N 与实数集 R 不存在一一对应关系
三、对角线方法意义

一、对角线方法

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

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

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

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

证明过程 :

rm N not=R

, 自然数集与实数集不存在一一对应 ;

证明的方法是 反证法 ;

假设 : 自然数集

rm N

与实数集

rm R

之间 , 一定存在一一映射 ;

rm N

可以进行一一枚举出来 ,

rm f(1) , f(2) , cdots , f(n)

rm f(n)

对应的是实数 , 将其限制在

[0, 1]

区间内 ;

[0, 1]

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

现在证明自然数集

rm N

与

[0, 1]

区间内的实数 , 不可能存在一一对应 ;

rm f(n)

是一个

[0, 1]

区间内的实数 , 则可以写成

rm f(1) = 0.a_{11}a_{12}a_{13}a_{14}cdots

rm f(2) = 0.a_{21}a_{22}a_{23}a_{24}cdots

vdots

rm f(n) = 0.a_{n1}a_{n2}a_{n3}a_{n4}cdots a_{nn}

其中

a_{1k}

的值 (

k = 1, 2,3,4, cdots

) 是

0, 1, 2,3,4,5,6,7,8,9

中的一个数字 ;

假设存在一个

是一一映射 , 从自然数集到

[0, 1]

区间内的实数之间的映射 ,

对角线上的值

a_{11} , a_{22} , cdots , a_{nn}

根据对角线上的值设计一个实数

b = b_1b_2b_3cdots b_n

选择

b_1

一定不等于

a_{11}

选择

b_2

一定不等于

a_{22}

选择

b_n

一定不等于

a_{nn}

;

如果自然数集

rm N

与实数集

rm R

是一一对应 , 那么一定可以找到一个自然数

rm k

, 与实数

b = b_1b_2b_3cdots b_n

一一对应 ;

实数

b = b_1b_2b_3cdots b_n

, 一定等于某个自然数

rm k

对应的

rm f(k)

;

现在得到了一个矛盾 , 设计过程中

rm b_k

肯定不等于

rm a_{kk}

, 而

rm f(k)

的第

rm k

个数值一定是

rm a_{kk}

, 因此这两个值

b = b_1b_2b_3cdots b_n

与

rm f(k)

不可能相等 ;

三、对角线方法意义

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

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

设计数学

0 人点赞