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 $0$ and $1$, respectively.

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

Definition

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.

Order-theoretic definition

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

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

Algebraic definition

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

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

Properties

• In a bounded lattice $(L,\wedge ,\vee ,0,1)$, for every $a\in L$, one has $a\wedge 0=0$.
• In a bounded lattice $(L,\wedge ,\vee ,0,1)$, for every $a\in L$, one has $a\vee 1=1$.

Bounding a lattice

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

Define $L^{\prime }:=\{\downarrow x\mid x\in L\}\cup \{\mathrm{\varnothing },L\}$, a collection of subsets of $L$, where for each $x\in L$, $\downarrow x$ denotes the principal lower set generated by $x$. It can be shown that $L^{\prime }$, ordered by inclusion $\subseteq$, is a bounded lattice. Define a function $\phi :L\to L^{\prime }$ by $\phi (x):=\downarrow x$. One can prove that $\phi$ 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).

Complemented lattice

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

In this case, $b$ is called a complement of $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.

Examples

• 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 $L$ be the collection of all vector subspaces of ${\mathbb{ℝ}}^2$, ordered by inclusion. This is a bounded lattice with minimum $0$ and maximum ${\mathbb{ℝ}}^2$.

• Let $C$ be the set of all continuous functions from $\mathbb{ℝ}$ to the closed interval $[0,1]$, ordered pointwise: $f\le g$ if and only if $f(x)\le g(x)$ for all $x\in \mathbb{ℝ}$. Then $(C,\le )$ 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 $m(x):=0$ and $M(x):=1$ serve as global minimum and maximum.

• Let $P$ be the collection of all convex and closed polygons in ${\mathbb{ℝ}}^2$, together with the empty set $\mathrm{\varnothing }$ and the whole space ${\mathbb{ℝ}}^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 $\mathrm{\varnothing }$ as minimum and ${\mathbb{ℝ}}^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.