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 R):

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.

If A is a subset of a poset X and aA is such that, for every element bA, 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:

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.

• What Is Infinity?.
• Infinity As a Limit.
  • Infinite Sums and Products
• Cardinal Numbers.
  • Cantor-Bernstein-Schroeder theorem.
• Ordinal Numbers.
  • Order. Well-ordered sets
• Surreal Numbers.
• Infinitesimals. Hyperreal Numbers.
• Various Geometric Infinities
  • Projective Infinity.
  • Infinity in Inversive Geometry.
  • Infinity in Compactification.
• Paradoxes of Infinity
  • Achilles and the Tortoise
  • Infinity and Probability
  • Infinite Border, Finite Area