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

（为了方便，本文中的整数集、实数集等不采用粗体。） （全文中，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)$ 的过程被称为逆康托展开。 如果要了解更多关于康托展开的知识，可以参考我的[另一篇博客](https://www.luogu.com.cn/blog/yummy-loves-114514/huoxingren)。（主要讲 C++ 怎么实现。） # 3. 对角论证法 ## 3.1 实数和正整数 很多书本都会提到如何证明实数和正整数之间无法一一对应，不过我们这里再复习一下。 假设我们已经将实数和正整数一一对应，那么我们就可以将 $[0,1)$ 内的实数和正整数一一对应。 我们将这些实数写成二进制，令 $d(x,y)$ 为正整数 $x$ 对应的实数的第 $y$ 位，则我们可以构造一个新实数 $n$，其第 $i$ 位是 $1-d(i,i)$. 显然这个实数 $n$ 和原来的每一个实数都有至少一位不一样，和“所有实数都已经和正实数一一对应”不符。因此实数和正整数无法一一对应。 如果你有注意，会发现[康托](https://baike.baidu.com/item/%E6%A0%BC%E5%A5%A5%E5%B0%94%E6%A0%BC%C2%B7%E5%BA%B7%E6%89%98%E5%B0%94/4614747)这位数学家出现了很多次（本节的对角论证法也是康托的）。 ## 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$。 相同等级的集合都可以一一对应。 - $A\to B$ 在 $0<lev(B)\le lev(A)+1$ 时可以将 $B$ 拆成 $B'\to C(lev(B)>lev(C)$，然后 $(A,B')\to C$ 可以转化为 $A\to C$。（这里 $B'$ 表示比 $B$ 低一级的集合）。 - $A\to B$ 在 $lev(B)>lev(A)+1$ 时，可以转化成 $A'\to (Z,B)$，和 $A'\to B$ 一一对应。 （听我同学说《从 1 到无穷大》上说的阿列夫 $k$ 就是这里定义的等级 $k$，所以我可能又造了一遍轮子） ## 4.3 未解决的问题 放心，我会 BFS。这些问题很有可能不只是我现在无法自己独立完成，可能给答案我的水平也看不懂。 - 如何说明存在/不存在集合 $S$，使不存在 $Z\to S$ 的满射，且不存在 $S\to R$ 的满射？ - 有反函数的函数和全体函数如何一一对应？没有反函数的函数和全体函数如何一一对应？