Lattice

Topics: Discrete Mathematics

---

(definition)

Let $(L,⪯)$ be a poset.

$(L,⪯)$ is a lattice if and only if every subset $\{a,b\}\subseteq L$ has a unique supremum and a unique infimum.

$\vee$ and $\wedge$ §

In a lattice, we define two operations $\vee$ and $\wedge$ as follows:

$$a\vee b:=\sup \{a,b\}$$

$$a\wedge b:=\inf \{a,b\}$$

Examples §

Examples of $a\vee b$ and $a\wedge b$

In the “less or equal to” relation ($\le$):

• $a\vee b=\max \{a,b\}$
• $a\wedge b=\min \{a,b\}$

In the “divisibility” relation ($|$):

• $a\vee b=\text{mcm}(a,b)$
• $a\wedge b=\text{MCD}(a,b)$

In the “inclusion” relation ($\subseteq$):

• $a\vee b=a\cup b$
• $a\wedge b=a\cap b$

Lattice Example 1

$(\mathbb{N},\le )$ is a lattice.

We have that:

• $a\vee b=\max \{a,b\}$
• $a\wedge b=\min \{a,b\}$

Lattice Example 2

Let $X=\{1,2,3\}$ and $L=\mathcal{P}(x)$ (power set).

$(\mathcal{P}(X),\subseteq )$ is a lattice.

Furthermore, this is true for any set $X$, irrespective of its cardinality or nature of elements.

All Totally Ordered Sets are Lattices

Notice that all totally ordered sets are lattices.