良序集

良序集（Well-Ordered Set）

定义
依赖深度 layer 6
序理论
序结构

def.wellorder · 定义 · 良序 · 超限归纳

又称良序·良序集·well-order·well-ordering

陈述

全序集 $(W, \preceq )$ 是良序的，当且仅当 $W$ 的每个非空子集都有最小元：

\forall S \subseteq W ( S \ne \emptyset \to \exists m \in S, \forall s \in S, m \preceq s )

等价于：不存在无穷严格递减链 $w_{0} \succ w_{1} \succ w_{2} \succ \cdots$ 。

说明

⭐ 良序的用处只有一个：让「下一步」有定义。 每一步之前的部分有头有尾，于是可以做超限归纳（证明）与超限递归（构造）—— 见「良序集上的递归定理」。

⭐ 每个良序集都序同构于唯一的一个序数（见「良序集的序型」），那个序数就是它的「长度」。于是「两个良序集谁更长」变成「两个序数谁大」，而序数的大小就是 $\in$ 。

$\langle \mathbb{N}, \le \rangle$ 是良序的； $\langle \mathbb{Z}, \le \rangle$ 、 $\langle \mathbb{R}, \le \rangle$ 不是（ $\mathbb{R}$ 的某些非空子集没有最小元）。

它指向谁（出边）

推出 1

本页 ⟹ 超限递归推出

良序性 $\implies$ 递归定理

设 $(W, \preceq )$ 是良序集， $G$ 任给。记 $W_{< w} = \{ v \in W : v \prec w \}$ 。
① 初始段上的解至多一个。 设 $w \in W$ ， $f, g$ 都是 $W_{< w}$ 上满足递归式的函数。反设 $f \ne g$ ，取最小的 $v \prec w$ 使 $f(v) \ne g(v)$ （这一步用的是良序性： $\{ u \prec w : f(u) \ne g(u) \}$ 非空故有最小元）。于是在 $W_{< v}$ 上 $f$ 与 $g$ 相同，从而
$f(v) = G\big( f \upharpoonright W_{< v} \big) = G\big( g \upharpoonright W_{< v} \big) = g(v)$
矛盾。故 $W_{< w}$ 上至多一个解，且这个解唯一确定。
② 构造候选关系的集合。 令
$R = \{ (w, y) : \text{存在函数} f \text{ 定义在} W_{< w} \text{ 上、满足递归式，且} y = G(f) \}$
它是集合：候选的 $f$ 都是 $W_{< w} \times V$ 的子集，先由幂集公理拿到 $\mathcal{P}(W \times V)$ ，再用分离公理模式从里面筛出满足条件的那些（ $V$ 取一个足够大的集合即可，例如 $G$ 的值域之并的幂集的幂集）。由 ①，对每个 $w$ 至多一个 $y$ ，所以 $R$ 是单值的，即 $R$ 是一个函数。
③ $R$ 的定义域是整个 $W$ 。 反设不然，取最小的 $w \notin \operatorname{dom}\, R$ 。则 $W_{< w} \subseteq \operatorname{dom}\, R$ ，于是 $f := R \upharpoonright W_{< w}$ 是 $W_{< w}$ 上满足递归式的函数（若 $v \prec w$ ，由 $v \in \operatorname{dom}\, R$ 及单值性得 $f(v) = G(f \upharpoonright W_{< v})$ ）。于是 $(w, G(f)) \in R$ ，与 $w \notin \operatorname{dom}\, R$ 矛盾。
故 $R$ 就是所求的函数 $F$ ，由 ① 唯一。
④ 超限归纳。 设 $W \setminus S$ 非空，取它的最小元 $w$ 。则 $W_{< w} \subseteq S$ ，由假设 $w \in S$ ，矛盾。故 $S = W$ 。∎

① 是唯一性、②③ 是存在性。整个证明里只用了良序性、幂集公理和分离公理模式 —— 没有用到选择公理。这是它能在 ZF 里安全使用的原因。

定义引用 4

序数用到本页定义引用

序数的第二条要求是「 $\in$ 在 $\alpha$ 上是良序」—— 先有良序集这个概念，才能说传递集上的 $\in$ 是不是良序。
超限递归用到本页定义引用

递归定理的舞台是良序集：每一步之前的部分必须是有头有尾的，递归才停得下来。
良序定理用到本页定义引用

良序定理断言「每个集合都能被良序化」，用到的正是良序集这个概念。
Hartogs 定理用到本页定义引用

Hartogs 数取的是「最小的那种序数」，而序数就是传递的良序集。

谁指向它（入边）

定义引用 2

偏序集 → 本页定义引用

良序集首先是全序集（从而也是偏序集），只是在它上面加了「非空子集有最小元」。
子集 → 本页定义引用

「 $W$ 的每个非空子集都有最小元」——良序性是靠子集量词说出来的。

类比 1

有限特征类比

两种「用有限/最小的东西控制无穷」的手法

两个定义都在回答同一个问题：面对一个无穷对象，怎么下手？
良序（def.wellorder）：要求「每个非空子集都有最小元」。有了最小元，就能做超限归纳、超限递归 —— 把「一步」规范化，无穷就被结构化了。
有限特征（def.finchar）：要求「整体属于 $\mathcal{A} \iff$ 每个有限子集都属于 $\mathcal{A}$ 」。于是验证一个无穷对象，只需要逐个检查它的有限片段 —— 无穷被压缩成有限。
共同的招：都不去正面描述无穷，而是找一个有限的抓手 （一个最小元 / 一个有限子集），让无穷变得可验证、可操作。
💡 这个招在数学里到处都是（紧致性、有限生成、可数逼近……）。

参考

Kunen, Set Theory, I.11

常见问法 1 条

超限归纳怎么做也看超限递归、序数

同一星团的其他概念 6 个

偏序集layer 5
界与确界layer 6
链layer 6
序同构layer 6
有限特征layer 7

继续

在星图里打开「良序集」　·　全部 709 个概念　·　 Markdown 原文　·　读图指南与记号表