|
Size: 673
Comment: Initial commit
|
← Revision 5 as of 2026-02-15 17:38:14 ⇥
Size: 1875
Comment: Property
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 17: | Line 17: |
| A set ordered by ''<'' has several properties: | An ordering must satisfy two properties: |
| Line 20: | Line 20: |
As a counter-example, consider the [[Analysis/PowerSet|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. |
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.