Lattice

A lattice is an abstract structure that consists of a partially ordered set in which every pair of elements has a unique LUB and a unique GLB.

\(a \lor b = lub(a,b)\) (join)

\(a \land b = glb(a,b)\) (meet)

in the case of a divisibility order, lub(a,b) is LCM(a,b), glb(a,b) is GCD(a,b)

this could be memoried by the method of "\(\lor\) opens up so it's upper bound, \(\land\) opens down so it's lower bound."

e.g. A power set of a set, partially ordered by inclusion.

e.g. Natural numbers, partially ordered by divisibility.

\((L; \preceq)\) is a lattice, when:

forall a,b in L, there is

1. \(a \preceq a \lor b, a \land b \preceq a\).
2. \(a \preceq b \Leftrightarrow a \lor b = b\).
3. \(a \preceq b \Leftrightarrow a \land b = a\).

so, two calculations \(\land\) and \(\lor\) are dual-operand operations on L != emptyset.

thus there is some patterns of its operation.

like

1. Idempotent (幂等) : \(a \lor a = a, \ a \land a = a\).
2. Commutative: \(a \lor b = b \lor a, \ a \land b = b \land a\).
3. Associative: \(a \lor (b \lor c) = (a \lor b) \lor c, \ a \land (b \land c) = (a \land b) \land c\)
4. Absorption: \(a \lor (a \land b) = a \land (a \lor b) = a\).

so when the four rules are valid, we could get \(a \land b = a \Leftrightarrow a \lor b = b\).

it's come to a network now that the lattice as an algebraic structure (\([L; \lor,\land]\)) corresponds to the lattice as an poset. (\([L; \preceq]\))

It has the property of Isotony (保序性), in which when \(b \preceq c, \ a \land b \preceq a \land c, \ a \lor b \preceq a \lor c\).

so there we could have a definition of sublattice. if T is a non-empty subset of L, and it has closure(封闭性) then it's a sublattice of L.

A complete lattice is a partially ordered set in which all subsets (infinite or finite)have both a supremum(join) and an infimum(meet).

the LUB of the whole set (meet of L) is called the greatest element (最大元)， notated as 1.

the GLB of the whole set (join of L) is called the least element (最小元), notated as 0.

thus \(\forall x \in L, \ x \preceq 1, \ 0\preceq x\).

Bounded Lattice is a lattice that has a greatest element 1 and a smallest element 0.

Thus it has the property of this: \(\forall a \in L, a \lor 1 = 1; \ a \land 0 = 0; \ a \land 1 = a; \ a \lor 0 = a\);

Forall lattice there is a distributive inequality:

• \(a \lor (b \land c) \preceq (a \lor b) \land (a \lor c)\).
• \((a \land b) \lor (a \land c) \preceq a \land (b \lor c)\).

When the \(\preceq\) becomes =, then the lattice is a Distributive Lattice.

e.g. the powerset of an non-empty set \(S\), \([P(s); \lor,\land]\) is a distributive lattice. and there is a greatest element and a least element, thus it's a bounded lattice, also a complemented lattice.

forall lattice \([L; \lor, \land]\), the following three statements are equal.

1. \(\forall a,b,c \in L\), there is \(a \land (b \lor c) = (a \land b) \lor (a \land c)\);
2. \(\forall a,b,c \in L\), there is \(a \lor (b \land c) = (a \lor b) \land (a \lor c)\);
3. \(\forall a,b,c \in L\), there is \((a \land b) \lor (v \land c) \lor (c \land a) = (a \lor b) \land (b \lor c) \land (c \lor a)\).
4. It doesnot have a sublattice that's isomorphic to M5 or N5.

A Boole Lattice is a complemented & distributive lattice, notated as \((B; \preceq)\).

When represented as an Algebraic Structure, it could be written as \((B; \lor, \land, ')\), in which ' is the complement operation.

Boole Lattice has following properties:

1. \(\forall a \in B\), a has only one complement.
2. \((a \land b)' = a' \lor b', \ (a \lor b)' = a' \land b'\)
3. \((a \land b) = 0 \Leftrightarrow a \preceq b'\)