定义

偏序关系 $:=$

• 自反
• 反对称
• 传递

• $\preceq$ 为偏序关系 $A$ 的偏关系

• $(A,\preceq)$ 为偏序集 (简记为 $A$)

• 覆盖 := $a \preceq b \land \neg \exists c(a\preceq c \preceq b)$ aka $b$ 覆盖 $a$

• 全序关系 := 任意两个元素可比

  • 字典序一定全序
  • 各属性全序 但 没优先级 $\Rightarrow$ 笛卡尔积不是全序

大小元

• 极大元 $$a\in S是S极大元 \equiv \forall b\in S(a \preceq b \to a =b)$$

• 极小元 $$a\in S是S极小元 \equiv \forall b\in S(b \preceq a \to a =b)$$

• 最大元 $$a\in S是S最大元 \equiv \forall b\in S(b \preceq a)$$

• 最小元 $$a\in S是S最小元 \equiv \forall b\in S(a \preceq b)$$

界

前提

• $S\subset A$
• $(A,\preceq)$ 偏序

定义

• 上界 $$a\in A是S上界 \equiv \forall b\in S(b\preceq a)$$

• 下界 $$a\in A是S下界 \equiv \forall b\in S(a\preceq b)$$

• 上确界 $$a\in A是S上确界 \equiv \forall b\in A(b是S上界 \to a\preceq b)$$

• 下确界 $$a\in A是S下确界 \equiv \forall b\in A(b是S下界 \to b\preceq a)$$

哈斯图

1. 哈斯图 $\neq$ 关系图
2. 只有当 $b$ 覆盖 $a$ 时，哈斯图才有 $(a,b)$