Dianpu River Bridge

Dianpu River Bridge, Minhang

适用教材:Advanced Modern Algebra
如有疏漏，敬请指正

偏序集

一个集合$X$是偏序集，如果在其上有一个二元关系$x \preceq y$，且该关系满足对所有$x,y,z \in X$，有

  • 自反性：$x \preceq x$
  • 反对称性：若$x \preceq y$，且$y \preceq x$，那么$x=y$
  • 传递性：若$x \preceq y$且$y \preceq z$，那么$x \preceq z$

若对于任意$a,b \in X$，必有$a \preceq b$或$b \preceq a$，则$X$是一个全序集

上下界

令$Y$是偏序集$X$的子集

元素$u$是$Y$的上界，如果对于所有$a \in Y$，都有$a \preceq u$
如果对所有上界$v$都有$u \preceq v$，那么$u$是上确界

下界及下确界也可以类似定义

格

格是一个偏序集$\mathcal{L}$，且满足$\mathcal{L}$中的每一对元素都有上确界和下确界

$a,b \in \mathcal{L}$的上确界被称为$a$和$b$的并，记作$a \vee b$
$a,b \in \mathcal{L}$的下确界被称为$a$和$b$的交，记作$a \land b$

举例

  • 所有全序集都是格
  • $U$是一个集合，定义$A \preceq B$为$A \subseteq B$，那么$\mathcal{P}(U)$是一个格，且$A \land B=A \cap B,A \vee B=A \cup B$
  • 若$G$是一个群，定义$\mathcal{L}=Sub(G)$是$G$的所有子群组成的集合，定义$A \preceq B$为$A \leq B$，即$A$是$B$的子群。那么$\mathcal{L}$是一个格，有$A \land B=A \cap B$，$A \vee B$是由$A \cup B$生成的子群
  • $\lbrace \varnothing , \lbrace 0 \rbrace ,\lbrace 1 \rbrace \rbrace$是偏序集，但不是格

定理

  • 对偶性:若命题对于一个格为真，则将命题与格中的$\preceq$和$\succeq$，$\vee$和$\land$互换后，命题依然为真
  • 交换律:$a \vee b=b \vee a, a \land b=b \land a$
  • 结合律:$a \vee (b \vee c)=(a \vee b) \vee c, a \land (b \land c)=(a \land b) \land c$
  • 幂等律:$a \vee a=a,a \land a=a$
  • 吸收律:$a \vee (a \land b)=a,a \land (a \vee b)=a$

布尔代数

引理:一个偏序集$X$可能会有

  • 最大元素$I$:对任何$a \in X$，有$a \preceq I$
  • 最小元素$O$:对任何$a \in X$，有$O \preceq a$

如果一个配备了这样的$I$和$O$的格$L$满足:
对任何$a \in L$，存在$a’ \in L$，使得$a \vee a’=I$且$a \land a’=O$
则称$L$是有补的

如果一个格$L$满足:
对任意$a,b,c \in L$，满足$a \land (b \vee c)=(a \land b) \vee (a \land c)$(将每个位置的$\vee$与$\land$互换亦可)
则称这个格满足分配律

定义:布尔代数是一个配备了最大元素$I$与最小元素$O$的格$B$，且$B$有补并满足分配律
一个偏序集$B$是布尔代数当且仅当其满足交换律，结合律，分配律，并配备最大元素$I$和最小元素$O$，且有补

举例

  • 集合$X$的幂集$\mathcal{P} (X)$是布尔代数
  • 配备了关系$\leq$的整数集$\lbrace 0,1,2,3,4 \rbrace$是一个格，但不是布尔代数，因为其不是有补的

性质

若$B$是布尔代数，那么有

  • 对任意$a,b,c \in B$，若$a \vee b=a \vee c$且$a \land b=a \land c$，那么$b=c$
  • 对任意$a \in B$，$a’$唯一，且有$(a’)’=a$
  • $I’=O$且$O’=I$
  • $(a \vee b)’ = a’ \land b’$且$(a \land b)’=a’ \vee b’$
  • $a \preceq b \Leftrightarrow a \land b’ = O \Leftrightarrow a’ \vee b =I$，它的等价表示为$\urcorner (a \preceq b) \Leftrightarrow a \land b’ \neq O \Leftrightarrow a’ \vee b \neq I$

有限布尔代数

若一个布尔代数有有限个元素，那么它就是有限布尔代数

布尔同构

令$B$和$C$是布尔代数。若对所有$a,b \in B$，有

那么双射$\phi : B \to C$是布尔同构

原子

令$b \neq O$是有限布尔代数$B$中的元素。若对任意$a \neq O$且$a \preceq b$，有$a=b$，那么$b$是$B$的一个原子。
$B$中的原子组成的集合可表示为$atom(B)$

性质

  • 若$a,b \in atom(B)$并且$a \neq b$，那么$a \land b =O$
  • 若$b \neq O$，$\urcorner (b \preceq c)$当且仅当存在$a \in atom(B)$，有$a \preceq b$且$\urcorner (a \preceq c)$
  • 令$b \in B, A_{b}= \lbrace a_{i} : i=1, \cdots ,n \; \mathrm{and} \; a_{i} \preceq b \rbrace$是$B$中的原子组成的一个集合，那么$A_{b}$是$\preceq b$的所有原子组成的集合当且仅当$b= a_{1} \vee \cdots \vee a_{n}$

布尔同构定理

令$B$是一个有限布尔代数且$A=atom(B)$，那么$B \cong \mathcal{P} (A)$