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
- x ≤ u for all x in S, and
- 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 u1 and u2 are both suprema of S then it follows that u1 ≤ u2 and u2 ≤ u1, and since ≤ is antisymmetric, one finds that u1 = u2.
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.
Read more about this topic: Supremum
Famous quotes containing the words partially, ordered and/or sets:
“Some men have a necessity to be mean, as if they were exercising a faculty which they had to partially neglect since early childhood.”
—F. Scott Fitzgerald (1896–1940)
“Then he rang the bell and ordered a ham sandwich. When the maid placed the plate on the table, he deliberately looked away but as soon as the door had shut, he grabbed the sandwich with both hands, immediately soiled his fingers and chin with the hanging margin of fat and, grunting greedily, began to much.”
—Vladimir Nabokov (1899–1977)
“To me this world is all one continued vision of fancy or imagination, and I feel flattered when I am told so. What is it sets Homer, Virgil and Milton in so high a rank of art? Why is Bible more entertaining and instructive than any other book? Is it not because they are addressed to the imagination, which is spiritual sensation, and but mediately to the understanding or reason?”
—William Blake (1757–1827)