Why is Boolean a lattice?

Question

I've had minimal exposure to lattice theory but I must answer this question due to a project I'm working in. If anyone could answer this question in the simplest explanation possible with examples included then I'd highly appreciate it!

I looked up the definition of lattice: a poset in which every two elements have a unique sup and inf. Can someone give me an example of a poset?

What is the binary relation in a Boolean?

Sorry for asking these basic lattice theory questions. For someone who hasn't taken boolean algebra class, this stuff is pretty advanced and confusing! I don't really need rigorous proof!

Answer 1

I'm a bit confused by your question. Let's start from the beginning.

A poset is a partially ordered set, that is, a set $S$ and a binary relation $\leq \subseteq S \times S$ such that $\leq$ is reflexive, antisymmetric, and transitive.

Examples of posets:

• $(\mathbb{N},\leq)$, where $\leq$ is the standard "less or equal" order.
• $(\mathcal{P}(S),\subseteq)$, where $\mathcal{P}(S)$ is the set of all subsets of some set $S$ and $\subseteq$ is the standard inclusion relation.
• $(\mathbb{N},\mid)$, where $\mid$ is the "divides" relation.

A poset doesn't have to be a lattice, but can be, assuming that infima and suprema exist for every pair of elements in $S$. Infimum and supremum of $a,b$ is standardly denoted as $a \land b$ and $a \lor b$.

A lattice $(S,\leq)$ is called a Boolean lattice if:

• there exist elements $0,1 \in S$ such that $0 \leq a$ and $a \leq 1$ for every $a \in S$.
• for every $a \in S$, there exists $a' \in S$ such that $a \land a' = 0$ and $a \lor a' = 1$.
• $S$ is distributive, ie. $a \lor (b \land c) = (a \lor b) \land (a \lor c)$ for every $a,b,c \in S$.

$S$ being distributive implies that $a'$ is in fact unique for every $a \in S$.

This set of requirements coincidentally (or perhaps not coincidentally) exactly corresponds to the standard definitions of boolean logic, so we use Boolean lattices to "model" it.

To answer your question, the binary operation can be any partial order, assuming that it satisfies all the conditions for Boolean lattices.

To give you a good example, $(\mathcal{P}(S),\subseteq)$ is a boolean lattice for every finite set $S$.