正整数和正整数中的偶数哪个多（如何证明）？ 第1页

证明太显然了，我就不讲了。我来解释一下题主口中的直觉可能是个什么东西。

首先是数学归纳法的误用。

不说归纳法，先给个不失一般性的直觉。假设我们限定整数的范围为 -32768 ~ 32767，正整数多^[1]。

根据数学归纳法，我们可以证明结论扩展到全体自然数上结论也成立。这在某种意义上来说是对的，而在另一种意义上来说则是错的，主要取决于我们如何理解什么叫做一个结论「被扩展到全体自然数上」。

归纳法能得到的结论是：对于任意一个至少包含两个元素^[2]的有穷主义自然数模型^[3]，其中自然数的数量都比偶数的数量多^[4]。

但是题主直觉出的结论却是：对于自然数本身这个无穷大的模型，其中自然数的数量都比偶数的数量多。

类似的错误如下，你可以用数学归纳法证明 对于任意的 n 都能得到一个有穷的，拥有某种特别性质的数。但是你不能用归纳法证明这种性质同样地适用于 ——至少这不是一个收敛的求和，因此一般来说我们认为它起码不是有穷的，因此也不是一个一般意义上的数；即便你强行算出来一个和，这个数也很有可能不具有之前那些有穷情况下的性质。

排除数学归纳法的错误应用并不解决问题，毕竟某个证明是错的不能说明证明的结论是错的。

关于『更多』的直觉还有可能依赖于子集关系：给定两个集合，A 中的元素个数不少于 B 中的元素，如果 A 包含了 B。问题在于子集关系是一个有缺陷的关系：它非常地不完全。

不仅仅绝大多数无穷集合之间无法在此关系下比较——比如说我们没法比较偶数和奇数的大小，因为两者相互不包含，有穷集也不行： ， ，甚至，我们无法比较一个有穷集和一个无穷集的大小，比如说只包含 3 的单点集和偶数集。

所以我们要扩充这里的比较关系，把这一个 partial order 扩展成一个 linear order。但是扩充本身指的是成立的等式/关系更多了，而不保证元素会更多，反而，这往往会导致原来不同的元素被黏在一起。扩充完的关系不再像原来的关系那样那么有辨识度，它分辨不出来某些具体的集合，而只能分辨出来它们所拥有的某种特征，比如说，尺寸（size）。

我们可以考虑下面这样一个代数中的简单例子。

我们知道，monoid 的定义是一个集合加上一个对所有二元组都有定义的二元运算，不妨叫它乘法；monoid 对乘法封闭，乘法有基本的结合律，并且有一个乘法的单位元，一个对象无论左乘还是右乘单位元得到的结果都不变。而 group 同时还要求逆元总是存在。

当我们把 这个monoid （按照 ee=e; ae=ea=aa=a 定义乘法）变成一个 group 的时候，我们会发现 a 不见了，它和 e 重合在了一起（通过在 aa=a 两侧乘以 a 的逆元，得到 a=e）。通过加入额外的条件（等式），使得原来的等式能够推出一些新的等同关系，进而导致成立的等式似乎更多了，但是与此同时元素更少了，因此实际上成立的等式某种意义上来说更少了：因为现在只剩下 ee=e 了。

再考虑一个 relational structure，论域有三元素，关系如下： aRb，aRc，bRa，bRc，cRc。

关系矩阵形如 。

我们试图将其变成一个 partial order，首先，我们要求 R 还要具有传递性，那么根据 aRb 和 bRa 能得到 aRa，类似地，也有 bRb。

新的关系矩阵则长成了 。

经过检验发现这样就满足了传递性，所以不需要再添加新的元素了。

在构建偏序的时候，我们还需要满足反对称性，即 。显然这里不满足反对称性。

注意到此时，R 在 上变成了一个等价关系，事实上 R 关系将这个三元集分成了两个等价类，按照 ，以及 ，我们知道 a 和 b 落在同一个等价类中，而 c 落在另一个等价类中。

通过上述增加了传递性的关系再，再模掉一个等价关系，即，认为满足等价关系的 实际上是相同的元素，或者严格地说，是 ，于是我们得到了二元集 上的偏序 ：

这个从原来矩阵偏序化得到的新矩阵要更小一些，因为 a 和 b 被黏在一起了。

根据上面这种直觉，我们容易在其诱导下给出一个想当然的回答：

如果我们要将前述的子集关系诱导出的 partial order 变成一个 linear order，并且在有穷的情况下保持我们关于大小的直觉，那么，我们最终一定会将所有元素都挤在同一个无穷大上。

但是这个直觉的解释力有限。事实上我们可以给出下述分层（每层看作一个等价类）：

• 含有 0 个元素的集合：
• 含有 1 个元素的集合：
• ……
• 那些本身无穷大，并且补集也无穷大的集合，比如说所有正偶数构成的集合， 。
• ……
• 比正整数全体少一个元素的集合：
• 正整数全体：

先不管中间那一坨东西要怎么办，就当它们都是一样大的。显然这是一个 linear order。在此 linear order 下，正偶数集依旧严格地“小于”正整数集。

也就是说，题主口中的直觉依旧没有被破除。

上面留了一个坑：中间那些东西到底能不能分层？

这里我们似乎可以证明一件事情：我们只能让那些本身无穷大，并且补集也无穷大的集合都处在同一个等价类里面，而不能细分。为什么我们想要给中间这坨东西分层？部分原因是这一坨很大——随机选取一个自然数的子集，「这个子集是有穷的，或者，这个子集相对于自然数全体的补集是有穷的」发生的概率为 0。几乎所有自然数子集都落在中间这一坨的情况下。

根据『直观』，我们似乎可以这样分层：

比如说对于所有偶数构成的集合 ，我们可以有意义地谈论那些表面上比它大 1 的集合： 以及表面上比它小 1 的集合 这里谈论的集合和它们的补集都是无穷集，所以看上去我们似乎能很好地给这些无穷集再排个序。

但是我们没有办法用这种方式谈论另一些集合，比如说全体正奇数构成的集合 ，是否和 一样大。但是既然我们要谈论 E 和 O 的大小关系，我们就必须要引入其他的比较方式。这个地方似乎只有一一对应能够充当这一角色。

通过简单构造法，我们知道我们可以构造一个从 E 到 O 的一一对应，然而我们也可以构造一个从 E 到 的一一对应。对于这两个不相交的集合，我们没有办法诉诸任何直觉。我们只知道 。同样地，虽然表面上我们能比较 和 E，但是两者都能建立一个和 O 的一一对应。因此我们的选项只剩下认为它们都一样大，毕竟一开始要将 subset 这个 partial order 变成 linear order 的时候就注定了我们不会允许有两两不可比较大小的集合这种情况存在。建立一一对应的本质是建立一个等价关系。

这个问题暂时不会蔓延到全体正整数上去，因为我们在谈论上述层级的时候考虑的不仅仅是一个集合本身的大小，还考虑了它补集的大小。无论是偶数还是奇数，都不是 cofinite set。

但是稍作思考，我们会发现对于正整数全体的保护操作是无效的，核心问题在于这里：上面的序列要求我们给定一个集合作为全体，无论是正整数也好，自然数也罢。但是最大的可列集这个东西似乎并不存在，举个例子，我们把自然数复制一份添加到原来的自然数集中，得到集合 ，在 作为全体的时候， 和 都落在下述序列的中间那一层：

• 含有 0 个元素的集合：
• 含有 1 个元素的集合：
• ……
• 那些本身无穷大，并且补集也无穷大的集合，比如说： 。
• ……
• 比全体少一个元素的集合：
• 全体：

在此分类下， ，而不再是 。（根据前面的解释，本身无穷大，并且补集也无穷大的集合这一坨东西里面没办法再有结构了要不然就是保持偏序结构，要不然就看成都相等）

所以就无解了。

而且我们知道 也不是最大的，我们可以把它复制一份，得到一个更大的集合，然后在新的层级中，它也落在中间。

也就是说，如果我们最后想要一个普遍适用的 linear order，至少在可列无穷大这一层里面，我们没有办法再分层。这个地方有没有循环论证呢？我觉得没有，因为除了引入「至少存在一个一一对应」这种判断方式之外，我们没有办法给出一个无穷集合和另一个无穷集合是否一样大的标准。

其实前面还留了一点是有点意思的东西。事实上我们可以发现，在之前的例子中，如果我们选择 E 作为一个基点，我们可以表面上很正常地谈论很多东西：不仅仅是看似有意义地谈论那些表面上比它大 1 的集合： 以及表面上比它小 1 的集合 我们还能说 和 E 一样大，等等等等。也就是说，我们可以从 E 出发构建一个和整数一样结构的层级，每个层级都有自然数那么多个元素。

这个构建看上去涵盖了很多东西，但是实际上它涵盖的部分很少，比如说，无论我们怎么构建，O 都不会落在任何一个层级之中，因为这个层级里面每个元素都是对于 E 添加有穷个元素然后减少有穷个元素之后得到的。而如果要硬给一个理由的话，这从某种意义上来说也展示了自然数的子集个数远大于可列是个什么感觉。即便，我们每一层里面都有可列无穷多个元素，并且我们有可列无穷多层，但是依旧有很多集合在这个构建下是根本摸不到的，只要它在 O 中取了无穷多个元素，或者，它比 E 少了无穷多个元素（比如说所有 4 的倍数构成的集合就比 E 少了无穷多个元素，并且是其子集，并且同时不是 finite 也不是 cofinite）。

作为结论，有两部分。第一，在给定论域的情况下，我们能良好地定义出一种层级关系，使得在这种层级关系中偶数集在序列中拥有某种性质，能和自然数集/正整数集区别开来。

第二，一般来说，这种依赖于补集的操作是没法做的，原因有三层：首先，因为不存在所有集合的集合，因此绝对补不是一个良定义的操作。其次，就算存在所有集合的集合，这里的绝对补也上升到了至少不可列的无穷大上，因此在这个视角上看，自然数和偶数还是只能一样多。再者，就算我们限定在可列的范围内，我们可以反复往一个可列的论域内加入可列多个元素，使得之前的论域变成一个夹在中间无法比较的情况。

当然，除了上述分层之外，如果不追求对称性，我们还可以用别的方式来给出大小依据。两个例子：

例一：权重求和

自然数 n 的权重是 。自然数集合的大小由其元素权重的和决定。只包含 1 的集合和只包含 2 的集合虽然都只有一个元素，但是在这种算法下大小不一样。

例二：超滤测度

给一个自然数上的超滤 ，也即： ； ； ； ； 。

然后 。

显然，在选取超滤恰当的情况下，偶数的测度可以是 0，而全集的测度总是 1。这个地方的对称性我不能确定地说被破坏了，毕竟所有有穷集是一样大的。这里能依赖的直觉只能说“偶数和奇数不一样大”^[5]或者类似的例子，但是这到底有没有乞题呢？

无论如何，这种例子都比前面给出的分层好不到哪里去，因为在用有穷数值度量大小的时候，考虑将自然数做可列无穷多个副本出来依然是可列的，但是如果我们仅仅是简单相加，那么我们就会重新面临无穷的问题，而如果我们不这样做，就会面临重新定义度量规则的问题（也即，前面所说的总是依赖于一个给定的全集）。

参考

1. ^ 其中正整数一共有 32767 个，而正偶数只有 16383 个
2. ^ 0 的时候论域为空，两者相等；1 的时候论域只包含 0，两者相等。2 论域中包含一个奇数，开始有更多一说。
3. ^ 这里粗糙地 理解为一个形如 {0, …, n} 的集合，其中 n 是一个自然数。也即，这里的 n 是量化的对象。
4. ^ 施归纳的对象是这个论域的大小 n，n 取 0、1 时命题空洞成立，因为不满足「至少包含两个元素」的条件，归纳起始步从 3 开始。归纳步利用归纳假设即可。
5. ^ 因为两者必定有一个的测度是0，而另一个是1