第三章　关系、函数与特殊关系

本章在前两章的集合与类运算基础上，介绍如何用有序对表示关系和函数，再讨论序关系、良基性、初始段以及关系的同构。

小写字母仍表示集合，大写字母表示允许带集合参数的可定义类。所有对象量词只取遍集合；关于任意可定义类的陈述，按相应公式的模式理解。记号 (0)、(V)、(\langle a,b\rangle)、(\cup(A)) 均沿用前两章。本章不使用选择公理。

目录最后一种函数同时满足单射与满射条件，应称为“双射”。本文约定 (A\circ B) 表示“先 (B)，后 (A)”。founded 与 well founded 在不同教材中用法不完全相同，第 7 节会明确本章的约定。

6. （二元）关系和函数

6.1 多变量量词与取值类记号

连续量化的缩写

对互不相同的变量 (x_1,\ldots,x_n)，约定：

[ \forall x_1,\ldots,x_n,\phi;\coloneqq;\forall x_1\cdots\forall x_n,\phi, ]

[ \exists x_1,\ldots,x_n,\phi;\coloneqq;\exists x_1\cdots\exists x_n,\phi. ]

同样，限制量词的连续记号表示逐个限制：

[ \forall x,y\in A,\phi(x,y) ;\coloneqq; \forall x\in A,\forall y\in A,\phi(x,y), ]

[ \exists x,y\in A,\phi(x,y) ;\coloneqq; \exists x\in A,\exists y\in A,\phi(x,y). ]

这里仍要求避免变量捕获；上式中的类 (A) 不以 (x,y) 为自由参数。

连续的全称量词可以交换顺序，连续的存在量词也可以交换顺序。但不同种类的量词一般不能交换。例如：

[ \forall x,\exists y,(x\in y) ]

与

[ \exists y,\forall x,(x\in y) ]

含义不同。前者允许 (y) 随 (x) 改变，由单元素集的存在性成立；后者要求同一个集合包含所有集合，与 (V) 是真类矛盾。

由表达式生成的类

设 (f(x_1,\ldots,x_n)) 是已定义的集合值表达式，即在所讨论的输入处唯一确定一个集合。定义：

[ \begin{aligned} &{f(x_1,\ldots,x_n)\mid\phi(x_1,\ldots,x_n)}\ &\quad\coloneqq {y\mid\exists x_1,\ldots,x_n, (y=f(x_1,\ldots,x_n)\land\phi(x_1,\ldots,x_n))}. \end{aligned} ]

其中 (y) 必须选为新变量；所有代入均须避免变量捕获。其他自由变量作为参数保留。

这只是类记号，不宣告生成的类一定是集合。这里的 (f) 也不是新增的原始函数符号，而是已经能够用原语言定义的表达式。例如：

[ {{x}\mid x\in a}={y\mid\exists x,(x\in a\land y={x})}. ]

其中 (y={x}) 可继续展开为 (\forall z,(z\in y\leftrightarrow z=x))。

本小节的表达式记号与后面的图式函数取值记号须区分：对于作为有序对类的函数 (F)，本文使用 (F`x)，不使用 (F(x))。

6.2 笛卡尔积

对任意可定义类 (A,B)，定义：

[ A\times B\coloneqq{\langle x,y\rangle\mid x\in A\land y\in B}. ]

利用第二章定理 4.1 的有序对识别性质：

[ \langle a,b\rangle\in A\times B\leftrightarrow(a\in A\land b\in B). ]

(A\times B) 称为 (A,B) 的笛卡尔积。它的成员是有序对，不是分别列出的坐标。

一般不能交换两个因子的次序：(A\times B) 与 (B\times A) 不一定相等。另外：

[ A\times0=0=0\times A. ]

定理 6.1　集合的笛卡尔积是集合

[ a\times b\in V. ]

证明。 令 (u=a\cup b)，这是集合。若 (x\in a) 且 (y\in b)，则：

[ {x}\subseteq u,\qquad{x,y}\subseteq u. ]

所以：

[ \langle x,y\rangle={{x},{x,y}}\subseteq\mathcal P(u), ]

从而：

[ \langle x,y\rangle\in\mathcal P(\mathcal P(u)). ]

因此 (a\times b) 是集合 (\mathcal P(\mathcal P(u))) 的可定义子类，由第二章定理 5.1 的分离模式，它是集合。证毕。

6.3 逆类与二元关系

对任意类 (A)，定义：

[ A^{-1}\coloneqq{\langle x,y\rangle\mid\langle y,x\rangle\in A}. ]

它交换 (A) 中有序对的两个坐标；(A) 中不是有序对的成员不会产生任何输出。

例如：

[ {\langle a,b\rangle}^{-1}={\langle b,a\rangle}. ]

定义：

[ A\text{ 是关系};\coloneqq;A\subseteq V\times V. ]

也就是说，关系的每个成员都是两个集合构成的有序对。

定义：

[ A\text{ 是 }B\text{ 上的关系};\coloneqq;A\subseteq B\times B. ]

“(B) 上的关系”只说明坐标都在 (B) 中，不要求每个 (B) 的元素实际出现在某个有序对里。

对任意类 (A)：

[ (A^{-1})^{-1}=A\cap(V\times V). ]

因此，当 (A) 是关系时才可以直接写：

[ (A^{-1})^{-1}=A. ]

这一限制提醒我们：一些熟悉的关系恒等式，隐含了输入确实是关系的前提。

6.4 单值、一一、函数与单射

定义 (A) 单值，是指：

[ \forall x,y,z,((\langle x,y\rangle\in A\land\langle x,z\rangle\in A)\to y=z). ]

即同一个第一坐标至多对应一个第二坐标。

定义 (A) 一一，是指 (A) 和 (A^{-1}) 都单值。后一个条件等价于：

[ \forall x,y,z,((\langle x,z\rangle\in A\land\langle y,z\rangle\in A)\to x=y). ]

它要求同一个第二坐标至多来自一个第一坐标。

定义：

[ A\text{ 是函数};\coloneqq;(A\text{ 是关系且单值}), ]

[ A\text{ 是单射};\coloneqq;(A\text{ 是关系且一一}). ]

所以每个单射都是函数，但函数不一定是单射。

单独的“单值”条件不会排除非有序对成员。例如 ({0}) 没有任何有序对成员，因而单值条件真空成立；但它不是关系，也就不是函数。这里 (0) 不是有序对，因为任何 Kuratowski 有序对都含有一个单元素集作为成员，因而非空。

一个有限例子

令 (u=0)、(v={0})，则 (u\ne v)。

[ F={\langle u,u\rangle,\langle v,u\rangle} ]

是函数，但不是单射：两个不同输入具有同一输出。

[ G={\langle u,u\rangle,\langle u,v\rangle} ]

不是函数，因为输入 (u) 有两个不同输出。

[ H={\langle u,v\rangle,\langle v,u\rangle} ]

是单射。

6.5 定义域与值域

对任意类 (A)，不要求它是关系，定义：

[ \operatorname{Dom}(A)\coloneqq{x\mid\exists y,(\langle x,y\rangle\in A)}, ]

[ \operatorname{Ran}(A)\coloneqq{y\mid\exists x,(\langle x,y\rangle\in A)}. ]

它们分别称为 (A) 的定义域和值域。这两个运算只读取有序对成员，忽略其他成员。

由定义：

[ \operatorname{Dom}(A^{-1})=\operatorname{Ran}(A), ]

[ \operatorname{Ran}(A^{-1})=\operatorname{Dom}(A). ]

若 (R) 是关系，则：

[ R\subseteq\operatorname{Dom}(R)\times\operatorname{Ran}(R). ]

定理 6.2　集合的定义域和值域都是集合

对任意集合 (a)：

[ \operatorname{Dom}(a)\in V,\qquad\operatorname{Ran}(a)\in V. ]

证明。 若 (\langle x,y\rangle\in a)，由 Kuratowski 定义：

[ {x}\in\langle x,y\rangle,\qquad{x,y}\in\langle x,y\rangle. ]

所以 ({x}) 和 ({x,y}) 都属于 (\cup(a))，进而 (x,y\in\cup(\cup(a)))。因此：

[ \operatorname{Dom}(a)\subseteq\cup(\cup(a)),\qquad\operatorname{Ran}(a)\subseteq\cup(\cup(a)). ]

右边是集合，再用分离即得结论。证毕。

这个证明不要求 (a) 本身是关系。

由此还可推出 (a^{-1}\in V)：它是集合 (\operatorname{Ran}(a)\times\operatorname{Dom}(a)) 的可定义子类。

6.6 限制与像

对任意类 (A,B)，定义 (A) 在 (B) 上的限制：

[ A\upharpoonright B\coloneqq A\cap(B\times V). ]

于是：

[ \langle x,y\rangle\in A\upharpoonright B\leftrightarrow(\langle x,y\rangle\in A\land x\in B). ]

限制保留第一坐标属于 (B) 的有序对；它同时删除所有非有序对成员。

定义 (B) 在 (A) 下的像：

[ A``B\coloneqq\operatorname{Ran}(A\upharpoonright B). ]

展开为：

[ y\in A``B\leftrightarrow\exists x\in B,(\langle x,y\rangle\in A). ]

这里的两个反引号是像记号；后面一个反引号用于取值，两者不要混淆。

由定义可验证：

[ \operatorname{Dom}(A\upharpoonright B)=\operatorname{Dom}(A)\cap B, ]

[ (A\upharpoonright B)\upharpoonright C=A\upharpoonright(B\cap C), ]

[ A(B\cup C)=(AB)\cup(A``C), ]

[ A``0=0. ]

例如，第三个等式来自：存在一个属于 (B\cup C) 的输入，等价于存在属于 (B) 的输入或存在属于 (C) 的输入。

一般只有：

[ A(B\cap C)\subseteq(AB)\cap(A``C), ]

反向包含不一定成立，因为同一个输出可以分别来自两个不同输入。

若 (a) 是集合，则 (a\upharpoonright B) 是集合，因而 (aB\) 也是集合。但若只有输入类 \(B=b\) 是集合，任意类关系 \(A\) 的像 \(Ab) 未必是集合。例如：

[ ({0}\times V)``{0}=V. ]

函数的单值性将使“集合输入产生集合像”成立，见定理 6.3。

6.7 关系的复合

对任意类 (A,B)，定义：

[ A\circ B\coloneqq{\langle x,y\rangle\mid\exists z,(\langle x,z\rangle\in B\land\langle z,y\rangle\in A)}. ]

这个约定表示：

[ x\mathrel{B}z\mathrel{A}y. ]

即先沿 (B) 从 (x) 到 (z)，再沿 (A) 从 (z) 到 (y)。复合的书写顺序与实际经过关系的顺序相反，计算时应先读右边。

例如：

[ {\langle b,c\rangle}\circ{\langle a,b\rangle}={\langle a,c\rangle}. ]

复合总是关系，并满足：

[ \operatorname{Dom}(A\circ B)\subseteq\operatorname{Dom}(B),\qquad\operatorname{Ran}(A\circ B)\subseteq\operatorname{Ran}(A). ]

包含可能严格，因为第一次得到的输出不一定能进入第二个关系。

复合的结合律

[ (A\circ B)\circ C=A\circ(B\circ C). ]

证明。 两边关于 (\langle x,y\rangle) 的成员条件都等价于：

[ \exists u,v,(\langle x,u\rangle\in C\land\langle u,v\rangle\in B\land\langle v,y\rangle\in A). ]

由类相等的定义得到结论。证毕。

逆与复合满足：

[ (A\circ B)^{-1}=B^{-1}\circ A^{-1}. ]

这是因为反向走完整条路径时，经过两个关系的顺序也随之颠倒。

对集合 (a,b)，(a\circ b) 是 (\operatorname{Dom}(b)\times\operatorname{Ran}(a)) 的可定义子类，因此也是集合。

6.8 存在唯一与单元素类

定义存在唯一量词：

[ \exists!x,\phi(x);\coloneqq;\exists x,(\phi(x)\land\forall y,(\phi(y)\to y=x)). ]

其中 (y) 是新变量。它同时要求至少存在一个满足条件的对象，以及任何两个满足条件的对象都相等。

定义 (A) 是单元素类，或简称单元集，是指：

[ \exists x,(A={x}). ]

这等价于：

[ \exists!x,(x\in A). ]

证明。 若 (A={a})，它恰有成员 (a)。反之，若 (a) 是 (A) 的唯一成员，则对任意 (x)，(x\in A\leftrightarrow x=a)，所以 (A={a})。证毕。

每个单元素类都是集合，因为它等于配对公理保证存在的单元素集。记号 (\exists!x:x\in A) 与 (\exists!x,(x\in A)) 表示同一件事。

6.9 提取运算

定义：

[ \operatorname{ext}(A)\coloneqq \begin{cases} 0,&A\text{ 不是单元集},\ \cup(A),&A\text{ 是单元集}. \end{cases} ]

称为提取运算。若 (A={a})，则：

[ \operatorname{ext}(A)=\cup({a})=a. ]

因此它提取单元素类的唯一成员；没有唯一成员时，统一返回空集。

对任意可定义类 (A)，(\operatorname{ext}(A)) 都是集合：单元素情形返回其集合成员，其他情形返回 (0)。

这不是把所有类作为一个集合定义域的普通函数。它是关于类记号的可定义运算，可以逐次展开为原语言公式。例如 (y=\operatorname{ext}(A)) 表示：

[ (A={y})\lor(y=0\land\neg\exists u,(A={u})). ]

特别地：

[ \operatorname{ext}(0)=0,\qquad\operatorname{ext}({0})=0. ]

所以仅凭提取结果为 (0)，不能判断原类是空类还是单元素类。

6.10 单点取值

对任意类 (A) 和集合 (b)，定义：

[ A`b\coloneqq\operatorname{ext}(A``{b}). ]

而：

[ A``{b}={y\mid\langle b,y\rangle\in A}. ]

因此 (A`b) 按以下规则计算：若从 (b) 出发恰有一个输出，就返回该输出；若没有输出，或存在多个不同输出，就返回 (0)。

对函数 (F)，若 (b\in\operatorname{Dom}(F))，则：

[ F``{b}={F`b}, ]

并且：

[ \langle b,y\rangle\in F\leftrightarrow y=F`b. ]

不预先假设 (b) 在定义域内时，正确的完整表述是：

[ \langle b,y\rangle\in F\leftrightarrow(b\in\operatorname{Dom}(F)\land y=F`b). ]

若 (b\notin\operatorname{Dom}(F))，则 (F`b=0)。但反方向不成立：(0) 也可以是定义域内的合法函数值。

例如空函数 (0) 与函数 ({\langle0,0\rangle}) 在每个集合处的取值都等于 (0)，它们仍是不同的图。因此，比较函数不能只比较这一约定下的所有取值，还要比较定义域。

函数的外延性

若 (F,G) 都是函数，则：

[ \begin{aligned} F=G\quad\leftrightarrow\quad \bigl(&\operatorname{Dom}(F)=\operatorname{Dom}(G)\ &\land\forall x\in\operatorname{Dom}(F),(Fx=Gx)\bigr). \end{aligned} ]

证明。 正方向直接成立。反方向中，两函数定义域相同，且每个定义域元素所对应的唯一输出相同，所以它们具有完全相同的有序对成员。证毕。

6.11 从一个类到另一个类的函数

定义：

[ F:A\to B ]

表示 (F) 是函数，且：

[ \operatorname{Dom}(F)=A,\qquad\operatorname{Ran}(F)\subseteq B. ]

这里 (B) 称为指定的陪域。它不一定等于值域。本文把函数本身定义为图，所以陪域不是函数图中额外存储的一部分；同一个图可以具有不同的合法陪域。

定义 (F:A\to B) 是满射，是指：

[ F\text{ 是函数},\qquad\operatorname{Dom}(F)=A,\qquad\operatorname{Ran}(F)=B. ]

定义 (F:A\to B) 是单射，是指：

[ F\text{ 是单射},\qquad\operatorname{Dom}(F)=A,\qquad\operatorname{Ran}(F)\subseteq B. ]

定义 (F:A\to B) 是双射，是指：

[ F\text{ 是单射},\qquad\operatorname{Dom}(F)=A,\qquad\operatorname{Ran}(F)=B. ]

因此双射恰好是既单射又满射的函数。对已经满足 (F:A\to B) 的函数，常用的等价条件为：

[ F\text{ 单射}\leftrightarrow\forall x,y\in A,(Fx=Fy\to x=y), ]

[ F\text{ 满射}\leftrightarrow\forall y\in B,\exists x\in A,(F`x=y). ]

空类 (0) 是函数，也是单射。对任意 (B)，都有 (0:0\to B)，但它仅在 (B=0) 时是满射。

6.12 类函数在集合上的像

定理 6.3

若 (F) 是函数，(a) 是集合，则：

[ F``a\in V,\qquad F\upharpoonright a\in V. ]

这里不要求 (F) 本身是集合，也不要求 (a\subseteq\operatorname{Dom}(F))。

证明。 取公式：

[ \phi(x,y)\equiv\langle x,y\rangle\in F. ]

(F) 的单值性保证每个输入至多有一个输出。因此由第二章 A5 的部分对应形式：

[ {y\mid\exists x\in a,\phi(x,y)}=F``a\in V. ]

再注意：

[ F\upharpoonright a\subseteq a\times(F``a). ]

右边是集合，由分离，限制也是集合。证毕。

特别地，若 (F) 的定义域是集合 (a)，则 (F=F\upharpoonright a)，所以 (F) 本身是集合。

这说明替代公理可以表述为一个直观原则：可定义类函数作用于集合时，其实际输出组成集合。

6.13 函数的复合、恒等函数与逆函数

设 (F:A\to B)、(G:B\to C)，则：

[ G\circ F:A\to C, ]

且对每个 (x\in A)：

[ (G\circ F)x=G(F`x). ]

证明。 (x\in A) 唯一确定 (Fx\in B\)，再唯一确定 \(G(F`x)\in C)。因此复合对每个 (A) 中的输入恰有一个输出，且不会出现其他输入。证毕。

若两者都是单射，则复合是单射；若两者都是满射，则复合是满射；若两者都是双射，则复合是双射。这些结论分别由消去相等的输出和逐层寻找原像得到。

定义 (A) 上的恒等函数：

[ \operatorname{id}_A\coloneqq{\langle x,x\rangle\mid x\in A}. ]

它是 (A) 到自身的双射，且 (\operatorname{id}_A`x=x) 对 (x\in A) 成立。若 (F:A\to B)，则：

[ F\circ\operatorname{id}_A=F,\qquad\operatorname{id}_B\circ F=F. ]

对函数 (F)，(F^{-1}) 是函数当且仅当 (F) 是单射。若 (F:A\to B) 是双射，则：

[ F^{-1}:B\to A ]

也是双射，并且：

[ F^{-1}\circ F=\operatorname{id}_A,\qquad F\circ F^{-1}=\operatorname{id}_B. ]

对于仅为单射的 (F:A\to B)，逆函数的定义域是 (\operatorname{Ran}(F))，不能擅自把它扩大为整个 (B)。

第 6 节练习

练习 6.1：两次取逆

证明对任意类 (A)，((A^{-1})^{-1}=A\cap(V\times V))，并以 (A={0}) 说明关系前提不可省略。

练习 6.2：像不保持交

令 (u=0)、(v={0})，(F={\langle u,u\rangle,\langle v,u\rangle})。比较 (F(\{u\}\cap\{v\})\) 与 \((F{u})\cap(F``{v}))。

练习 6.3：单射保持交

若 (F) 是单射，证明 (F(A\cap B)=(FA)\cap(F``B))。

练习 6.4：单点取值与图

解释为什么 (F`b=0) 不能推出 (b\notin\operatorname{Dom}(F))，并说明函数外延性中为什么必须要求定义域相同。

第 6 节练习参考解答

练习 6.1 解答

(\langle x,y\rangle) 属于两次取逆的结果，当且仅当它原本属于 (A)；两次取逆的结果没有任何非有序对成员。因此结果正是 (A\cap(V\times V))。若 (A={0})，则 (A^{-1}=0)，两次取逆仍为 (0\ne A)。

练习 6.2 解答

因为 (u\ne v)，({u}\cap{v}=0)，所以左边的像为空集。另一方面，两单元素集的像都为 ({u})，其交仍为 ({u})。

练习 6.3 解答

从左向右的包含对任意关系都成立。反过来，若 (y\in(FA)\cap(FB))，则存在 (a\in A)、(b\in B)，使 (\langle a,y\rangle,\langle b,y\rangle\in F)。单射性给出 (a=b)，所以这个共同输入属于 (A\cap B)，进而 (y\in F``(A\cap B))。

练习 6.4 解答

函数 ({\langle0,0\rangle}) 在定义域元素 (0) 处的值就是 (0)。它与空函数在所有集合处的默认取值均相同，但定义域分别为 ({0}) 和 (0)，因此图不同。

7. 特殊的关系

7.1 关系记号与承载类

约定：

[ aRb;\coloneqq;\langle a,b\rangle\in R. ]

“(R) 是 (A) 上的关系”始终包含 (R\subseteq A\times A) 这个要求。讨论自反、全序或极小元时，要明确这个承载类 (A)。

同一个关系图可以放在不同承载类上，但性质可能改变。例如 (0) 在空类上自反；在任意非空类上不自反。

若 (B\subseteq A)，则 (R) 在 (B) 上的诱导关系是：

[ R\cap(B\times B). ]

它与第 6 节的 (R\upharpoonright B) 不同：后者只限制第一坐标，而诱导关系限制两个坐标。

7.2 偏序与全序

设 (R\subseteq A\times A)。定义以下性质。

自反性：

[ \forall x\in A,(xRx). ]

反对称性：

[ \forall x,y\in A,((xRy\land yRx)\to x=y). ]

传递性：

[ \forall x,y,z\in A,((xRy\land yRz)\to xRz). ]

若三者都成立，就称 (R) 是 (A) 上的偏序。

反对称不表示两个方向绝不同时成立；当 (x=y) 时，自反性正要求它们成立。它排除的是不同元素之间的双向比较。

若偏序还满足完全性：

[ \forall x,y\in A,(xRy\lor yRx), ]

则称为全序，也称线序。它要求任意两个元素都可以比较。

例如包含关系：

[ {\langle x,y\rangle\mid x\in\mathcal P(a)\land y\in\mathcal P(a)\land x\subseteq y} ]

是 (\mathcal P(a)) 上的偏序，但一般不是全序。若 (u\ne v) 都属于 (a)，则 ({u}) 与 ({v}) 互不包含。

7.3 严格偏序与严格全序

设 (R\subseteq A\times A)。称 (R) 非自反，是指：

[ \forall x\in A,\neg(xRx). ]

这里的意思是每个元素都不与自身相关，不只是“自反性没有成立”。

若 (R) 非自反且传递，则称为严格偏序。它自动满足非对称性：

[ xRy\to\neg(yRx), ]

因为若两方向同时成立，传递性会给出 (xRx)。

若严格偏序还满足：

[ \forall x,y\in A,(x\ne y\to(xRy\lor yRx)), ]

则称为严格全序。此时对任意 (x,y\in A)，(xRy)、(x=y)、(yRx) 三种情况恰有一种成立。

严格形式与非严格形式的转换

以下两个转换都在固定承载类 (A) 内进行，所列变量均属于 (A)。若 (\preccurlyeq) 是偏序，定义：

[ x\prec y\leftrightarrow(x\preccurlyeq y\land x\ne y). ]

则 (\prec) 是严格偏序。反过来，若 (\prec) 是严格偏序，定义：

[ x\preccurlyeq y\leftrightarrow(x\prec y\lor x=y), ]

则 (\preccurlyeq) 是偏序。两种构造互相还原，并且全序与严格全序也相互对应。

例如严格形式的传递性可这样验证：若 (x\prec y\prec z)，原偏序给出 (x\preccurlyeq z)；若 (x=z)，原偏序的反对称性会迫使 (x=y)，矛盾，故 (x\prec z)。

7.4 前驱类与 (R)-极小元

对关系 (R) 和集合 (x)，定义其前驱类：

[ \operatorname{Pred}_R(x)\coloneqq{y\mid yRx}. ]

用第 6 节的像记号表示，就是：

[ \operatorname{Pred}_R(x)=R^{-1}``{x}. ]

这里必须取逆，因为原关系中的前驱在第一坐标，而 (R``{x}) 收集的是满足 (xRy) 的后继。

设 (B\subseteq A)。称 (x) 是 (B) 的一个 (R)-极小元，是指：

[ x\in B\land\neg\exists y\in B,(yRx). ]

等价地：

[ x\in B\land B\cap\operatorname{Pred}_R(x)=0. ]

极小元不要求唯一，也不要求能与所有其他元素比较。

对严格全序，极小元就是最小元：若 (x) 极小，任取 (y\in B\setminus{x})，完全性给出 (yRx) 或 (xRy)，前者被极小性排除，故 (xRy)。最小元因此唯一。

本章后续的极小性和良基性使用这个“没有前驱”的定义。对于自反偏序，应先转成严格关系；否则 (xRx) 会使每个元素都成为自己的前驱。

7.5 Founded 关系

对于类关系，必须说明“每个非空部分”允许是集合还是任意可定义类。本章采用以下约定。

称 (R) 是 (A) 上的 founded 关系，是指 (R\subseteq A\times A)，并且每个非空可定义子类 (B\subseteq A) 都有 (R)-极小元。

也就是对每个这样的 (B)，有：

[ B\ne0\to\exists x\in B,\neg\exists y\in B,(yRx). ]

这是关于定义 (B) 的公式的模式，不能把它误写成 ZF 对象量词直接取遍任意类。

若承载对象 (A=a) 本身是集合，则它的每个可定义子类都由分离成为集合。因此，在集合承载的情形，这与“每个非空子集都有极小元”的通常表述一致。

定理 7.1　Founded 关系非自反，且没有有限环

若 (R) 在 (A) 上 founded，则：

[ \forall x\in A,\neg(xRx), ]

并且不存在固定有限长度的环：

[ a_1Ra_2,\ a_2Ra_3,\ \ldots,\ a_nRa_1. ]

证明。 若 (xRx)，单元素集 ({x}) 没有极小元。若存在有限环，则类 ({a_1,\ldots,a_n}) 的每个成员都有一个仍在此类中的前驱，也没有极小元。两者都与 founded 性矛盾。证毕。

Founded 性不包含传递性，也不包含完全性。不能据此把关系直接当成严格偏序或全序。

7.6 Well founded：加上前驱为集合的条件

称 (R) 在 (A) 上是集合式的（set-like），是指：

[ \forall x\in A,(\operatorname{Pred}_R(x)\in V). ]

即每个元素的前驱类都是集合。

本章称 (R) 在 (A) 上 well founded（良基），是指它在 (A) 上 founded，且是集合式的。

有些教材直接把 founded 所表达的性质称为 well founded，并把 set-like 单独列出；也有教材先只量化非空集合子集。阅读其他资料时，应检查定义，尤其不要在真类承载的情形无说明地互换这些版本。

若 (A=a) 是集合，则任意 (R\subseteq a\times a) 都是集合，而每个前驱类都是 (a) 的子集，因而自动是集合。此时，本章 founded 与 well founded 没有区别。

一个 founded 但不 well founded 的类关系

令：

[ R=(V\setminus{0})\times{0}. ]

它只把每个非空集合连向 (0)。若非空类 (B) 含非空集合 (b)，则 (b) 没有任何 (R)-前驱，因而极小；若 (B) 不含非空集合，则 (B={0})，其中 (0) 也极小。所以 (R) founded。

但：

[ \operatorname{Pred}_R(0)=V\setminus{0} ]

是真类。否则将它与 ({0}) 作并便得到集合 (V)，矛盾。因此 (R) 不是集合式的，也就不是本章意义下的 well founded。

7.7 Well ordering：良序

称 (R) 是 (A) 上的 well ordering（良序），是指它是 (A) 上的严格全序，并且 well founded。

因此本章的良序有三项要求：严格全序；每个非空可定义子类有极小元；每个元素的前驱类是集合。严格全序保证这些极小元实际上是唯一的最小元。

在集合 (a) 上，最后一项自动成立，所以定义化为通常的表述：

一个严格全序是良序，当且仅当每个非空子集都有最小元。

如果使用自反的非严格良序记号，则应先去掉对角线，得到本章的严格良序关系，再谈“没有前驱”的极小性。

最小元的唯一性

设 (x,y) 都是非空子类 (B) 的极小元。若 (x\ne y)，严格全序给出 (xRy) 或 (yRx)，任一情况都与其中一个元素的极小性矛盾。故 (x=y)。

空类上的空关系也算良序：所有条件均真空成立。良序只要求非空子类有最小元，不要求空类有最小元。

7.8 初始段

设 (R\subseteq A\times A)。对于 (x\in A)，称：

[ I_R(x)\coloneqq\operatorname{Pred}_R(x)=R^{-1}``{x} ]

为由 (x) 截出的主初始段或 (x) 之前的段。

另外，称子类 (I\subseteq A) 是一个 (R)-初始段，是指它向前驱封闭：

[ \forall x\in I,\forall y\in A,(yRx\to y\in I). ]

在这个广义用法下，(0) 和 (A) 本身都算初始段。“真初始段”再要求 (I\ne A)。

对一般非传递关系，前驱类未必向前驱封闭。若 (R) 传递，则每个 (I_R(x)) 都是初始段：由 (zRy) 和 (yRx) 得 (zRx)。

若 (R) 非自反，则 (x\notin I_R(x))；若 (R) well founded，则 (I_R(x)) 是集合。

定理 7.2　良序的真初始段是主初始段

设 (R) 是 (A) 上的良序，(I\subset A) 是可定义初始段。则存在唯一 (x\in A)，使：

[ I=I_R(x). ]

证明。 因为 (A\setminus I\ne0)，它有唯一最小元 (x)。

若 (yRx)，则 (y) 不可能也在 (A\setminus I) 中，否则违反 (x) 的极小性。因此 (y\in I)，即 (I_R(x)\subseteq I)。

反过来，若 (y\in I)，则 (y\ne x)。由严格全序，(yRx) 或 (xRy)。若 (xRy)，初始段的封闭性给出 (x\in I)，矛盾。所以 (yRx)，从而 (I\subseteq I_R(x))。

最后，若不同的 (x,z) 截出相同的段，不妨有 (xRz)。则 (x\in I_R(z))，但 (x\notin I_R(x))，矛盾。证毕。

根据本章对良序的集合式要求，每个可定义真初始段因此都是集合。

7.9 非空子类的极小元公式

定理 7.3

设 (R) 是 (A) 上的 well founded 关系。若 (B\subseteq A) 且 (B\ne0)，则：

[ \exists x\in B,(B\cap(R^{-1}``{x})=0). ]

特别地，当 (R) 是良序时结论成立，而且满足条件的 (x) 唯一。

证明。 Well founded 包含 founded 性，因此 (B) 有 (R)-极小元 (x)。而：

[ y\in B\cap(R^{-1}``{x})\leftrightarrow(y\in B\land yRx). ]

极小性正是否定右边对任何 (y) 成立，所以交为空。良序情形的唯一性已在第 7.7 小节证明。证毕。

按本章定义，这个结论是极小性用像记号写出的等价形式；它并不需要另行使用正则公理。只有在证明某个具体关系确实 founded 时，才需要相应依据。

7.10 关系的同构

设 (R) 是 (A) 上的关系，(S) 是 (B) 上的关系。称 (F) 是它们之间的同构，是指 (F:A\to B) 为双射，并且：

[ \forall x,y\in A,(xRy\leftrightarrow(Fx)S(Fy)). ]

记作：

[ F:(A,R)\cong(B,S). ]

这里 ((A,R)) 表示带承载类的关系结构，是元语言中的记号；若 (A) 或 (R) 是真类，不能把它理解为前面已经构造的集合有序对。

双条件很重要：同构既保持关系，也反映关系。只要求 (xRy\to(Fx)S(Fy)) 不足以排除目标结构中出现额外关系。

同构可以理解为对对象作一一重命名，并完整保留哪些对象彼此相关。

恒等、逆与复合

恒等函数是 ((A,R)) 到自身的同构。

若 (F:(A,R)\cong(B,S))，则：

[ F^{-1}:(B,S)\cong(A,R). ]

若另有 (G:(B,S)\cong(C,T))，则：

[ G\circ F:(A,R)\cong(C,T). ]

例如复合的关系条件来自：

[ xRy\leftrightarrow(Fx)S(Fy)\leftrightarrow(G(Fx))T(G(Fy)). ]

定理 7.4　同构保持序性质和良基性

若 (F:(A,R)\cong(B,S))，则 (R) 与 (S) 同时具有偏序、全序、严格偏序、严格全序、founded、well founded 或良序性质。

证明。 自反、反对称、非自反、传递及完全性，均可用双射把任意目标元素唯一写成源元素的像，再用关系双条件逐项转移。

例如若 (uSv) 且 (vSw)，写 (u=Fx\)、\(v=Fy)、(w=F`z)。关系反映性给出 (xRy) 且 (yRz)；若 (R) 传递，则 (xRz)，再由保持性得 (uSw)。

为证明 founded 性，取非空可定义子类 (C\subseteq B)。其原像：

[ D=F^{-1}``C ]

是 (A) 的非空可定义子类。若 (x) 是 (D) 的 (R)-极小元，则 (F`x) 是 (C) 的 (S)-极小元；否则一个位于 (C) 中的前驱可通过 (F^{-1}) 拉回为 (D) 中 (x) 的前驱。

最后，对 (x\in A)，有：

[ \operatorname{Pred}_S(F`x)=F``\operatorname{Pred}_R(x). ]

若 (R) 的前驱类是集合，则由定理 6.3，右边也是集合，所以集合式性质得到保持。应用逆同构即可得到所有反方向。证毕。

同构还把初始段送到初始段，并且：

[ F``I_R(x)=I_S(F`x). ]

这直接来自“一个对象是 (x) 的前驱，当且仅当它的像是 (F`x) 的前驱”。

7.11 隶属关系在 (V) 上的已学性质

为了把原始符号 (\in) 作为本章的关系类讨论，定义：

[ E\coloneqq{\langle x,y\rangle\mid x\in y}. ]

于是 (E\subseteq V\times V)，且：

[ xEy\leftrightarrow x\in y. ]

口头上说“(\in) 在 (V) 上的性质”，指的就是这个关系类。

一、定义域和值域

每个集合 (x) 都属于其单元素集 ({x})，所以：

[ \operatorname{Dom}(E)=V. ]

一个集合有元素当且仅当它不为空，因此：

[ \operatorname{Ran}(E)=V\setminus{0}. ]

由定理 6.2，若 (E) 是集合，则其定义域 (V) 也是集合，矛盾。因此 (E) 是真类关系。

二、逆像与并

对任意集合 (a)：

[ \operatorname{Pred}_E(a)=E^{-1}``{a}=a. ]

因此 (E) 是集合式的：每个集合的所有前驱恰好就是它的元素所组成的集合。

对任意可定义类 (A)，还有：

[ E^{-1}``A=\cup(A). ]

这把第二章的并运算解释为逆隶属关系下的像。注意方向：(E``{a}) 收集的是所有以 (a) 为元素的集合，而不是 (a) 的元素。

三、非自反性与有限环

第二章定理 5.3 给出：

[ \forall a,(a\notin a). ]

所以 (E) 非自反。第二章定理 5.4 排除了所有有限隶属环，特别排除了：

[ a\in b\land b\in a. ]

因此 (E) 也非对称。

四、Founded 与 well founded

正则公理 A6 直接给出：每个非空集合 (a) 都有元素 (x)，使 (x\cap a=0)。这就是 (a) 内的 (E)-极小性。

第二章第 5.7 小节陈述的正则公理类形式进一步给出：

[ A\ne0\to\exists x\in A,(x\cap A=0). ]

借助这个已陈述但尚未证明的加强形式，(E) 在 (V) 上 founded；结合其前驱类等于集合本身，(E) 在本章意义下 well founded。

这里保留前章的证明边界：关于任意非空可定义类的结论依赖正则公理类形式；本章不补入该加强形式所需的后续构造。 对集合子集的极小元结论则已由 A6 直接证明。

五、隶属关系不传递，也不全序

令 (u=0)、(v={0})、(w={{0}})。则：

[ u\in v,\qquad v\in w,\qquad u\notin w. ]

最后一个断言成立，是因为 (w) 的唯一元素是 (v\ne u)。所以 (E) 不传递，因而不是严格偏序。

同时 (u\ne w)，但 (u\notin w)，而 (w\notin u) 因 (u=0) 成立。所以不同集合未必可以通过隶属比较，(E) 也不是严格全序，更不是良序。

它也不是非严格偏序，因为它不自反。

六、隶属关系不是函数

同一个集合可以属于多个不同集合。例如 (0) 同时属于：

[ {0},\qquad{0,{0}}, ]

而这两个集合不同。因此 (E) 不单值，不是函数。

这些性质共同说明：良基性控制的是非空部分中能否找到没有前驱的元素；它不自动提供传递性、可比较性或函数的单值性。

第 7 节练习

练习 7.1：极小不等于最小

令 (a={0,{0}})，取 (a) 上的空关系 (R=0)。证明 (a) 的两个元素都是 (R)-极小元，并说明这个严格偏序不是严格全序。

练习 7.2：限制与诱导关系

令 (u=0)、(v={0})，(R={\langle u,v\rangle})，(B={u})。分别计算 (R\upharpoonright B) 与 (R\cap(B\times B))。

练习 7.3：Founded 不推出传递

取三个两两不同的集合 (a,b,c)，令 (R={\langle a,b\rangle,\langle b,c\rangle})。证明 (R) 在 ({a,b,c}) 上 well founded，但不传递。

练习 7.4：同构与极小元

设 (F:(A,R)\cong(B,S))、(C\subseteq A)。证明 (x) 是 (C) 的 (R)-极小元，当且仅当 (F`x) 是 (F``C) 的 (S)-极小元，其中假设 (x\in A)。

练习 7.5：识别隶属关系的方向

证明 (E^{-1}A=\cup(A)\)，并用文字解释 \(EA) 收集什么对象。

第 7 节练习参考解答

练习 7.1 解答

空关系没有任何前驱，所以两个元素都极小。它非自反且传递，因而是严格偏序；但两个不同元素之间两个方向的关系都不成立，所以不是严格全序，也没有严格序意义下位于另一个元素之前的最小元。

练习 7.2 解答

(R\upharpoonright B=R)，因为唯一有序对的第一坐标属于 (B)。但 (R\cap(B\times B)=0)，因为第二坐标 (v\notin B)。

练习 7.3 解答

任意非空子集若含 (a)，就以 (a) 为极小元；不含 (a) 但含 (b) 时，以 (b) 为极小元；否则只能是 ({c})。前驱类都是有限集合，所以关系 well founded。但 (aRb) 且 (bRc)，却没有 (aRc)，因此不传递。

练习 7.4 解答

双射给出 (x\in C\leftrightarrow Fx\in F``C\)。若 \(Fx) 在像类中有前驱，它唯一来自某个 (y\in C)，关系反映性给出 (yRx)。反之，(C) 中 (x) 的前驱通过关系保持性产生像类中的前驱。因此两侧同时没有前驱。

练习 7.5 解答

[ y\in E^{-1}``A\leftrightarrow\exists x\in A,(y\in x)\leftrightarrow y\in\cup(A). ]

而 (E``A) 收集所有至少含有一个 (A) 中成员的集合：

[ E``A={y\mid\exists x\in A,(x\in y)}={y\mid y\cap A\ne0}. ]