计算理论］可判断性 ( 对角线法 | 证明自然数集 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

中的一个数字 ;

假设存在一个

f

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

[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)

不可能相等 ;

三、对角线方法意义

---

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

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