半格
| 半格 | |
|---|---|
| 术语名称 | 半格 |
| 英语名称 | semilattice |
| 交半格 | |
|---|---|
| 术语名称 | 交半格 |
| 英语名称 | meet-semilattice |
| 别名 | lower semilattice |
| 并半格 | |
|---|---|
| 术语名称 | 并半格 |
| 英语名称 | join-semilattice |
| 别名 | upper semilattice |
| 交 | |
|---|---|
| 术语名称 | 交 |
| 英语名称 | meet |
| 并 | |
|---|---|
| 术语名称 | 并 |
| 英语名称 | join |
交半格(meet-semilattice)指一个偏序集的有限子集总有下确界。 并半格(join-semilattice)指一个偏序集的有限子集总有上确界。 也指其由抽象出的，满足结合律、交换律、幂等律的代数系统。
满足这一条件的偏序满足这样的运算规则，满足这一规则的代数结构本身也定义了一个偏序，可认为是等价地描述了同一个结构。
定义
以下两个定义的结构等价。
序理论定义
对偏序集 [math]\displaystyle{ (P, \preceq) }[/math] ，若对任意子集 [math]\displaystyle{ \{x,y\} \subseteq P }[/math] 都存在其下确界，则此时， 称 [math]\displaystyle{ P }[/math] 是一个交半格(meet-semilattice)， 其中由 [math]\displaystyle{ x,y }[/math] （可相同）构成的集合的下确界称为元素 [math]\displaystyle{ x,y }[/math] 的交(meet)， 记作 [math]\displaystyle{ x \wedge y }[/math] 。
对偏序集 [math]\displaystyle{ (P, \preceq) }[/math] ，若对任意子集 [math]\displaystyle{ \{x,y\} \subseteq P }[/math] 都存在其上确界，则此时， 称 [math]\displaystyle{ P }[/math] 是一个并半格(join-semilattice)， 其中由 [math]\displaystyle{ x,y }[/math] （可相同）构成的集合的上确界称为元素 [math]\displaystyle{ x,y }[/math] 的并(join)， 记作 [math]\displaystyle{ x \vee y }[/math] 。
交半格和并半格统称半格(semilattice)。
代数系统定义
对非空集合 [math]\displaystyle{ S }[/math] 及其上一个二元运算 [math]\displaystyle{ \wedge }[/math] ，若其满足以下公理：
- 封闭性(closure)： [math]\displaystyle{ (\forall a, b \in S) (a\wedge b \in S) }[/math] ；
- 结合性(associativity)： [math]\displaystyle{ (\forall a,b,c \in S) ((a\cdot b)\cdot c = a\cdot (b\cdot c)) }[/math] 。
- 交换性(commutativity)： [math]\displaystyle{ (\forall a,b \in S) (a\wedge b = b\wedge a) }[/math] 。
- 幂等性(idempotency)： [math]\displaystyle{ (\forall a \in S) (a\wedge a = a) }[/math] 。
则构成的代数系统 [math]\displaystyle{ \langle S, \wedge \rangle }[/math] 称为一个半格(semilattice)。
以上定义的代数系统中，运算 [math]\displaystyle{ \wedge }[/math] 称为交(meet)，并称代数系统 [math]\displaystyle{ (S, \wedge) }[/math] 为交半格(meet-semilattice)； 如果使用 [math]\displaystyle{ \vee }[/math] ，称为并(join)，并称代数系统 [math]\displaystyle{ (S, \vee) }[/math] 为并半格(join-semilattice)。
性质描述
- 满足幂等律的交换半群称为半格。
两种定义的等价性
序理论定义和代数系统定义是等价的：
- 序理论到代数
- 在序理论定义的交半格 [math]\displaystyle{ (P, \leq) }[/math] 中，定义任意两个元素到其下确界的运算 [math]\displaystyle{ a \wedge b = \inf\{a,b\} }[/math] ；
- 在序理论定义的并半格 [math]\displaystyle{ (P, \leq) }[/math] 中，定义任意两个元素到其上确界的运算 [math]\displaystyle{ a \vee b = \sup\{a,b\} }[/math] ；
- 则这些运算满足结合律、交换律、幂等律的代数结构。
- 从代数到序理论
- 在代数定义的交半格 [math]\displaystyle{ (S, \wedge) }[/math] 中，定义偏序 [math]\displaystyle{ a \leq b \Leftrightarrow a \wedge b = a }[/math] ；
- 在代数定义的并半格 [math]\displaystyle{ (S, \vee) }[/math] 中，定义偏序 [math]\displaystyle{ a \leq b \Leftrightarrow a \vee b = b }[/math] ；
- 这些偏序关系使得代数运算对应偏序中的确界。
性质
- 基本特征
- 交半格：任意两个元素有下确界（交运算 [math]\displaystyle{ \wedge }[/math] ）。
- 并半格：任意两个元素有上确界（并运算 [math]\displaystyle{ \vee }[/math] ）。
- 半格是交半格和并半格的统称，只要求有上确界和下确界之一。
- 半格是有向集：交半格是下有向集，并半格是上有向集。
- 与格的关系
- 格是半格的特化，两个运算使其既是交半格也是并半格。
- 半格是格的推广，只要求的一侧的运算关系，去掉了另一个运算的存在性要求。
- 通过添加元素可以将半格完备化为格。
- 运算性质
- 代数性质
- 半格是幂等、交换的半群。
| 二元关系复合类型 | |||||
|---|---|---|---|---|---|
| 名称 | 自反、反自反 | 对称、反对称 | 传递 | 其他 | |
| 相容关系 | 自反 | 对称 | - | - | |
| 预序 | 自反 | - | 传递 | - | |
| 等价关系 | 自反 | 对称 | 传递 | - | |
| 方向 | 自反 | - | 传递 | 有上/下界 | |
| 偏序 | 自反 | 反对称 | 传递 | - | |
| 半格 | 自反 | 反对称 | 传递 | 有上/下确界 | |
| 弱序/全序划分 | 自反 | - | 传递 | 完全 | |
| 全序 | 自反 | 反对称 | 传递 | 完全 | |
| 良序 | 自反 | 反对称 | 传递 | 完全、良基 | |
| 不对称 | 反自反 | 反对称 | - | - | |
| 拟序/严格偏序 | 反自反 | 反对称 | 传递 | - | |
| 严格弱序/严格全序划分 | 反自反 | 反对称 | 传递 | 不可比关系传递 | |
| 严格全序 | 反自反 | 反对称 | 传递 | 完全 | |