选择公理有哪些反直觉的应用？

选择公理（Axiom of Choice, AC）是集合论中的一个基本公理，它断言对于任何非空集的集合，都存在一个“选择函数”，该函数为集合中的每一个非空集合选取一个元素。虽然在日常生活中我们似乎总能进行选择，但选择公理在数学的某些领域却带来了非常反直觉的结果，这些结果挑战了我们对大小、长度、体积等基本概念的直观理解。

以下是一些选择公理最著名且反直觉的应用：

1. 维塔利集合（Vitali Sets）与不可测集合的构造

这是选择公理最经典的例子之一，它直接导出了勒贝格测度的局限性，并证明了存在无法用勒贝格测度来度量的集合。

背景：

勒贝格测度 (Lebesgue Measure): 这是我们理解长度、面积、体积等概念的数学推广。对于一个区间 $[a, b]$，它的勒贝格测度就是 $ba$。勒贝格测度的基本性质包括：
非负性: 任何集合的测度都大于或等于零。
可加性 (Countable Additivity): 如果一个集合可以被分解成一列不相交的可数子集，那么这个集合的测度就是这些子集测度的总和。
平移不变性 (Translation Invariance): 如果一个集合被平移，它的测度保持不变。即 $mu(A+x) = mu(A)$，其中 $A+x = {a+x mid a in A}$。
可数集测度为零: 任何可数集（如整数集）的勒贝格测度都为零。

维塔利集合的构造：

我们考虑实数集合 $mathbb{R}$，并在此集合上定义一个等价关系：
$x sim y$ 当且仅当 $xy$ 是一个有理数（$xy in mathbb{Q}$）。

等价类: 这个等价关系将实数轴划分成一系列互不相交的等价类。每个等价类是一个形如 ${r+q mid q in mathbb{Q}}$ 的集合，其中 $r$ 是该等价类中的一个代表元。
选择公理的应用: 现在，我们使用选择公理从每一个等价类中选取一个代表元。我们将所有这些代表元组成的集合称为 维塔利集合 $V$。
反直觉的推论:
1. 维塔利集合的性质: 维塔利集合 $V$ 是不可数的。
2. 平移: 对维塔利集合 $V$ 的每一个元素加上一个有理数 $q$，我们得到一个新的集合 $V+q = {v+q mid v in V}$。
3. 等价类与平移: 关键在于，如果 $q_1$ 和 $q_2$ 是两个不同的有理数，那么 $V+q_1$ 和 $V+q_2$ 是不相交的。这是因为如果 $x in V+q_1$ 和 $x in V+q_2$，那么 $x = v_1 + q_1 = v_2 + q_2$ 对于某个 $v_1, v_2 in V$。这意味着 $v_1 v_2 = q_2 q_1$。由于 $v_1$ 和 $v_2$ 来自不同的等价类（如果我们假设它们来自同一个等价类，那它们就是同一个元素），它们的差不可能是非零有理数。因此，如果 $q_1 eq q_2$，则 $(V+q_1) cap (V+q_2) = emptyset$。
4. 覆盖区间: 考虑实数轴上的任何一个长度为 1 的区间，例如 $[0, 1]$。我们可以找到一个可数的有理数序列 $q_1, q_2, dots$ 使得 $[0, 1]$ 被包含在 $igcup_{i=1}^infty (V+q_i)$ 中。更精确地说，我们可以考虑区间 $[1/2, 1/2]$，它会被包含在 $igcup_{q in mathbb{Q}, 1/2 le q le 1/2} (V+q)$ 中。
5. 测度矛盾: 假设维塔利集合 $V$ 是可测的，并且它的勒贝格测度为 $mu(V) = m$。由于平移不变性，对于任何有理数 $q$，$mu(V+q) = m$。
如果 $m=0$，那么 $mu(igcup_{q in mathbb{Q}, 1/2 le q le 1/2} (V+q)) = 0$（由于可数可加性，即使有理数有无穷多个，由于每个子集测度为零，总和也为零）。然而，这个并集包含了区间 $[1/2, 1/2]$，其测度为 1。这就产生了 $0 = 1$ 的矛盾。
如果 $m > 0$，考虑区间 $[0, 1]$。它被包含在 $igcup_{q in mathbb{Q}, 0 le q le 1} (V+q)$ 中。这个并集中的集合是互不相交的（除了可能与 $V$ 本身的交集，但我们选择的等价类是互斥的）。然而，我们知道 $[0, 1]$ 包含的与 $V$ 的平移是无限多个（有理数是无限的）。如果我们将所有 $V+q$ 的测度加起来，会得到无限多个 $m$。但如果它们 disjoint 且覆盖 $[0,1]$，其总测度应该是 1。这里的问题在于，我们无法确定这些平移后的集合 $V+q$ 是否真正是互不相交的。
更严谨的论证：考虑区间 $[0,1]$。我们可以找到一个有理数集合 $Q subseteq [1, 1]$，使得 $[0,1] subseteq igcup_{q in Q} (V+q)$。设 $Q = {q_1, q_2, dots}$ 是一个可数集合。那么 $mu([0,1]) le sum_{i} mu(V+q_i) = sum_{i} m$。如果 $m > 0$，那么我们会有 $1 le sum_{i} m$，这可能是无穷大的。
更关键的问题是，如果在 $[1/2, 1/2]$ 范围内取有理数 $q$，那么 $V+q$ 的集合会覆盖整个实数轴。具体来说，对于任何实数 $x$，存在一个 $v in V$ 和一个 $q in mathbb{Q}$ 使得 $x sim v+q$。这意味着 $x(v+q) in mathbb{Q}$。如果 $V$ 是我们选择的代表元集合，那么 $V subset [0, 1)$（我们可以调整代表元到这个区间）。那么 $V+q$ 的集合会延伸到整个实数轴。
回到最初的矛盾：如果我们考虑 $[1/2, 1/2]$ 中的所有有理数 $q$，那么 $igcup_{q in mathbb{Q} cap [1/2, 1/2]} (V+q)$ 是一个包含 $[1/2, 1/2]$ 的集合。这个并集由很多个与 $V$ 测度相同的集合组成。如果 $V$ 是可测的，设 $mu(V) = m$。那么 $mu(V+q) = m$ 对于所有 $q in mathbb{Q}$。
如果 $m=0$，那么 $mu(igcup_{q in mathbb{Q} cap [1/2, 1/2]} (V+q)) = 0$ （因为有理数是可数的，且每个子集的测度为0）。但是这个并集包含了 $[1/2, 1/2]$，其测度为 1。所以 $0 = 1$，矛盾。
如果 $m > 0$，那么考虑一个更大的区间，比如 $[1, 1]$。我们可以找到有限个有理数 $q_1, dots, q_n$ 使得 $[1, 1] subseteq igcup_{i=1}^n (V+q_i)$。那么 $2 = mu([1, 1]) le sum_{i=1}^n mu(V+q_i) = nm$。这意味着 $m ge 2/n$。但是，我们可以选择更多的有理数覆盖一个更大的区间，得到更小的 $m$ 的下界。问题的核心是，我们无法确定这些集合 $V+q$ 的测度是否严格为正。而且，更关键的是，维塔利集合本身不能被勒贝格测度度量，即它是一个不可测集合。 选择公理保证了它的存在。

结论： 维塔利集合的存在表明，在经典测度论中，并非所有集合都是可测的。而选择公理是构造这些不可测集合的关键工具。这挑战了我们认为“所有集合都应该有大小”的直觉。

2. 班赫塔斯基悖论（BanachTarski Paradox）

这是选择公理最令人费解和反直觉的应用之一。它表明，一个三维球体可以被分解成有限多个块，然后通过刚性运动（平移和旋转）重新组合成两个与原球体完全相同的球体。

背景：

刚性运动: 保持距离的变换，即平移和旋转。
集合分解: 将一个集合分成有限多个不相交的子集，它们的并集是原集合。
选择公理的应用: 该悖论的构造依赖于选择公理来选择球体上的点，或者说，选择自由群的陪集代表元。

悖论的直观描述（简化版）：

1. 分解球体: 将一个三维实心球体 $S$ 分解成有限多个（例如 5 个）互不相交的“块”（在数学上是集合 $S_1, S_2, S_3, S_4, S_5$），使得 $S = S_1 cup S_2 cup S_3 cup S_4 cup S_5$ 且 $S_i cap S_j = emptyset$ 当 $i eq j$。
2. 重新组合: 选择公理被用来构造这些“块”以及它们如何被重新组合。具体来说，这涉及到对球体表面点的分组和对自由群（Free Group）的运用。自由群的陪集（cosets）是与群元素相对应的一系列集合。选择公理允许我们从这些陪集中选择代表元。
3. 产生两个球体: 将其中一些块（例如 $S_1, S_2, S_3$）通过刚性运动（旋转和/或平移）重新组合，得到一个球体 $S'$。将剩余的块（例如 $S_4, S_5$）通过刚性运动重新组合，得到另一个与 $S$ 完全相同的球体 $S''$。最终结果是，我们从一个球体“变出了”两个球体。

反直觉之处：

体积守恒的颠覆: 我们直觉上认为，体积是守恒的。将一个物体分解再重组，其体积应该保持不变。但班赫塔斯基悖论似乎表明，我们可以通过分解和重组来“创造”体积。
“块”的性质: 这里的“块”并非我们日常理解的具有连续表面的三维区域。它们是非常“粗糙”的、分散的集合，其结构高度依赖于选择公理。这些块的测度（体积）是零，并且它们是非连续的、稠密的。如果这些块是可测的，并且我们假设体积是可加的，那么这个悖论就会导致 $2 imes ext{Volume}(S) = ext{Volume}(S)$，从而得出 $ ext{Volume}(S)=0$，这是显然错误的。因此，这些块必须是不可测的。

数学的严谨解释：

班赫塔斯基悖论的严谨证明涉及到群论和测度论。
1. 自由群: 对于两个以上变量的自由群（Free Group on two generators），存在一种“非遍历”（nonamenable）的性质，这意味着它不允许定义一个具有特定性质的测度（例如，在群作用下不变的测度）。
2. 群作用: 将三维空间中的旋转群（或更准确地说，是欧几里得群）作用在三维球体上。
3. 选择公理的应用: 选择公理被用来从自由群的陪集中选择代表元，从而构造出球体的分解。这些分解出的集合“非常奇怪”，它们在群的作用下展现出一种“自相似”的性质，允许我们通过组合来产生更多的“副本”。
4. 不可测集: 班赫塔斯基悖论所构造的“块”是不可测的。如果它们是可测的，并且测度具有平移和旋转不变性以及可数可加性，那么悖论就会导致矛盾。因此，悖论的存在正是证明了存在不可测集，并且我们不能期望测度（如体积）能够以我们直观理解的方式作用在这些由选择公理构造出的极端集合上。

结论： 班赫塔斯基悖论表明，在我们所使用的公理系统（包含选择公理）下，我们对体积的直观理解是无效的。一个物体可以被分解成有限个部分，然后通过重新组合产生比原来更多的相同物体，这完全颠覆了我们对“物质守恒”和“空间大小”的朴素认知。

3. 存在非可数集，其所有子集都是可数的

背景：

可数集: 其元素可以与自然数集合一一对应（或被自然数集合覆盖）。例如，整数集、有理数集。
不可数集: 其元素不能被可数集覆盖。例如，实数集。
幂集: 集合 $A$ 的幂集 $mathcal{P}(A)$ 是 $A$ 的所有子集的集合。
康托尔定理 (Cantor's Theorem): 对于任何集合 $A$，其幂集 $mathcal{P}(A)$ 的势（大小）严格大于 $A$ 的势。 $|A| < |mathcal{P}(A)|$。

反直觉的应用：

选择公理（或更弱的公理如选择函数存在于所有集合族）允许我们证明以下陈述：

存在一个集合 $X$，其势 $|X|$ 很大（例如，大于自然数的可数势），但是它所有的子集都是可数的。

这听起来有点矛盾，因为康托尔定理表明，对于任何集合 $X$，其幂集 $mathcal{P}(X)$ 的势比 $X$ 大。如果 $mathcal{P}(X)$ 的势比 $X$ 大，并且 $X$ 的势是不可数的，那么 $mathcal{P}(X)$ 的势也应该是不可数的。所以，怎么可能 $mathcal{P}(X)$ 的所有子集都可数呢？

这里的关键在于，“所有的子集都是可数的”并不意味着这些子集本身是可数的集合。

让我澄清一下：

1. 康托尔定理与幂集势: 如果我们有一个不可数集 $X$，那么它的幂集 $mathcal{P}(X)$ 也是不可数的。$mathcal{P}(X)$ 的元素是 $X$ 的子集。所以，我们有一个不可数集合（$mathcal{P}(X)$），它的元素是 $X$ 的子集。
2. 选择公理的作用: 选择公理允许我们从不可数集合 $X$ 中“挑选”出一个大小与 $X$ 相同的子集 $Y$，使得 $Y$ 的所有子集都是可数的。这通常是通过在具有良好序的集合（如果存在的话）上使用选择公理来构造的。

一个更精确但仍然反直觉的陈述是：

存在一个集合 $A$，其势为 $aleph_1$（最小的不可数基数），并且 $A$ 的所有子集都是可数的。

这听起来非常奇怪。如果 $A$ 是不可数的，那么它的幂集 $mathcal{P}(A)$ 的势至少是 $2^{|A|}$。如果 $|A| = aleph_1$，那么 $2^{aleph_1}$ 是一个比 $aleph_1$ 大得多的基数。$mathcal{P}(A)$ 是由 $A$ 的子集组成的集合。如果 $A$ 是不可数的，那么 $mathcal{P}(A)$ 中应该包含不可数个不可数子集（因为 $A$ 本身就是不可数子集，而且 $mathcal{P}(A)$ 的大小比 $A$ 大）。

这个说法的核心在于 “其所有子集都是可数的”。这并不意味着这些子集本身是可数集（比如 ${1, 2, 3}$），而是指这些子集的元素个数是可数的。但如果我们有一个不可数集合 $A$，那么 $A$ 本身就是一个子集，它的元素个数是不可数的。

正确的表述应该是：

如果存在一个不可数集 $X$，那么 $X$ 的幂集 $mathcal{P}(X)$ 的势大于 $X$ 的势。
选择公理可以用来构造这样的集合：存在一个集合 $X$，其势是不可数的，并且可以为 $X$ 的每一个元素构造一个“代表元”。 （这更接近于选择公理本身的意义，而不是关于子集的性质。）

一个更相关的反直觉结果是关于集合的基数（大小）的：

连续统假设 (Continuum Hypothesis, CH): CH 声称，不存在一个集合的势，它严格介于自然数集合的势（$aleph_0$）和实数集合的势（$2^{aleph_0}$）之间。换句话说，$2^{aleph_0} = aleph_1$（在 ZFC 集成论中，实数集的势是 $2^{aleph_0}$）。
选择公理与 CH 的关系: 选择公理本身并不直接蕴含或矛盾于连续统假设。事实上，哥德尔和科恩的工作表明，CH 在 ZFC（包含选择公理）中是独立的。这意味着我们可以选择一个包含选择公理的公理系统，在这个系统中 CH 为真；也可以选择另一个包含选择公理的公理系统，在这个系统中 CH 为假。
反直觉的含义: 如果 CH 为假，那么存在一个不可数集合的势，它的势严格大于 $aleph_0$ 但严格小于 $2^{aleph_0}$。我们无法直观地想象这样的“中间大小”的无穷集合。选择公理是 ZFC 的一部分，而 ZFC 是我们数学的基础。CH 的独立性使得我们在理解无穷集合的“层级”时，面临着非直观的选择。

更贴近选择公理直接反直觉的应用是关于势的比较：

存在一个集合 $A$，使得 $|A| > aleph_0$，但我们无法确定它的势是 $aleph_1$ 还是更大的基数，除非我们额外假设 CH 或其否定。
选择公理允许我们证明所有有限集合的并集都是可数的。 （这本身不反直觉。）
选择公理允许我们证明任何有限集合的幂集，其势是 $2^n$ 的形式。 （也不反直觉。）

真正的反直觉在于：存在非可数集，其元素我们可以选择性地“标记”，但这些标记本身却可能非常奇怪。

4. 无穷多个物体的平均

想象一下，你有一个无穷多的数字序列，比如 $a_1, a_2, a_3, dots$。你想计算它们的“平均值”。

直观的想法: 如果这些数字是 $1, 1, 1, dots$，那么平均值应该是 1。如果它们是 $1, 0, 1, 0, dots$，平均值应该是 $1/2$。
问题: 当我们遇到无穷多的数字时，如何定义“平均”？一个自然的想法是取前 $N$ 个数字的平均值，然后让 $N o infty$。但对于某些无穷序列，这个极限不存在。

选择公理的应用（反直觉）：

选择公理可以被用来构造一个例子，说明我们可以为无穷多个对象赋予“公平”的分配，但这种分配的方式却非常不直观。

假设我们有一个无穷多的相同物品（例如，苹果）。我们希望将它们分配给无穷多的不同人（编号为 $1, 2, 3, dots$）。

直观分配: 每人分配一个苹果。或者每两人分配一个苹果，等等。这些都是有序的、可数的分配。
反直觉的分配（依赖于选择公理）： 选择公理允许我们构造一个“非标准”的分配方式。例如，我们可以构造这样一个场景：
我们有无穷多的苹果。
我们有无穷多的人。
我们可以为每个人分配一个“概率”，这些概率加起来等于 1（表示每个人最终会得到一定比例的苹果）。
然而，选择公理允许我们构造一个情况，即我们可以从无穷多的人中选择一个可数无穷子集的人，并且为他们分配所有苹果，而剩余的人则一无所有。 即使我们直觉上认为苹果应该“平均”地分配给所有人。

更严谨的例子是关于“等势的无穷集”：

两个集合是等势的（拥有相同的势/大小），如果它们之间可以建立一对一的对应关系。我们知道可数无穷集是等势的（例如，自然数和整数是等势的）。

选择公理保证了所有无限集合都可以与自然数集合建立一对一的对应关系，也就是说，所有的无限集合都是可数的。 (这是 错误的！选择公理并不能证明所有无限集合都是可数的。它只是说，对于任何无限集合，它都有一个“大小”或“势”。)

正确的反直觉应用是关于集合的“分类”：

选择公理允许我们证明，所有无限集合都可以被划分为“可数的无穷集”。 这不是说它们都是有限的，而是说它们的“大小”（势）可以用基数 $aleph_0, aleph_1, aleph_2, dots$ 来描述。
反直觉之处： 我们直觉上认为，无穷集合的大小有不同的“等级”。例如，实数集合比自然数集合“大”。选择公理和康托尔定理告诉我们，确实如此。但是，选择公理允许我们对这些不同等级的无穷集合进行操作，结果可能与我们的直觉不符。

一个更具体的问题是在“无限的房间”悖论的变种中：

考虑一个有无穷多个房间的旅馆，每个房间都住着一位客人。
现在，一个新客人来了。我们可以将每个客人都移到下一个房间（房间 $n$ 的客人移到房间 $n+1$）。这样房间 1 就空出来了，新客人可以入住。
现在，无穷多辆巴士来了，每辆巴士上都载着无穷多的客人。
在这种情况下，我们可以用选择公理来安排，让所有新来的客人都住进来。例如，可以将房间 $n$ 的客人移到房间 $2n$，然后新来的客人可以住进奇数房间 $1, 3, 5, dots$。

反直觉之处： 虽然这个例子本身并不那么反直觉（它说明了无穷集合的“收纳能力”），但它依赖于选择公理能够为每个房间的客人提供一个“下一个”房间，或者为无穷多辆巴士上的无穷多位客人找到一个“容身之所”。如果我们要“公平”地分配，或者有更复杂的要求，选择公理的应用就可能产生令人费解的结果。

总结选择公理的反直觉应用：

选择公理最核心的反直觉之处在于它 “断言了一个非构造性的存在”。它说“一定存在一个选择函数”，但并没有给出如何构造这个函数的方法。正是这种非构造性的存在，使得我们可以证明许多“意想不到”的数学事实，这些事实挑战了我们基于有限经验形成的直觉。

维塔利集合: 证明了存在“没有长度”的集合，并且不是所有集合都可测。
班赫塔斯基悖论: 证明了在一个三维空间中，一个球体可以被分解成有限块，然后重组成两个相同的球体，颠覆了体积守恒的直觉。
无穷集合的结构: 允许我们证明关于无穷集合势的许多难以想象的属性，以及它们之间的复杂关系，特别是在连续统假设等问题上。

这些例子说明，当我们进入数学的严谨世界，特别是处理无穷时，我们必须谨慎对待我们的直觉，因为数学公理可能会引导我们走向与直觉相悖但逻辑上一致的结论。选择公理就是这样一个强大的工具，它为数学带来了深刻的洞察力，但也伴随着令人着迷的悖论。

众所周知, 数学里的反直觉有两个意思

1. 这tm也要证?
2. 这tm也能证?

选择公理在这两个意义上的反直觉应用都不少. 我个人认为哲学(可能世界语义学和voting theory)上的应用比较有趣

1. 这tm也要(用到选择公理来)证? (意思是说，如果我们不接受选择公理，以下每一条我们都能找到一个模型使得它为假)

-如果存在一个X到Y的满射，那么存在一个Y到X的单射 (这个叫做the partition principle, 目前已知的所有证明都要用到选择公理)

-给定一系列的非空集合，这些集合的笛卡尔积非空

-任意两个集合都能比较大小(意思是要么存在X到Y的单射，要么存在Y到X的单射，要么两者都成立)

-可数个可数集的并是可数的(弱化一点地说, 实数集无法拆分为可数个可数集合)

-如果我们把一个集合划分成一堆两两不相交的集合，那么这些划分的数量不大于原集合内元素的数量

-任何一个无限的集合都存在一个可以和自然数一一对应的子集

-一阶逻辑的完备性和紧致性(completeness & compactness)

-符合我们直觉的对于“有限”的几个定义等价

-每一个nontrivial ring都存在maximal ideal

-每一个connected graph都存在一个spanning tree

2. (用了选择公理)这tm也能证?

-实数上存在一个良序

-存在一个不可测集

-Banach-Tarski分球悖论

-另一个回答里提到的必胜策略类型的结果

-任意一阶公理集如果存在无限大的模型，那么这个公理集存在可数无限大的模型 (downward Löwenheim-Skolem)

-complex p-adic numbers和complex numbers作为fields是同构的

-(在普遍接受的可能世界语义学下)存在一个一致的语句集，但这个语句集不在任何一个可能世界为真

-存在(阿罗不可能定理意义上的)完美的投票系统

-在直觉主义数学中证明排中律

讲一个选择公理的有趣应用。

假设有100个绝顶聪明的人要参加一个游戏，这个游戏参与过程中所有人不能以任何形式交流。

道具：假设有100个完全一样的房间，房间中有可列无穷张正面朝下的纸条，纸条下写了一个实数。

规则：100个人同时进入这些房间（一人一个房间），进入房间后，可以查看除了一张以外的所有纸条（不要求在一开始就决定不看哪张，可以先看一部分之后再做决定，每个人选择的纸条可能不同)。这时候，神奇的地方来了，他需要猜测这张未翻开纸条上的数，如果猜错了，死亡。

问题：这100个人是否可以提前商量一个策略，使得至少有99个人可以存活？

第一反应肯定觉得不可能，因为剩下所有纸条上的数和要猜的那张上的数没有任何关联....

答案：存在这样的策略，下面开始构造这个策略，为此我们需要使用一些记号。

我们把所有纸条编号，因此纸条上的数构成一个无穷长的向量 。

在集合 上构造等价关系 当且仅当 使得对任意 （也就是说 当且仅当他们只有有限位不同，那么容易验证 是一个等价关系）

根据选择公理，我们可以从每个等价类中选取一个代表元 ，把此代表元对应的等价类记为

下面构造策略如下，首先这100个人先把所有代表元构成的表格背下来。假设房间中的向量为 ,考虑 为所有下标模100余 的元素构成的子列。那么第k个人保留 ,直接查看所有

考虑 所对应的等价类中的代表元为 ,即 。于是由等价关系的定义我们有 除了有限项以外均相同，设 。于是第k人可以观测到 以外的所有 .

那么设 ,此人现在保留 的第 位，查看其余所有的数，由于他只有第 位不知道，因此他可以确定 所在的等价类为 ,那么现在他猜测

我们断言这个策略可以保证至少99个人存活（猜中数字）

为什么？因为只有当 时，第 个人才有可能猜错，（想想为什么？），而这样的i显然最多有一个，证毕！