Ordered Sets
Ordered sets are sets with an ordering.
Contents
Description
A set does not inherently have an ordering. For some sets however, it is possible to specify one.
Consider the set of natural numbers. All members of the set can be ordered by the 'less than' binary operator (<). This is sometimes called the standard ordering for set of the natural numbers.
An ordering must satisfy two properties:
∀ x,y ∈ A either x=y, x<y, or y<x
transitivity: if x<y and y<z, then x<z
As a counter-example, consider the power set of natural numbers and an ordering by subsets (⊆). Transitivity is satisfied. But two valid members of this set are {1} and {2}, and none of the following are true:
{1}⊆{2}
{2}⊆{1}
{1}={2}
A common prototype is dictionary ordering. For example, the set of Q x Q (i.e., all pairs as Cartesian coordinates) can be ordered by dictionary ordering; (a,b) < (c,d) if
a < c, or
a = c AND b < d
Bounds
Consider a subset A ⊆ S.
If ∃ b ∈ S such that ∀ a ∈ A a ≤ b, then A is bounded above by b, and b is an upper bound for A.
If instead ∀ a ∈ A b ≤ a, then A is bounded below by b, and b is a lower bound for A.
There are also concepts of least upper bound (or supremum) and greatest lower bound (or infimum).
A universe S is said to have a least upper bound property if every non-empty A ⊆ S has a least upper bound that is also a member of S. Importantly, the set of rational numbers does not have this property.