Ordered Sets

The concept of a partial order generalizes the inequality ≤ on ℤ and ℝ to a ordering of objects in a set.

Definition 1.3.1. A relation on a set S is a subset R of the cartesian product S x S. The relation R is an ordering (or partial order) of S provided that it obeys the following axioms, where we use the notations s ≼ t to signal that (s,t) ∈ R, and s ≺ t to mean that s ≼ t and s ≠ t:

1. Reflexivity. s ≼ s for each s ∈ S;

2. Antisymmetry. If, for a pair of elements s and t in S, we have s ≼ t and t ≼ s, then s = t;

3. Transitivity. If, for a triple s, t, u ∈ S, we have s ≼ t and t ≼ u, then s ≼ u.

If in addition an ordering ≼ of S satisfies

then the ordering is called total order. □

Note. The order relation is not an equivlance relation (it isn't symmetric). The symmetric property is replaced by the antisymmetric property.

Definition 1.3.2. A pair (A, ≼), where A is a set and ≼ is a partial order on A is often succinctly called a poset.  □

Notice that in a partial order on a set A it is not required that every pair of elements of A be related in one way or the other. That is why the adjective partial is used. In a general poset (A, ≼), given two arbitrary elements a, b ∈ A, it is possible that neither a ≼ b nor b ≼ a; in this case we say that a and b are not comparable.

In the posets (ℤ, ≤) , (ℕ, ≤) and (ℝ, ≤) every pair of numbers are related via ≤, so ≤ is a total order. (ℤ, |) is a poset: The relation a|b means “a divides b.” Many posets are not total orders as the following examples illustrate:

Example 1.3.3. Consider the donor relation → defined on the set of blood types X = {o, a, b, ab}. Then → is reflexive, antisymmetric, and transitive. This shows that (X, →) is a poset. Note that a and b are not comparable, meaning that neither can donate to the other.  ■

Example 1.3.4. In the power set 𝒫(X) the relations ⊆ as ⊇ are partial orders but not a total orders; For example let A = 𝒫(X) where X = {a,b,c} we have

Trichotomy does not hold as neither {a} ⊆ {b}, {b} ⊆ {a} or {a} = {b} holds. ■

Definition 1.3.5. Let (A, ≼) be a poset. If for some pair {a, b} of distinct elements, either a ≼ b or b ≼ a then we say that a and b are comparable; otherwise a and b are called incomparable. A partial order in which every pair of elements is comparable is called a total order. □

In example 1.3.4 the sets {a} and {b} are incomparable.

Example 1.3.6. Consider the relation ≤ on ℤ. For all x ∈ ℤ, x ≤ x so ≤ is reflexive. For all x, y ∈ ℤ, if x ≤ y and y ≤ x, then x = y and hence ≤ is antisymmetric. It is also true that x ≤ y and y ≤ z implies that x ≤ z and hence ≤ is transitive. Since for all x,y in ℤ, x ≤ y or y ≤ x. Thus, the inequality ≤ on ℤ is a total order.  ■

Note that ≥ is also a partial order on ℤ but that the strict inequalities < and > are not. The inequality < is not reflexive though it is both antisymmetric and transitive. (< is antisymmetric because there do not exist any x, y ∈ ℤ such that x.

Motivated by the notations for inequalities over ℤ, we use the symbol ≺ to mean

and the symbol ⊀ to mean that it is not true that x ≼ y.