Lattice

up:: Universal Algebra

A triple $(X,\wedge ,\vee )$ is said to be a lattice if its functions $\wedge (\vee ):X\times X\to X$ satisfy the properties

• Idempotency:
  • $\forall x\in X:x\wedge x=x$
  • $\forall x\in X:x\vee x=x$
• Commutativity:
  • $\forall x,y\in X:x\wedge y=y\wedge x$
  • $\forall x,y\in X:x\vee y=y\vee x$
• Associativity:
  • $\forall x,y,z\in X:(x\wedge y)\wedge z=x\wedge (y\wedge z)$
  • $\forall x,y,z\in X:(x\vee y)\vee z=x\vee (y\vee z)$
• Absorption Laws:
  • $\forall x,y\in X:x\wedge (x\vee y)=x$
  • $\forall x,y\in X:x\vee (x\wedge y)=x$

Examples

Given a set $X$, its powerser $\mathbb{P}(X)$, alongside the intersection and union operators, can be thought of as a lattice. In it, the absorption rules are clear:

• $X\cap (X\cup Y)=X$
• $X\cup (X\cap Y)=X$

Properties

For any lattice $(X,\wedge ,\vee )$, it is true that

$$x=x\wedge y⟺y=x\vee y$$

$(⟹)$: $x=x\wedge y⟹x\vee y=(x\wedge y)\vee y=y$
$(⟸)$: $y=x\vee y⟹x\wedge y=x\wedge (x\vee y)=x$

From this, it follows that Every lattice induces a partial ordering.

A lattice with global upper and lower bounds is said to be a Limited Lattice, whose maximum and minimum we denote as $1$ and $0$, respectively.

When a lattice’s operators distribute, such as

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

it is called a Distributive Lattice.

---

References

• Notas para um Curso de Física-Matemática, João Carlos Alves Barata. Cap. 02
• discrete mathematics - absorption laws don’t understand it with Venn diagrams - Mathematics Stack Exchange