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.^[1]

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

Order-theoretic 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.

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

$L$ $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.
$L$ $L$ is a bounded poset:
1. There exists $m\in L$ such that for every $a\in L$ , $m\leq a$ . This element is unique and is denoted by $0$ .
2. There exists $M\in L$ such that for every $a\in L$ , $a\leq M$ . This element is unique and is denoted by $1$ .

Algebraic definition

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

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

Properties

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

Bounding a lattice

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

Define $L':=\{\downarrow \!x\mid x\in L\}\cup \{\emptyset ,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'$ , ordered by inclusion $\subseteq$ , is a bounded lattice. Define a function $\varphi \colon L\to L'$ by $\varphi (x):=\downarrow \!x$ . One can prove that $\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).^[2]

Complemented lattice

Let $(L,\land ,\lor ,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\land b=0$ and $a\lor 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 {R} ^{2}$ , ordered by inclusion. This is a bounded lattice with minimum ${0}$ and maximum $\mathbb {R} ^{2}$ .

Let $C$ be the set of all continuous functions from $\mathbb {R}$ to the closed interval $[0,1]$ , ordered pointwise: $f\leq g$ if and only if $f(x)\leq g(x)$ for all $x\in \mathbb {R}$ . Then $(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 $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 {R} ^{2}$ , together with the empty set $\emptyset$ and the whole space $\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 $\emptyset$ as minimum and $\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.