# 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, *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):

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 *order-preserving* 1-1 correspondence

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.

|Contact| |Front page| |Contents| |Up| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny