{%hackmd @RintarouTW/About %}

# Lattice

## Join($\vee$) and Meet ($\land$)

lub = $a\vee b$ = a join b
glb = $a\land b$ = a meet b

:::info
unique if exist, consider them as binary operations on a set.
:::

### $\vee$ and $\land$ are communative

$a\vee b = b\vee a$
$a\land b = b\land a$

:::warning
unlike $\preceq$ which is antisymmetric relation(or binary operation) and not communative.
:::

## Lattice

A lattice is a [Poset](/@RintarouTW/Poset) ($L$, $\preceq$)

$\implies \forall a,b \in L, \exists! (a\land b)\text{ and }\exists!(a\vee b)$, donoted by [$L$;$\vee$,$\land$]

It is a lattice under $\preceq$.

:::success
Lattice is more strict condition than poset, which require all pairs of the elements have lub, glb exist in $L$
:::

### The power set of a three element set

$(\mathcal{P}(A),\subseteq)$ is a poset, and every pair of A had a greatest lower bound and least upper bound. Then $(\mathcal{P}(A),\subseteq)$ is a lattice.

digraph {graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->"{a}","{b}","{c}";"{a}"->"{a,b}","{a,c}";"{b}"->"{b,c}","{a,b}";"{c}"->"{a,c}","{b,c}";"{a,b}","{a,c}","{b,c}"->"{a,b,c}"}

$\cases{
a\vee b = a\cup b\\
a\land b = a\cap b
}\implies [\mathcal{P}(A);\cup,\cap]$

### Distributive Lattice

[$L;,\vee,\wedge$] is a distributive lattice,

$\forall a,b,c \in L,\cases{a\wedge(b\vee c)\iff (a\wedge b)\vee(a\wedge c)\\
a\vee(b\wedge c)\iff (a\vee b)\wedge(a\vee c)
}$

### Nondistributive Lattice

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->0,a,b,c;a->a,1;b->b,1;c->c,1;1->1
}

$\cases{a\wedge(b\vee c)=a\\
(a\wedge b)\vee(a\wedge c)=0
}$

$\cases{a\vee(b\wedge c)=a\\
(a\vee b)\wedge(a\vee c)=1
}$

#### Diamond Lattice

If a lattice contains a sublattice which is isomorphic to the diamond lattice, it's a nondistributive lattice.

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->a,b,c->1;
}

#### Pantegon Lattice

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->a,b;
a->c;
b->1;
c->1;
}

$\cases{a\vee(b\wedge c)=a\\
(a\vee b)\wedge(a\vee c)=c
}$

The lattice contains pategon lattice is also a nondistributive lattice.

## Bounded Lattice

Both the gratest element(**1**) and the least element(**0**) exist. Then it's called a bounded lattice.

:::success
$$
\forall x\in L\cases{
x\vee 1 = 1\\
x\land 1 = x\\
x\vee 0 = x\\
x\land 0 = 0
}
$$
:::

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [fontcolor="#888800";color="#888800"];
edge [arrowsize=0.5]
0->x [xlabel="lub"];
x->1 [xlabel="lub"];
x->0 [xlabel="glb"];
1->x [xlabel="glb"];
}

## The Complement(s) of a Lattice Element

If [$L;\vee,\land$] is a bounded lattice, if $a\in L$ has a complement $b\in L$,

$$
\cases {
a\vee b = 1\\
a\land b = 0
}
$$

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->a,b->1;
}

$a,b$ are the complments of each other.

:::warning
A lattice element can have multiple complements.
:::

digraph {
graph [rankdir=BT];
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800"];
0->a,b,c->1;
}

$a,b,c$ are the complments of each others.

## Complemented Lattice

Let $\mathcal{L}$ = [$L;\vee,\land$] is a bounded lattice,
$\mathcal{L}$ is a complemented lattice if $\forall a\in L$ has a(at least one) complement(s) in $L$.

## Complementation as an opeartion ($a\to \bar{a}$)

If a complmented lattice has the property that the complement of every elelment is **unique**, then we consider complmentation to be a unary operation. (denotated by $\bar{a}$)

## One condition for unique complements

[$L;\vee,\land$] is a **complemented** and **distributive** lattice, then the complement of each element $a\in L$ is **unique**.

Assume $b,c\in L, b\neq c$ are both $a$'s complements,

$\implies \cases{
a\vee b = a\vee c = 1\\
a\land b = a\land c = 0
}$

since [$L;\vee,\land$] is a distributive lattice,

$\implies a\vee (b\land c) = (a\vee b)\land(a\vee c) = 1\land 1 = 1$

$a\vee (b\land c) = 1\implies b\land c = b\text{ or } b\land c = c\\
\implies b=c$

:::info
Since it's a distributive lattice, both diamond and pantegon lattice are not allowed, this impiles when $(b\land c = b)\implies b = c$, or $(b\land c = c) \implies b = c$.
:::

This is contradiction to $b\neq c$. So there's a unique complement of each element in $L$.

###### tags: `math` `lattice`