Ordering

Definition 35   A partial ordering on a set A is a relation on A which is antisymmetric and transitive.

Definition 36   A ordering on a set A is a relation on A which is reflexive, antisymmetric and transitive.

Definition 37   A linear ordering on a set A is a relation on A which is reflexive, antisymmetric, transitive, and total.

Proposition 4.10   If R is a relation which is an ordering, then so is R^-1.

Proposition 4.11   If R and S are linear orderings, then so is $R\circ S$.

Proposition 4.12   If R and S are partial orderings, then so is $R \cap S$.

Proposition 4.13   If R and S are partial orderings, then there is a smallest partial ordering containing both R and S, but it need not be $R\cup S$.

Proposition 4.14   If R is a partial order on A and S is a partial order on B then there are natural partial orders on

1.

$A\times B$ so that both projections preserve order

2.

A+B so that both injections preserve order

Proposition 4.15   If R is a linear order on A and S is a linear order on B then there are natural linear orders on

1.

$A\times B$ so that both projections preserve order

2.

A+B so that both injections preserve order

Definition 38   A set A is well ordered by a relation R if R is a linear ordering and every nonempty subset of A has a least element.

The following theorem is known to be equivalent to the axiom of choice:

Theorem 4.16   Every set can be well ordered.