离散数学笔记(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$ 有唯一的极小(大)元,则这个极小(大)元就是最小(大)元。否则就没有最小(大)元。

39

上界与下界

若 $\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$ 个反链组成的划分。

40

定理 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:所有良序集,一定是全序集。

41

定理 2:有限的全序集,一定是良序集。

42

 

点赞 0

No Comments

Add your comment