有关集合大小的比较
Published:
\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert}
写在前面
今天上的离散数学做了一些有意思的证明，这里放一下
集合的大小，我知道
在对付有限集合时，我们很容易就能比较两个集合的大小（只需要数一数各自有多少个元素就行了）。但是当这个问题拓展到无限集合时，我们往往不能简单地给出答案。原因是什么呢？
## 问题1：证明$|\mathbb{N}|$=$|\mathbb{E}|$，其中$\mathbb{E}=\left{2n|n\in\mathbb{N}\right}$
定义映射$f:\mathbb{N}\mapsto\mathbb{E}$为$f(x)=2x$，通过这样一个操作我们可以发现$\forall x\in\mathbb{N},\exist y\in\mathbb{E},f(x)=y. And \ \forall y\in\mathbb{E},\exist x\in\mathbb{N},f(x)=y$
也就是说，我们建立起了一个从自然数到偶数的双射，任意一个偶数都唯一确定对应一个整数，反之亦然。
这时，我们就说这两个集合的大小相等，也称他们是等势的
上面的这个例子比较简单，我们可以接着看下一个例子
问题2：证明$|\mathbb{R}|=|[0,1]|$
这个问题乍一看是反直觉的，但是有了上面问题的铺垫我们可以知道一件事情：一个无限集是可以和它的一个真子集等势的。
先说说我的做法。一个有趣的证明是这样的：
我们把区间$[0,1]$卷起来形成一个半圆，不难得到它的半径$r=\frac{1}{\pi}$
在数轴上取一个点，不妨就取0，过0作一直线垂直于数轴，在这条直线上取一点$A$使得点到数轴的距离恰好为r
以点A为圆心，作半圆与数轴相切，不难得到这个半圆的长度恰好为1
在数轴上任取一点$D(x,0)$，连接$D$、圆心$A$，交半圆于$E$
如上图，可以发现，数轴上的任意一点都唯一对应着半圆上的一个点，而半圆上的任意一点（除去两端）也恰好唯一地对应了数轴上的一点
| 因此我们断言$ | (0,1) | = | \mathbb{R} | $ |
等等，你不是要证明$ [0,1] = \mathbb{R} $吗
| 是的，所以我们接下来要做的是证明$ | [0,1] | = | (0,1) | $ |
如何下手？考虑这样集合$A=\left{\frac{1}{2},\frac{1}{4}…\frac{1}{2^n}…\right}$和$B=\left{0,1,\frac{1}{2},\frac{1}{4}…\frac{1}{2^n}…\right}$
注意！这里的$A$和$B$都是无限集
不难发现，我们将A和B分别一一列举了出来，也就是说他们是可列集合，也叫可数集，这样的两个集合是可以一一对应的，我们只需要把$A$中的第i个元素映射到$B$中的第i个元素，这样就造出了两个集合间的一个双射
| 我们又注意到$[0,1]\backslash B=(0,1)\backslash A$，这一点是非常显然的，那么就有$ | [0,1]\backslash | ||
| B | = | (0,1)\backslash A | $ |
这样我们把A和B分别劈成了两半，使得这两半之间存在双射，所以只需要把两个互不相干的映射并在一起就可以得到$f:(0,1)\mapsto[0,1]$
| 故$ | \mathbb{R} | = | [0,1] | $，并且易得$\forall x,y\in\mathbb{R} 若x\neq | ||||||
| y, | [x,y] | = | (x,y) | = | (x,y] | = | [x,y) | = | \mathbb{R} | $ |
这个证明看起来非常直观，但是关键步骤缺乏严密性。毕竟我们无法严谨地说明把线段弯曲后它和原来仍然是一样的（笑
但是观察这个证明，我们发现这等价于利用函数$f(x)=\tan\left(\pi \left(x-\frac{1}{2}\right)\right)$，将$\mathbb{R}$映射到$(0,1)$，并且由单调性可知这样的映射是双射，所以上述证明可以用更加严谨的方式进行说明，是没有问题的。
问题3：证明$|\mathbb{R}^2|=|\mathbb{R}|$
| 这个平方指集合和他自身的笛卡尔积，即设$A$为一非空集合，则$A^2=\left{(x,y) | x\in A,y\in A\right}$ |
| 由前一题可知，$ | \mathbb R | = | [0,1) | $ |
| 于是我们只需要证明$ | [0,1) | = | [0,1)^2 | $ |
观察可知，$[0,1)$中的实数都是整数部分为0的小数，我们可以构造这样一个映射
\begin{aligned} f(a,b)=\sum_{i=1}^{+\infin}\left(\frac{[a\times 10^{2i-1}]}{10^{2i-1} }+\frac{[b\times 10^{2i}]}{10^{2i} }\right) \end{aligned}
其中$[x]$表示取$x$的整数部分，不难发现这样就是在把$a、b$的每一位交替插在一起，形成一个新的实数
这个构造过程是可逆的，并且是一个双射
这个结论能说明什么呢？我们在二维平面上的点和数轴上一样多！很奇妙
| 并且这个结论是可以推广的。也就是$\forall n\in \mathbb{N}, | {\mathbb R}^n | = | \mathbb R | $ |
| 而$ | {\mathbb R}^{+\infin} | = | \mathbb |
| R | $也是可以得出的，我们只需要按行列出实数的每一位，然后沿着反对角线取数字构造就可以了 |
问题4：证明$|2^{\mathbb{N} }|=|\mathbb{R}|$
这个幂次的含义是自然数的幂集，也就是自然数所有子集形成的集合。
| 由上一问可知，我们只需要证明$ | 2^{\mathbb{N} } | = | [0,1) | $ |
而对于任意一个$\mathbb N$的子集$S$，我们都可以用一个无限长度的二进制串来唯一表示，其中若第i位为0，代表$i\not\in S$，否则$i\in S$
于是立刻就可以想到，我们只需要把$[0,1)$中的实数化成二进制小数，就可以获得无线多个互不相同的任意长的二进制串（取小数点后的部分）
例如，一个实数$a=0.1101100000…$，唯一地表达了集合$S=\left{1,2,4,5\right}$
但是，这样的表示是完美的吗？
并不！考虑一个无限循环小数$a=0.011000\dot{1}$，我们可以发现它其实等价于有限小数$b=0.011001$，也就是说，我们这样存在一个实数映射到了两个不同的$\mathbb N$的子集。当然这个很好解决，我们只需要规定若一个数能表示成有限小数，那么我们绝不考虑它的无限小数表示法。但是，我们无法通过这样的映射找到一个逆映射，使得$\mathbb N$中的每一个子集都能在$[0,1)$中找到唯一对应的实数（例如，我们把从9开始往后的所有正整数都选出来，组成的集合就不能映射到一个实数上，因为这是一个无限小数，而前面我们规定了不取这种写法）
| 怎么办呢？这里有一个比较奇妙的做法。考虑这样一个事实，我们在第一问证明了$ | \mathbb N | = | \mathbb | ||
| E | $，因此我们似乎只需要证明$ | \mathbb E | = | 2^{\mathbb N} | $就可以了！ |
观察$\mathbb E$的性质，我们可以发现对它做上述构造后，是不存在与另一个有限小数相等的无限循环小数的！为什么呢？因为这里都是偶数，因此最多出现$0.00010101010101…$这样的循环小数
| 因此这个构造就成立了！我们就成功地证明了$ | 2^{\mathbb N} | = | 2^{\mathbb E} | = | [0,1) | = | \mathbb R | $ |
小小的总结
离散数学这门课听起来还是很有意思的，但是真正要做题的时候就很懵逼了，算是很需要idea的学科
经过了几次课大概可以感受到离散数学主要研究的问题无非就是围绕着集合开展，并且多和无限扯上关系。因为和无限扯上了关系，我们初等数学中的一些结论就变得不那么显然和可拓展了，原本的直觉也会失效。
希望能活过大一的离散数学（一），然后看看能不能活过离散（二）吧(希望)