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

韩曙亮

发布于 2023-03-28 19:56:03

5080

发布于 2023-03-28 19:56:03

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、对角线方法

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

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_3\cdots b_n

选择

b_1

一定不等于

a_{11}

选择

b_2

一定不等于

a_{22}

选择

b_n

一定不等于

a_{nn}

;

如果自然数集

\rm N

与实数集

\rm R

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

\rm k

, 与实数

b = b_1b_2b_3\cdots b_n

一一对应 ;

实数

b = b_1b_2b_3\cdots 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_3\cdots b_n

与

\rm f(k)

不可能相等 ;

三、对角线方法意义

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

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-12-09，如有侵权请联系 cloudcommunity@tencent.com 删除

设计

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

设计

数学

登录后参与评论

0 条评论

热度