|
Size: 968
Comment: Counterexample
|
Size: 1203
Comment: Note
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 26: | Line 26: |
| 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'' |
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