前情提要,如果两个集合之间存在双射,则称二者等势,记作 。基于此,我们可以对一些熟知的集合玩玩。

开集与闭集

对于两个任意的开集或者两个闭集,我们可以简单地通过乘系数放缩区间长度,再加上偏置对齐二者,所以自然可以通过一个一次函数作为双射,说明二者等势。

要推演到无穷,也许需要稍微转换形式,从初等函数中挑选, 是一个自然的选择,选取 ,则 作为双射链接其与无穷。所以任意一个闭区间都与 等势。

那么对于开区间,感性上去掉端点不影响等势,如何技术上实现呢?考虑易于说明的 与 ,那么我们要做的就是扣掉端点。在无穷数列,我们知道加入几个数不会影响太多,对于一个区间我们没有具体抓手,所以仍然退回数列。我们取 ,具体把 指向 , 指向 ,然后 指向 , 指向 ,其余的数在函数作用下保持不变。这样一个关系自然是双射,也就说明了二者等势。当然,也可以选取 或者别的什么数列。

综上呢,一个非空的区间都与 等势。

N R

自然数集不与实数集等势。

感觉上自然成立,如何利用定义去证明呢。要否定,也只好利用反证法。假设二者等势,那么也就存在二者之间的双射。那么,也就是说 的所有实数都可以被编号。方便起见,只考虑 。

我们列出这些实数, ,那么我们希望找出一个不在这其中的数,就是和每一个 都不同。让 其中 取决于 的第 位,如果 则 否则 。这样就做到和每一个列出的实数都不同,从而得到了矛盾。

A P(A)

一个集合不与其幂集等势。从而不存在最“大”的集合。

这不那么显然,证明则一样,利用反证法,假设二者等势,那么能否找到反例? 等势则存在双射,则 ,那么能否找到一个 。

我们没法列出所有元素,但是可以任取一个 ,试图让 。这只要一个元素不同即可,让 时 ,反之亦然即可。也就是 满足这件事,就得到了矛盾。

上方的两个证明有某种共性,我们通过逐位否定构造一个反例,不需要得知任何信息,从而简短优雅。 这也许有某种延续

停机问题

如果这里的元素是若干程序 ,我们问是否存在一个判定器 能够判定 接受输入 是否停机。

依旧唱反调,考虑一个神秘程序 ,输出 的反面。那么 也就是 的反面,那么就使得 怎么判断都不对了。

为什么构造如此的 呢,笔者自行如下推演:最自然的动机是找到一个 作为 的反面,但是这样 的定义出现了自指,所以退而求其次,考虑 给出 的反面,再套进去就得到 作为 的否反面,但是这样参数上不好对齐,所以为了让 接受单参数,直接让 对应 反面,这样就写的非常顺了。

Russell 悖论

类似上方那种自己给出自己的否定,实际上有更直接的构造: 那么 就既不能属于自己,也不能不属于,否则都会带来矛盾。

据GPT指示,这么下去可以顺到哥德尔不完备定理,但是似乎需要的前置有点多,暂且停在这好了。