自反 Reflexive 自己到自己
每个元素都和自身相关。
对所有 s ∈ S，都有 s R s
2.2 有序集：先理解关系的四个性质
二元关系可以先粗略想成“两个元素之间画箭头”。这些性质描述箭头应该满足什么规律。
对称 Symmetric 双向
如果 s 能到 t，那么 t 也能到 s。
s R t ⇒ t R s
传递 Transitive 可接力
如果 s 到 t，t 到 u，那么 s 也到 u。
s R t ∧ t R u ⇒ s R u
反对称 Antisymmetric 互相小于只能相等
如果 s 到 t 且 t 到 s，那么它们其实是同一个元素。
s R t ∧ t R s ⇒ s = t
| 概念 | 需要哪些性质 | 直觉 | 典型想法 |
|---|---|---|---|
| 预序 preorder | 自反 + 传递 | 可以比较“可达性”或“弱顺序”，允许两个不同元素互相可达。 | s ≤ t 表示 s 不超过 t；s < t 表示 s ≤ t 且 s ≠ t。 |
| 偏序 partial order | 预序 + 反对称 | 真正有“高低层级”的顺序，但不是任意两点都能比较。 | 集合包含关系 ⊆ 是偏序。 |
| 全序 total order | 偏序 + 任意两个元素可比较 | 所有元素都能排成一条线。 | 自然数上的 ≤ 是全序。 |
| 等价关系 equivalence | 自反 + 对称 + 传递 | 把元素分成若干“同类”。 | “模 n 同余”是一种等价关系。 |
Join：最小上界
j 是 s 和 t 的 join，意思是 j 同时在 s、t 上面，而且在所有共同上界里，j 是最低的那个。
s ≤ j ∧ t ≤ j，并且任意共同上界 k 都满足 j ≤ k
Meet：最大下界
m 是 s 和 t 的 meet，意思是 m 同时在 s、t 下面，而且在所有共同下界里，m 是最高的那个。
m ≤ s ∧ m ≤ t，并且任意共同下界 n 都满足 n ≤ m
2.3 序列：逗号既能加元素，也能拼序列
TAPL 这里的约定很轻量：序列就是用逗号隔开的元素列表，空序列写成 bullet 或留空。
例子复盘
设 a 是序列 3, 2, 1；b 是序列 5, 6。
0, a =0321
a, 0 =3210
b, a =56321
需要记住的约定
1..n 表示从 1 到 n 的序列，中间只有两个点。
|a| 表示序列 a 的长度。
permutation 表示两个序列包含完全相同的元素，只是顺序可能不同。
逗号同时表示 cons 和 append；只要不讨论“序列的序列”，通常不会混淆。
2.4 归纳法：证明无限对象的工具箱
归纳法的核心感觉是：只要能从“更小情况已经成立”推出“当前情况成立”，就能覆盖所有情况。
普通归纳 一步接一步
证明 P(0)，再证明 P(i) 能推出 P(i+1)，于是所有自然数 n 都满足 P(n)。
P(0) ∧ ∀i. P(i) ⇒ P(i+1) ⟹ ∀n. P(n)
完全归纳 依赖所有更小项
证明每个 n 时，可以假设所有 i < n 的 P(i) 都已经成立。
若 ∀n. (∀i<n. P(i)) ⇒ P(n)，则 ∀n. P(n)
字典序归纳：二维版本的“更小情况”
你问“这个公理应该怎么理解”，关键就在于把 (m,n) 想成二维表格里的一个格子。
正在证明 P(2,3)
蓝色格子是字典序上已经可以假设成立的情况；黄色格子是当前要证明的情况。
(0,0)
(0,1)
(0,2)
(0,3)
(0,4)
(0,5)
(1,0)
(1,1)
(1,2)
(1,3)
(1,4)
(1,5)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(2,5)
(3,0)
(3,1)
(3,2)
(3,3)
(3,4)
(3,5)
蓝色：m' < m 的所有行，或同一行 n' < n
黄色：当前目标
一句话理解
对一对自然数 (m,n) 做归纳：如果每一格只依赖它之前所有“更小的格子”，那整张无限表格上的所有格子都成立。
(m',n') < (m,n) 当且仅当 m' < m，或 m'=m 且 n'<n
这就是嵌套归纳的抽象写法：外层对 m 归纳，固定 m 后内层再对 n 归纳。
普通归纳像一条线
0, 1, 2, 3... 每次只往前走一步。
完全归纳像看左边全部
证明 n 时，左边所有小于 n 的点都可以作为前提。
字典序归纳像读表格
先读完上一行，再读当前行左边的格子，然后证明当前格子。
闭包：给关系补上缺失性质
闭包的关键词是“最小”。不是随便扩展，而是在满足某性质的前提下，尽量少加东西。
自反闭包
给 R 补上所有 (s,s)，让每个元素都和自己相关。
R' = R ∪ {(s,s) | s ∈ S}
传递闭包
给 R 补上所有通过多步能到达的关系，通常记作 R+。
若 a R b 且 b R c，就需要补出 a R c
自反且传递闭包
同时补自反性和传递性，通常记作 R*。
R* 包含“走 0 步或多步”的可达关系
最小的含义
如果另一个关系也包含 R 且满足目标性质，那么闭包一定包含在那个关系里面。
若 R'' 也满足要求，则 R' ⊆ R''
练习 2.2.6：为什么 R ∪ {(s,s) | s ∈ S} 是 R 的自反闭包？
先证明它包含 R。 因为 R' 是 R 和另一组有序对的并集，所以 R ⊆ R'。
再证明它自反。 对任意 s ∈ S，(s,s) 都被显式加入到 R' 里，所以 R' 是自反的。
最后证明它最小。 任取一个自反关系 R''，并且 R ⊆ R''。因为 R'' 自反，所以所有 (s,s) 都在 R'' 里；又因为 R 中的对也都在 R'' 里，所以 R' 的所有元素都在 R'' 里，即 R' ⊆ R''。
结论。 R' 既包含 R，又自反，并且在所有满足这两个条件的关系里最小，所以它就是 R 的自反闭包。