集合与关系

参考资料

• 集合 (数学) - 维基百科
• 关系 (数学) - 维基百科

引入

集合 在高中已学过基础。本章在此之上引入 二元关系（集合元素之间的「联系」），并讨论关系的结构性质——等价关系 与 偏序关系，它们贯穿整个离散数学。

集合的进一步话题

幂集

集合 $A$ 的 所有子集 构成的集合：

$$\mathcal{P}(A)=\set{B\mid B\subseteq A}$$

若 $|A|=n$，则 $|\mathcal{P}(A)|=2^n$。

笛卡尔积

$$A\times B=\set{(a,b)\mid a\in A,b\in B}$$

性质：$|A\times B|=|A|\cdot|B|$。一般 $A\times B\ne B\times A$。

可推广到 $n$ 元：$A_1\times\dots\times A_n$。

二元关系

定义

$A$ 到 $B$ 的 二元关系 $R$ 是 $A\times B$ 的子集。若 $(a,b)\in R$，写作 $aRb$。

特别地，$A$ 到自身的关系 $R\subseteq A\times A$ 称为 $A$ 上的关系。

表示

方式	含义
集合表示	列出所有有序对 $(a,b)\in R$
关系矩阵	$M_R=(m_{ij})$，$m_{ij}=1$ 当 $a_iRa_j$ 时
关系图	顶点为元素，$aRb$ 时画有向边 $a\to b$

性质

设 $R$ 为 $A$ 上的关系：

名称	定义
自反	$\forall a\in A,aRa$
反自反	$\forall a\in A,\neg(aRa)$
对称	$aRb\Rightarrow bRa$
反对称	$aRb\land bRa\Rightarrow a=b$
传递	$aRb\land bRc\Rightarrow aRc$

tip

「反自反」不是「自反」的否定；同样「反对称」不是「对称」的否定。 存在既不自反也不反自反的关系（如 $\set{(1,1),(2,3)}$）。

关系的运算

复合

$$R\circ S=\set{(a,c)\mid \exists b,(a,b)\in R\land(b,c)\in S}$$

逆

$$R^{-1}=\set{(b,a)\mid (a,b)\in R}$$

闭包

包含 $R$ 且具备某性质的 最小关系：

• 自反闭包 $r(R)=R\cup I_A$（$I_A$ 为恒等关系）。
• 对称闭包 $s(R)=R\cup R^{-1}$。
• 传递闭包 $t(R)=R\cup R^2\cup R^3\cup\dots$。

等价关系

同时满足 自反、对称、传递 的关系。

等价类

$$[a]_R=\set{x\in A\mid xRa}$$

性质：

• $[a]_R\ne\varnothing$（含 $a$ 本身）。
• 两个等价类要么相等，要么不相交。
• 所有等价类构成 $A$ 的 划分。

划分

$A$ 的一个 划分 $\set{A_1,A_2,\dots}$ 满足：

1. 各 $A_i\ne\varnothing$。
2. 两两不相交。
3. 并为 $A$。

等价关系与划分一一对应。

偏序关系

同时满足 自反、反对称、传递 的关系，记为 $\preceq$。

$(A,\preceq)$ 称为 偏序集（poset）。

哈斯图

省略自反边和可由传递推出的边，把元素按大小自下而上摆放：

• $a\preceq b$ 且 $a\ne b$ 且不存在 $c$ 使 $a\prec c\prec b$ 时，画一条无向连边。

极值元素

名称	定义
最大元	$\forall x,x\preceq m$
最小元	$\forall x,m\preceq x$
极大元	不存在 $x$ 使 $m\prec x$
极小元	不存在 $x$ 使 $x\prec m$
上界	子集 $B$ 的元素都 $\preceq u$
下界	$l\preceq$ 子集 $B$ 中所有元素
上确界	最小上界
下确界	最大下界

最大元若存在则唯一；极大元可能不唯一。

全序与良序

• 全序：任意两元素 可比（$a\preceq b$ 或 $b\preceq a$）。
• 良序：任一非空子集都有 最小元。

良序集是数学归纳法的基础。