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, (x, y)∈R we write xRy. A binary relation may have many properties; the ones of interest for the definition of order are listed below (I'll omit the expression "for all x" or "for all y". The properties listed are assumed to hold for all elements from X):

	Reflexivity:		xRx
	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 (|X| = |Y|) and there exists an order-preserving 1-1 correspondence f: X→Y between them:

f(x)Sf(y) iff xRy.

Similar sets are said to be of the same order-type.

Examples

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.

71925074