# Example of Lattices: Boolean Lattice (with Complemented Lattice and Boolean Algebras)

# Prerequisite: Complemented Lattice

**Definition 3.1:** Let $L$ be a bounded lattice.

- An element $x \in L$ is said to be
**complemented**(by $y$) if $\exists y \in L$ such that $x \wedge y = \bot$ and $x \vee y = \top$. - We call $y$, also denoted by $x^\ast$, the
**complement**of $x$. - Accordingly, lattice $R$ is said to be
**complemented**if $\forall x \in L$, $x$ has a complement.

**Theorem 3.3:** In a bounded, distributive lattice, every element has at most one complement.

Proof: Consider a bounded distributive lattice $L$ and elements $a,b,c \in R$. Suppose $b,c$ are both complements of $a$. We have:

\[c = c \vee \bot = c \vee (a \wedge b) = (c \vee a) \wedge (c \vee b) = \top \wedge (c \vee b) = c \vee b,\]which implies $b \leq c$.

A similar argument can show that $c \leq b$. Therefore $b = c$ and there is only one complement of $a$. $\blacksquare$

# Boolean Lattices

**Definition 3.4:** A lattice $L$ is said to be **Boolean** if it is bounded, distributive, and complemented.

The most common example of a Boolean lattice is the **powerset Boolean lattice**. Given a positive integer $n$ and a set $[n] = \lbrace 1,2,\dots,n \rbrace$, the poset $B_n=(2^{[n]}, \subseteq)$ is called a **powerset boolean lattice of order $n$**.

E.g. when $n=2$, $B_2 = \big\lbrace \varnothing, \, \lbrace 1 \rbrace, \, \lbrace 2 \rbrace, \, \lbrace 1,2 \rbrace \big\rbrace$

Some textbooks simply call $B_n$ the “Boolean lattice of order $n$”.

# Boolean Algebras

**Definition 3.6:** A **Boolean algebra** is a structure $(L, \wedge, \vee, \ast, \bot, \top)$ such that:

- $(L, \wedge, \vee, \bot, \top)$ is a Boolean lattice
- $\ast$ is the unary complement operation.

The most common example of a Boolean algebra is the **powerset Boolean algebra** such as $(B_n, \cap, \cup, \overline{}, \varnothing, [n])$

# References

- https://arxiv.org/abs/2307.16671
- https://moraschini.github.io/files/teaching/OLBA.pdf

## Comments