集合论：无穷乘客消失之谜

大家好我是渡鸦，几天前网友sepia大大分享了这么一个谜题（感谢！）：

一个\(\omega_1\)个车站的轨道上，行驶着一辆谜之火车。火车从0号车站出发的时候，车上一个人也没有。之后，火车在1号车站、2号车站……每一站停车的时候，如果车上有人就会有1个人下车，之后有\(\omega\)个新的乘客上车。当火车到达\(\omega_1\)号车站的时候，还有多少人正在车上呢？

这其中\(\omega\)指的是可数无穷，而\(\omega_1\)指的是最小的不可数无穷。如标题所示，这个问题的答案正是：0人。你猜到了吗？

要了解这个现象，就要从最基础的定义说起。这里假设读者有对朴素集合论的充分了解，包括交集并集还有可数性等等。

首先定义序数为对于“\(\in\)”关系的传递且三分的集合。通俗点说，序数有以下三种构造方式：

1. \(0=\{\}=\emptyset\)是一个序数；
2. 对于一个序数\(\alpha\)而言，\(\alpha+1=\alpha\cup\{\alpha\}\)是一个序数；
3. 对于一个包含序数的集合\(A\)而言，\(\sup A=\bigcup_{X\in A}X=\bigcup A\)是一个序数，这里的\(\sup\)称作\(A\)的上确界或者极限。

例如：
1. \(1=\{0\}\)，\(2=\{0,1\}\)，\(3=\{0,1,2\}\)是序数；
2. \(\sup\{0,1,2,\ldots\}=\{0,1,2,\ldots\}=\omega\)是序数；
3. \(\sup\{\omega,\omega+1,\omega+2,\ldots\}=2\omega\)是序数。

接下来对序数\(\alpha,\beta\)可以记\(\alpha<\beta\)当且仅当\(\alpha\in\beta\)。例如：

1. 对所有序数\(\alpha,\beta\)而言，“\(\alpha<\beta\)”、“\(\alpha=\beta\)”、“\(\alpha>\beta\)”三种关系总有恰好其中一种成立；
2. 对所有序数\(\alpha\)而言，\(\alpha=\{\gamma\mid\gamma<\alpha\}\)成立；
3. 对一个包含序数的非空集合（或非空类）\(A\)而言，总存在一个最小元素\(\min A\)使得\(\forall \alpha\in A\)，\(\min A\le\alpha\)，这是因为“\(\in\)”关系是良序（或称作正则）的。

对任意集合\(A\)，记\(A\)的势\(|A|\)为它包含的元素个数，称\(A\)为至多可数当且仅当\(|A|\le|\omega|\)，反之称\(A\)为不可数。因此（由于良序定理）所有不可数的序数所构成的集合存在最小元素，称之为\(\omega_1\)，于是\(|\omega_1|>|\omega|\)且\(\forall\alpha<\omega_1\)，\(|\alpha|\le|\omega|\)。

同理可以定义基数为和同一个固定序数等势的所有序数中的最小元素，于是（由于良序定理）基数可以用来表示势，例如：

1. 对非负整数\(\forall n<\omega\)，有\(|n|=n\)；
2. 对\(\forall \omega\le\alpha<\omega_1\)，有\(|\alpha|=\omega\)；
3. \(|\omega_1|=\omega_1\)；
4. 对\(\forall |\alpha|<\omega_1\)，有\(\alpha<\omega_1\)，因此不存在序数\(\alpha\)使得\(\omega_1=\alpha+1\)。

此外，在一般意义下称一个函数\(f:X\to Y\)为压下的（regressive）当且仅当对所有\(x\in X\)，有\(f(x)\in x\)。再对一个序数\(\alpha\)和集合\(X\subseteq\alpha\)，称集合\(X\)是无界的当且仅当\(\sup X=\alpha\)。我们现在可以证明第一个引理：

---

引理：对于一个压下函数\(f:(\omega_1-\{0\})\to\omega_1\)，存在一个序数\(\beta<\omega_1\)使得逆像\(f_{-1}\{\beta\}=\{s\in\omega_1\mid f(s)=\beta\}\)无界。

证明：我们证明它的逆否命题。假设对\(\forall\beta<\omega_1\)，有\(\sup f_{-1}\{\beta\}<\omega_1\)，那么接下来可以先证明成立\(\sup f_{-1}(\beta)<\omega_1\)。注意到

\[f_{-1}(\beta)=\bigcup_{\gamma\in\beta}f_{-1}\{\gamma\}\]

由于每个集合\(f_{-1}\{\gamma\}\subseteq \sup f_{-1}\{\gamma\}\)至多可数、且\(\beta\)至多可数，\(f_{-1}(\beta)\subseteq \omega_1\)作为至多可数个至多可数集的并集也至多可数，于是\(\sup f_{-1}(\beta)\)作为至多可数个至多可数集的并集也至多可数，所以\(\sup f_{-1}(\beta)<\omega_1\)。

接下来构造一个可数无穷项的数列\(C=\{c_n\mid n\in \omega\}\)。任取一个\(c_0<\omega_1\)，并以归纳的方式构造其余每一项：假设选定了一个\(c_n<\omega_1\)，那么由于\(\sup f_{-1}(c_n)<\omega_1\)，可以任选一个

\[\sup f_{-1}(c_n)< c_{n+1}<\omega_1\]

比如说\(c_{n+1}=\sup f_{-1}(c_n)+1\)。

因此\(C\subseteq\omega_1\)。接下来令\(\alpha=\sup C\)，于是同样地，\(\alpha\)也是可数个集合的可数并集，所以\(\alpha<\omega_1\)。对于\(\forall \gamma\in\alpha\)，由\(\alpha\)的定义有\(\exists c_n\in C\)，使得\(\gamma\in c_n\)。因此考虑

\[\begin{align*}
f_{-1}(\alpha)&=\bigcup_{\gamma\in\alpha}f_{-1}\{\gamma\}\\
&=\bigcup_{c_n\in C}\bigcup_{\gamma\in c_n}f_{-1}\{\gamma\}\\
&=\bigcup_{c_n\in C}f_{-1}(c_n)\\
&\subseteq\bigcup_{c_n\in C}c_{n+1}\\
&\subseteq\sup C\\
&=\alpha
\end{align*}\]

也即\(f_{-1}(\alpha)\subseteq\alpha\)。此时有\(\alpha\notin\alpha\)，意味着\(\alpha\notin f_{-1}(\alpha)\)，也即\(f(\alpha)\notin \alpha\)，也即\(f\)不是压下的。QED

---

定理：火车空无一人。

证明：定义\(f:(\omega_1-\{0\})\to\omega_1\)，使得对任意的\(\alpha<\omega_1\)：如果有一个人在\(\alpha\)号车站下车，那么记这个人在\(f(\alpha)\)号车站上车；如果没有人在\(\alpha\)号车站下车，那么记\(f(\alpha)=0\)。

显然\(f(\alpha)<\alpha\)，所以\(f\)是压下的。由于引理，存在\(\beta\)使得\(f_{-1}\{\beta\}\)无界。如果\(\beta>0\)，那么\(f_{-1}\{\beta\}\)表示所有在\(\beta\)号车站上车的人的下车顺序。由于只有\(\omega\)个人上车，因此\(f_{-1}\{\beta\}\subseteq\omega_1\)至多可数，所以\(\sup f_{-1}\{\beta\}\)作为至多可数个至多可数集的并集也至多可数，也即\(\sup f_{-1}\{\beta\}<\omega_1\)有界，产生矛盾。

因此\(\beta=0\)成立。我们记\(X=f_{-1}\{0\}\subseteq\omega_1\)，这是所有无人下车的车站号的集合。对于曾经上过车的每个人，假设这个人在\(\alpha\)号车站上车，那么由于\(\alpha\in\omega_1=\sup X\)，所以有\(\exists\gamma\in X\)使得\(\alpha\in\gamma\)，也即在\(\alpha\)号车站之后的某\(\gamma\)号车站，车上无人下车。这必意味着，这位乘客已经在\(\gamma\)号车站之前就下过车了。由于每个上过车的人必定下过车，所以在火车到达\(\omega_1\)号车站时，车上是没有人的。QED

---

接下来是一点补充。

首先相比不可数的\(\omega_1\)来说，可数的\(\omega\)的情况会更符合直觉：

谜之火车（弱化版）：假设火车仅驶过\(\omega\)个车站，在\(n\)号车站上有最多1人下车、恰好\(n\)人上车。那么对于任意的\(\alpha\le\omega\)，总有一种下车顺序使得在火车到达\(\omega\)车站时，车上正好有\(\alpha\)人。

简单的思考就可以证实上面这种情况的正确性。

对于比\(\omega_1\)更大的数而言，“有人”和“没有人”的情况都会接连发生，而这里更不平凡的情况自然是“没有人”的时候。我们需要一个定义：

对于一个不可数基数\(\kappa\)，我们称\(\kappa\)为正则的（regular）当且仅当对任意无界的\(X\subseteq\kappa\)，总有\(|X|=\kappa\)。

例如，\(\omega_1\)是一个正则基数，因为可数集的可数并仍可数。\(\omega\)不是正则基数，但也满足\(X\subseteq\omega\)无界意味着\(|X|=\omega\)，因为有限集的有限并也有限。此时就有：

谜之火车（强化版）：假设\(\kappa\)是个正则基数，且火车驶过共\(\kappa\)个车站。在火车到达\(\alpha\)号车站时，有至多1人下车，\(|\alpha|\)个人上车。那么在火车刚驶到\(\kappa\)号车站时，车上空无一人。（此外，有一类很大的正则基数\(\kappa\)满足，在\(\kappa\)之前的“几乎所有”车站内，到站的火车空无一人。）

证明这个强化版的谜之火车现象，大体的证明思路和上面证明\(\omega_1\)的情况相似，但是取代引理地位的是一条叫做“Fodor压下引理”的定理。这里由于用初等语言叙述Fodor引理会过于冗长，我鼓励感兴趣的读者专门学习相关知识，或者阅读：

 

---

谜题来源和解法：

1. 谜之火车：渕野 昌，Mystery Train — 無限組合せ論への招待 —

2. 谜之火车（强化版）：Aras Ergus, Fodor’s Train: Some Club Filter Sorcery

主要参考资料：

Thomas Jech, Set Theory