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 <math>0</math> and <math>1</math>, 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 <math>(L,\le)</math> be a partially ordered set. Then <math>L</math> is called a bounded lattice if and only if:

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

Algebraic definition

Let <math>L</math> be a set equipped with two binary operations <math>\and</math> and <math>\or</math>, and two distinguished elements <math>0,1\in L</math>. Then <math>L</math> is called a bounded lattice if and only if the following conditions hold:

  1. <math>L</math> is a lattice with respect to <math>\and</math> and <math>\or</math>:
  2. Associativity: for all <math>a,b,c\in L</math>, <math>(a\and b)\and c = a\and (b\and c)</math> and <math>(a\or b)\or c = a\or (b\or c)</math>.
  3. Commutativity: for all <math>a,b\in L</math>, <math>a\and b = b\and a</math> and <math>a\or b = b\or a</math>.
  4. Idempotence: for all <math>a\in L</math>, <math>a\and a = a</math> and <math>a\or a = a</math>.
  5. Absorption: for all <math>a,b\in L</math>, <math>a\and (a\or b) = a</math> and <math>a\or (a\and b) = a</math>.
  6. <math>0</math> and <math>1</math> are identity elements for <math>\or</math> and <math>\and</math>, respectively:
  7. For all <math>a\in L</math>, <math>a\or 0 = a</math>.
  8. For all <math>a\in L</math>, <math>a\and 1 = a</math>.

Properties

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

Bounding a lattice

Let <math>(L,\le)</math> be an arbitrary lattice. One may ask whether there exists a bounded lattice <math>L'</math> into which <math>L</math> can be order-embedded.

Define

<math>L' := \{\downarrow\!x \mid x\in L\}\cup\{\emptyset, L\}</math>,

a collection of subsets of <math>L</math>, where for each <math>x\in L</math>, <math>\downarrow\!x</math> denotes the principal lower set generated by <math>x</math>. It can be shown that <math>L'</math>, ordered by inclusion <math>\subseteq</math>, is a bounded lattice. Define a function <math>\varphi\colon L\to L'</math> by <math>\varphi(x):=\downarrow\!x</math>. One can prove that <math>\varphi</math> 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 <math>(L,\and,\or,0,1)</math> be a bounded lattice. It is called a complemented lattice if and only if for every <math>a\in L</math> there exists <math>b\in L</math> such that<math>a\and b = 0</math> and <math>a\or b = 1</math>.

In this case, <math>b</math> is called a complement of <math>a</math>. 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 <math>L</math> be the collection of all vector subspaces of <math>\mathbb{R}^2</math>, ordered by inclusion. This is a bounded lattice with minimum <math>{0}</math> and maximum <math>\mathbb{R}^2</math>.
  • Let <math>C</math> be the set of all continuous functions from <math>\mathbb{R}</math> to the closed interval <math>[0,1]</math>, ordered pointwise: <math>f\le g</math> if and only if <math>f(x)\le g(x)</math> for all <math>x\in\mathbb{R}</math>. Then <math>(C,\le)</math> 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 <math>m(x):=0</math> and <math>M(x):=1</math> serve as global minimum and maximum.
  • Let <math>P</math> be the collection of all convex and closed polygons in <math>\mathbb{R}^2</math>, together with the empty set <math>\emptyset</math> and the whole space <math>\mathbb{R}^2</math>, 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 <math>\emptyset</math> as minimum and <math>\mathbb{R}^2</math> 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