关系与序 | 杨星宇

NBG 集合论与二元关系

关系把对象之间的联系写成集合语言。函数、同余、整除、字典序，都可以看成某种关系。函数是关系的特例：每个原象只对应一个象。

日常例子已经够用：

学生学号对应成绩。每个学号恰好配一个成绩，这是函数关系。
“生日相同”在人与人之间是等价关系：自己与自己同日生，关系对称，也传递。
数值高度具有通常的大小顺序。但在书本身上定义“高度不超过”，只会得到预序：两本不同的书可能同高，因此反对称性可能不成立。

从初等集合到类

朴素集合论用直观语言介绍常见集合构造，并明确从哪个集合中选取元素，并没有假设任意描述都能定义一个集合。导致矛盾的是无限制概括：如果把罗素汇集 $R=\{x:x\notin x\}$ 当成集合，就会得到 $R\in R$ 当且仅当 $R\notin R$ 。

本章引入 NBG（von Neumann–Bernays–Gödel）集合论的语言，以便同时讨论集合与更大的汇集。这是本章采用的基础框架；在普通集合上定义序关系，并不需要先用到真类。集合 $A$ 上的关系本来就可以表示为 $A\times A$ 的子集[1]。

定义集合与真类

在 NBG 的单论域表述中，讨论的对象都是类，而类的每个元素都是集合。能够作为另一个类之元素的类叫作集合；不是集合的类叫作真类。因此，集合都是类，但真类不能成为元素。

所有集合组成的类 $V$ 、所有序数组成的类，都是真类。允许将这些汇集作为类来讨论，并不意味着它们成了集合，也不意味着任意类都能成为元素。

外延性与初等类概括

公理类的外延公理

两个类有完全相同的元素，就相等：

\forall A\,\forall B\bigl(\forall x\,(x\in A\leftrightarrow x\in B)\to A=B\bigr).

公理初等类概括

设公式 $P(x)$ 中的量词只对集合取值，允许出现固定的集合参数与类参数。则存在类

C=\{x:x\text{ 是集合且 }P(x)\}.

也就是说， $u\in C$ 当且仅当 $u$ 是集合且 $P(u)$ 成立。这里是对公式有所限制的公理模式，不能任意允许量词遍历类。

这些原则说明后面如何构造类，并不构成 NBG 的完整公理清单。仅仅引入“类”这个名称，也不能自动解决所有集合存在性问题。不同文献对选择公理的约定还可能不同，用到时需要明确说明。

类的性质与运算

并与交的写法与朴素集合论相同。对类 $A$ 、 $B$ ，

\begin{aligned} A\cup B&=\{x:(x\in A)\lor(x\in B)\},\\ A\cap B&=\{x:(x\in A)\land(x\in B)\}. \end{aligned}

幂等、结合、交换、分配仍然成立：

\begin{aligned} \forall X\,(X\cup X=X),&\quad \forall X\,(X\cap X=X), \\ \forall X\forall Y\forall Z\bigl(X\cup(Y\cup Z)=(X\cup Y)\cup Z\bigr), \\ \forall X\forall Y\forall Z\bigl(X\cap(Y\cap Z)=(X\cap Y)\cap Z\bigr), \\ \forall X\forall Y\,(X\cup Y=Y\cup X),&\quad \forall X\forall Y\,(X\cap Y=Y\cap X), \\ \forall X\forall Y\forall Z\bigl(X\cup(Y\cap Z)=(X\cup Y)\cap(X\cup Z)\bigr), \\ \forall X\forall Y\forall Z\bigl(X\cap(Y\cup Z)=(X\cap Y)\cup(X\cap Z)\bigr). \end{aligned}

定义类的补

把 $x\notin y$ 当作 $\neg(x\in y)$ 的缩写。类 $A$ 的补是

\sim A=\{x:x\notin A\}.

定义类的差

对类 $A$ 、 $B$ ，差集为

A\sim B \quad\text{或}\quad A-B =\{x:(x\in A)\land(x\notin B)\} =A\cap(\sim B).

双重否定与 De Morgan 律对类同样成立。空类与全集类也有。

定义空类与全集类

\emptyset=\{x:x\neq x\}, \qquad V=\{x:x=x\}.

对一个类还可以做一元的并与交，这与两个类之间的二元运算不是同一层。

定义类的并与交

设 $A$ 是类。它的并与交分别是

\begin{aligned} \bigcup A&=\{x:(\exists y)((y\in A)\land(x\in y))\}, \\ \bigcap A&=\{x:(\forall y)((y\in A)\to(x\in y))\}. \end{aligned}

这里 $x$ 是集合， $y$ 是类。

于是 $C\in\bigcup A$ 当且仅当 $C$ 是集合，并且属于 $A$ 的某个成员； $C\in\bigcap A$ 当且仅当 $C$ 是集合，并且属于 $A$ 的每一个成员。

集合的并、交作用在两个集合上。类的并、交作用在一个类的全部成员上，结果通常仍是类，不必是集合。

引理空类的并与交

$\bigcap\emptyset=V$ ，且 $\bigcup\emptyset=\emptyset$ 。

证明

设 $C$ 是类。则 $C\in\bigcap\emptyset$ 当且仅当 $C$ 是集合，并且属于 $\emptyset$ 的每一个成员。空类没有任何成员，后半句对每个集合都成立，因此这等价于“ $C$ 是集合”，也就是 $C\in V$ 。由外延公理， $\bigcap\emptyset=V$ 。

另一方面， $C\in\bigcup\emptyset$ 当且仅当 $C$ 是集合，并且存在 $x\in\emptyset$ 使 $C\in x$ 。空类没有成员，所以这等价于 $C\in\emptyset$ 。再由外延公理， $\bigcup\emptyset=\emptyset$ 。

定义类的包含

若 $A$ 、 $B$ 是类，且

\forall x\bigl((x\in A)\to(x\in B)\bigr),

则称 $A$ 包含于 $B$ ，或 $A$ 是 $B$ 的子类，记 $A\subseteq B$ 。若 $A$ 还是集合，则称 $A$ 是 $B$ 的子集。若 $A\subseteq B$ 且存在集合 $b\in B\setminus A$ ，则称 $A$ 真包含于 $B$ ，记 $A\subset B$ 。

幂类 $P(A)=\{x:x\subseteq A\}$ 是 $A$ 的全部子集组成的类。这引出幂集公理。

公理幂集公理

对每个集合 $x$ ，存在集合 $y$ ，使得 $u\in y$ 当且仅当 $u\subseteq x$ 。

因此集合 $x$ 的每个子类实际上都是集合，并且 $P(x)$ 本身也是集合，通常就叫 $x$ 的幂集。

公理配对公理

对任意集合 $x$ 、 $y$ ，类 $\{z:(z=x)\lor(z=y)\}$ 是集合。

这个集合记作 $\{x,y\}$ ，叫做无序对。若 $x=y$ ，则记作 $\{x\}$ ，叫做单点集。

注无序对

无序对 $\{a,b\}$ 不管次序： $\{a,b\}=\{b,a\}$ 。在区分集合与真类的理论里，两个对象仍然可以这样配在一起，只是真类不能再充当别的汇集的元素。

公理并公理

对每个集合 $x$ ，类 $\bigcup x$ 是集合。

有序对定义为 $(a,b)=\{\{a\},\{a,b\}\}$ 。类 $A$ 、 $B$ 的笛卡尔积是

A\times B =\{t:(\exists x)(\exists y)\bigl((x\in A)\land(y\in B)\land(t=(x,y))\bigr)\},

也就是第一分量在 $A$ 、第二分量在 $B$ 的全部有序对。若 $P(x,y)$ 是开语句，把

\{(x,y):P(x,y)\}

当作

\{t:(\exists x)(\exists y)\bigl((t=(x,y))\land P(x,y)\bigr)\}

的缩写，于是

A\times B=\{(x,y):(x\in A)\land(y\in B)\}.

二元关系、复合与逆

两个集合 $A$ 、 $B$ 之间理论上可以有各种各样的配对。 $A\times B$ 收集全部有序对， $P(A\times B)$ 的每个元素对应一种可能的配对方式。欧氏平面里的圆、函数图像，都是这种配对的特例。

定义二元关系

从集合 $A$ 到集合 $B$ 的二元关系 $R$ 是笛卡尔积 $A\times B$ 的子集。若 $(a,b)\in R$ ，就说 $a$ 与 $b$ 有关系 $R$ ，记 $aRb$ ，否定则写 $a\not R b$ 。

用类来写，定义可以更一般。

定义作为有序对之类的关系

关系就是由有序对组成的类。对关系 $R$ ，定义

\begin{aligned} \operatorname{Dom} R&=\{x:(\exists y)\,((x,y)\in R)\}, \\ \operatorname{Range} R&=\{y:(\exists x)\,((x,y)\in R)\}. \end{aligned}

若 $(x,y)\in R$ ，称 $x$ 与 $y$ $R$ -相关， $y$ 是 $x$ 的一个 $R$ -相对。定义域是所有具有 $R$ -相对的集合，值域是所有作为 $R$ -相对出现的集合。

例平面上的圆与抛物线

平面上全体点组成的集合里，方程 $x^2+y^2=r^2$ 给出一个关系：所有落在圆上的点 $(x,y)$ 。对多数 $x$ ，对应两个 $y$ （正负各一），所以这不是函数。对比之下， $y=x^2$ 对每个 $x$ 只给出一个 $y$ ，才是函数。

下图把圆关系与二次函数画在一起：函数不会让同一个 $x$ 对应两个 $y$ ，圆可以。

圆关系与函数 y=x^2。

例整除关系

设 $A=\{1,2,3,4\}$ 。关系 $R=\{(a,b):a\text{ 整除 }b\}$ 里有哪些有序对？

因为 $(a,b)\in R$ 当且仅当 $a$ 、 $b$ 都是不超过 $4$ 的正整数且 $a$ 整除 $b$ ，所以

R=\{(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)\}.

这也不是函数：同一个 $a$ 可以对应多个 $b$ 。

$集合 \{1,2,3,4\} 上整除关系的二分有向图。$

定义函数关系

若定义域中每个元素恰好有一个 $R$ -相对，则称 $R$ 是函数关系，也叫函数。此时把 $a$ 的那个唯一相对记作 $R(a)$ 。

公理替换公理

对每个函数关系 $R$ ，若 $\operatorname{Dom} R$ 是集合，则 $\operatorname{Range} R$ 也是集合。

映射、复合与逆

有了类，可以把映射写得更干净。

定义映射

映射是有序对 $((A,B),R)$ ，其中 $A$ 、 $B$ 是集合， $R$ 是 $A$ 与 $B$ 之间的函数关系，且 $\operatorname{Dom} R=A$ 。若 $f=((A,B),R)$ ，称 $f$ 是从 $A$ 到 $B$ 的映射， $A$ 是定义域， $B$ 是陪域， $R$ 是图像，常写 $f:A\to B$ 。对 $a\in A$ ，集合 $R^{\to}(\{a\})$ 只含 $B$ 中一个元素，记作 $f(a)$ ，叫做 $a$ 在 $f$ 下的像。

要给出一个映射，必须同时交代定义域、陪域，以及每个原象的像。对 $X\subseteq A$ ，把 $R^{\to}(X)$ 记作 $f^{\to}(X)$ ；对 $Y\subseteq B$ ，把 $R^{\leftarrow}(Y)$ 记作 $f^{\leftarrow}(Y)$ 。 $f$ 在子集 $A_1\subseteq A$ 上的限制是

f\mid A_1=\bigl((A_1,B),\,R\cap(A_1\times B)\bigr).

函数能复合、能求逆。关系同样可以。

定义满射、单射与双射

设 $f=((A,B),R)$ 。若 $\operatorname{Range} R=B$ ，即 $B$ 中每个元素都至少是某个原象的像，则称 $f$ 为满射。

若逆关系 $R^{-1}$ 仍是函数关系，则称 $f$ 为单射。等价地说， $f(a_1)=f(a_2)$ 蕴含 $a_1=a_2$ 。

既单又满则称双射。若存在从 $A$ 到 $B$ 的双射，称 $A$ 与 $B$ 等势。

$((B,A),R^{-1})$ 是映射当且仅当 $f$ 是双射；此时记 $f^{-1}=((B,A),R^{-1})$ ，叫做 $f$ 的逆映射。

例满射

$A=\{1,2,3\}$ ， $B=\{a,b\}$ ，令 $f(1)=a$ ， $f(2)=a$ ， $f(3)=b$ 。 $B$ 中每个元素都有原象，所以 $f$ 是满射。

例单射

$A=\{1,2,3\}$ ， $B=\{a,b,c,d\}$ ，令 $f(1)=a$ ， $f(2)=b$ ， $f(3)=c$ 。不同原象映到不同像，所以 $f$ 是单射。

例双射

$A=\{1,2,3\}$ ， $B=\{a,b,c\}$ ，令 $f(1)=a$ ， $f(2)=b$ ， $f(3)=c$ 。 $f$ 既单又满，因此 $A$ 与 $B$ 等势。

例逆映射

对上一例的双射， $f^{-1}(a)=1$ ， $f^{-1}(b)=2$ ， $f^{-1}(c)=3$ 。

定义关系的复合

若 $R$ 、 $S$ 是关系，复合 $S\circ R$ 为

S\circ R =\{(x,z):(\exists y)\bigl(((x,y)\in R)\land((y,z)\in S)\bigr)\}.

若 $R$ 从 $A$ 到 $B$ ， $S$ 从 $B$ 到 $C$ ，则 $S\circ R$ 从 $A$ 到 $C$ ，并且 $\operatorname{Dom}(S\circ R)\subseteq\operatorname{Dom} R$ ， $\operatorname{Range}(S\circ R)\subseteq\operatorname{Range} S$ 。

定义映射的复合

设 $f=((A,B),R)$ ， $g=((B,C),S)$ 。则 $((A,C),S\circ R)$ 仍是映射，记作 $g\circ f$ ，并对每个 $a\in A$ 满足 $(g\circ f)(a)=g(f(a))$ 。

注复合的记号

另一种说法： $R$ 从 $A$ 到 $B$ ， $S$ 从 $B$ 到 $C$ ，复合由这样的 $(a,c)$ 组成：存在 $b\in B$ 使 $(a,b)\in R$ 且 $(b,c)\in S$ 。记号仍是 $S\circ R$ 。

定义类之间的关系与逆

类 $A$ 、 $B$ 之间的关系是 $A\times B$ 的子类，即满足 $\operatorname{Dom} R\subseteq A$ 且 $\operatorname{Range} R\subseteq B$ 的关系。类 $A$ 上的关系是 $A\times A$ 的子类。

逆关系为

R^{-1}=\{(x,y):(y,x)\in R\}.

若 $R$ 从 $A$ 到 $B$ ，则 $R^{-1}$ 从 $B$ 到 $A$ ，并且 $\operatorname{Dom} R^{-1}=\operatorname{Range} R$ ， $\operatorname{Range} R^{-1}=\operatorname{Dom} R$ 。

$A$ 在 $R$ 下的像是 $A$ 中成员的全部 $R$ -相对：

R^{\to}(A)=\{y:(\exists x)\bigl((x\in A)\land((x,y)\in R)\bigr)\}.

逆像 $R^{\leftarrow}(B)$ 就是 $(R^{-1})^{\to}(B)$ ：

R^{\leftarrow}(B)=\{x:(\exists y)\bigl((y\in B)\land((x,y)\in R)\bigr)\}.

定义对角关系

对集合 $A$ ，令

D_A=\{x:(\exists a)\bigl((a\in A)\land(x=(a,a))\bigr)\},

叫做 $A\times A$ 的对角线。 $D_A$ 是 $A$ 上的函数关系，定义域为 $A$ 。映射 $I_A=((A,A),D_A)$ 叫做 $A$ 的恒等映射，对每个 $a\in A$ 都有 $I_A(a)=a$ 。

例恒等映射

恒等映射把每个元素送到自己。

$B=\{x\in\mathbb{R}:-1\le x\le 1\}$ 上， $I_B(x)=x$ 。
$C=\{\text{apple},\text{banana},\text{cherry}\}$ 上， $I_C$ 把每种水果送到它自己。
$D=\mathbb{Z}$ 上， $I_D(n)=n$ 。

相应的对角线分别是全部 $(x,x)$ （ $x\in B$ ）、 $\{(\text{apple},\text{apple}),(\text{banana},\text{banana}),(\text{cherry},\text{cherry})\}$ ，以及全部 $(n,n)$ （ $n\in\mathbb{Z}$ ）。

集族

序列是指标与项之间的函数关系，指标通常取遍自然数。它是集族的特例。

定义元素族

设 $I$ 、 $A$ 是类， $F$ 是从 $I$ 到 $A$ 的函数关系。常把 $F$ 叫做以 $I$ 为指标类的 $A$ 中元素族，并写 $(F(i))_{i\in I}$ 。特别地，若 $E$ 是集合，则 $P(E)$ 中的元素族叫做 $E$ 的子集族。若记 $X_i=F(i)$ ，就把这个族写成 $(X_i)_{i\in I}$ 。

若 $X$ 是 $E$ 的若干子集组成的集合，对角线 $D_X$ 本身就是一个子集族，有时记作 $(x)_{x\in X}$ 。

族 $(X_i)_{i\in I}$ 的并与交为

\bigcup_{i\in I}X_i=\{x:(\exists i)\bigl((i\in I)\land(x\in X_i)\bigr)\}, \qquad \bigcap_{i\in I}X_i=\{x:(x\in E)\land(\forall i)\bigl((i\in I)\Rightarrow(x\in X_i)\bigr)\}.

$I$ 为空时， $\bigcap_{i\in I}X_i=E$ 。

例三个子集的并与交

设 $I=\{1,2,3\}$ ，

$X_1=\{a,b\}$
$X_2=\{b,c\}$
$X_3=\{a,c,d\}$

则

\bigcup_{i\in I}X_i=\{a,b,c,d\}, \qquad \bigcap_{i\in I}X_i=\emptyset.

定义作为函数的序列

集合 $E$ 中的序列是从 $\mathbb{N}$ 到 $E$ 的函数，可写成族 $(x_i)_{i\in\mathbb{N}}$ 。第 $n$ 项记 $x_n$ ，整个序列也常写 $(x_n)_{n=1}^{\infty}$ 。

设 $(X_i)_{i\in I}$ 是集族， $X=\bigcup_{i\in I}X_i$ 。该族的乘积是

\prod_{i\in I}X_i =\{f:(f\in\operatorname{Map}(I,X))\land(\forall i)\bigl((i\in I)\Rightarrow(f(i)\in X_i)\bigr)\}.

若记 $f(i)=x_i$ ，有时把 $f$ 写成 $\prod_{i\in I}x_i$ 。第 $j$ 个投影 $\pi_j:\prod_{i\in I}X_i\to X_j$ 由 $\pi_j(f)=f(j)$ 给出。

例两个二元集合的乘积

$X_1=\{a,b\}$ ， $X_2=\{1,2\}$ ， $I=\{1,2\}$ 。则

\prod_{i\in I}X_i = X_1\times X_2 = \{(a,1),(a,2),(b,1),(b,2)\}.

对应 $(a,1)$ 的函数满足 $f(1)=a$ ， $f(2)=1$ ，投影为 $\pi_1(f)=a$ ， $\pi_2(f)=1$ 。

公理笛卡尔积公理

设 $(E_i)_{i\in I}$ 是由集合 $I$ 指标的非空集族。则乘积 $\prod_{i\in I}E_i$ 非空。

定义选择函数

设 $(E_i)_{i\in I}$ 是非空集族。该族的选择函数是从 $I$ 到 $\bigcup_{i\in I}E_i$ 的映射 $f$ ，满足每个 $f(i)\in E_i$ 。选择函数恰是乘积中的元素。若当 $i\neq j$ 时 $E_i\cap E_j=\emptyset$ ，称该族两两不交；此时选择函数的值域从每个成员里恰好取一个元素，叫做选取集。

选择公理断定：每个非空集族都有选择函数；每个两两不交的非空集族都有选取集。

例选择函数

设

\begin{aligned} E_1&=\{1,2\},\\ E_2&=\{3,4\},\\ E_3&=\{5,6\}, \end{aligned}

$I=\{1,2,3\}$ 。一个选择函数可以是 $f(1)=1$ ， $f(2)=4$ ， $f(3)=5$ ，选取集是 $\{1,4,5\}$ 。

自反、对称与传递

特殊关系都可以对照对角线来刻画。

定义自反关系

集合 $X$ 上的关系 $R$ 称为自反，若 $D_X\subseteq R$ ，即对每个 $x\in X$ 都有 $(x,x)\in R$ 。

例哪些关系自反

在 $\{1,2,3,4\}$ 上考虑

$R_1=\{(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)\}$
$R_2=\{(1,1),(1,2),(2,1)\}$
$R_3=\{(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)\}$
$R_4=\{(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)\}$
$R_5=\{(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)\}$
$R_6=\{(3,4)\}$

$R_3$ 与 $R_5$ 含有全部 $(a,a)$ ，因此自反。其余都不含 $(3,3)$ ，不自反。

定义反自反关系

$X$ 上的关系 $R$ 称为反自反，若 $D_X\cap R=\emptyset$ ，即没有任何 $(x,x)$ 属于 $R$ 。

定义对称关系

$X$ 上的关系 $R$ 称为对称，若 $(x,y)\in R$ 蕴含 $(y,x)\in R$ ，即 $R=R^{-1}$ 。

定义不对称关系

$X$ 上的关系 $R$ 称为不对称，若 $(x,y)\in R$ 蕴含 $(y,x)\notin R$ 。特别地 $R\cap R^{-1}=\emptyset$ 。

定义反对称关系

$X$ 上的关系 $R$ 称为反对称，若 $(x,y)\in R$ 且 $(y,x)\in R$ 蕴含 $x=y$ ，即 $R\cap R^{-1}\subseteq D_X$ 。

这三组词容易混：

对称：有来有回。
不对称：有来就不能有回，自环也不许。
反对称：双向同时出现时，两端必须是同一个元素。自环允许。

例兄弟姐妹

“是兄弟姐妹”对称：Tom 是 Jerry 的兄弟姐妹，Jerry 也是 Tom 的兄弟姐妹。

例小于

实数上的 $<$ 不对称： $3<4$ 时不可能有 $4<3$ 。

例整除

整数上的整除反对称： $6$ 整除 $12$ ，但 $12$ 不整除 $6$ ；同时 $6$ 整除 $6$ 并不破坏反对称。

习题

练习集合还是类

在 NBG 中判断下列汇集是集合还是类，并说明理由。

所有不以自身为元素的集合组成的汇集。
全体自然数。
全体序数组成的类。

解集合还是类

这是真类。把它当成集合就会回到 Russell 悖论。
全体自然数是集合。它本身是“所有集合”这个类的元素。
全体序数是真类，过大，不能是集合。

练习真类如何避开 Russell 悖论

NBG 用更严格的公理修补朴素集合论。真类不能再作为别的类或集合的元素。说明这如何挡住 Russell 悖论。

解真类如何避开 Russell 悖论

有了类，就可以谈论“所有集合组成的类”这类过大的汇集。Russell 悖论里的 $R$ 不再被承认为集合，而只是真类。公理系统不允许再对它做只对集合合法的那些运算，于是悖论进不来。

练习循环包含推出相等

设 $A$ 、 $B$ 、 $C$ 是类，且 $A\subseteq B$ 、 $B\subseteq C$ 、 $C\subseteq A$ 。证明 $A=B=C$ 。

解循环包含推出相等

由 $A\subseteq B$ 且 $B\subseteq C$ 得 $A\subseteq C$ 。再与 $C\subseteq A$ 合用外延公理，得 $A=C$ 。同理 $A=B$ 。

练习真包含传递

设 $A$ 、 $B$ 、 $C$ 是类，且 $A\subset B$ 、 $B\subset C$ 。证明 $A\subset C$ 。

解真包含传递

$A\subseteq B\subseteq C$ 给出 $A\subseteq C$ 。又存在 $b\in B\setminus A$ ，且 $b\in C$ ，所以 $A\neq C$ ，从而 $A\subset C$ 。

关系的表示

符号写关系精确，图和矩阵则更直观。

用矩阵表示

有限集之间的关系可以用 $0$ - $1$ 矩阵写出。设 $R$ 从 $A=\{a_1,\ldots,a_m\}$ 到 $B=\{b_1,\ldots,b_n\}$ （元素事先排好序； $A=B$ 时两边用同一排序）。矩阵 $M_R=[m_{ij}]$ 满足

m_{ij} = \begin{cases} 1,&(a_i,b_j)\in R,\\ 0,&(a_i,b_j)\notin R. \end{cases}

例三元关系的矩阵

$X=\{1,2,3\}$ 上 $R=\{(1,2),(2,3),(3,1)\}$ 的矩阵是

M = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}.

自反关系的矩阵

关系自反当且仅当对角线全是 $1$ 。非对角元可以任意，所以自反关系不必是恒等关系。

例自反矩阵

$X=\{1,2,3\}$ 上自反关系至少含 $(1,1),(2,2),(3,3)$ ，矩阵形如

M = \begin{bmatrix} 1 & a & b \\ c & 1 & d \\ e & f & 1 \end{bmatrix},

其中 $a,\ldots,f$ 各为 $0$ 或 $1$ 。对角线必须全 $1$ ，但整张矩阵不必是单位阵。

对称、反对称与不对称的矩阵

对称意味着 $(a,b)\in R$ 当且仅当 $(b,a)\in R$ ，即 $M=M^T$ 。对称并不要求对角线为 $1$ ，那是自反的事。

例对称矩阵

$X=\{1,2,3\}$ 上 $R=\{(1,1),(3,3),(1,2),(2,1)\}$ 的矩阵是

M = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}.

关于主对角线对称。它不含 $(2,2)$ ，所以不自反。自反管的是“自己连自己”，对称管的是“有来就有回”，两者独立。

反对称：若 $a\neq b$ ，不能同时有 $(a,b)$ 和 $(b,a)$ 。对角线上的自环不影响反对称。

例反对称矩阵

$X=\{1,2,3\}$ 上 $R=\{(1,2),(2,3),(3,3)\}$ 的矩阵是

M = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix}.

$m_{12}=1$ 而 $m_{21}=0$ ， $m_{23}=1$ 而 $m_{32}=0$ ； $m_{33}=1$ 不破坏反对称。

不对称更强：只要 $(a,b)\in R$ ，就禁止 $(b,a)\in R$ ，自环通常也不出现。

例不对称矩阵

$R=\{(1,2),(2,3)\}$ 的矩阵是

M = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}.

没有互为反向的边，对角线也全是 $0$ 。

关系矩阵的运算

并、交可以对位比较。

例并与交

设

A=\begin{bmatrix}0&1&0\\0&0&1\\0&0&0\end{bmatrix}, \qquad B=\begin{bmatrix}1&1&0\\0&0&0\\1&0&0\end{bmatrix}.

则

A\cup B=\begin{bmatrix}1&1&0\\0&0&1\\1&0&0\end{bmatrix}, \qquad A\cap B=\begin{bmatrix}0&1&0\\0&0&0\\0&0&0\end{bmatrix}.

复合对应布尔积。设 $R$ 从 $A$ 到 $B$ ， $S$ 从 $B$ 到 $C$ ，三边分别有 $m$ 、 $n$ 、 $p$ 个元素。 $(a_i,c_j)\in S\circ R$ 当且仅当存在 $b_k$ 使 $(a_i,b_k)\in R$ 且 $(b_k,c_j)\in S$ 。因此

M_{S\circ R}=M_R\otimes M_S,

其中 $\otimes$ 把加法换成逻辑或，把乘法换成逻辑与。

例布尔积

M_R = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix}, \qquad M_S = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{bmatrix}.

解布尔积

M_{S\circ R} = M_R\otimes M_S = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix}.

例关系的平方

M_R = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix}.

解关系的平方

M_{R^{[2]}} = M_R\otimes M_R = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}.

其中 $1$ 表示对应顶点之间存在长度为 $2$ 的有向路。

用有向图表示

定义有向图

有向图是有序对 $G=(V,A)$ ，其中 $V$ 是非空顶点集， $A$ 是有序顶点对组成的弧集。弧 $(x,y)$ 从 $x$ 指向 $y$ 。

把定义域、陪域里的元素当顶点，把关系里的有序对当弧，就得到关系的有向图。

例从 A 到 B 的有向图

$A=\{a,b,c\}$ ， $B=\{a,d\}$ ，

R=\{(a,a),(a,d),(b,a),(c,a),(c,d)\}.

从 A 到 B 的关系的有向图。

自反、对称等性质在图上往往一眼能看出来。

例自反的有向图

$A=\{a,b,c\}$ 上 $R=\{(a,a),(b,b),(c,c),(b,a)\}$ 自反：每个顶点都有自环。

自反关系的有向图。

例对称与反对称

仍在 $A=\{a,b,c\}$ 上，取 $R_1=\{(a,b),(b,a),(a,c),(c,a)\}$ ， $R_2=\{(a,a),(b,b),(c,c),(a,b),(b,c)\}$ 。

对称关系 R_1 与反对称关系 R_2 的有向图。

$R_1$ 对称：不同顶点之间的边都成对出现。 $R_2$ 反对称：只有自环是双向的，其余边都是单向。

例传递

$R_1=\{(a,b),(b,c),(a,c)\}$ ， $R_2=\{(a,a),(a,b),(b,b)\}$ 都传递。 $R_2$ 的传递性特别用到了 $a$ 、 $b$ 上的自环。既自反、对称又传递的关系就是下一节的等价关系。

两个传递关系的有向图。

习题

练习由矩阵列出有序对

下列矩阵给出 $\{1,2,3,4\}$ 上的关系（行列都按递增顺序）。列出各自的有序对。

\text{a)} \begin{bmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{bmatrix} \quad \text{b)} \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \end{bmatrix} \quad \text{c)} \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix}

解由矩阵列出有序对

$(1,1)$ 、 $(1,2)$ 、 $(1,4)$ 、 $(2,1)$ 、 $(2,3)$ 、 $(3,2)$ 、 $(3,3)$ 、 $(3,4)$ 、 $(4,1)$ 、 $(4,3)$ 、 $(4,4)$ 。
$(1,1)$ 、 $(1,2)$ 、 $(1,3)$ 、 $(2,2)$ 、 $(3,3)$ 、 $(3,4)$ 、 $(4,1)$ 、 $(4,4)$ 。
$(1,2)$ 、 $(1,4)$ 、 $(2,1)$ 、 $(2,3)$ 、 $(3,2)$ 、 $(3,4)$ 、 $(4,1)$ 、 $(4,3)$ 。

练习由有序对写出矩阵

把 $\{1,2,3,4\}$ 上的下列关系写成矩阵（元素按递增顺序）。

$\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$
$\{(1,1),(1,4),(2,2),(3,3),(4,1)\}$
$\{(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)\}$
$\{(2,4),(3,1),(3,2),(3,4)\}$

解由有序对写出矩阵

\begin{bmatrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \quad \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \quad \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix} \quad \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}

练习一千阶矩阵里有多少个 1

$A=\{1,2,\ldots,1000\}$ 上的关系 $R$ 用矩阵表示，下列情形各有多少个非零元？

$\{(a,b):a\le b\}$
$\{(a,b):a=b\pm 1\}$
$\{(a,b):a+b=1000\}$
$\{(a,b):a+b\le 1001\}$
$\{(a,b):a\neq 0\}$

解一千阶矩阵里有多少个 1

矩阵一共 $1000^2=1{,}000{,}000$ 个位置。

上三角（含对角）的个数是 $\binom{1000}{2}+1000=500{,}500$ 。
除首末两行各一个 $1$ 外，其余每行两个 $1$ ，共 $998\cdot 2+2=1998$ 。
位置 $(1,999),\ldots,(999,1)$ ，共 $999$ 个。
反对角线及其左上方，个数与 (1) 相同，仍是 $500{,}500$ 。
$1\le a\le 1000$ 时条件恒真，全部 $1{,}000{,}000$ 个位置都是 $1$ 。

练习画出有向图

画出关系

\{(a,a),(a,b),(b,c),(c,b),(c,d),(d,a),(d,b)\}

的有向图。

习题中关系的有向图。

练习补关系的有向图

设 $R$ 是集合 $A$ 上的关系。如何从 $R$ 的有向图得到补关系 $\overline{R}$ 的有向图？

解补关系的有向图

对每一对顶点 $(a,b)$ （包括 $a=b$ ）：原来有弧就删掉，原来没有就补上。

练习并、交、对称差、差与复合

已知两个关系的有向图，如何得到它们的并、交、对称差、差以及复合的有向图？

解并、交、对称差、差与复合

假定两个关系定义在同一集合上。并：两边只要有一边有弧就保留。交：两边都有才保留。对称差：恰好一边有才保留。差：只保留第一边有、第二边没有的弧。复合 $S\circ R$ ：若存在顶点 $k$ 使 $R$ 中有 $i\to k$ 且 $S$ 中有 $k\to j$ ，就连 $i\to j$ 。

关系的闭包

本节待撰写 / 占位标记

本节关于关系的闭包（自反闭包、对称闭包与传递闭包/Warshall 算法）为源讲义保留的大纲占位，完整的概念定义与算法推导已列入后续撰写队列。

等价关系

等价关系把集合拆成互不相交的块，块里的元素在某种意义上“一样”。三个性质缺一不可：自反、对称、传递。

常见例子：数的相等、模 $n$ 同余、三角形相似、集合等势。

等价

定义等价关系

集合 $A$ 上同时自反、对称、传递的关系叫做等价关系。若 $a$ 、 $b$ 被某个等价关系连着，就称它们等价，常记 $a\sim b$ 。

例模 m 同余

设 $m>1$ 为整数。证明

R=\{(a,b):a\equiv b\pmod{m}\}

是 $\mathbb{Z}$ 上的等价关系。

解模 m 同余

$a\equiv b\pmod{m}$ 当且仅当 $m$ 整除 $a-b$ 。 $a-a=0=0\cdot m$ ，所以自反。

若 $a-b=km$ ，则 $b-a=(-k)m$ ，所以对称。

若 $a-b=km$ 且 $b-c=\ell m$ ，则 $a-c=(k+\ell)m$ ，所以传递。

例等基数的子集

$A$ 非空。在幂集 $P(A)$ 上规定 $X\sim Y$ 当且仅当 $|X|=|Y|$ 。

解等基数的子集

基数相等显然自反、对称、传递。等价类按元素个数分块。例如 $A=\{1,2,3\}$ 时：

$[\emptyset]=\{\emptyset\}$
$[\{1\}]=\{\{1\},\{2\},\{3\}\}$
$[\{1,2\}]=\{\{1,2\},\{1,3\},\{2,3\}\}$
$[A]=\{A\}$

例相差不到 1 不是等价

在 $\mathbb{R}$ 上规定 $xRy$ 当且仅当 $|x-y|<1$ 。证明 $R$ 不是等价关系。

解相差不到 1 不是等价

$|x-x|=0<1$ ，自反。 $|x-y|=|y-x|$ ，对称。但不传递：取 $x=2.8$ ， $y=1.9$ ， $z=1.1$ ，则 $|x-y|=0.9<1$ ， $|y-z|=0.8<1$ ，而 $|x-z|=1.7>1$ 。

等价类

定义等价类

设 $R$ 是 $A$ 上的等价关系。与 $a\in A$ 相关的全部元素组成 $a$ 的等价类，记 $[a]_R$ ，在不致混淆时简写 $[a]$ 。

注代表元

$[a]_R=\{s:(a,s)\in R\}$ 。其中任意 $e\in[a]_R$ 都叫做这个类的一个代表元。

例绝对值相等

关系 $a=|b|$ 给出的等价类是什么？（更干净的说法是 $a\sim b$ 当且仅当 $|a|=|b|$ 。）

解绝对值相等

$|a|=|b|$ 当且仅当 $b=\pm a$ ，所以 $[a]=\{-a,a\}$ ，对 $0$ 也成立： $[0]=\{0\}$ 。例如 $[3]=\{-3,3\}$ 。

例模 4 的 0 与 1

模 $4$ 同余之下， $0$ 与 $1$ 的等价类是什么？

解模 4 的 0 与 1

[0]=\{\ldots,-8,-4,0,4,8,\ldots\}, \qquad [1]=\{\ldots,-7,-3,1,5,9,\ldots\}.

定义模 m 剩余类

正整数 $m$ 给定后，整数 $a$ 的模 $m$ 剩余类是

[a]_m=\{b\in\mathbb{Z}:b\equiv a\pmod{m}\}=\{a+km:k\in\mathbb{Z}\}.

例分数化简

在“化简后相同”这个关系下， $\frac12$ 的等价类是什么？

解分数化简

所有分子是分母一半的分数，例如

\Bigl[\tfrac12\Bigr] = \Bigl\{\tfrac24,\tfrac36,\tfrac48,\tfrac{5}{10},\ldots\Bigr\}.

例等长字符串

在“长度相同”这个关系下，字符串 $\mathrm{cat}$ 的等价类是什么？

解等长字符串

所有长度为 $3$ 的字符串，例如 $\{\mathrm{dog},\mathrm{pen},\mathrm{sun},\mathrm{mom},\ldots\}$ 。

划分把集合拆成非空、互不相交、并起来等于全集的块。等价类正好给出这样一种划分。

定理等价类的三条刻画

设 $R$ 是 $A$ 上的等价关系。对 $a,b\in A$ ，下列三条等价：

(i)\ aRb \qquad (ii)\ [a]=[b] \qquad (iii)\ [a]\cap[b]\neq\emptyset.

证明

先证 $(i)\Rightarrow(ii)$ 。设 $aRb$ 。若 $c\in[a]$ ，则 $aRc$ 。由对称得 $bRa$ ，再由传递得 $bRc$ ，故 $c\in[b]$ 。于是 $[a]\subseteq[b]$ 。对称地 $[b]\subseteq[a]$ 。

再证 $(ii)\Rightarrow(iii)$ 。 $[a]=[b]$ 且由自反 $a\in[a]$ ，交非空。

最后 $(iii)\Rightarrow(i)$ 。若 $c$ 同属两块，则 $aRc$ 且 $bRc$ 。对称给出 $cRb$ ，传递给出 $aRb$ 。

因为每个 $a$ 都在自己的类里，所以 $\bigcup_{a\in A}[a]_R=A$ 。不同的类不相交。

引理不同等价类不相交

若 $[a]_R\neq[b]_R$ ，则 $[a]_R\cap[b]_R=\emptyset$ 。

这正是上一定理 $(ii)$ 与 $(iii)$ 的逆否。

定义划分

集合 $S$ 的划分是一族非空子集 $(A_i)_{i\in I}$ ，满足 $i\neq j$ 时 $A_i\cap A_j=\emptyset$ ，并且

\bigcup_{i\in I}A_i=S.

例模 3 的三条陈述

$A=\mathbb{Z}$ ， $R$ 为模 $3$ 同余。判断：

$1R4$
$[1]=[4]$
$[1]\cap[4]\neq\emptyset$

解模 3 的三条陈述

三条都真： $4\equiv 1\pmod{3}$ ，因此同类，交当然非空。这正好对照三条刻画。

等价关系把集合分成等价类。模三同余把所有整数划分为三个互不相交的等价类。

模三同余把所有整数划分为三个互不相交的等价类。

习题

练习模 5 的 2

写出模 $5$ 同余之下 $2$ 的等价类。

解模 5 的 2

[2]_5=\{\ldots,-8,-3,2,7,12,\ldots\}=\{2+5k:k\in\mathbb{Z}\}.

练习并上 \{2\} 后的基数

在 $P(\{1,2,3,4\})$ 上规定 $X\sim Y$ 当且仅当 $|X\cup\{2\}|=|Y\cup\{2\}|$ 。写出全部等价类。

解并上 \{2\} 后的基数

$P(\{1,2,3,4\})$ 有 $16$ 个子集。按 $|X\cup\{2\}|$ 分组：

\begin{aligned} &\{\emptyset,\{2\}\}, \\ &\{\{1\},\{3\},\{4\},\{1,2\},\{2,3\},\{2,4\}\}, \\ &\{\{1,3\},\{1,4\},\{3,4\},\{1,2,3\},\{1,2,4\},\{2,3,4\}\}, \\ &\{\{1,3,4\},\{1,2,3,4\}\}. \end{aligned}

练习差为偶数

$A=\mathbb{Z}$ ， $xRy$ 当且仅当 $x-y$ 为偶数。对 $a=2$ 、 $b=5$ 判断：

$aRb$
$[2]=[5]$
$[2]\cap[5]\neq\emptyset$

解差为偶数

$2-5$ 为奇数，所以 $aRb$ 不成立。 $[2]$ 是全体偶数， $[5]$ 是全体奇数，两块既不相等也不相交。三条刻画在这里同时为假，与定理并不矛盾：定理说的是三条一起真或一起假。

反过来，每个划分也诱导一个等价关系：规定 $x$ 与 $y$ 相关当且仅当它们落在同一块。自反、对称显然。若 $a$ 、 $b$ 同属 $X$ ， $b$ 、 $c$ 同属 $Y$ ，则因块不相交必有 $X=Y$ ，于是 $a$ 与 $c$ 同类，故传递。

定理等价类构成划分

集合 $S$ 上的等价关系，其等价类构成 $S$ 的一个划分。反之，给定划分 $\{A_i:i\in I\}$ ，存在等价关系，其等价类恰好就是这些 $A_i$ 。

证明

自反性使每个元素都在自身的非空等价类中；前面的引理保证不同类不相交，并且所有类的并为 $S$ ，因此构成划分。反过来，规定 $xRy$ 当且仅当两者属于同一块。每个元素都在某块中，故自反；定义显然对称。若 $x,y$ 同块、 $y,z$ 同块，两个块共有 $y$ ，由不相交性必为同一块，故传递。对 $x\in A_i$ ，与 $x$ 相关的元素恰好就是 $A_i$ ，所以 $[x]_R=A_i$ ，也证明两种构造互相还原。

例划分与关系互推

$S=\{1,2,3,4,5,6\}$ 。模 $3$ 同余给出 $[1]=\{1,4\}$ ， $[2]=\{2,5\}$ ， $[3]=\{3,6\}$ 。

反过来，划分 $A_1=\{1,2\}$ ， $A_2=\{3,4\}$ ， $A_3=\{5,6\}$ 诱导的关系是：两个数相关当且仅当它们在同一块里。

序关系

另一大家族是序：偏序、全序、良序。先从最宽的偏序说起。

偏序、全序与良序

定义偏序与偏序集

集合 $S$ 上自反、反对称、传递的关系叫做偏序。配上这个关系的集合 $(S,R)$ 叫做偏序集，或 poset。

注偏序的记号

偏序通常定义在同一个集合上，定义域与陪域相同。等价关系则常常用来比较不同集合里的对象。

最常见的偏序是 $\ge$ 、 $\subseteq$ 和整除。

例整数上的大于等于

$\ge$ 在 $\mathbb{Z}$ 上是偏序： $a\ge a$ ；若 $a\ge b$ 且 $b\ge a$ 则 $a=b$ ； $a\ge b$ 且 $b\ge c$ 蕴含 $a\ge c$ 。因此 $(\mathbb{Z},\ge)$ 是偏序集。

例正整数上的整除

整除在 $\mathbb{Z}^+$ 上自反、反对称、传递，所以 $(\mathbb{Z}^+,|)$ 是偏序集。

例幂集上的包含

$A\subseteq A$ ；若 $A\subseteq B$ 且 $B\subseteq A$ 则 $A=B$ ； $A\subseteq B$ 且 $B\subseteq C$ 蕴含 $A\subseteq C$ 。因此 $(P(S),\subseteq)$ 是偏序集。

记号偏序符号

任意偏序都用 $\preccurlyeq$ 写 $a\preccurlyeq b$ 。若还要求 $a\neq b$ ，则写 $a\prec b$ 。

定义可比较

偏序集 $(S,\preccurlyeq)$ 中，若 $a\preccurlyeq b$ 或 $b\preccurlyeq a$ ，称 $a$ 、 $b$ 可比较；否则称不可比较。

例3 与 9，4 与 5

在 $(\mathbb{Z}^+,|)$ 中， $3\mid 9$ ，所以 $3$ 与 $9$ 可比较。 $4\nmid 5$ 且 $5\nmid 4$ ，所以 $4$ 与 $5$ 不可比较。

“偏”就偏在这里：有些元素根本比不了。若任意两个都能比，就得到全序。

定义全序

若偏序集 $(S,\preccurlyeq)$ 中任意两个元素都可比较，则称 $S$ 为全序集或线性序集， $\preccurlyeq$ 为全序或线性序。全序集也叫链。

$\le$ 与 $\ge$ 都是全序。

例词典

词典里的单词按字母序排列，任意两个都能比出先后，所以是全序。

例有向直线

指定了方向的直线上，任意两点都能比出谁在前，所以是全序。

定义良序

偏序集 $(S,\preccurlyeq)$ 称为良序集，若 $\preccurlyeq$ 是全序，并且 $S$ 的每个非空子集都有最小元。

例自然数

$(\mathbb{N},\le)$ 既是全序也是良序：每个非空子集都有最小元。

反例全序未必是良序

令 $S=\{1/n:n\in\mathbb{N},\ n\geq 1\}$ 。通常的 $\le$ 在 $S$ 上是全序，却不是良序：非空子集 $S$ 本身就没有最小元。对任何 $1/n\in S$ ，集合中总还有更小的 $1/(n+1)$ 。自然数的良序性保证非空子集有最小元，并不保证有最大元。

例前一百个正整数

$\{1,2,\ldots,100\}$ 配上 $\le$ 是良序，因为它是良序集 $\mathbb{N}$ 的有限子集。

良序保证归纳能踩到实在的起点。

定理良序归纳

设 $S$ 是良序集。若对每个 $y\in S$ ，只要所有 $x\prec y$ 都使 $P(x)$ 为真，就有 $P(y)$ 为真，则 $P(x)$ 对一切 $x\in S$ 为真。

证明

若不然，集合 $A=\{x\in S:P(x)\text{ 为假}\}$ 非空，因而有最小元 $a$ 。于是所有 $x\prec a$ 都使 $P(x)$ 为真，归纳步骤迫使 $P(a)$ 为真，矛盾。

注良序归纳不必单列奠基

$S$ 的最小元 $x_0$ 前面没有任何元素，归纳步骤的前提空成立，于是 $P(x_0)$ 自动为真。

字典序

词典按第一个不同的字母排序。把这件事搬到两个偏序集的笛卡尔积上，就得到字典序。

定义字典序

给定偏序集 $(A_1,\preccurlyeq_1)$ 与 $(A_2,\preccurlyeq_2)$ ， $A_1\times A_2$ 上的字典序先比第一分量，第一分量相等时再比第二分量。其严格部分为

(a_1,a_2)\prec(b_1,b_2) \quad\Longleftrightarrow\quad a_1\prec_1 b_1 \quad\text{或}\quad \bigl(a_1=b_1\text{ 且 }a_2\prec_2 b_2\bigr).

并上相等就得到偏序 $\preccurlyeq$ 。

证明

自反： $(a_1,a_2)$ 与自己比，第一分量相等且 $a_2\preccurlyeq_2 a_2$ 。

反对称：若双向都成立且 $a_1\neq b_1$ ，则第一分量的严格不等式会互相打架。故 $a_1=b_1$ ，此时第二分量给出 $a_2=b_2$ 。

传递：第一分量已经严格有序时，用 $\preccurlyeq_1$ 的传递；第一分量相等时，用 $\preccurlyeq_2$ 的传递。

两个分量都是全序时，字典序也是全序。

例两个小偏序集的字典序

$A_1=\{1,2\}$ 配通常的 $\le$ ， $A_2=\{a,b\}$ 且 $a\le_2 b$ 。则 $(1,a)\le(2,a)$ ，因为 $1<2$ ； $(2,a)\le(2,b)$ ，因为第一分量相等且 $a\le_2 b$ 。 $(1,a)$ 小于 $(2,b)$ ，此时不必再看第二分量。

这个构造可以对任意有限个偏序集迭代，得到 $n$ 元组上的字典序，也就是字符串比较的数学版。

Hasse 图

本节待撰写 / 占位标记

本小节关于 Hasse 图构建与偏序集可视化的内容为源讲义保留的大纲占位。

极大元与极小元

本节待撰写 / 占位标记

本小节关于偏序集中极大元、极小元、最大元与最小元的严格形式化定义与例题已列入后续撰写队列。

格

本节待撰写 / 占位标记

本小节关于格（Lattice）、上确界（Join）、下确界（Meet）及分配格性质的内容已列入后续撰写队列。

拓扑排序

本节待撰写 / 占位标记

本小节关于有限偏序集拓扑排序原理与 DAG 线性扩展算法的内容已列入后续撰写队列。

习题

练习把字典序做成良序

对字典序的证明做一点改动，使它成为良序。

解把字典序做成良序

让 $A_1$ 、 $A_2$ 都是良序集，例如从 $1$ 起的正整数。全序已经有了。非空子集先看第一分量组成的非空子集，取它的最小元 $a_1$ ，再在第一分量为 $a_1$ 的那些对里看第二分量，再取最小。得到的对就是原子集的最小元。

练习小于或模 2 同余

在 $\mathbb{Z}$ 上规定

xRy\quad\text{当且仅当}\quad x<y\text{ 或 }x\equiv y\pmod{2}.

$R$ 自反吗？对称吗？反对称吗？传递吗？每条都要完整论证。

解小于或模 2 同余

自反。 对任意整数 $x$ ， $x\equiv x\pmod{2}$ ，所以 $xRx$ 。

对称。 $2R3$ 因为 $2<3$ ，但 $3\not R 2$ ：既没有 $3<2$ ，也没有 $3\equiv 2\pmod{2}$ 。所以不对称。

反对称。 $2R4$ 因为 $2<4$ ，同时 $4R2$ 因为 $4\equiv 2\pmod{2}$ ，但 $2\neq 4$ 。所以不反对称。

传递。 $2R3$ 因为 $2<3$ ， $3R1$ 因为 $3\equiv 1\pmod{2}$ ，但 $2\not R 1$ ：既没有 $2<1$ ，也没有 $2\equiv 1\pmod{2}$ 。所以不传递。

练习偏序与等价硬拼在一起

解释：为什么把偏序条件和等价条件用“或”连在一起，会得到上一题那种四不像。

解偏序与等价硬拼在一起

偏序要自反、反对称、传递。等价要自反、对称、传递。用“或”拼起来，自反还能保住，因为两边各自都自反。但反对称与对称互相拆台：小于给出单向， $x\equiv y\pmod{2}$ 又给不同的偶数互相关。传递也被两种机制搅乱，例如 $2<3$ 再接上 $3\equiv 1\pmod{2}$ ，跨不过去。所以既不是偏序也不是等价。

$n$ 元关系

本节待撰写 / 占位标记

本节关于 $n$ 元关系与关系数据库模型（投影、连接与主键运算）的内容为源讲义保留的大纲占位，已列入后续撰写队列。

查找算法

查找要在长度为 $n$ 的数组 $A$ 里定位目标 $T$ 。代价取决于 $A$ 有没有序。

在无序数组里查找

没有顺序时，只能依次检查 $A[1],\ldots,A[n]$ 。这就是线性查找。

算法 1 线性查找

1:procedure LinearSearch( $A, T$ )

2:for $j \gets 1$ to $n$ do

3:if $A[j] = T$ then

4:return $j$

5:end if

6:end for

7:return $-1$

8:end procedure

最坏情况要把每一项都看一遍，时间是 $O(n)$ 。若 $T$ 正好在第一格，一次比较就结束。最好情况用 $\Omega$ 记号，上下夹紧的界用 $\Theta$ 记号。

记号

\Omega

记号

$\Omega(g(n))$ 是至少和 $g$ 长得一样快的函数：存在 $c>0$ 和 $n_0$ ，使得对一切 $n\ge n_0$ 都有 $0\le c g(n)\le f(n)$ 。

记号

\Theta

记号

$\Theta(g(n))$ 是被 $g$ 的两个正倍数夹住的函数：存在 $c_1,c_2>0$ 和 $n_0$ ，使得对一切 $n\ge n_0$ 都有 $0\le c_1 g(n)\le f(n)\le c_2 g(n)$ 。

若目标等可能出现在任一位置，平均探查次数是

\bar p=\frac1n\sum_{i=1}^n i=\frac{n+1}{2},

所以线性查找的平均代价是 $\Theta(n)$ 。

在有序数组里查找

定义有序数组

数组 $A$ 有序，是指 $A[1]\le\cdots\le A[n]$ 或 $A[1]\ge\cdots\ge A[n]$ 。

拿 $A[i]$ 比一次，就能丢掉一半：

若 $T<A[i]$ ，则 $T$ 不可能出现在 $A[i],\ldots,A[n]$ ；
若 $A[i]<T$ ，则 $T$ 不可能出现在 $A[1],\ldots,A[i]$ 。

要把最坏情况压得尽量小，就在当前子段 $A[p],\ldots,A[q]$ 的中点附近探查，取 $j=\bigl\lfloor(p+q)/2\bigr\rfloor$ 。这就是二分查找。

算法 2 二分查找

1:procedure BinarySearch( $A, T$ )

2: $p \gets 1$

3: $q \gets n$

4:while $p \leq q$ do

5: $j \gets \bigl\lfloor (p+q)/2 \bigr\rfloor$

6:if $A[j] = T$ then

7:return $j$

8:else if $A[j] < T$ then

9: $p \gets j+1$

10:else

11: $q \gets j-1$

12:end if

13:end while

14:return $-1$

15:end procedure

比较过程可以在这段演示里看。

取 $n=12$ ， $A=(3,5,8,8,9,16,29,41,50,63,64,67)$ 。若 $T=99$ ，各变量如下变化。

$p$	$j$	$q$	$A[j]$	关系	输出
1	6	12	16	$A[j]<T$
7	9	12	50	$A[j]<T$
10	11	12	64	$A[j]<T$
12	12	12	67	$A[j]<T$
13		12			$T$ 不在 $A$ 中

记当前长度为 $k=q-p+1$ ，探查失败后拆成 $k_1=j-p$ 和 $k_2=q-j$ 。取 $j=\lfloor(p+q)/2\rfloor$ 会让 $k_1$ 是较短的那一半。

定理二分查找的子段长度

每一轮取 $j=\bigl\lfloor(p+q)/2\bigr\rfloor$ 时，剩下的长度满足

k_1=\Bigl\lfloor\frac{k-1}{2}\Bigr\rfloor \le k_2=\Bigl\lceil\frac{k-1}{2}\Bigr\rceil \le\frac k2.

证明

由 $j\le(q+p)/2<j+1$ ，两边减 $p$ 得到 $k_1\le(q-p)/2<k_1+1$ ，所以 $k_1=\lfloor(k-1)/2\rfloor$ 。再由 $k_1+k_2=k-1$ 得到 $k_2$ 的界。

定理二分查找会停

二分查找至多探查 $\lceil\lg n\rceil+1$ 次就会停。

证明

令 $w=\lfloor\lg n\rfloor$ 。失败 $w$ 次之后，当前长度 $k$ 不超过 $n/2^w$ 。因为 $2^w\le n<2^{w+1}$ ，所以 $1\le n/2^w<2$ ，从而 $k=1$ 。下一次探查只剩这一格，找到就返回，找不到就把 $p>q$ 。

定义循环不变式

循环不变式是在循环每一轮开始前和结束后都成立的断言。

设 $T$ 出现在下标 $i$ 。第一种算法的不变式是：经过 $k$ 轮之后，若 $T=A[i]$ ，则 $p\le i\le q$ 。

定理二分查找的循环不变式

经过 $k$ 轮之后，若 $T=A[i]$ ，则 $p\le i\le q$ 。

证明

对 $k$ 作归纳。循环开始前 $p=1$ 、 $q=n$ 。假设 $w$ 轮后成立，下一轮算出 $j_{\mathrm{new}}=\lfloor(p+q)/2\rfloor$ ，于是 $p\le j_{\mathrm{new}}\le q$ 。若 $A[j_{\mathrm{new}}]<T$ ，新的左端是 $j_{\mathrm{new}}+1$ ；若 $A[j_{\mathrm{new}}]>T$ ，新的右端是 $j_{\mathrm{new}}-1$ ；相等则两端不动。只要 $T$ 还在数组里， $i$ 就仍落在留下的区间中。

循环以 $p>q$ 结束时， $[p,q]$ 里没有下标， $T$ 不在 $A$ 中。否则已经在探查 $j$ 处返回。所以算法正确，而且比线性查找便宜得多。

分支图

定义分支图

算法的分支图是一棵树，画出它可能执行的全部操作序列。

$n=12$ 时第一次探查 $A[6]$ 。两次比较分别走向 $A[3]$ 或 $A[9]$ ，依此类推。

第一种二分查找的分支树，n=12。

这是一棵二叉树：根在顶上，每个点向下至多两条边，没有向下边的是叶子，除根以外每个点恰有一条来自上方的边。

二分查找的第二版

第二版把右端改成 $q\gets j$ ，循环里只比较 $A[j]<T$ 。

算法 3 二分查找第二版

1:procedure BinarySearch( $A, T$ )

2: $p \gets 1$

3: $q \gets n$

4:while $p < q$ do

5: $j \gets \bigl\lfloor (p+q)/2 \bigr\rfloor$

6:if $A[j] < T$ then

7: $p \gets j+1$

8:else

9: $q \gets j$

10:end if

11:end while

12:if $A[p] = T$ then

13:return $p$

14:else

15:return $-1$

16:end if

17:end procedure

同一个 $T=99$ 的表少一轮。

$p$	$j$	$q$	$p<q$	$A[j]$	$A[j]<T$	输出
1	6	12	t	16	t
7	9	12	t	50	t
10	11	12	t	64	t
12		12	f			$T$ 不在 $A$ 中

这时 $A[j]$ 是左段的最后一格，不再单独占第三块。若 $A[j]<T$ ，下一步看 $A[j+1],\ldots,A[q]$ ；否则看 $A[p],\ldots,A[j]$ 。取 $j=\lfloor(p+q)/2\rfloor$ 时，新长度满足 $k_2=\lfloor k/2\rfloor\le k/2\le k_1=\lceil k/2\rceil$ 。因此有的轮次里，下一段比上一段的一半还长。

记 $L(w)$ 为 while 循环进行 $w$ 轮后仍要查找的长度。

定理第二版的长度界

经过 $w$ 轮之后，

\Bigl\lfloor\frac n{2^w}\Bigr\rfloor\le L(w)\le\Bigl\lceil\frac n{2^w}\Bigr\rceil.

证明

$w=0$ 时 $L(0)=n$ 。假设第 $m$ 步成立。下一步是对 $L(m)$ 取一半再取整。下取整和上取整都单调，并且对任意实数 $x$ 有 $\lfloor\lfloor x\rfloor/2\rfloor=\lfloor x/2\rfloor$ 、 $\lceil\lceil x\rceil/2\rceil=\lceil x/2\rceil$ 。令 $x=n/2^m$ ，第 $m+1$ 步仍是同一形状的界。

定理第二版会停

形如“ $A[j]<T$ ？”的比较至多做 $\lceil\lg n\rceil$ 次；当 $p=q$ 时，当前子段长度为 $1$ 。

引理

若实数 $x<y$ ，则 $\lceil x\rceil\le\lceil y\rceil$ 且 $\lfloor x\rfloor\le\lfloor y\rfloor$ 。

$n=12$ 时第二版的分支图仍是二叉树，但每个内点恰好两条向下的边：满二叉树。

定理满二叉树的叶子数

有 $m$ 个内点的满二叉树有 $m+1$ 片叶子。

证明

对 $m$ 归纳。 $m=1$ 时根有两个叶子儿子。再加一个内点，等于把一片叶子变成内点并添两个新叶子，叶子数增加 $1$ 。

习题

练习查找失败时插在哪里

若二分查找没有找到 $T$ ，它该插在哪？

最终的 $q$ 是否总比最终的 $p$ 小 $1$ ？
何时有 $A[q]<T<A[p]$ ？
若 $p$ 一直是 $1$ ，是否 $T<A[1]$ ？
若 $q$ 一直是 $n$ ，是否 $A[n]<T$ ？

解查找失败时插在哪里

最终的 $q$ 不必总是 $p-1$ ，取决于两端怎么挪。 $A[q]<T<A[p]$ 描述的是有序数组里 $T$ 该待的缝。若 $p$ 从未增大，则 $T<A[1]$ ；若 $q$ 从未减小，则 $A[n]<T$ 。

练习平均代价能否写成

\Theta

二分查找最好情形用 $\Omega$ ，最坏情形用 $O$ 。平均情形能不能写成 $\Theta$ ？

解平均代价能否写成

\Theta

最好情形是第一次就探到中点， $\Omega(1)$ 。最坏是 $O(\log n)$ 次。平均的 $\Theta$ 界需要在目标下标的概率模型下同时有上界和下界。教材里通常只说平均 $O(\log n)$ ，并不给 $\Theta$ ，因为那个模型并不唯一。

参考文献

[1] T. Banakh, “Classical Set Theory: Theory of Sets and Classes,” arXiv:2006.01613, 2026. Version 6, August 15, 2026; NBG sets, classes, and class existence. https://arxiv.org/abs/2006.01613 ↩

NBG 集合论与二元关系

从初等集合到类

外延性与初等类概括

类的性质与运算

二元关系、复合与逆

映射、复合与逆

集族

自反、对称与传递

习题

关系的表示

用矩阵表示

自反关系的矩阵

对称、反对称与不对称的矩阵

关系矩阵的运算

用有向图表示

习题

关系的闭包

等价关系

等价

等价类

习题

序关系

偏序、全序与良序

字典序

Hasse 图

极大元与极小元

格

拓扑排序

习题

nnn 元关系

查找算法

在无序数组里查找

在有序数组里查找

分支图

二分查找的第二版

习题

参考文献

评论

$n$ 元关系