几个有关集合势的“简单”证明
By 苏剑林 | 2014-10-01 | 78459位读者 |我们这学期开设《实变函数》的课程,实变函数的第一章是集合。关于无穷集合的势,有很多异于直觉的结论。这些结论的证明技巧,正是集合论的核心方法。然而,我发现虽然很多结论跟我们的直觉相违背,但是仔细回想,它又没我们想象中那样“离谱”。而我们目前使用的教科书《实变函数论与泛函分析》(曹广福),却没有使用看来简单的证明,反而用一些相对复杂的定理,给人故弄玄虚的感觉。
一、全体实数不能跟全体正整数一一对应
这是集合论中的基本结论之一。证明很简单,如果全体实数可以跟全体正整数一一对应,那么$(0,1)$上的实数就可以跟全体正整数一一对应,把$(0,1)$上的全体实数表示为没有0做循环节的无限小数(比如0.1表示为0.0999...),那么设一种对应为:
$$\begin{aligned}&a_1=0.a_{11} a_{12} a_{13} a_{14}\dots\\
&a_2=0.a_{21} a_{22} a_{23} a_{24}\dots\\
&a_3=0.a_{31} a_{32} a_{33} a_{34}\dots\\
&\dots\dots
\end{aligned}$$
其中$a_{ij}$为0,1,2,...,9中的任意一个,表示$a_{i}$的第$j$位小数。现在构造一个数字
$$b=0.b_1 b_2 b_3 b_4\dots$$
其中$b_i=1$,如果$a_{ii}\neq 1$;$b_{i}=0$,如果$a_{ii} =1$。由$b$的构造方式可知,$b$不在$\{a_n\}$之中,这与假设矛盾。
以上的证明技巧被称为“对角线技巧”,是一种极其初等易懂的技巧,我记得我在初中的时候就能够看懂这个证明(虽然那时候还没有集合的明确概念)。可不知道为什么,我们的教科书却使用了区间套定理这种高大上的证明,难道是因为学过难懂的东西,就要使用难懂的证明?只有这样才显得我们学的数学“很高等”?我就不信我初中就可以看懂区间套定理了。
二、可数个连续统集合的并仍然是连续统
连续统集合就是势等于实数集的势的集合,实数集的势一般记为$C$。这个命题的证明非常容易,甚至就是显然成立的,却不知道为什么我们的教科书用上了一大堆让人讨厌的符号。
我们知道$[0,1)$上的实数集的势为$C$,$[1,2)$上的实数集的势为$C$,$[2,3)$上的实数集的势为$C$,...,这样一来
$$[0,1)\cup [1,2)\cup[2,3)\cup\dots=[0,\infty)$$
就是全体非负实数的集合,难道它的势不是$C$吗?
三、可数个可数集的并仍然可数
这个跟上面的证明是类似的。我们知道$[0,1)$上的有理数集可数,$[1,2)$上的有理数集可数,$[2,3)$上的有理数集可数,...,这样一来
$$[0,1)\cup [1,2)\cup[2,3)\cup\dots=[0,\infty)$$
就是全体非负有理数的集合,自然是可数的。
四、$\mathbb{R}^{\infty}$仍然是连续统
这里的$\infty$表示一个可数无穷大。这表明实数序列的集合$\{x_1 x_2 x_3 \dots\}$仍然跟实数本身一一对应,其中$x_i$是$(0,1)$的任意实数。这里的证明不一定是简单的,但是值得一提。
证明并不是十分困难,只要构造
$$\{x_1 x_2 x_3 \dots\}\mapsto (0,1)$$
的一个单射即可。我们只需要把元素$x_1 x_2 x_3\dots$映射到$y\in (0,1)$,$y$的构造如下(记$S_i (x)$为$x$的第$i$位小数):
$$S_{(2^i+2^{i+1} j)} (y)=S_{j+1} (x_{i+1}),\quad i,j=0,1,2,\dots$$
看起来很玄,不知道怎么构造出来的?只需要写写前面几项,读者必然能够恍然大悟了~~这也是一种相当有用的集合证明的技巧。
转载到请包括本文地址:https://kexue.fm/archives/2964
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Oct. 01, 2014). 《几个有关集合势的“简单”证明 》[Blog post]. Retrieved from https://kexue.fm/archives/2964
@online{kexuefm-2964,
title={几个有关集合势的“简单”证明},
author={苏剑林},
year={2014},
month={Oct},
url={\url{https://kexue.fm/archives/2964}},
}
October 2nd, 2014
那个"可数个连续统集合的并仍然是连续统"那样证明的话不太严格吧= =
我觉得是可以的。因为只要告诉我各$x_i$的每一位小数是多少,我就可以明确告诉你$y$的每一位是多少。这正是可数个的特点。这其实跟$\mathbb{A}^{\infty}$是连续统的证明是一样的,其中$\mathbb{A}$是一个有限集,$\infty$是可数无穷大。
你可能会想,如果$x_1=\sqrt{2}-1$,那怎么知道每一位小数是多少呢?如果是这方面的困惑的话,应当这样理解,$\sqrt{2}-1$是一个明确的数字,自然每一位都确定了,只是我们不一定能够(很快地)写出来而已,但是构造却是可以实现的。
正如我们说$\sqrt{2}$是一个有理数列的极限,我们事实上也无法只在有理数的范围内写出这个数列是什么样子的。
哦,我不是这个意思.其实我想说的是二和三这两条中作为记忆的方法比较合适,但是证明并不严格。例如,点集是有限集,但是无限个点集的并也可以构成可列集、连续统。。。我觉得还是应该用映射证明一下更好。
PS:实数集的势一般记为C吗?不是应该为\aleph_{1}吗?
我觉得修改为严格证明也是很容易的,添加几句话即可。你举的例子不恰当,“点集是有限集,但是无限个点集的并也可以构成可列集、连续统”,无限跟可数是有区别的,这里已经说明了是可数个并了。而正整数集合的势就正好是可数的,或者说,“可数”就是定义为正整数集的势,这样一来,$[0,1)\cup [1,2)\cup[2,3)\cup\dots$就是很恰当的“可数个集合的并”。
December 9th, 2014
可数个连续统集合的并仍然是连续统,你这样的证明只能说是特例,没有证明这样的情况不成立:某些可数个连续统集合的并的势可能不等于C,某些等于C
书上的证明的意义应该是为了说明对集合的势的运算具有这样的确定性质,当我们知道了这样的确定性之后,就可以像你这样记忆了
这是同构思想。要证明可数个互不相交的连续统集合之并仍然是连续统,只需要将这些连续统集合分别一一对应与$[0,1),[1,2),[2,3)\dots$,其中单个的连续统集合跟区间是等势的,从而后者的并的势等于前面可数个连续统集合的并的势,从而是连续统。
或者说,上面的虽是一个特例,但是一切非特例本就等价于这个特例。我觉得,这样才是最直观,最舒服的证明,而且并不失严谨性。
不错!不过最好在文章中说一声,我乍一看,也觉得太失严谨性啦
December 10th, 2014
嗯,那汤松那本实变函数论里就是这么证明的
以后还是很欢迎来批评指出毛病,谢谢^_^
July 4th, 2015
以前初一时在别的网页看过第一个.没看懂..现在还是不懂 谁能解释一下啊
August 30th, 2021
[...]给出参考:几个有关集合势的“简单”证明 – 科学空间|Scientific Spaces[...]
September 15th, 2021
[...]给出参考:几个有关集合势的“简单”证明 - 科学空间|Scientific Spa[...]
February 6th, 2023
苏神你好,我这里有一个肯定错误的证明,仿照上面的康托尔对角线方法,证明自然数和自然数的势不相等,帮我看看哪里错了,困惑我好久了。
首先,对于任何一个自然数,我们可以倒着写,就是写成个十百千万……这样的形式,低位先写,后写高位。例如,数1可以写成1000000000……,91写成1900000……,反正没有的数位用0补齐。这样我们可以得到一张数表:
$$
a_1 = 124320000000000000…… \\
a_2 = 100000000000000000…… \\
a_3 = 134234128889900000…… \\
\vdots
$$
然后用康托尔对角线法则,我们可以规定,对第$i$个数的第$i$位做$(k+1)\ mod\ 10$的操作,那么新添加的数一定不在数表里面。于是就证明了自然数的势和自然数的势不相等。请问这个证明错误在哪里呢?
为了表述更加清楚,不妨改为0.x的小数点形式:
$$a_1 = 0.124320000000000000…… \\
a_2 = 0.100000000000000000…… \\
a_3 = 0.134234128889900000…… \\
\vdots$$
那么你的证明错误在哪呢?很简单,自然数经过你这样表示后,必然是一个有限小数(或者说循环节为0或9,这里存在一个数有两种表示的问题,细节上需要处理一下,不过暂时忽略吧);而可以证明,你用对角线法则构造出来的新数,必然是一个无限小数(可能循环,但是循环节不为0或者9),于是你构造出来的新数,无法对应回来一个自然数,所以它不在这个列表中是正常的,不存在矛盾。
赞!