集合与图论学习笔记02

定义

定义 2.1 闭包

$A$ 非空 $R$ 是 $A$ 的二元关系，定义 $R$ 的自反（对称、传递）闭包 $R'$ 满足：

$R \subseteq R'$
$R'$ 是自反（对称的，传递的）的
对任意自反（对称、传递）关系 $R''$，若 $R \subseteq R''$ ，则 $R' \subseteq R''$ （最小的）

闭包	记为
自反闭包	$r(R)$
对称闭包	$s(R)$
传递闭包	$t(R)$

容易知道：

$R$ 是自反的 $iff \space r(R)=R$

$R$ 是对称的 $iff \space s(R)=R$

$R$ 是传递的 $iff \space t(R)=R$

且

若 $R_{1} \subseteq R_{2}$ 则 $r(R_{1}) \subseteq r(R_{2})$ $s(R_{1}) \subseteq s(R_{2})$ $t(R_{1}) \subseteq t(R_{2})$

$R$ 为 $A$ 上任意一关系

$r(R)=R \cup I_{A}$
$s(R)=R\cup R^{-1}$
$t(R)=\bigcup_{n \in \mathbb{Z}^{+}}R^{n}$

证明：点击查看证明

$R\cup I_{A}$ 显然自反，且包含 $R$
设 $R'$ 为包含 $R$ 满足自反性的最小的关系
$R'$ 满足自反性，则 $I_{A} \subseteq R'$，则 $R\cup I_{A}\subseteq R'$
则 $r(R) = R\cup I_{A}$
$(R\cup R^{-1})^{-1}=(R^{-1}\cup (R^{-1})^{-1})=R^{-1}\cup R$ ，$R\cup R^{-1}$满足对称性，且包含 $R$
设 $R'$ 为包含 $R$ 满足对称性的最小的关系
$R'$ 对称，则 $R'^{-1}=R'$ 由 $R \subseteq R'$ 知 $R^{-1} \subseteq R'^{-1}=R'$，则 $R \cup R^{-1} \subseteq R'$
则 $s(R) = R\cup R^{-1}$
容易验证 $(\bigcup_{n \in \mathbb{\mathbb{Z}}^{+}}R^{n})\cdot (\bigcup_{n \in \mathbb{\mathbb{Z}}^{+}}R^{n}) \subseteq \bigcup_{n \in \mathbb{\mathbb{Z}}^{+}}R^{n}$ 则 $\bigcup_{n \in \mathbb{Z}^{+}}R^{n}$ 是传递的且包含 $R$
设 $R'$ 为包含 $R$ 满足传递性的任意的关系
$R\subseteq R'$，$R^{2}\subseteq R'^{2}\subseteq R'$ … 由数学归纳法知 $R^{k} \subseteq R'(k \in \mathbb{Z}^{+})$
则 $\bigcup_{k\in \mathbb{Z}^{+}}R^{k} \subseteq R'$
则 $t(R) = \bigcup_{k\in \mathbb{Z}^{+}}R^{k}$

若 $|A|=n$ 则 $t(R)= \bigcup^{n}_{k=1}R^{k}$

证明：点击查看证明

也就是证 $k > n$ 时

$R^{k} \subseteq \bigcup^{n}_{k=1}R^{k}$

考虑 $\forall (a,b) \in R^{k}$

则存在序列 $c_{0}=a,c_{1},c_{2},...,c_{k-1},c_{k}=b$

使得 $1 \le i \le k$ $(c_{i},c_{i+1})\subseteq R$

由于 $k > n$ ，必有 $c_{i}$ 不只出现一次

则 $(a,c_{0}),(c_{0},c_{1}),...,(c_{i-1},c_{i}),(c_{i},c_{p}),...,(c_{q},c_{i}),(c_{i},c_{i+1}),...,(c_{k-1},b)\subseteq R$

删去 $(c_{i},c_{p}),...,(c_{q},c_{i})$ 这一段，若序列元素个数大于 $n$ 重复这一过程，知道 $k'\le n$ 为止

此时有 $(a,b)\in R^{k'}$ 则 $(a,b)\in \bigcup^{n}_{k=1}R_{k}$

则 $t(R)= \bigcup^{n}_{k=1}R^{k}$

考虑 $R$ 对闭包的影响

若 $R$ 自反，$s(R),t(R)$ 自反
若 $R$ 对称，$r(R),t(R)$ 对称
若 $R$ 传递，$r(R)$ 传递

考虑多个闭包之间的关系

$rs(R)=sr(R)$
$rt(R)=tr(R)$
$st(R)\subseteq ts(R)$

证明：点击查看证明

\[ \begin{align*} sr(R) &= s(R\cup I_{A})=(R\cup I_{A})\cup(R^{-1}\cup I_{A}) \\ &= R\cup R^{-1}\cup I_{A} \\ &= s(R)\cup I_{A} = rs(R) \end{align*} \]
\[ \begin{align*} rt(R) &= r(\bigcup_{k=1}^{\infty}R^{k}) = \bigcup_{k=1}^{\infty}R^{k}\cup I_{A} \\ &= \bigcup_{k=1}^{\infty}R^{k} \cup \bigcup_{k=1}^{\infty}I_{A} = \bigcup_{k=1}^{\infty}(R^{k}\cup I_{A}) \\ &= \bigcup_{k=1}^{\infty}r(R^{k}) = tr(R) \end{align*} \]
\[R\subseteq s(R)\space \rightarrow \space t(R) \subseteq ts(R)\space \rightarrow \space st(R) \subseteq sts(R)\]
又 $s(R)$ 对称，则 $ts(R)$ 对称，则 $sts(R)=ts(R)$ 得到 $st(R)\subseteq ts(R)$
$e.g$：$R=\{(1,2)\}$
$t(R)=\{(1,2)\}$ $st(R)=\{(1,2),(2,1)\}$
$s(R)={(1,2),(2,1)} $ $ts(R)=\{(1,2),(2,1),(1,1),(2,2)\}$

定义 2.2 等价关系

设 $A$ 为非空集合，$R$ 为 $A$ 上的关系。如果 $R$ 是自反的、对称的和传递的，那么称 $R$ 为 $A$ 上的等价关系

$I_{A}$ 和 $A\times A$ 均为等价关系

定义 2.3 等价类

集合 $A$ 非空，$R$ 为 $A$ 上等价关系，记

\[[x]_{A}=\{y\in A\mid (x,y)\in R\}\]

称 $[x]_{A}$ 为 $x$ 关于 $R$ 的等价类，有时也简记为 $x$ 或 $[x]$

$A$ 非空，$R$ 为 $A$ 上等价关系，对 $\forall x,y\in A$ ，有

$x\in [x]$
若 $(x,y)\in R$ 则 $[x]=[y]$
若 $(x,y)\notin R$ 则 $[x]\cap [y] = \emptyset$
$\bigcup _{x\in A}[x]=A$

证明：点击查看证明

$R$ 具有自反性，有等价类定义知 $x\in [x]$
设 $\exists z \in [x]-[y]$，$(z,x),(x,y)\in R$ 知 $(z,y)\in R$ 则 $z\in [y]$ 矛盾，另一侧同理
设 $z\in[x]\cap [y] \ne \emptyset$，$(z,x),(y,z)\in R$ 则 $(x,y)\in R$ 矛盾
取 $\forall y\in \bigcup _{x\in A}[x]$ 由等价类定义显然 $y\in A$，$\forall z\in A$ 显然 $z\in [z]$ 则 $z\in \bigcup _{x\in A}[x]$ 故 $\bigcup _{x\in A}[x]=A$

定义 2.4 商集

集合 $A$ 非空，$R$ 为 $A$ 上等价关系，所有以 $R$ 产生的等价类的集合叫做 $A$ 的商集，记作 $A/R$

\[A/R=\{[x]\mid x\in A\}\]

定义 2.5 划分

设 $A$ 为非空集合，如果 $A$ 的子集族 $\pi = \{A_i\}_{i \in I} \subseteq \mathcal{P}(A)$ 满足下述条件:

$\varnothing \notin \pi$,
若 $i \neq j$, 则 $A_i \cap A_j = \varnothing$,
$\bigcup_{i \in I} A_i = A$,

那么称 $\pi$ 是 $A$ 的一个划分，称每个 $A_i$ 为 $A$ 的一个划分块。当 $|I| = n$ 时，也称 $\pi$ 是 $A$ 的一个 $n$-划分。

集合 $A$ 上的任意一个划分可以确定 $A$ 上的一个等价关系 $R$

证明：点击查看证明

证明：设集合 $A$ 上有一个划分 $\pi = \{A_i\}_{i \in I}$ 定义关系 $R =\bigcup_{i \in I} A_i \times A_i$，则 $R$ 是 $A$ 上的等价关系。

自反性：对任意 $x \in A$，必存在 $(x,x) \in R$。
对称性：若 $(x,y) \in R$，则存在 $i \in I$ 使 $x,y \in A_i$。因此 $y,x \in A_i$，故 $(y,x) \in R$。
传递性：若 $(x,y) \in R$ 且 $(y,z) \in R$，则存在 $i,j \in I$ 使 $x,y \in A_i$ 且 $y,z \in A_j$。由于划分中的不同块不相交，必有 $i=j$，从而 $x,z \in A_i$，故 $(x,z) \in R$。

综上，$R$ 是 $A$ 上的一个等价关系。

设 $R_1, R_2$ 是集合 $A$ 上的两个等价关系，记 $R = R_1 \cap R_2$。证明 $R$ 也是 $A$ 上的等价关系。

证明：点击查看证明

自反性：对任意 $x \in A$，有 $(x,x) \in R_1$ 且 $(x,x) \in R_2$，因此 $(x,x) \in R$。
对称性：若 $(x,y) \in R$，则 $(x,y) \in R_1$ 且 $(x,y) \in R_2$。由对称性，$(y,x) \in R_1$ 且 $(y,x) \in R_2$，因此 $(y,x) \in R$。
传递性：若 $(x,y) \in R$ 且 $(y,z) \in R$，则 $(x,y),(y,z) \in R_1$，由 $R_1$ 的传递性得 $(x,z) \in R_1$；同理 $(x,y),(y,z) \in R_2$，由 $R_2$ 的传递性得 $(x,z) \in R_2$。于是 $(x,z) \in R_1 \cap R_2 = R$。

综上，$R$ 是 $A$ 上的一个等价关系。

定义 2.6 划分的积

设 $R_1, R_2$ 是集合 $A$ 上的两个等价关系，记 $R = R_1 \cap R_2$，由 $R_{1},R_{2}$ 确定的划分 $\pi_{1},\pi_{2}$ ，则称 $R$ 确定的划分为 $\pi_{1},\pi_{2}$ 的积，记作 $\pi_{1}\cdot \pi_{2}$

定义 2.7 划分的加细

设 $A$ 是一个集合，$ = {A_i}{i I} $ 与 $ = {B_j}{j J} $ 是 $ A $ 的两个划分。

若满足：对任意 $B_j \in \sigma$，都存在某个 $A_i \in \pi$，使得 $B_j \subseteq A_i$，

则称 $\sigma$ 是 $\pi$ 的一个加细，记作 $\sigma \preceq \pi$

设 $ A $ 是一个集合，$\pi, \sigma$ 是 $ A $ 上的两个划分，对应的等价关系分别为 $R_\pi, R_\sigma$

如果 $\sigma$ 是 $\pi$ 的一个加细，即 $\forall B \in \sigma, \; \exists A \in \pi, \; B \subseteq A$

\[ \sigma \preceq \pi \quad \Longleftrightarrow \quad R_\sigma \subseteq R_\pi. \]

证明：点击查看证明

设 $A$ 是集合，$\pi, \sigma$ 是 $A$ 的两个划分，对应的等价关系分别为 $R_\pi, R_\sigma$。

若 $\sigma \preceq \pi$，则 $R_\sigma \subseteq R_\pi$。

假设 $(x,y) \in R_\sigma$，则存在 $B \in \sigma$ 使 $x,y \in B$。

由于 $\sigma \preceq \pi$，必存在某个 $A \in \pi$，使得 $B \subseteq A$。

因此 $x,y \in A$，从而 $(x,y) \in R_\pi$

故 $R_\sigma \subseteq R_\pi$。

若 $R_\sigma \subseteq R_\pi$，则 $\sigma \preceq \pi$。

任取 $B \in \sigma$，并任取 $x,y \in B$，有 $(x,y) \in R_\sigma$。

由 $R_\sigma \subseteq R_\pi$，得 $(x,y) \in R_\pi$。

这说明 $B$ 中所有元素在 $R_\pi$ 下互相等价，因此 $B \subseteq A$，其中 $A \in \pi$ 是 $R_\pi$ 的等价类。

故 $\sigma \preceq \pi$。

综上，
\[ \sigma \preceq \pi \quad \Longleftrightarrow \quad R_\sigma \subseteq R_\pi. \]

设 $\pi_{1},\pi_{2}$ 为 $A$ 划分，则

$\pi_{1}\cdot \pi_{2}$ 细分 $\pi_{1},\pi_{2}$
设 $\pi'$ 为 $A$ 划分，若 $\pi'$ 细分 $\pi_{1},\pi_{2}$ 则 $\pi'$ 细分 $\pi_{1}\cdot \pi_{2}$

都可由关系与划分的对应关系直接可得

定义 2.8 划分的和

设 $R_1, R_2$ 是集合 $A$ 上的两个等价关系，记 $R = R_1 \cup R_2$。
$R_1 \cup R_2$ 是 $A$ 上的自反对称关系，但未必是等价关系，我们取其生成的最小传递关系 $t(R_1 \cup R_2)$，记作 $\langle R \rangle$ 或 $(R_1 \cup R_2)^{+}$

由 $R_1, R_2$ 确定的划分分别为 $\pi_1, \pi_2$，则称 $\langle R \rangle$ 确定的划分为 $\pi_1, \pi_2$ 的和，记作

\[ \pi_1 + \pi_2. \]

容易知道 $\pi_1, \pi_2$ 细分 $\langle R \rangle$

设 $\pi'$ 为 $A$ 划分，若 ${1},{2} $ 细分 $\pi'$ 则 $\pi_1 + \pi_2$ 细分 $\pi'$

简单来说，$\pi_1 + \pi_2$ 是同时比 $\pi_1, \pi_2$ 更粗的最细划分，即它是所有 $\pi$ 的下确界，其中 $\pi \succeq \pi_1, \pi_2$。

定义 2.9 偏序关系

设 $A$ 为非空集合，$R$ 为 $A$ 上的关系。如果 $R$ 是自反的、反对称的和传递的，那么称 $R$ 为 $A$ 上的偏序关系，$(A,R)$ 称为偏序集

$(A,I_{A})$ 是偏序集但 $(A,A\times A)$ 不是偏序集

一般将偏序关系 $R$ 记为 $\preceq$ ，若 $(x,y)\in R$ 则 $x\preceq y$，也有 $\prec$ 的记法，表示 $x\preceq y$ 且 $x\ne y$

偏序关系中的偏意味着部分可比较但未必全部都能比较

定义2.10 偏序的覆盖

设 $(A,\preceq)$ 为偏序集， $\forall x,y\in A$ 若 $x\prec y$ 且不存在 $z\in A$ 使得 $x\prec y\prec z$ 则称 $y$ 覆盖 $x$

定义2.11 哈斯图

对于给定偏序集 $(A,\preceq)$ 按照如下方法画 哈斯图

以 $A$ 中所有元素为顶点，适当排列顶点顺序，满足

$\forall x,y\in A$ 若 $x\prec y$ 则把 $x$ 画在 $y$ 下方
若 $y$ 覆盖 $x$ ，则用一条线段连接 $x$ 和 $y$

定义 2.12 偏序集的特殊元素

设 $(A,\preceq)$ 为偏序集，$b\in B\subseteq A$，$a\in A$

若 $\forall x\in B$ 都有 $x\preceq b$，则称 $b$ 是 $B$ 的最大元
若 $\forall x\in B$ 都有 $b\preceq x$，则称 $b$ 是 $B$ 的最小元
若 $\forall x\in B$ 都有当 $b\preceq x$ 时必有 $x=b$，则称 $b$ 是 $B$ 的极大元
若 $\forall x\in B$ 都有当 $x\preceq b$ 时必有 $x=b$，则称 $b$ 是 $B$ 的极小元
若 $\forall x\in B$ 都有 $x\preceq a$，则称 $a$ 为 $B$ 的上界
若 $\forall x\in B$ 都有 $a\preceq x$，则称 $a$ 为 $B$ 的下界
若 $a$ 为 $B$ 的上界，且对 $B$ 的任意上界 $a'$ 都有 $a\prec a'$ 则称 $a$ 为 $B$ 的最小上界或者上确界
若 $a$ 为 $B$ 的下界，且对 $B$ 的任意下界 $a'$ 都有 $a'\prec a$ 则称 $a$ 为 $B$ 的最大下界或者下确界

从定义可知

最大元和极大元可能是不同的，最大元要求 $B$ 中的所有元素都可比，而极大元只要求能够和极大元比较的元素里不存在比极大元大的元素

$B$ 的最大元一定是 $B$ 的上界，同时也是 $B$ 的最小上界，但 $B$ 的上界不一定是 $B$ 的最大元，因为它可能不是 $B$ 的元素，最小元同理。

如果 $B$ 的最大下界和最小上界存在，那么一定唯一

每个非空有限偏序集 $(A,\preceq)$ 至少有一个极小元

证明：点击查看证明

反证法，假设没有极小元，任意 $x_{0}\in A$ $\exists x_{1}\in A$ 使得 $x_{0}\prec x_{1}$ 无限重复这一过程可得无限序列 $\{x_{n}\}\subseteq A$ 这说明 $A$ 有无限多个元素，这与 $A$ 是个有限集矛盾，故 $A$ 中存在极小元

定义 2.13 全序关系

设 $(A,\preceq)$ 为偏序集， $\forall x,y\in A$ 都是可比的，则称 $\preceq$ 为 $A$ 上的全序关系（或简称全序、线性序）

定义 2.14 拓扑排序

设 $\preceq$ 为非空集合 $A$ 上的偏序关系，$\preceq'$ 为 $A$ 上的全序关系，$\forall x,y\in A$，只要 $x\preceq y$ 成立，必有 $x\preceq' y$，则称全序 $\preceq'$ 与偏序 $\preceq$ 是相容的，由一个偏序构造相容的全序的过程叫做拓扑排序

设 $(A,\preceq)$ 是非空有限偏序集，则 $A$ 上存在与 $\preceq$ 相容的全序 $\preceq'$

证明：点击查看证明

$A$ 中一定有极小元 $x_{1}$，考虑 $A-\{x_{1}\}$，若该集合非空，则 $(A-\{x_{1}\},\preceq)$ 是一个偏序集，继续这一过程，由于 $A$ 是有限集，这个过程一定会终止，最终得到元素序列$x_{1},x_{2},...,x_{n}$ ，所需要的全序关系 $\preceq'$ 由下面的序给出

\[x_{1}\prec' x_{2}\prec' x_{3}\prec' ... \prec' x_{n}\]

$\forall x\prec y$，当 $y$ 作为极小元被选中时，$x$ 已经被选中了，否则 $y$ 不可能是极小元，因此有 $x\prec' y$，即当 $x\preceq y$ 时一定有 $x\preceq' y$，这就证明了全序 $\preceq'$ 和偏序 $\preceq$ 是相容的

拓扑排序算法

输入：$n$ 元偏序集 $(A, \preccurlyeq)$

输出：与 $\preccurlyeq$ 相容的全序 $L: x_1 \preccurlyeq' x_2 \preccurlyeq' \cdots \preccurlyeq' x_n$

$k \leftarrow 1$;
$L \leftarrow \varnothing$;
$\text{while } A \neq \varnothing \text{ do}$
$\quad x_k \leftarrow A \text{ 的极小元}$;
$\quad A \leftarrow A \setminus \{x_k\}$;
$\quad L.\text{append}(x_k)$;
$\quad k \leftarrow k + 1$;
$\text{end}$
$\text{return } L$

拓展

拓展2.1 格

设 $(L,\preceq)$ 是偏序集，如果 $\forall x,y\in L$，$\{x,y\}$ 都有最大下界和最小上界，那么称 $L$ 为偏序 $\preceq$ 的格

用 $a\vee b=\text{lub}(a,b)$ 表示 $a$ 和 $b$ 的最小上界

用 $a\wedge b=\text{glb}(a,b)$ 表示 $a$ 和 $b$ 的最大下界

一般地，设 $n\in N^{+}$，$F_{n}$ 是 $n$ 的正因子的集合，$D$ 为整除关系，偏序集 $(F_{n},D)$ 构成格，事实上，$\forall x,y\in F_{n}$，$\{x,y\}$ 的最小上界是 $lcm(x,y)$，最大下界是 $gcd(x,y)$

拓展2.2 离散与覆盖

$(L,\preceq)$ 是格，若 $a\prec b$，且不存在 $u\in L-\{a,b\}$ 使得 $a\prec u\prec b$，则称 $b$ 覆盖 $a$

若有 $c_{1},c_{2},...,c_{k}\in L$，使得 $c_{i+1}$ 覆盖 $c_{i}$，且 $a=c_{1}\prec c_{2}\prec...\prec c_{k}=b$，则称 $c_{1},c_{2},...,c_{k}$ 为连接 $a$ 和 $b$ 的链。

如果 $L$ 的任何两个元素 $a\prec b$，总有连接它们的链，则称 $L$ 是离散的

有限的离散全序集的哈斯图由一条链组成

拓展2.3 完全格

$(L,\preceq)$ 为格，当任 $A\subseteq L$ 有最大下界、最小上界时，$L$ 显然是格，称为完全格

$L$ 自身的最小上界是整个格 $L$ 的最大元，记为 $1$

$L$ 自身的最大上界是整个格 $L$ 的最小元，记为 $0$

若 $(L,\preceq)$ 为格，则 $\forall a,b\in L$

$a\preceq a\vee b,a\wedge b\preceq a$
$a\preceq b$ $iff$ $a\vee b=b$
$a\preceq b$ $iff$ $a\wedge b=a$

若 $(L,\preceq)$ 为格，$\forall a,b,c\in L$

幂等律：$a\vee a=a,a\wedge a=a$
交换律：$a\vee b=b\vee a,a\wedge b=b\wedge a$
结合律：$a\vee (b\vee c)=(a\vee b)\vee c,a\wedge (b\wedge c)=(a\wedge b)\wedge c$
吸收律：$a\vee (a\wedge b)=a,a\wedge (a\vee b)=a$

证明：点击查看证明

幂等律、交换律由定义直接可得

结合律由上一性质立即可得

吸收律：由 $a \wedge b \preceq a$，得 $a \vee (a \wedge b) \preceq a$；又 $a \preceq a \vee (a \wedge b)$，故 $a = a \vee (a \wedge b)$

至此，可将 $[L; \vee, \wedge]$ 视为代数系统

在 $[L;\vee;\wedge]$ 中，$\vee,\wedge$ 满足上面的四个律，定义关系 $\preceq$ 如下：

$\forall a, b \in L$， $a \preceq b$ 当且仅当 $a \vee b = b$，则 $(L, \preceq)$ 为偏序集

证明：点击查看证明

自反性：由 $a \vee a = a$，得 $a \preceq a$。

反对称性：若 $a \preceq b$ 且 $b \preceq a$，则 $a \vee b = b$，$b \vee a = a$，故 $a = b$

传递性：若 $a \preceq b$ 且 $b \preceq c$，则 $a \vee b = b$，$b \vee c = c$，

于是 $a \vee c = (a \vee b) \vee c = b \vee c = c$ 故 $a \preceq c$

因此 $\preceq$ 是偏序关系。

下面证明 $(L,\preceq)$ 是格

证明：点击查看证明

只需证明 $a \vee b = \text{lub}(a, b)$，$a \wedge b = \text{glb}(a, b)$

由结合律和幂等律 $a \vee (a \vee b) = (a \vee a) \vee b = a \vee b$ 故 $a \preceq a\vee b$

同理 $b \preceq a \vee b$，所以 $a \vee b$ 是 $\{a, b\}$ 的上界

设 $u \in L$ 满足 $a \preceq u$ 且 $b \preceq u$，即 $a \vee u = u$，$b \vee u = u$ 则 $(a \vee b) \vee u = a \vee (b \vee u) = a \vee u = u$ 故 $a \vee b \preceq u$ 因此 $a \vee b = \text{lub}(a, b)$

由吸收律：$a \wedge b = a \wedge (a \vee b) \preceq a$，同理 $a \wedge b \preceq b$，故 $a \wedge b$ 是 $\{a, b\}$ 的下界

设 $v \preceq a$ 且 $v \preceq b$，则 $v \vee a = a$，$v \vee b = b$，于是 $v \wedge (a \wedge b) = (v \wedge a) \wedge b = v \wedge b = v$ 故 $v \preceq a \wedge b$，因此 $a \wedge b = \text{glb}(a, b)$

所以 $[L; \vee, \wedge]$ 为格。

$[L; \vee, \wedge]$ 是一代数系统，$\vee$ 和 $\wedge$ 为定义在 $L$ 上的二元运算。当其满足以上四个律时，称为格。并称 $\wedge$ 为积（或交），$\vee$ 为和（或并）

格 $[L; \vee, \wedge]$，任意 $a, b, c \in L$，当 $b \preceq c$ 时有 $a \wedge b \preceq a \wedge c$ 及 $a \vee b \preceq a \vee c$。

证明：点击查看证明

$(a \wedge b) \wedge (a \wedge c) = a \wedge (b \wedge c) = a \wedge b$

因此 $a \wedge b \preceq a \wedge c$

同理可证 $a \vee b \preceq a \vee c$

拓展2.4 子格

$[L; \vee, \wedge]$ 为格，$T \subseteq L$，$T \neq \emptyset$，若 $T$ 关于 $\vee$ 和 $\wedge$ 封闭（即对任意 $a, b \in T$，有 $a \vee b \in T$ 且 $a \wedge b \in T$），则称 $T$ 为 $L$ 的子格

当 $T$ 为 $L$ 的子格时，$T$ 一定是格。但当 $T \subseteq L$，且 $T$ 关于 $L$ 中的偏序关系 $$ 构成格时，$T$ 不一定是 $L$ 的子格

例如：

当 $S = \{1,2,3\}$ 时，$S_3 = \{e, \sigma_1, \sigma_2, \sigma_3, \sigma_4, \sigma_5\}$ 是3次对称群

$[\mathcal{P}(S); \cup, \cap]$ 是格，且为完全格

取 $T = \{\{e\}, H_1, H_2, H_3, H_4, S\}$

其中 $H_1 = \{e, \sigma_1\}$ $H_2 = \{e, \sigma_2\}$ $H_3 = \{e, \sigma_3\}$ $H_4 = \{e, \sigma_4, \sigma_5\}$

这4个都是 $S_3$ 的子群，$\{e\}, S$ 是其两个平凡子群，则 $(T; \subseteq)$ 也是格，但不是 $[\mathcal{P}(S); \subseteq]$ 的子格。

推广

一个群 $G$ 的子群全体关于包含关系 $\subseteq$ 所构成的格，不是该群的所有子集组成的集合（即 $G$ 的幂集 $\mathcal{P}(G)$）关于包含关系所构成的格的子格，因为子群的并（或交）并不一定是子群

闭包	记为
自反闭包	\(r(R)\)
对称闭包	\(s(R)\)
传递闭包	\(t(R)\)

(´-ω-｀)

集合与图论学习笔记02

定义

定义 2.1 闭包

定义 2.2 等价关系

定义 2.3 等价类

定义 2.4 商集

定义 2.5 划分

定义 2.6 划分的积

定义 2.7 划分的加细

定义 2.8 划分的和

定义 2.9 偏序关系

定义2.10 偏序的覆盖

定义2.11 哈斯图

定义 2.12 偏序集的特殊元素

定义 2.13 全序关系

定义 2.14 拓扑排序

拓展

拓展2.1 格

拓展2.2 离散与覆盖

拓展2.3 完全格

拓展2.4 子格