1.3 笛卡尔积与关系

有序对与笛卡尔积

集合没有元素的次序：$\{a,b\}=\{b,a\}$。有序对 $(a,b)$ 则要保留第一、第二个元素的信息。一种纯集合论编码是

$$(a,b)=\{\{a\},\{a,b\}\}.\text{\hspace{1em}(1.1)}$$

被引用 2 次

• 1.3 笛卡尔积与关系所给 PDF 式 (1.1) 印为 …。这不是一般有效的有序对编码；这里采用标准的 Kuratowski 定义，并据此表述随文练习。此形式定义仅用于说明“次序”可以由集合表达，后续计算不必反复展开它。
• 1.3 笛卡尔积与关系根据式 (1.1) 证明 … 当且仅当 … 且 …。

编校说明 · 有序对

所给 PDF 式 (1.1) 印为 $\{\{a,b\},a\}$。这不是一般有效的有序对编码；这里采用标准的 Kuratowski 定义，并据此表述随文练习。此形式定义仅用于说明“次序”可以由集合表达，后续计算不必反复展开它。

随文练习 1.3-A · 有序对的相等

根据式 (1.1) 证明 $(a,b)=(a^{\prime },b^{\prime })$ 当且仅当 $a=a^{\prime }$ 且 $b=b^{\prime }$。

有序 $n$ 元组可以递归定义为

$$(a_1,a_2,\dots ,a_n)=(a_1,(a_2,\dots ,a_n)).$$

随文练习 1.3-B · 有序三元组

把 $(a,b,c)$ 展开写成集合。

笛卡尔积由全部有序对构成：

$$S\times T=\{(s,t)\mid s\in S,t\in T\}.$$

一般地，$S_1\times \cdots \times S_n$ 是全部满足 $s_i\in S_i$ 的有序元组 $(s_1,\dots ,s_n)$ 的集合。若各集合都等于 $S$，记为 $S^n$。

随文练习 1.3-C · 空的笛卡尔积

证明 $S\times T=\varnothing$ 当且仅当 $S=\varnothing$ 或 $T=\varnothing$。

关系

$S^n$ 的任意子集称为 $S$ 上的 $n$ 元关系。一元关系是 $S$ 的子集；二元关系是 $S\times S$ 的子集；三元关系是 $S^3$ 的子集。

二元关系最常用。若 $R\subseteq S\times S$，常把 $(a,b)\in R$ 写作 $aRb$。

关系的三种性质

• 自反：对所有 $a\in S$，有 $aRa$。
• 对称：$aRb\Rightarrow bRa$。
• 传递：$aRb$ 且 $bRc\Rightarrow aRc$。

例 1.2 · 实数的次序关系

实数上的 $\le$ 自反、传递，但不对称。严格次序 $<$ 传递，但既不自反也不对称。整数与有理数上的相应次序也有这些性质。通常直接写 $x\le y$，而不会把它展开为 $(x,y)\in \le \subseteq {\mathbb{R}}^2$。

等价关系与商空间

自反、对称、传递的关系称为等价关系。相等关系就是一个例子。对 $S$ 上的等价关系 $R$，定义

$$[a{]}_R=\{b\in S\mid aRb\}.$$

当关系明确时，简记为 $[a]$。自反性保证 $a\in [a]$，因此等价类覆盖 $S$。

等价类构成划分（随文结论）

若 $aRb$，则 $[a]=[b]$。任意两个等价类或者相等，或者不相交。因此等价关系把 $S$ 划分为互不相交的等价类。

证明

若 $aRb$ 且 $c\in [a]$，则 $aRc$。由对称性 $bRa$，再由传递性得 $bRc$，即 $c\in [b]$，所以 $[a]\subseteq [b]$；交换 $a,b$ 得反向包含。

若 $c\in [a]\cap [b]$，则 $aRc$ 且 $cRb$，传递性给出 $aRb$，故 $[a]=[b]$。

把同一等价类中的元素看作被“识别”在一起，所有等价类构成商空间（原书称 factor space）：

$$S/R=\{[a{]}_R\mid a\in S\}.$$

例 1.3 · 模 $p$ 的剩余类

设 $p$ 是正整数。在 $\mathbb{Z}$ 上定义

$$m\equiv n(\mathrm{mod}p)⟺\exists k\in \mathbb{Z},m-n=kp.$$

这是等价关系。例如，$m-n=kp$ 与 $n-j=lp$ 推出 $m-j=(k+l)p$，说明传递性。等价类为 $[m]=\{m+kp\mid k\in \mathbb{Z}\}$，恰有 $p$ 个不同的类 $[0],\dots ,[p-1]$，其并是 $\mathbb{Z}$。

例 1.4 · 二维环面

在 ${\mathbb{R}}^2$ 上规定

$$(x,y)\sim (x^{\prime },y^{\prime })⟺x^{\prime }=x+m,y^{\prime }=y+n(m,n\in \mathbb{Z}).$$

每个等价类有唯一代表满足 $0\le x,y<1$。商空间

$$T^2={\mathbb{R}}^2/\sim$$

称为二维环面。把单位正方形的两对相对边分别识别，可理解其几何名称；原书第 10 章再讨论这一图像。

偏序与全序

关系 $R$ 若自反、传递并满足反对称性

$$aRb\text{ 且 }bRa⟹a=b,$$

则称为偏序。若任意两元素都可比较，即 $a\le b$ 或 $b\le a$，则称为全序。

例 1.5 · 幂集的偏序

$2^S$ 上的包含关系 $\subseteq$ 是偏序：它自反、传递，且 $U\subseteq V$ 与 $V\subseteq U$ 推出 $U=V$。

它一般不是全序。例如，两个不同的单元素子集互不包含。

集合连同其偏序称为偏序集，写为 $(S,\le )$。这是“带结构的集合”的第一个例子。“集合连同结构”可以形式化为有序对，但把所有表达都展开成集合并不能自动帮助理解。

习题

习题 1.8 · 笛卡尔积的运算

证明

$$\begin{array}{rl}(A\cup B)\times P& =(A\times P)\cup (B\times P),\\ (A\cap B)\times (P\cap Q)& =(A\times P)\cap (B\times Q),\\ (A-B)\times P& =(A\times P)-(B\times P).\end{array}$$

**勘误：**第二式右侧最后一项在 PDF 中印为 $B\times P$，应为 $B\times Q$。

习题 1.9 · 集合族与乘积

对非空指标集 $I,J$ 和集合族 $\mathcal{A}=\{A_i\mid i\in I\}$、$\mathcal{B}=\{B_j\mid j\in J\}$，证明

$$(\bigcup \mathcal{A})\times (\bigcup \mathcal{B})=\bigcup _{i\in I,j\in J}(A_i\times B_j),$$ $$(\bigcap \mathcal{A})\times (\bigcap \mathcal{B})=\bigcap _{i\in I,j\in J}(A_i\times B_j).$$

习题 1.10 · 两种偏序的比较

证明 ${\mathbb{R}}^2$ 上以下关系都是偏序：

$$\begin{array}{rl}(a,b)\le (x,y)& ⟺a<x\text{ 或 }(a=x\text{ 且 }b\le y),\\ (a,b)⪯(x,y)& ⟺a\le x\text{ 且 }b\le y.\end{array}$$

若 $u\le v\Rightarrow u⪯v$，称 $\le$ 比 $⪯$ 强。字典序 $\le$ 比逐分量序 $⪯$ 强、弱，还是不可比较？