一一对应法则存在性与构造问题

· · 个人记录

（为了方便，本文中的整数集、实数集等不采用粗体。）

（全文中，1.1.3 和 1.2.4 是从课外读物看到的，其余均为 yummy 自行思考的结果。）

全文共 2400+ 字，阅读时间取决于你的数学基础和阅读习惯。建议根据目录跳读。

1. 经典的对应法则

1.1 有理数集的子集

1.1.1 奇数和偶数

设置这一部分内容，主要是确认一下一一对应法则的定义。

对于一个奇数 x，其对应的偶数为 x+1。显然每个偶数只对应一个奇数。

事实上对应法则不止一种，例如奇数 x 对应 1-x 也可以。

请注意奇数 x 对应偶数 2x 并不是一种一一对应法则，因为形如 4,8,\ldots 的偶数没有奇数与其对应。

之后的题目大多只会提供一种对应方法。

1.1.2 正整数和整数

对于一个正数 x，f(x)=2x。对于一个负数 x，f(x)=-2x+1。

1.1.3 正整数正整数对和正整数

将 (p,q) 放在矩阵的第 p 行第 q 列。我们以 Z 字形给上表的每一项编号。第一项是 (1,1)，然后是 (1,2)，(2,1)，(3,1)，(2,2)，…，显然所有正整数对都可以如此对应。

如果你之前做过某年普及组题你可能知道，这叫 Cantor 表。

同样地对于负有理数也可以和正整数一一对应。使用类似 1.1.2 的方法将两列数并在一起。

1.2 实数集的子集

1.2.1 正实数和区间 (0,1)

对于正实数 x，f(x)=\dfrac{1}{x+1}。

1.2.2 实数和区间 (0,1)

先将负实数对应到 (-1,0) 上，正实数对应到 (0,1) 上，0 对应 0，然后将 (-1,1) 对应到 (0,1) 上。

我们使用类似的方法可以将任意两个区间对应。

对于本题还有一种更省事的办法是使用指数函数——将实数对应到正实数上然后使用 1.2.1。

1.2.3 整数实数对和实数

对于每个整数实数对 (z,r)，将 r 对应到 [0,1) 上，然后加上 z。（(0,1) 和 [0,1) 的转换方法可以参考 2.1）。

1.2.4 实数实数对和实数

首先将所有实数对应到 (0,1) 上。然后将实数写成二进制，然后将两个实数按位组合成一个四进制数，还原成实数。

举个将 2 进制转成 4 进制的例子：

(0.110000...)_2
(0.101010...)_2
--------结合--------
(00.11 10 01 00 01 00...)_2
(0 .3  2  1  0  1  0 ...)_4

2. 开闭区间转化及拓展

2.1 非负实数和正实数

对于非负实数 x，定义 f(x)=\begin{cases}x+1 & x\in Z\\ x & x\notin Z\end{cases}。

虽然很简单，但是似乎很少有人想到。

2.2 应用：奇函数和偶函数

对于偶函数 f，定义 odd(f(x))=\begin{cases}\begin{cases}f(x) & x>0\\0 & x=0 \\ -f(x) & x<0\end{cases},f(0)=\operatorname{undefined}\\\begin{cases}f(x) & x>0,x\notin Z\\f(x-1) & x>0,x\in Z\\-f(x) & x<0,x\notin Z\\-f(x+1) & x<0,x\in Z\end{cases},\operatorname{otherwise}\end{cases}。

2.3 无理数和实数

2.1 启发我们，对于一个数集，如果要插入一个数字，我们可以只选择其中一个可数集，只平移这一个可数集，其余不动。

如果要在不可数集里面插入可数集，我们同样可以找一列可数集，分别平移。也就是：

对于实数 x，f(x)=\begin{cases}x+\pi&\exist(q\in Q,n\in N),x=q+n\pi\\x&\forall(q\in Q,n\in N),x\neq q+n\pi\end{cases}

2.4 正整数的全排列和正整数的映射

对于每一个因变量只对应一个自变量的定义域和值域都是 [1,n]\cap Z 的函数 f(x)（可以简单理解成全体正整数的全排列），定义 g(x)=\bigg|\big\{a\in Z|a\le x\and f(a)\le f(x)\big\}\bigg|。

给 f(x) 求 g(x) 的过程被称为康托展开（能不能等问题不大），给 g(x) 求 f(x) 的过程被称为逆康托展开。

如果要了解更多关于康托展开的知识，可以参考我的另一篇博客。（主要讲 C++ 怎么实现。）

3. 对角论证法

3.1 实数和正整数

很多书本都会提到如何证明实数和正整数之间无法一一对应，不过我们这里再复习一下。

假设我们已经将实数和正整数一一对应，那么我们就可以将 [0,1) 内的实数和正整数一一对应。

我们将这些实数写成二进制，令 d(x,y) 为正整数 x 对应的实数的第 y 位，则我们可以构造一个新实数 n，其第 i 位是 1-d(i,i).

显然这个实数 n 和原来的每一个实数都有至少一位不一样，和“所有实数都已经和正实数一一对应”不符。因此实数和正整数无法一一对应。

如果你有注意，会发现康托这位数学家出现了很多次（本节的对角论证法也是康托的）。

3.2 函数和实数、实数集和实数

似乎到这里已经没多少课外读物讲了。实际上还是对角论证法。

假设实数集和实数已经一一对应，那么存在值域为 \{0,1\} 的函数 d(f,x) 为实数 f 对应的实数集是否包含 x。

如果你时刻跟进那么你可能猜到要干啥了——新建一个集合 S=\{x|d(x,x)=0\}，那么这个实数集和原来的每一个实数集都有至少一个实数的区别。所以，实数集与实数无法一一对应。

证明函数和实数之间的一一对应不存在本质完全相同。

3.3 函数集合与函数，以及之后

如果要证明函数集合和函数无法一一对应，只需要画两根“垂直”的“超直线” f 和 x，f 轴表示函数映射对应的函数，x 轴表示函数对应的函数映射，那么就可以构成一个“超点集”，取对角线的补集即可。

因此，对于任意集合，其子集和其元素无法一一对应。

4. 总结一下

4.1 整数集、实数集、函数集、...

众所周知，函数是实数到实数的映射。而实数也可以和整数到 \{0,1\} 的映射一一对应，因此定义域为实数的 f(x)=y:Z\to \{0,1\} 可以和 f(z,x)\in \{0,1\}(z\in Z) 一一对应。使用 1.2.3 可知其与 f(x)\in \{0,1\} 一一对应，也就是函数与实数集一一对应。

使用类似的方法，我们知道实数和整数集一一对应，也就意味着实数与整数到整数的映射一一对应。

玩点生草的东西：

我们班有同学说 “数学里面能遇到的最大的集合就是全体函数”,我们根据 3.3 知道，全体函数集合（或全体函数映射）的势大于全体函数，而且我们可以继续扩大这个集合。

4.2 谁到谁的映射可以一一对应？

定义一种叫“等级”的东西，定义 lev(S) 为 S 的等级。规定 lev(Z)=0。

接下来，规定 lev(A\to B)=\max(lev(A)+1,lev(B))，那么 lev(R)=lev(Z\to R)=1，lev(R\to R)=lev(R\to Z)=2。

相同等级的集合都可以一一对应。

（听我同学说《从 1 到无穷大》上说的阿列夫 k 就是这里定义的等级 k，所以我可能又造了一遍轮子）

4.3 未解决的问题

放心，我会 BFS。这些问题很有可能不只是我现在无法自己独立完成，可能给答案我的水平也看不懂。