Supremum - Suprema Within Partially Ordered Sets

Suprema Within Partially Ordered Sets

Least upper bounds are important concepts in order theory, where they are also called joins (especially in lattice theory). As in the special case treated above, a supremum of a given set is just the least element of the set of its upper bounds, provided that such an element exists.

Formally, we have: For subsets S of arbitrary partially ordered sets (P, ≤), a supremum or least upper bound of S is an element u in P such that

1. x ≤ u for all x in S, and
2. for any v in P such that x ≤ v for all x in S it holds that u ≤ v.

Thus the supremum does not exist if there is no upper bound, or if the set of upper bounds has two or more elements of which none is a least element of that set. It can easily be shown that, if S has a supremum, then the supremum is unique (as the least element of any partially ordered set, if it exists, is unique): if u₁ and u₂ are both suprema of S then it follows that u₁ ≤ u₂ and u₂ ≤ u₁, and since ≤ is antisymmetric, one finds that u₁ = u₂.

If the supremum exists it may or may not belong to S. If S contains a greatest element, then that element is the supremum; and if not, then the supremum does not belong to S.

The dual concept of supremum, the greatest lower bound, is called infimum and is also known as meet.

If the supremum of a set S exists, it can be denoted as sup(S) or, which is more common in order theory, by S. Likewise, infima are denoted by inf(S) or S. In lattice theory it is common to use the infimum/meet and supremum/join as binary operators; in this case (and similarly for infima).

A complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet).

In the sections below the difference between suprema, maximal elements, and minimal upper bounds is stressed. As a consequence of the possible absence of suprema, classes of partially ordered sets for which certain types of subsets are guaranteed to have least upper bound become especially interesting. This leads to the consideration of so-called completeness properties and to numerous definitions of special partially ordered sets.