Figure 2
The powerset of {a, b, c},
ordered by ⊆
Figure 1
The integers,
totally
ordered
by ≤;
a chain
Figure 3
Incomparable items forming an antichain
Figure 4
Part of the java.util inheritance structure
Let P be a set and ⊑ be a (partial) order on P. Then P and ⊑ form a (partially) ordered set.
If the order is total, so that no two elements of P are incomparable, then the ordered set is a totally ordered set. Totally ordered sets are the ones people are first familiar with. See Figure 1 for an example.
A totally ordered set is also termed a chain.
If the order is partial, so that P has two or more incomparable elements, then the ordered set is a partially ordered set. See Figure 2 for an example.
At the other extreme, if no two elements are comparable unless they are equal, then the ordered set is an antichain. See Figure 3.
On any set, = is an order; this is termed the discrete order on the set. Any set ordered by = forms an antichain.
It is common for people to refer briefly though inaccurately to an ordered set as an order, to a totally ordered set as a total order, and to a partially ordered set as a partial order. It is usually clear by context whether "order" refers literally to an order (an order relation) or by synecdoche to an ordered set.
Examples:
Figure 6
The conjunctions of any of
p, q,
and r,
ordered by implication
Figure 5
The binary strings no longer than 3,
ordered by the prefix relation ≤
Each ordered set P corresponds to another ordered set P^{∂}, the dual of P, defined by: y⊑x in P^{∂} iff x⊑y in P.
Each statement Φ about P corresponds to a dual statement Φ^{∂} about P^{∂}. Φ^{∂} is obtained by replacing each occurrence of ⊑ in Φ by ⊒, and each occurrence of ⊒ in Φ by ⊑. Φ is true about P if and only if Φ^{∂} is true about P^{∂}. Generalizing, it can be shown that if a statement Φ is true about all ordered sets, then its dual statement Φ^{∂} is also true. This assertion is the Duality Principle.
Pairs of dual concepts that are defined in terms of ⊑ and ⊒ (such as upper bound and lower bound, below), are also exchanged in dual statements.
Example: Let Q be the ordered set shown in Figure 7, in which ⊑ is the integer divides relation, with the divisor "lower than" the dividend. Then the ordered set of the positive integers to 15 ordered by the converse of divides (now with the divisor considered "higher" than the dividend), is the dual Q^{∂} of Q. The converse of |, |^{-1}, relates two integers if one divides the other, but unlike | it classifies the numerically-smaller integer as the "higher" one by this relation, so that for this order 2⊑1, for example. Q^{∂} is shown in Figure 8. In Q, 4⊑8, so we know without looking at Figure 8 that in Q^{∂}, the dual statement 4⊒8 holds in the relation for that ordered set.
Figure 8
The dual of the ordered set in Figure 7
Figure 7
The positive integers to 15,
ordered by the divisibility relation
Let S be an ordered set.
Examples:
Let S be an ordered set and let E⊆S.
Figure 5 (again)
The binary strings no longer than 3,
ordered by the prefix relation (with prefix low)
Examples, using the ordered set of Figure 5 as S:
The dual concept for upper bound is lower bound, and analogous definitions apply.
Examples:
A LUB (GLB) can fail to exist for either of two reasons:
The table below gives the several synonyms and symbols related to greatest lower bound and least upper bound.
Name | Abbrev. | Synonyms | Operator | Goes with … |
---|---|---|---|---|
least upper bound | LUB | supremum, join | ∨ | top ⊤ |
greatest lower bound | GLB | infimum, meet | ∧ | bottom ⊥ |
Figure 9.
The ordered set of Figure 6, lifted
It is often useful for an ordered set to have a bottom, but not all ordered sets have one (for example, the set in Figure 6). In this case, we can produce a new ordered set with a bottom by adding a (new) least element to the original ordered set. This process is called lifting, and the result of lifting an ordered set P can be called "P lifted", written P_{⊥}.
Example: The non-empty conjunctions of any of p, q, and r, ordered by implication (see Figure 6), has no bottom element. We can lift this set by adding a new element, ⊥, which is implied by all other elements. Here, ⊥ may be thought of as representing the conjunction of 0 propositions. The lifted set is diagrammed in Figure 9. In terms of the knowledge expressed by each conjunction, we may say that a conjunction is an assertion that we know each of its conjuncts is true; thus, for example, p∧r is an assertion that we know p is true and we know r is true. Then ⊥ is an empty assertion, one that does not assert that we know that any of p, q, or r are true.
We have been using diagrams of ordered sets without defining what they mean, relying on the reader's intuition. It is time to confirm that intuition by defining what the diagrams mean.
First we must consider the concept of covering. For x,y ∈ set P ordered by ≤, we say x is covered by y (written x⤙y) if x<y and for any z∈P, x≤z<y implies x=z. This means that there is no element of P "between" x and y. Equivalently, we say y covers x.
A diagram (or Hasse diagram) of an ordered set is a graph in which
Thus we see that in interpreting diagrams, it does not matter whether one node is above or below another unless there is a monotonic path between them; and that if there is a monotonic path from y through one or more nodes down to x, there is no separate edge directly from y to x.
Examples in Figure 9:
Other examples:
The ordering of two sets may be the same even if the two sets are different. Two ordered sets P and Q are order-isomorphic, written P ≅Q, if there is a mapping φ from P onto Q such that x ≤y in P if and only if φ(x) ≤φ(y) in Q. Then φ is called an order-isomorphism on the two sets. In discussing ordered sets, we often simply say P and Q are isomorphic or φ is an isomorphism.
It can be shown that two ordered sets are order-isomorphic if and only if they can be drawn with identical diagrams.
Figure 2 (again)
℘{a, b, c},
ordered by ⊆
Example: The powerset of {a, b, c} ordered by the subset relation (Figure 2), and the conjunctions of any of a, b, and c ordered by implication and lifted by the addition of ⊥ (Figure 9), are isomorphic. The isomorphism between them is given in the table below.
x∈P | φ(x)∈Q |
---|---|
{a, b, c} | a∧b∧c |
{a, b} | a∧b |
{a, c} | a∧c |
{b, c} | b∧c |
{a} | a |
{b} | b |
{c} | c |
∅ | ⊥ |
From this isomorphism, we can see that because {a, b, c} ⊇{b, c}, we know that φ({a, b, c}) implies φ({b, c}) or (written in terms of Q) a∧b∧c implies b∧c.
Figure 6 (again)
Q: Conjunctions ordered by implication
Figure 3 (again)
P: Incomparable items forming an antichain
The disjoint union of two disjoint ordered sets P and Q, written PQ, is the union of P and Q, with P's elements ordered as in P and Q's elements ordered as in Q, and each element of P incomparable with each element of Q. The diagram of PQ consists of P's diagram beside Q's diagram, with no connection between them.
The linear sum of two disjoint ordered sets P and Q, written P⊕Q, is the union of P and Q, with P's elements ordered as in P and Q's elements ordered as in Q, and x≤y for each x∈P and y∈Q. The diagram of P⊕Q consists of Q's diagram above P's diagram, with an edge between each minimal element of Q and each maximal element of P.
Figure 10. Disjoint union (PQ) of Figures 3 (P) and 6 (Q)
Figure 12. Linear sum (Q⊕P) of Figs. 6 (Q) and 3 (P)
Figure 11. Linear sum (P⊕Q) of Figs. 3 (P) and 6 (Q)
Examples, using the ordered sets P from Figure 3 and Q from Figure 6:
Figure 13. Down-set ↓3 of ordered set of Figure 8
Figure 14. Up-set ↑6 of ordered set of Figure 8
A subset Q of ordered set P with order ⊑ is a down-set of P if whenever x∈Q, y∈P, and y⊑x, then y∈Q. Informally, Q contains one or more maximal elements and every member of P that is below any member of Q.
Dually, a subset Q of ordered set P with order ⊒ is an up-set of P if whenever x∈Q, y∈P, and y⊒x, then y∈Q.
Let R be an arbitrary subset of ordered set P with order ⊑. Then the smallest down-set containing R, denoted ↓R and pronounced "down R", is the set of all x∈P for which there is a y∈R such that x⊑y.
Dually, the smallest up-set containing R, denoted ↑R and pronounced "up R", is the set of all x∈P for which there is a y∈R such that x⊒y.
If R is a singleton set {r}, then we may write ↓r in place of ↓{r} or ↓R; or, dually, ↑r in place of ↑{r} or ↑R. Such down-sets (up-sets) are termed principal down-sets (up-sets) of P.
Examples, using the ordered set P shown in Figure 8:
B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, 2002.