一、前言
对角化方法是由数学家康托于1873年提出的，当时关心的是测量无限集合的规模问题。
假如有两个集合，我们可以比较它们的大小吗？
对于其中一个是有限的集合，答案是trivial的。
但假如对于两个集合都是infinite的，直观上也许会觉得，是无法比较的。
然而，康托尔提出的对角化方法，非常优雅地解决了这个问题。
他注意到，对于两个有限集合，如果其中一个的元素能与另一个集合的元素一一对应（可以理解为双射），则它们规模相同。
而不管这两个集合究竟元素有多少个。
这个思想直接比较两个元素，打破了比较两个集合大小传统的思想框框：通过集合元素个数来比较。
二、一个例子
N是自然数集，E是偶自然数的集合。N={1,2,3,...}，E={2,4,6...}
直观上，E属于N，因为E是N的一个真子集。但根据康托尔的理论，N与E具有相同的规模。
显然对于N中每一个元素，使用f(x)=2*x来映射到E中的每一个元素即可。
三、可数的集合(countable set)
定义1：称一个集合是可数的，如果它的元素个数有限，或它与自然数集N有相同的规模。
一个有无限元素的集合可能是可数的，也可能是不可数的。
再来一个例子。设Q是正有理数集合，即Q={m/n| m,n 属于 N}。
Q看起来似乎比N大得多，但是，Q与N规模相同，即Q是可数的。
证明如下：
思路：通过排列Q的元素，得到一个序列，该序列的元素"下标"与N的自然序列（1,2,3...）一一对应。
构造Q的一个矩阵如下：
1 2 3 4 ...
1 1/1 1/2 1/3 1/4 ...
2 2/1 2/2 2/3 2/4 ...
3 3/1 3/2 3/3 3/4 ...
4 4/1 4/2 4/3 4/4 ...
... ...
从1/1开始，按对角线从西南到东北方向，排列所有的矩阵元素。则得到一个序列 1/1,2/1,1/2,3/1,1/3,4/1,3/2,2/3,1/4 ...
注意每次我们都舍弃掉重复的元素(如1/1, 2/2, 3/3以及 2/1, 4/2 ...)
这样就得到了Q与N的一个一一对应。
四、不可数的集合(uncountable set)
定理1：实数集R是不可数的。
要证明R是不可数的，必须证明不存在到N的一一对应。使用反证法。
假设f是R到N的对应，则必须找到一个x属于R，使得x与N中的任何元素都不能配对。
证明的思路非常巧妙：使用构造方法，来构造出这个不能配对的x。
设f存在且f(1) = 3.14159.... f(2) = 55.5555.... f(3)=....
即R中的3.14159对应到N中的1，55.5555对应到2等等。
假设x是0到1之间的一个数，只关注其小数点后的数字。为使任意f(n)都不存在x=f(n)
只要保证x的第k位小数不等于f(k)的第k位小数即可。
即，对于以上给定的f(1),f(2)，x的小数第一位不等于1，任意地，使其为4；第二位不等于5，任意地，使其为6，则x=0.46....
显然x不等于f(1),f(2).因此，沿着小数点的对角线，即可构造出这样一个x，使得x不与任何f(n)相等。
n f(n)
1 3.14159.... x!=f(1)
2 55.5555... x!=f(2)
3 0.123456... x!=f(3)
4 0.500000.... x!=f(4)
....
令x=0.4641....
1530...
以这种方法下去，就能得到x的所有数字。因此不论n取到多大的值，总能找到这样一个x，使得f(n)中找不到匹配。
注意其中的一个问题：实数的十进制表示法中，有些数是相等的，如 0.999....=1.0000
因此只要在构造过程中总是不选择9与0，即可避免这个问题。
五、对角化方法的应用与意义
对角化方法在计算理论中发挥着重要的作用。
它可以用来证明图灵机的停机问题、图铃不可识别语言等。
即：有些语言是不可判定的（图灵机的停机问题），甚至是图铃不可识别的（图灵机的计算能力）
原因是：根据定理1可以证明，设A={所有语言的集合}，B={所有图灵机的集合}，A是不可数的，但是B却是可数的。
或者说：有不可数的语言（问题），但是却只有可数的图灵机。
六、总结
以上证明、思路是对计算理论导引的归纳与总结。可以说，对角化方法以及对图灵机不可识别、不可判定问题的证明，
是至今为止，我所看到的最优美的数学证明，其意义是哲学性的：
虽然现代计算机异常强大，并且似乎计算能力在不断地增强，但是由于它只是一个有限能力的图灵机模型，
因此无论它如何发展，也不能跨越可计算性的限制。
对角化方法是由数学家康托于1873年提出的，当时关心的是测量无限集合的规模问题。
假如有两个集合，我们可以比较它们的大小吗？
对于其中一个是有限的集合，答案是trivial的。
但假如对于两个集合都是infinite的，直观上也许会觉得，是无法比较的。
然而，康托尔提出的对角化方法，非常优雅地解决了这个问题。
他注意到，对于两个有限集合，如果其中一个的元素能与另一个集合的元素一一对应（可以理解为双射），则它们规模相同。
而不管这两个集合究竟元素有多少个。
这个思想直接比较两个元素，打破了比较两个集合大小传统的思想框框：通过集合元素个数来比较。
二、一个例子
N是自然数集，E是偶自然数的集合。N={1,2,3,...}，E={2,4,6...}
直观上，E属于N，因为E是N的一个真子集。但根据康托尔的理论，N与E具有相同的规模。
显然对于N中每一个元素，使用f(x)=2*x来映射到E中的每一个元素即可。
三、可数的集合(countable set)
定义1：称一个集合是可数的，如果它的元素个数有限，或它与自然数集N有相同的规模。
一个有无限元素的集合可能是可数的，也可能是不可数的。
再来一个例子。设Q是正有理数集合，即Q={m/n| m,n 属于 N}。
Q看起来似乎比N大得多，但是，Q与N规模相同，即Q是可数的。
证明如下：
思路：通过排列Q的元素，得到一个序列，该序列的元素"下标"与N的自然序列（1,2,3...）一一对应。
构造Q的一个矩阵如下：
1 2 3 4 ...
1 1/1 1/2 1/3 1/4 ...
2 2/1 2/2 2/3 2/4 ...
3 3/1 3/2 3/3 3/4 ...
4 4/1 4/2 4/3 4/4 ...
... ...
从1/1开始，按对角线从西南到东北方向，排列所有的矩阵元素。则得到一个序列 1/1,2/1,1/2,3/1,1/3,4/1,3/2,2/3,1/4 ...
注意每次我们都舍弃掉重复的元素(如1/1, 2/2, 3/3以及 2/1, 4/2 ...)
这样就得到了Q与N的一个一一对应。
四、不可数的集合(uncountable set)
定理1：实数集R是不可数的。
要证明R是不可数的，必须证明不存在到N的一一对应。使用反证法。
假设f是R到N的对应，则必须找到一个x属于R，使得x与N中的任何元素都不能配对。
证明的思路非常巧妙：使用构造方法，来构造出这个不能配对的x。
设f存在且f(1) = 3.14159.... f(2) = 55.5555.... f(3)=....
即R中的3.14159对应到N中的1，55.5555对应到2等等。
假设x是0到1之间的一个数，只关注其小数点后的数字。为使任意f(n)都不存在x=f(n)
只要保证x的第k位小数不等于f(k)的第k位小数即可。
即，对于以上给定的f(1),f(2)，x的小数第一位不等于1，任意地，使其为4；第二位不等于5，任意地，使其为6，则x=0.46....
显然x不等于f(1),f(2).因此，沿着小数点的对角线，即可构造出这样一个x，使得x不与任何f(n)相等。
n f(n)
1 3.14159.... x!=f(1)
2 55.5555... x!=f(2)
3 0.123456... x!=f(3)
4 0.500000.... x!=f(4)
....
令x=0.4641....
1530...
以这种方法下去，就能得到x的所有数字。因此不论n取到多大的值，总能找到这样一个x，使得f(n)中找不到匹配。
注意其中的一个问题：实数的十进制表示法中，有些数是相等的，如 0.999....=1.0000
因此只要在构造过程中总是不选择9与0，即可避免这个问题。
五、对角化方法的应用与意义
对角化方法在计算理论中发挥着重要的作用。
它可以用来证明图灵机的停机问题、图铃不可识别语言等。
即：有些语言是不可判定的（图灵机的停机问题），甚至是图铃不可识别的（图灵机的计算能力）
原因是：根据定理1可以证明，设A={所有语言的集合}，B={所有图灵机的集合}，A是不可数的，但是B却是可数的。
或者说：有不可数的语言（问题），但是却只有可数的图灵机。
六、总结
以上证明、思路是对计算理论导引的归纳与总结。可以说，对角化方法以及对图灵机不可识别、不可判定问题的证明，
是至今为止，我所看到的最优美的数学证明，其意义是哲学性的：
虽然现代计算机异常强大，并且似乎计算能力在不断地增强，但是由于它只是一个有限能力的图灵机模型，
因此无论它如何发展，也不能跨越可计算性的限制。
No comments:
Post a Comment