离散数学笔记（6）——集合论（2）

离散数学笔记（6）——集合论（2）

集合论

关系性质证明方法

自反性

1. 用自反定义证明：任取 $x \in A$，证明 $\langle x,x \rangle \in R$。
2. 用恒等关系 $I_A$ 证明：证明 $I_A \in R$。
3. 用自反闭包证明：证明 $r(R) = R$，即 $R \cup I_A = R$。

反自反性

1. 用反自反定义证明：任取 $x \in A$，证明 $\langle x,x \rangle \not \in R$。

对称性

1. 用对称定义证明：任取 $x,y \in A$，设 $\langle x,y \rangle \in R$，证明 $\langle y,x \rangle \in R$。
2. 用求逆关系证明：证明 $R^c = R$。
3. 用对称闭包证明：证明 $s(R) = R$，即 $R \cup R^c = R$。

反对称性

1. 用定义 1 证明：任取 $x,y \in A$，设 $\langle x,y \rangle \in R,\langle y,x \rangle \in R$，证明 $x = y$。
2. 用定义 2 证明：任取 $x,y \in A,x \not = y$，设 $\langle x,y \rangle \in R$，证明 $\langle y,x \rangle \not \in R$。
3. 用定理证明：证明 $R \cap R^c \subseteq I_A$。

传递性

1. 用传递定义证明：任取 $x,y,z \in R$，设 $\langle x,y \rangle \in R,\langle y,z \rangle \in R$，证明 $\langle x,z \rangle \in R$。
2. 用传递闭包证明：证明 $t(R) = R$，即 $R \cup R^2 \cup R^3 \cup \cdots = R$。
3. 用定理证明：证明 $R \circ R \subseteq R$。

集合的划分与覆盖

定义

设 $X$ 是一个非空集合，$A = \{A_1,A_2,\cdots,A_n\}$，$A_i \not = \varnothing,A_i \subseteq X(i=1,2,\cdots,n)$，如果满足 $A_1 \cup A_2 \cup \cdots \cup A_n = X$，则称 $A$ 为集合 $X$ 的覆盖。

设 $A=\{A_1, A_2,\cdots,A_n\}$ 是 $X$ 一个覆盖, 且 $A_i \cap A_j=\varnothing(i \not = j,1 \le i,j \le n)$.

则称 $A$ 是 $X$ 的划分。每个 $A_i$ 均称为这个划分的一个划分块（类）。

最小划分与最大划分

最小划分：划分块最少的划分。即只有一个划分块的划分，这个划分块就是 $X$ 本身。

最大划分：划分块最多的划分。即每个划分块里只有一个元素的划分。

等价关系与等价类

等价关系

设 $R$ 是 $A$ 上关系,若 $R$ 是自反的、对称的和传递的，则称 $R$ 是 $A$ 中的等价关系。

若 $a,b \in A$，且 $aRb$，则称 $a$ 与 $b$ 等价。

等价关系的关系图

等价关系 $R$ 的关系图由若干个独立子图构成，每个独立子图都是完全关系图。

等价类

$R$ 是 $A$ 上的等价关系，$a \in A$，由 $a$ 确定的集合 $[a]_R$：

$$[a]_R = \{x|x \in A \land \langle a,x \rangle \in R\}$$
称集合 $[a]_R$ 为由 $a$ 生成的 $R$ 等价类，简称 $a$ 等价类。

可见 $x \in [a]_R \Leftrightarrow \langle a,x \rangle \in R$。

不同的等价类个数 $=$ 独立子图个数。

等价类性质

$R$ 是 $A$ 上等价关系，任意 $a,b,c \in R$：

1. $[a]_R \not = \varnothing,[a]_R \subseteq A$
2. $[a]_R \cap [b]_R = \varnothing$，当且仅当 $\langle a,b \rangle \not \in R$。
3. $[a]_R = [b]_R$，当且仅当 $\langle a,b \rangle \in R$。

商集

$R$ 是 $A$ 上等价关系，由 $R$ 的所有等价类构成的集合称之为 $A$ 关于 $R$ 的商集。

记作 $A / R$。即 $A / R = \{[a]_R |a \in A\}$。

定理 1：集合 $A$ 上的等价关系 $R$，决定了 $A$ 的一个划分，该划分就是商集 $A / R$。

定理 2：集合 $X$ 的一个划分可以确定 $X$ 上的一个等价关系。

思路：每个划分类做笛卡尔积再取并集即可。

偏序关系

定义

$R$ 是 $A$ 上自反、反对称和传递的关系，则称 $R$ 是 $A$ 上的偏序关系。并称 $\langle A,R \rangle$ 是偏序集。用符号 $\preccurlyeq$ 表示任意偏序关系。

可比较的

$\langle A,\preccurlyeq \rangle$ 是偏序集，$x,y \in A$，如果要么 $x \preccurlyeq y$,要么 $y \preccurlyeq x$, 则称 $x$ 与 $y$ 是可比较的。

全序（线序，链）

$\langle A,\preccurlyeq \rangle$ 是偏序集，任何 $x,y \in A$，如果 $x$ 与 $y$ 都是可比较的，则称 $\preccurlyeq$ 是全序关系（线序、链）。

全序关系一定是偏序关系，但是偏序不一定是全序。

“盖住”

$\langle A,\preccurlyeq \rangle$ 是偏序集，$x,y \in A$，如果 $x \preccurlyeq y$ 且 $x \not = y$，且不存在 $z \in A$，使得 $z \not = x \land z \not = y \land x \preccurlyeq z \land z \preccurlyeq y$，则称元素 $y$ 盖住元素 $x$。

记 $\mathrm{COV} A = \{\langle x,y \rangle|x,y \in A,y \text{ 盖住 } x\}$

偏序集 Hasse 图的画法

令 $\langle A,\preccurlyeq \rangle$ 是偏序集：

1. 用 $\circ$ 表示 $A$ 中元素。
2. 如果 $x \preccurlyeq y$ 且 $x \not = y$，则结点 $y$ 要画在结点 $x$ 的上方。
3. 如果 $x \preccurlyeq y$,且 $y$ 盖住 $x$ ，$x$ 与 $y$ 之间连一直线。
4. 一般先从最下层结点，逐层向上画，直到最上层结点。（采用抓两头，带中间的方法）

偏序集中的重要元素

极大元与极小元

设 $\langle A,\preccurlyeq \rangle$ 是偏序集，$B$ 是 $A$ 的非空子集。

若 $\exists y(y \in B \land \forall (x \in B \land x \preccurlyeq y \to x = y))$，则称 $y$ 是 $B$ 的极小元。

若 $\exists y(y \in B \land \forall (x \in B \land y \preccurlyeq x \to x = y))$，则称 $y$ 是 $B$ 的极大元。

最小元与最大元

设 $\langle A,\preccurlyeq \rangle$ 是偏序集，$B$ 是 $A$ 的非空子集。

若 $\exists y(y \in B \land \forall (x \in B \to y \preccurlyeq x))$，则称 $y$ 是 $B$ 的最小元。

若 $\exists y(y \in B \land \forall (x \in B \to x \preccurlyeq y))$，则称 $y$ 是 $B$ 的最大元。

性质

• 对任意非空有限集合 $B$，极大（小）元必存在，但极大（小）元不一定唯一。
• 不同的极大（小）元之间是无关的。
• $B$ 的最小元应小于等于 $B$ 中其他各元。
• $B$ 中其他各元应小于等于 $B$ 的最大元。
• 最大（小）元不一定存在，但若存在，必唯一。如果 $B$ 有唯一的极小（大）元，则这个极小（大）元就是最小（大）元。否则就没有最小（大）元。

上界与下界

若 $\exists y(y \in A \land \forall (x \in B \to x \preccurlyeq y))$，则称 $y$ 是 $B$ 的上界。

若 $\exists y(y \in A \land \forall (x \in B \to y \preccurlyeq x))$，则称 $y$ 是 $B$ 的下界。

最小上界（上确界）和最大下界（下确界）

设 $C = \{ y|y\text{ 是 }B \text{ 的上界}\}$，则 $C$ 的最小元称为 $B$ 的最小上界（上确界）。

设 $C = \{ y|y\text{ 是 }B \text{ 的下界}\}$，则 $C$ 的最大元称为 $B$ 的最大下界（下确界）。

相关性质

设 $\langle A,\preccurlyeq \rangle$ 是偏序集，$B \subseteq A$，则：

1. 若 $b$ 是 $B$ 的最大（小）元，则它必是 $B$ 的极大（小）元。
2. 若 $b$ 是 $B$ 的最大（小）元，则它必是 $B$ 的上（下）确界。
3. 若 $b$ 是 $B$ 的上（下）确界，且 $b \in B$，则 $b$ 必是 $B$ 的最大（小）元。

链与反链

设 $\langle A,\preccurlyeq \rangle$ 是偏序集，$B \subseteq A$：

1. 若 $\forall x \forall y(x \in B \land y \in B \to x \preccurlyeq y \lor y \preccurlyeq x)$，则称 $B$ 为 $A$ 上的链，$B$ 中元素个数为称为链 $B$ 的长度。
2. 若 $\forall x \forall y(x \in B \land y \in B \to \lnot (x \preccurlyeq y \lor y \preccurlyeq x))$，则称 $B$ 为 $A$ 上的反链，$B$ 中元素个数为称为反链 $B$ 的长度。

规定：若 $B$ 只含有一个元素，则 $B$ 既是链又是反链。

结论：若 $\langle A,\preccurlyeq \rangle$ 是全序关系，则 $A$ 是链，且 $A$ 的任何子集都是链。

定理 1：设 $\langle A,\preccurlyeq \rangle$ 是偏序集，设 $A$ 中最长链的长度为 $n$，则 $A$ 中存在一个由 $n$ 个反链组成的划分。

定理 2：对偏序集 $\langle A,\preccurlyeq \rangle$，若 $A$ 中元素个数为 $mn+1$，则 $A$ 中或者存在一条长度为 $m+1$ 的反链，或者存在一条长度为 $n + 1$ 的链。

良序

设 $\langle A,\preccurlyeq \rangle$ 是偏序集，如果对 $A$ 的任何非空子集 $B$ 都有最小元，则称 $\preccurlyeq$ 是A上的良序，并称 $\langle A,\preccurlyeq \rangle$ 为良序集。

定理 1：所有良序集，一定是全序集。

定理 2：有限的全序集，一定是良序集。

 离散数学 笔记