Order. Well-ordered sets
A binary relation R on a set X is a subset of the product X×X. Very often instead of writing, say,
|Symmetry:||if xRy then yRx|
|Antisymmetry:||if xRy and yRx then x = y|
|Asymmetry:||if xRy then not yRx|
|Transitivity:||if xRy and yRz then xRz|
|Totality:||either xRy or yRx|
|Density:||xRy implies existence of z such that xRz and zRy|
A relation which is reflexive, symmetric and transitive is an equivalence relation. The one which is reflexive, antisymmetric and transitive is a partial order. The one which is antisymmetric, transitive and total is a total (or linear) order. A total order is partial because totality implies reflexivity.
A set X along with a binary relation R is said to be partially (totally) ordered if R is a partial (total) order. A partially ordered set is called poset. (Strangely enough, a totally ordered set is not called toset.)
When it comes to considering ordered sets, the partial order relation R is usually written as "≤". Alongside a partial order "≤" it is common and convenient to work with a relation "<" defined as
x < y iff x ≤ y and x ≠ y.
The relation "<" is irreflexive, asymmetric and transitive.
If A is a subset of a poset X and a∈A is such that, for every element b∈A, a≤b, then a is called the minimum (or the least) element of A. The minimum element, if exists, is unique because of the antisymmetry of the partial order.
A totally ordered set in which every non-empty subset has a minimum element is called well-ordered. A finite set with a total order is well-ordered. All total orderings of a finite set are, in a sense, the same. This is not true of the infinite sets. The countable transfinite ordinals correspond to various well-orderings of the set N of natural numbers.
Two sets X and Y totally ordered by relations R and S are said to be similar if they are of the same cardinality
f(x)Sf(y) iff xRy.
Similar sets are said to be of the same order-type.
- The set of all subsets of a set with more than one element is partially ordered by inclusion.
- The set of natural numbers is naturally well ordered by the magnitude of the numbers. This ordering is denoted ω.
- Sarkovskii's ordering of natural numbers is total but any infinite subset of powers of 2 has no minimum element.
- The set of rational numbers is naturally totally ordered but not well ordered; the ordering is dense.
- The set of real numbers is naturally totally ordered but not well ordered; the ordering is dense.
- Lexicographic order is total for sequences and complex numbers.
- The set of negative integers does not have a minimum element and is not, therefore, similar to the set of positive integers.