Lattice

algebra

Definition

Lattice

A lattice $(L,\wedge ,\vee )$ is an algebraic structure that has the following axioms:

1. $(L,\wedge )$ is a commutative semigroup
2. $(L,\vee$ is a commutative semigroup
3. Absorption: For all $a,b\in L$:

$$\begin{array}{rl}a& =a\wedge (a\vee b)\\ a& =a\vee (a\wedge b)\end{array}$$

Examples:

1. $(P(A),\cap ,\cup )$
2. $(\mathbb{N},\min ,\max )$
3. $(\mathbb{N}\setminus \{0\},\gcd ,\mathrm{lcm})$

Distributivity

Definition

Distributive Lattice

A lattice $(L,\wedge ,\vee )$ is called distributive if the following holds for all $a,b,c\in L$:

1. $a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$
2. $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$

Link to original

Boolean Algebra

Definition

Boolean Algebra

A distributive lattice $(L,\wedge ,\vee )$ is called Boolean Algebra if it has the following properties:

1. $(L,\wedge )$ is a monoid.
2. $(L,\vee )$ is a monoid.
3. Neutral element $1_{\wedge }$ for $(L,\wedge )$:

$$\exists 1_{\wedge }\in L:\forall x\in L:x\wedge 1_{\wedge }=1_{\wedge }\wedge x=x$$

4. Neutral element $0_{\vee }$ for $(L,\vee )$:

$$\exists 0_{\vee }\in L:\forall x\in L:x\vee 0_{\vee }=0_{\vee }\vee x=x$$

5. All elements $x\in L$ have a complement $x^{\prime }\in L$:

$$\forall x\in L:\exists x^{\prime }\in L:x\vee x^{\prime }=1_{\wedge }\text{and}x\wedge x^{\prime }=0_{\vee }$$

Link to original

Examples

Min and Max over $\mathbb{N}$

Show that $(\mathbb{N},\min ,\max )$ is a lattice:

Show that $(\mathbb{N},\min )$ is a commutative semigroup:

Associativity:

$$\forall a,b,c\in \mathbb{N}:\min (\min (a,b),c)=\min (\min (a,c),\min (b,c))$$

This is trivially true.

Commutativity:

$$\forall a,b\in \mathbb{N}:\min (a,b)=\min (b,a)$$

This is also trivially true.

Show that $(\mathbb{N},\max )$ is a commutative semigroup:

Associativity:

$$\forall a,b,c\in \mathbb{N}:\max (\max (a,b),c)=\max (\max (a,c),\max (b,c))$$

This is trivially true.

Commutativity:

$$\forall a,b\in \mathbb{N}:\max (a,b)=\max (b,a)$$

This is also trivially true.

Show Absorption for $\wedge =\min$

Show that:

$$\forall a,b\in \mathbb{N}:\min (a,\max (a,b))=a$$

This can be achieved by case analysis on $a$ and $b$:

1. If $a\ge b$, then $\max (a,b)=a$. Thus $\min (a,\max (a,b))=a$.
2. If $a<b$, then $\max (a,b)=b$. Thus $\min (a,\max (a,b))=a$.

Show Absorption for $\vee =\max$

Show that:

$$\forall a,b\in \mathbb{N}:\max (a,\min (a,b))=a$$

This can be achieved by case analysis on $a$ and $b$:

1. If $a\le b$, then $\min (a,b)=a$. Thus $\max (a,\min (a,b))=a$.
2. If $a>b$, then $\min (a,b)=b$. Thus $\max (a,\min (a,b))=a$.