引子：Pre-ordering on MonoidsPermalink

某些 Elementary Algebraic Structures 由其定义可以很自然地引出一些 ordering 的结构，比如 wikipedia: Monoid 说：

Any commutative monoid is endowed with its algebraic preordering $\le$, defined by $x\le y$ if there exists $z$ such that $x+z=y$.

并不是说 “只有 commutative monoid 才有 pre-order”，Non-commutative 的 monoid 也可以有，见 讨论。可能是 commutative monoid 的 pre-order 更普遍，具体的细节我们不用深究。

Order-Theoretic Definition of SemilatticesPermalink

Poset = Partially Ordered Set. 这个简写还蛮常用的。

Theorem 2.1: Meet semilattices 与 Posets 等价

(1) Meet Semilattice $(S,\wedge )$ $\Rightarrow$ Poset $(S,\le )$

In a meet semilattice $(S,\wedge )$, define $x\le y⟺x\wedge y=x$. Then $(S,\le )$ is a poset in which $\mathrm{\forall }$ pair of elements $(x,y)$ has a greatest lower bound $\mathrm{glb}(x,y)=x\wedge y$.

(2) Poset $(S,\le )$ $\Rightarrow$ Join Semilattice $(S,\wedge )$

Conversely, given a poset $(S,\le )$ in which $\mathrm{\forall }$ pair of elements $(x,y)$ has a greatest lower bound $\mathrm{glb}(x,y)$, define $x\wedge y=\mathrm{glb}(x,y)$. Then $(S,\wedge )$ is a semilattice. $◼$

注意 $\mathrm{glb}(x,y)=x\wedge y$ 这个值不一定等于 $x$ 或者 $y$。考虑 Theorem 2.1 (1) 中 comparable vs incomparable 的情况：

• comparable: $x\le y⟺x\wedge y=x$，于是 $\mathrm{glb}(x,y)=x$
• comparable: $y\le x⟺x\wedge y=y$，于是 $\mathrm{glb}(x,y)=y$
• incomparable: $x\oslash y⟺x\wedge y\ne x\text{ and }x\wedge y\ne y$，于是 $\mathrm{glb}(x,y)\ne x\text{ and }\mathrm{glb}(x,y)\ne y$，更严格来说是 $\mathrm{glb}(x,y)<x\text{ and }\mathrm{glb}(x,y)<y$

我们来证明 Theorem 2.1 (1) 中的 $(S,\le )$ is a poset

Proof: (Reflexive)

• 因为 semilattice 是 idempotent 的，所以 $x\wedge x=x$，所以 $x\le x$

(Antisymmetric)

• 若 $x\le y$，则 $x\wedge y=x$
• 若 $y\le x$，则 $y\wedge x=y$
• 若 $x\le y$ 和 $y\le x$ 同时成立，根据 semilattice 的 commutative 性质，我们有 $x\wedge y=y\wedge x$，相当于 $x=y$

(Transitive)

• 若 $x\le y$，则 $x\wedge y=x$
• 若 $y\le z$，则 $y\wedge z=y$
• 若 $x\le y\le z$，根据 semilattice 的 associative 性质，我们有 $x\wedge z=(x\wedge y)\wedge z=x\wedge (y\wedge z)=x\wedge y=x$，于是 $x\le z$

于是 $(S,\le )$ is a poset. $◼$

同样的思路也可以证明 Theorem 2.1 (2) 中的 $(S,\wedge )$ is semilattice.

Theorem 2.2: Join semilattices 与 Posets 等价

(1) Join Semilattice $(S,\vee )$ $\Rightarrow$ Poset $(S,\ge )$

In a meet semilattice $(S,\vee )$, define $x\ge y⟺x\vee y=x$. Then $(S,\ge )$ is a poset in which $\mathrm{\forall }$ pair of elements $(x,y)$ has a least upper bound $\mathrm{lub}(x,y)=x\vee y$.

(2) Poset $(S,\ge )$ $\Rightarrow$ Join Semilattice $(S,\vee )$

Conversely, given a poset $(S,\ge )$ in which $\mathrm{\forall }$ pair of elements $(x,y)$ has a least upper bound $\mathrm{lub}(x,y)$, define $x\vee y=\mathrm{lub}(x,y)$. Then $(S,\vee )$ is a semilattice. $◼$

Order-Theoretic Definition of LatticesPermalink

Theorem 2.3: Lattices 与 Posets 等价

(1) Lattice $(S,\wedge ,\vee )$ $\Rightarrow$ Poset $(S,\le )$

In a lattice $(S,\wedge ,\vee )$, define $x\le y⟺x\wedge y=x$. Then $(S,\le )$ is a poset in which $\mathrm{\forall }$ pair of elements $(x,y)$ has

• a greatest lower bound $\mathrm{glb}(x,y)=x\wedge y$, and
• a least upper bound $\mathrm{lub}(x,y)=x\vee y$.

(2) Poset $(S,\le )$ $\Rightarrow$ Lattice $(S,\wedge ,\vee )$

Conversely, given a poset $(S,\le )$ in which $\mathrm{\forall }$ pair of elements $(x,y)$ has

• a greatest lower bound $\mathrm{glb}(x,y)$, and
• a least upper bound $\mathrm{lub}(x,y)$,

define

• $x\wedge y=\mathrm{glb}(x,y)$, and
• $x\vee y=\mathrm{lub}(x,y)$.

Then $(S,\wedge ,\vee )$ is a lattice. $◼$

Claim: Given a lattice $(S,\wedge ,\vee )$, $x\wedge y=x⟺x\vee y=y$

Proof: (1) $x\wedge y=x\Rightarrow x\vee y=y$

我们有 absorption law:

我们可以调换 $x,y$，把 absorption law 转写成：

当 $x\wedge y=x$ 时，因为 lattice 的 commutative 性质，我们有：

将 $\text{(3)}$ 带入 $\text{(2)}$，并再次根据 commutative 性质，得到：

所以 $x\wedge y=x\Rightarrow x\vee y=y$ 成立。

(2) $x\wedge y=x\Leftarrow x\vee y=y$ 证明类似 $◼$

结合这个 claim，我们可以看到 Theorem 2.3 (1) 中的 “define $x\le y⟺x\wedge y=x$” 本质是：

也就是意味着，”用 $\wedge$ 去定义 $\le$” 和 “用 $\vee$ 去定义 $\le$” 是等效的。

更精炼的定义Permalink

前面说 “$\mathrm{\forall }$ pair of elements $(x,y)$ of $S$ has a greatest lower bound $\mathrm{glb}(x,y)$”，其实可以递归描述成 “$\mathrm{\forall }$ nonempty finite subset of $S$ has a meet”，于是我们有：

Definition 1: A poset $S$ is a meet-semilattice (resp. join-semilattice) if $\mathrm{\forall }$ nonempty finite subset of $S$ has a meet (resp. join).

Definition 2: A poset that is both a meet-semilattice and a join-semilattice is a lattice.

Observation 1: Every finite meet-semilattice (resp. join-semilattice) $S$ is bounded by $\bigwedge S$ (resp. $\bigvee S$)

Observation 2: Every finite lattice $S$ is bounded by $\bigwedge S$ and $\bigvee S$

Proposition 1: Every finite meet-semilattice (resp. join-semilattice) also bounded by $\bigvee S$ (resp. $\bigwedge S$) is a lattice.

Proof: 假设 $S$ 是一个 finite meet-semilattice also bounded by $\bigvee S$. 往证：$\mathrm{\forall }$ pair of elements $x,y\in S$ has a join.

构造 $S_{xy}=\{z\in S\mid x\le z\text{ and }y\le z\}$. 因为 $S$ 是 finite meet-semilattice 且 $S_{xy}$ 是 $S$ 的 finite subset，所以 $S_{xy}$ has a meet $m$. 往证：$m$ is the join of $x,y$.

明显 $x$ 是 $S_{xy}$ 的一个 lower bound，由于 $m$ 是 $S_{xy}$ 的 meet, i.e. greatest lower bound，所以 $x\le m$；同理 $y\le m$。所以 $m$ 是 $x,y$ 的一个 upper bound。往证：$m$ is the least upper bound of $x,y$.

考虑 $x,y$ 的 $\mathrm{\forall }$ upper bound $m^{\prime }$，一定有 $m^{\prime }\in S_{xy}$，且由于 $S_{xy}$ 的 meet 是 $m$，所以 $m\le m^{\prime }$，所以 $m$ is the least upper bound of $x,y$。

结论成立。$◼$

ReferencesPermalink

• https://math.hawaii.edu/~jb/math618/os2uh_17.pdf
• https://math.mit.edu/~fgotti/docs/Courses/Combinatorial Analysis/37. Intro to Lattices/Intro to Lattices.pdf