序数是什么
在这篇文章中，我们希望用一种自然的方式引入序数这一数学概念。
本文试图让任何一个对集合与映射有朴素认知的人（比如，高中生）能看懂。
（本文改写自知乎问答：什么样的集合可以排序？张智浩的回答）
零、引子
一、序是什么
二、什么时候可以排序
三、良序
四、序数
让我们从简单的场景开始。一年级二班的小朋友们要去做课间操，都是排着队去操场的。怎么排队呢，比如按学号排，1 号小朋友站在开头，他的后面站着 2 号，以此类推，一个接一个。这是最简单的“按序排列”的场景。当然了，因为一年级二班只有有限多个小朋友，所以这也很简单。
如果有无限多个小朋友呢？哦，如果小朋友们的学号都是正整数，那似乎也差不多：还是 1 号站在开头，2 号次之，一个一个下去，无非队伍没有尽头了嘛。
但是，如果小朋友们的学号是 [0,1] 区间里的有理数呢？这个时候这个队伍就有些奇怪了，学号为 0 的小朋友当然在开头，但他后面站谁呢？这时候似乎有点奇怪了，根本没有谁正好在他后面：如果觉得学号为 q 的小朋友在他后面，那么学号为 q/2 的小朋友肯定在他们俩中间，所以学号为 q 的这位并不正好在学号为 0 的后面。换言之，如果学号用有理数来标记，根本没法排出队伍来——至少跟我们想象中的队伍不太一样。
这似乎带来一个问题：什么样的集合可以按序排列呢？
回答这个问题的关键当然是“什么叫‘按序排列’”？
（注：一个没有说清楚的问题自然是没法回答的，第一步自然是搞清楚这个问题究竟在问什么；很多时候我们的问题都是一些用自然语言表述的“朴素”的问题，将其转化为用严格数学语言表述的问题之后，问题“基本上”也就解决了）
按照上面的朴素分析，我们已经看到了排队的要点：首先有个开头的小朋友，然后他后面站一个，他后面这个小朋友的后面还有一个，每个小朋友后面都站一个，除了最后一个小朋友（如果有最后一个的话）。不能出现一个小朋友后面不知道站谁的情况，一大群人站在他后面，但没有谁刚好在他后面。
看起来我们已经遇到了一个关键点，即“后面一个”。我们是不是可以说：一个集合能够“按序排列”，就是说这个集合中每个元素都能找到“后面一个”的元素？
仔细想一想，这似乎符合我们朴素的理解。那么某个元素的“后面一个”，是什么意思？
要严格回答这些问题，我们得严格定义什么叫“序”，因为显然这些问题都依赖于“什么叫序”。
序是一种关系。这句看起来像废话一样的话其实在数学上也有明确的含义，但是在这里我们不想讨论什么叫“关系”，因为这可能稍微有点离题了。在下面有个 注释 提到这件事，但是所有的 注释 都是可以跳过的内容，与正文关系不大。
就我们朴素的认知来说，什么叫序呢？序是拿来比较大小的，比如我说一个集合 X 上有个序，我的意思是从中任取两个元素 x₁,x₂ ∈ X，我能比较哪个大哪个小。所以我们给出以下定义：
定义. 设 X 是一个集合。一个 X 上的全序，或者简称为序，是一个满足以下条件的二元关系 ≤：
如果你忽略掉一个神秘的名词“二元关系”，仅仅从字面上理解，这几条要求似乎完全满足我们对“序”的想象：前两条几乎是废话，第三条是所谓的“传递性”，第四条则是说“任意两个元素都能比较大小”，所以叫“全序”。下面我们都将使用“全序”这一名称，而不再用“序”。
多说一句，第四条加第二条能推出第一条自动满足，所以其实不需要这么多条件。
注释. 这个定义其实不那么完整，因为我还没定义“二元关系”这个神秘的名词。对于不知道的读者，我们简单说一下。我要怎么描述一种“关系”呢？最简单的一种办法是：我把所有有关系的对子都拿出来，那我自然就知道这个关系是什么了。比如，我宣称 X 上有一种关系叫“小于等于”，我只需要给出所有 (x₁,x₂) 的对子，其中 x₁ 小于等于 x₂，那么我就确定了这个关系。所以，一个 X 上的关系就是 X × X 的一个子集。这里我并未写得很严格，但我想在正文中应当不影响理解。
注释. 如果在上述定义中去掉第四条，我们就得到了“偏序”的定义。简单来说，一个偏序基本上就是一个全序，唯一的区别是，两个元素并不一定可以比较大小。不过本文中我们暂且不讨论偏序的事情。
一个全序集 (X,≤) 就是一个集合 X 和其上的一个全序 ≤ 一起组成的对子。一个集合上可以有很多不同的全序，所以我们应当将全序视为一种结构。换言之，一个全序集，是一个集合装备了全序这种结构之后得到的东西，它已经不再是原来那个集合了，而是一个有结构的集合。所以一开始的问题应当是：什么样的全序集可以排序？
本节的最后我们来看几个全序的例子：
我没有仔细给出后几个例子的定义，也没有验证它们确实是全序，但我想这是很容易感受到的。细节就留给读者吧。
现在我们已经严格定义了什么叫“序”了，现在我们来看看给定一个全序集 (X,≤)，我们是不是能把 X 中的元素“排”起来。
如果能够把 X 中的元素排起来，这个队伍首先有个开头，这个开头是谁呢？哦，那当然是 X 里面最小的那个元素了。那啥叫“最小”呢，当然是没有比它更小的了。所以以下定义是显然的：
定义. 设 (X,≤) 是一个全序集。如果一个元素 x ∈ X 满足以下条件：
那么称 x 为极小元素。
等等，也许你会说，“最小”的意思难道不是比其它所有元素都小吗？那么我们定义：
定义. 设 (X,≤) 是一个全序集。如果一个元素 x ≤ X 满足以下条件：
那么称 x 为最小元素。
为了区分这两种定义，前者我叫做“极小”而后者我叫做“最小”。如果有过求函数的极值与最值的经验，可能会对这一命名感到亲切。那么这两个概念是一样的吗，我们的感觉是不是对的呢？确实是对的。
命题. 设 (X,≤) 是一个全序集。如果 x ∈ X 是一个极小元素，那么它也是最小元素；反之，如果它是一个最小元素，那么它也是一个极小元素。此外，不论极小元素还是最小元素，如果存在，那么是唯一的。
证明. 证明是比较容易的。先假设 x 是最小元素。如果有 x' ∈ X 满足 x' ≤ x，由于 x 是最小元素，必定有 x ≤ x'，所以 x = x' 。换言之 x 是极小元素。
反过来，假设 x 是极小元素。对任意 y ∈ X，由全序的定义知道要么 x ≤ y 要么 y ≤ x。如果 x ≤ y，那么没什么可说的；如果 y ≤ x，由于 x 是极小元素，必定有 y = x，那还是有 x ≤ y。总之，不论如何都有 x ≤ y，即 x 是最小元素。
至于唯一性是比较显然的。如果 x,x' ∈ X 是两个最小元素，那么由 x 最小知道 x ≤ x'，由 x' 最小知道 x' ≤ x，故 x = x'。
注释. 对于全序集这两个概念自然是一样的，但是对于偏序集就不同了。由于任意两个元素并不一定能比较大小，所以在偏序集中“最小元素”并不是一个很好的概念；仔细看上面的证明，任意两个元素能比较大小这一条也是关键的一步。此外，在一般的偏序集中，极小元素不一定唯一。
上面的命题并没有提及最小元素或者极小元素的存在性，只是说“如果存在那么怎么样”。事实上一个全序集也不一定存在最小元素，比如整数集合按照通常的序关系就没有最小的那个数，但自然数集合就有最小的数，即 0。
所以 (X,≤) 的元素能“按序排列”的第一个条件是：全序集 (X,≤) 存在极小元素。好了，现在队伍的开头有了，下一个排谁呢？
注意，我们已经说了“下一个”，所以立马的问题就是，什么叫“下一个”？任取 x ∈ X，自然的“下一个”显然要比 x 大，并且它们之间没其它元素了。所以我们定义：
定义. 设 (X,≤) 是一个全序集且 x ∈ X，则 x 的后继是满足以下条件的一个元素 S(x) ∈ X：
这个定义看起来有些拗口，或许我们能改写一下。用符号 (x,+∞) 表示 X 中比 x 大的元素形成的子集，即 (x,+∞) := {y ∈ X ∣ x < y}。那么上述定义就是在说：后继 S(x) 是 (x,+∞) 中的极小元素。如果这个极小元素存在，那么我们就找到了 x 的“后一个”。如果每个 x ∈ X，只要不是“最后一个”，都有“后一个”，那么我似乎就可以把 X 中的元素“按序排列”起来了。
至此我们似乎已经找到了 (X,≤) 可以“按序排列”的条件，包括两条：
当然，子集 (x,+∞) 是空集的意思就是“没有比 x 更大的元素”，即 x 是极大元素。我没有写下极大元素和最大元素的定义，但原则上跟前面写的没什么区别。
至此问题结束了吗？不，这里还有两个问题。第一个问题是，如果记 m 是极小元素，我的排列总是像 m,S(m),S²(m) = S(S(m)),… 这样排起来的，但是所有 x ∈ X 都会出现在这里面吗，会不会有些元素不在队伍里面？换言之，如果某些 x ∈ X 没有“前一个”，我这算是“按序排列”吗？
这其实不是一个特别关键的问题，它依赖于我们对“按序排列”的理解，我们将在最后讨论这个问题。第二个问题比较关键，我们马上来讨论。
上面给出的可以“按序排列”的条件有个最大的问题：这些条件不是被子集保持的。这句话的意思是，如果 (X,≤) 满足“按序排列”的两个条件，而 Y 是 X 的一个子集，那么 (Y,≤) 并不见得可以满足这两个条件。这想一想似乎违背了我们朴素的直觉：如果我把一些元素排列起来，我从里面取一部分元素，它们应该也自动排列起来了才对。
来看一个例子。在第一节中我们有一个 [0,+∞) × N,≦) 的字典序的例子，它满足“按序排列”的两个条件：首先极小元素是 (0,0)，其次对每个 (x,n) ∈ [0,∞) × N，它的后继是 (x,n+1)。然而，考虑它的一个子集，比如 {(x,0) ∣ x > 1}，它就没有极小元素，在里面也没有后继，因为这个全序集和 (1,+∞) 几乎就是一样的。（关于什么叫“一样”我们也会在之后讨论）
所以，可能更好的选择是 (X,≤) 的任意子集都满足上述可“按序排列”的条件。但是子集的子集还是子集，所以这件事情显然等价于说 X 的任意子集都存在极小元素。
定义. 设 (X,≤) 是一个全序集。如果全序 ≤ 满足以下条件：
则称 ≤ 是一个良序，而 (X,≤) 称为一个良序集。
顾名思义，“良序”的意思就是这个序很好，当然经过上面的讨论我们也知道它到底好在哪里：从一个良序集里面任取一个子集，都能“按序排列”。
看几个例子。显然自然数集合按照通常的序关系 (N,≤) 是一个良序集。上面给出了 N 上的另一个全序关系 ≦，容易验证 (N,≦) 是一个良序集。可以感受到，(N,≦) 就是把两个 (N,≤) 给“拼”在一起了。
那么这里说个题外话。所谓的“良序原理”说：对任意一个集合 X，存在一个 X 上的良序。
乍一听这是一个很强的命题，因为一个集合上的序实在是太多了，但良序这个条件又这么苛刻，几乎不太可能实现的样子。事实上它也确实很强，它等价于“选择公理”。对于那些不了解什么是选择公理的读者，我们也简单提一下，它基本上是这么个意思：如果我现在有一大堆非空集合，记为 {X_i}，其中 i ∈ I 用来标记这些集合，那么我可以从每个 X_j 里面挑一个元素 x_j ∈ X_j。
这听起来什么也没说，难道不是显然的吗？嗯，确实是这样，不过“挑一个”的意思是找到这么一个映射 f : I o ∪ X_i 使得 f(j) ∈ X_j，称为选择函数。这个映射怎么找呢？
关于选择公理，在此我不详细阐述了，有兴趣的读者可以参考这个知乎问答：
如何让一个 5 岁小孩听懂什么是选择公理？匡世珉的回答。（此处没有链接）
不过如果有了良序原理，这样的选择函数似乎很容易找到了：首先在 ∪ X_i 上给一个良序。那么每个子集 X_j，按照定义会有一个极小元素 x_j。好了，那么我们定义 f(j) = x_j 就完事了。
这或许会对大家理解选择公理提供一些帮助。
多说一句，问题描述中有“把 [0,1] 中的有理数”排成一列的做法。这里并不需要用良序原理，只需要注意到 [0,1] 中的有理数其实可以和自然数集 N 建立一个双射，这就完了。当然这件事情也并不显然。
我们大概已经回答了原本的问题：什么样的全序集可以“按序排列”？按照我的理解，就是良序集。好了，每当我们有一个数学对象，我们就可以做一些常规的操作。
定义. 设 (X,≤) 和 (Y,≦) 是全序集。如果一个映射 f : X → Y 满足以下条件：
则称 f 是一个保序映射。如果 f 还是一个双射（一一对应），则称 f 是一个保序同构。
容易验证保序同构的逆映射还是保序同构。
注释. 如果读者知道一些基本的范畴论，容易看出，所有全序集和保序映射组成一个范畴，这个范畴的同构就是保序同构。所有良序集组成这个范畴的一个满子范畴。
如果两个全序集是保序同构的，那么它们几乎就是“一样”的。所谓“同构”，就是“有相同的结构”，即序结构是一样的。
注释. 当然了，什么叫“一样”其实是个很大的问题，如果有不一样的“一样”那还是“一样”吗？比如整数集合 (Z,≤) 到自身有很多保序同构：对每个 m ∈ Z 定义 f_m(n) := n + m，那么 f_m 显然是保序的；换言之，整数集合与自己有很多不一样的“一样”；不过又说回来，它自己与自己有一个特别的“一样”即恒等，所以到底是不是“一样”呢？对于这些范畴论的讨论，我推荐读者阅读下文：
孔良：1+1=2？（此处没有链接，可以去知乎搜索孔良老师，或者在返朴公众号中寻找）
然后我们会发现，良序集真的性质很好：如果两个良序集“一样”，那么它们只有唯一的方式“一样”，换言之它们真的一样！
命题. 设 (X,≤) 和 (Y,≦) 是两个保序同构的良序集，则它们之间的保序同构是唯一的。
在此我们不给出具体的证明。大概的想法是，保序同构总是把极小元素映到极小元素，后继映到后继，两边都排成一排，那么显然只有一种保序同构。当然了，这不算是思路，因为要严格化这种想法还需要很多工作。或许会感受到，这种说法很像数学归纳法；事实上我们确实会有一种新的归纳法，在此不细说了。
既然我们把保序同构的良序集看成一样的，那么唯一有用的就是良序集的“等价类”了，保序同构的良序集视为等价的。我们给这些等价类取个名字，叫“序数”。
定义. 一个序数是一个良序集的等价类。
比如，我们用正整数 n 来表示 {0,1,…,n-1} 这个良序集对应的序数，用 0 表示空集这个良序集对应的序数，用 ω 来表示正整数集合 (N,≤) 对应的序数。
习题. 空集如何成为一个良序集？
注释. 这里其实有一些小问题。众所周知，所有集合的“集合”并不是一个集合；类似地，和某个集合同构的所有集合也不构成一个集合。比如，对每个集合 X，集合 {X} × Y 当然和 Y 有一个双射。所以，如果考虑和某个良序集保序同构的所有良序集，这也太大了而不是一个集合。不过这到不是什么大问题，因为我们还有别的办法定义什么叫序数。不过在这里理解成等价类没有什么影响。
序数可以比较大小，事实上随便拿一些序数出来组成的集合也自然地是一个良序集。序数可以做加法，也就是把两个良序集“拼”在一起，比如我们前面看到的 (N,≦) 对应的序数就是 ω + ω。序数也可以做乘法，也就是把两个良序集做笛卡尔积然后取字典序，比如 ω + ω = ω · 2（不过通常的字典序和我上面的例子是反的）。序数的加法和乘法都不是交换的，比如 1 + ω = ω ≠ ω + 1 以及 2 · ω = ω ≠ ω · 2。
习题. 验证这两个等式和不等式。
最后我们把前面挖的一个坑填上：我们只讨论了元素有后继的情况，如果我还希望元素有前继，即每个元素，除了极小元素，都是某个元素的后继，又会怎么样？可以证明，只有有限的序数和 ω 满足这一条件。其实这比较显然，更大的序数一定包含 ω，那么自然就会出现一个没有前继的元素。
当然了，严格的证明依赖于更严格的定义。这一节我们几乎没有给出任何严格的定义，主要是写得太长了，不打算继续了。
拓展阅读. 有兴趣的读者可以参考维基百科，搜索序数（ordinal number）即可。
