Bounded lattice

In mathematics, and in particular in order theory, a bounded lattice is a lattice that has a least element and a greatest element, usually denoted by ${\displaystyle 0}$ and ${\displaystyle 1}$, respectively.¹

Bounded lattices are of considerable importance because many algebraic structures are bounded lattices, including complete lattices, Heyting algebras, Boolean algebras, and others.

A bounded lattice can be defined in two equivalent ways: via an order relation or algebraically. These two definitions can be shown to be equivalent.

Let ${\displaystyle (L,\leq )}$ be a partially ordered set. Then ${\displaystyle L}$ is called a bounded lattice if and only if:

1. ${\displaystyle L}$ is a lattice with respect to the order relation:
   1. For every pair ${\displaystyle a,b\in L}$, there exists an infimum.
   2. For every pair ${\displaystyle a,b\in L}$, there exists a supremum.
2. ${\displaystyle L}$ is a bounded poset:
   1. There exists ${\displaystyle m\in L}$ such that for every ${\displaystyle a\in L}$, ${\displaystyle m\leq a}$. This element is unique and is denoted by ${\displaystyle 0}$.
   2. There exists ${\displaystyle M\in L}$ such that for every ${\displaystyle a\in L}$, ${\displaystyle a\leq M}$. This element is unique and is denoted by ${\displaystyle 1}$.

Let ${\displaystyle L}$ be a set equipped with two binary operations ${\displaystyle \land }$ and ${\displaystyle \lor }$, and two distinguished elements ${\displaystyle 0,1\in L}$. Then ${\displaystyle L}$ is called a bounded lattice if and only if the following conditions hold:

1. ${\displaystyle L}$ is a lattice with respect to ${\displaystyle \land }$ and ${\displaystyle \lor }$:
   1. Associativity: for all ${\displaystyle a,b,c\in L}$, ${\displaystyle (a\land b)\land c=a\land (b\land c)}$ and ${\displaystyle (a\lor b)\lor c=a\lor (b\lor c)}$.
   2. Commutativity: for all ${\displaystyle a,b\in L}$, ${\displaystyle a\land b=b\land a}$ and ${\displaystyle a\lor b=b\lor a}$.
   3. Idempotence: for all ${\displaystyle a\in L}$, ${\displaystyle a\land a=a}$ and ${\displaystyle a\lor a=a}$.
   4. Absorption: for all ${\displaystyle a,b\in L}$, ${\displaystyle a\land (a\lor b)=a}$ and ${\displaystyle a\lor (a\land b)=a}$.
2. ${\displaystyle 0}$ and ${\displaystyle 1}$ are identity elements for ${\displaystyle \lor }$ and ${\displaystyle \land }$, respectively:
   1. For all ${\displaystyle a\in L}$, ${\displaystyle a\lor 0=a}$.
   2. For all ${\displaystyle a\in L}$, ${\displaystyle a\land 1=a}$.

• In a bounded lattice ${\displaystyle (L,\land ,\lor ,0,1)}$, for every ${\displaystyle a\in L}$, one has ${\displaystyle a\land 0=0}$.
• In a bounded lattice ${\displaystyle (L,\land ,\lor ,0,1)}$, for every ${\displaystyle a\in L}$, one has ${\displaystyle a\lor 1=1}$.

Let ${\displaystyle (L,\leq )}$ be an arbitrary lattice. One may ask whether there exists a bounded lattice ${\displaystyle L'}$ into which ${\displaystyle L}$ can be order-embedded.

Define ${\displaystyle L':=\{\downarrow \!x\mid x\in L\}\cup \{\emptyset ,L\}}$, a collection of subsets of ${\displaystyle L}$, where for each ${\displaystyle x\in L}$, ${\displaystyle \downarrow \!x}$ denotes the principal lower set generated by ${\displaystyle x}$. It can be shown that ${\displaystyle L'}$, ordered by inclusion ${\displaystyle \subseteq }$, is a bounded lattice. Define a function ${\displaystyle \varphi \colon L\to L'}$ by ${\displaystyle \varphi (x):=\downarrow \!x}$. One can prove that ${\displaystyle \varphi }$ is an order embedding.

The Dedekind–MacNeille completion proves a much stronger statement: every partially ordered set (not necessarily a lattice) can be embedded into a complete lattice (which is necessarily bounded).²

Let ${\displaystyle (L,\land ,\lor ,0,1)}$ be a bounded lattice. It is called a complemented lattice if and only if for every ${\displaystyle a\in L}$ there exists ${\displaystyle b\in L}$ such that${\displaystyle a\land b=0}$ and ${\displaystyle a\lor b=1}$.

In this case, ${\displaystyle b}$ is called a complement of ${\displaystyle a}$. In contrast to a Boolean algebra, a complemented lattice may have more than one complement for a given element. Intuitively, a complement can be thought of as a negation of the element.

• Every finite partially ordered set that is a lattice is a complete lattice, and hence a bounded lattice.

• Every closed interval in the real line is a bounded lattice.

• Let ${\displaystyle L}$ be the collection of all vector subspaces of ${\displaystyle \mathbb {R} ^{2}}$, ordered by inclusion. This is a bounded lattice with minimum ${\displaystyle {0}}$ and maximum ${\displaystyle \mathbb {R} ^{2}}$.

• Let ${\displaystyle C}$ be the set of all continuous functions from ${\displaystyle \mathbb {R} }$ to the closed interval ${\displaystyle [0,1]}$, ordered pointwise: ${\displaystyle f\leq g}$ if and only if ${\displaystyle f(x)\leq g(x)}$ for all ${\displaystyle x\in \mathbb {R} }$. Then ${\displaystyle (C,\leq )}$ is a lattice, since for any two functions one may take their pointwise minimum and maximum, which are again continuous. However, for an infinite family of continuous functions, this construction need not yield a continuous function. Hence, this lattice is not complete. It is bounded, since the constant functions ${\displaystyle m(x):=0}$ and ${\displaystyle M(x):=1}$ serve as global minimum and maximum.

• Let ${\displaystyle P}$ be the collection of all convex and closed polygons in ${\displaystyle \mathbb {R} ^{2}}$, together with the empty set ${\displaystyle \emptyset }$ and the whole space ${\displaystyle \mathbb {R} ^{2}}$, ordered by inclusion. This is a lattice because the intersection of two closed convex polygons is again a closed convex polygon, and the closure of the convex hull of their union is also a closed convex polygon. It is bounded, with ${\displaystyle \emptyset }$ as minimum and ${\displaystyle \mathbb {R} ^{2}}$ as maximum. However, it is not complete: the family of all closed convex polygons contained in the unit disk has no supremum in this lattice, since their union is a circle, which is not a polygon.