Totally Ordered Set
A set is totally ordered if
- ifor any pair of elements in the set a and b, either a ≤ b or b ≤ a (totality)
- if a ≤ b and b ≤ c, then a ≤ c (transitivity)
- if a ≤ b and b ≤ a, then a = b (antisymmetry)
If a set is totally ordered, then any subset is also totally ordered.
If a set E is totally ordered, then we might want to find least element or greatest element in it. That is, we seek elements in E such that
- min(E) ≤ a for all a ∈ E
- max(E) ≥ a for all a ∈ E
Such elements might not exist. For example, the set of integers under the customary order does not have a smallest or largest element. Finite, nonempty, totally ordered sets always have least and greatest elements, however.
The antisymmetry property guarantees the uniqueness of a least element or a greatest element if it exists.
A set is well-ordered if every non-empty set has a least element. The natural numbers are well-ordered; the integers, rationals, and real numbers are not.
If X is totally ordered and E ⊆ X, then an upper bound (resp. lower bound) of E is an element x ∈ X such that
- a ≤ x (resp. a ≥ x) for all a ∈ E.
An upper bound or lower bound might not exist, in which case E is said to be unbounded.
Even if the upper bound or lower bound exists, it might not be unique. An upper bound or lower bound might or might not be in the set E. At most one upper bound and one lower bound can be in the set E.
Although upper bounds and lower bounds are not necessarily unique, the least upper bound and greatest lower bound are unique if they exist. They can fail to exist even if there are upper bounds and lower bounds.
A totally ordered set is complete if every nonempty set with an upper bound has a least upper bound.
Partially Ordered Set
- inf, sup
- limit (sequence)
- limit (function)
- right limit, left limit