Ordering

Definition 42   A preordering on a set $A$ is a relation on $A$ which is reflexive and transitive.

Definition 43   A partial ordering on a set $A$ is a relation on $A$ which is reflexive, antisymmetric and transitive.

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

Proposition 62   If $R$ is a relation which is a partial ordering, then so is $R^{-1}$.

(3 Points )

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

(3 Points )

Proposition 64   The intersection of any family of partial orderings is a partial ordering.

(3 Points )

Proposition 65   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$.

Definition 45   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 66   Every set can be well ordered.