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.

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 \and and \or, 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 \and and \or:
    1. Associativity: for all a,b,c\in L, (a\and b)\and c = a\and (b\and c) and (a\or b)\or c = a\or (b\or c).
    2. Commutativity: for all a,b\in L, a\and b = b\and a and a\or b = b\or a.
    3. Idempotence: for all a\in L, a\and a = a and a\or a = a.
    4. Absorption: for all a,b\in L, a\and (a\or b) = a and a\or (a\and b) = a.
  2. 0 and 1 are identity elements for \or and \and, respectively:
    1. For all a\in L, a\or 0 = a.
    2. For all a\in L, a\and 1 = a.

Properties

  • In a bounded lattice (L,\and,\or,0,1), for every a\in L, one has a\and 0 = 0.
  • In a bounded lattice (L,\and,\or,0,1), for every a\in L, one has a\or 1 = 1.

Bounding a lattice

Let (L,\le) 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,\and,\or,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 thata\and b = 0 and a\or 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.
  • 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\le g if and only if f(x)\le g(x) for all x\in\mathbb{R}. 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{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.

References

  1. ^ Grätzer, George (2011). Lattice Theory: Foundation. doi:10.1007/978-3-0348-0018-1
  2. ^ Schröder, Bernd (2016). Ordered Sets. doi:10.1007/978-3-319-29788-0