Basic Order Theory

• Partial Ordering
• Total Ordering
• Well-Founded Relations
• Well-Ordering Relations

We will denote an arbitrary ordering relation by $R$. We will establish some preliminary definitions:

• An ordering $R$ is reflexive if and only if $xRx$, for all $x$ in the domain of $R$.
• An ordering $R$ is irreflexive if and only if $\neg xRx$.
• An ordering $R$ is transitive if and only if $xRy$ and $yRz$ implies $xRz$, for all $x$, $y$, and $z$.
• An ordering $R$ is antisymmetric if and only if $xRy$ and $yRx$ implies $x=y$.
• An ordering $R$ is trichotomous if and only if $xRy$, $x=y$, or $yRx$ for all $x$ and $y$ in the field of $R$.

Partial Ordering

A partial ordering consists of a relation along with a set such as $( A , \le )$ such that the order is reflexive, transitive, and antisymmetric for all members of $A$.

A strict partial ordering consists of an ordered pair $( A , \lt )$ that is irreflexive and transitive for all members of $A$.

All strict partial orders are asymmetric, meaning that $xRy$ implies that $\neg yRx$.

Total Ordering

A total ordering consists of a partial ordering where any two elements are comparable, that is, for all $x$ and $y$ in $A$, $x\le y \lor y\le x$

A strict total ordering is a strict partial ordering that is also trichotomous.

Well-Founded Relations

A minimal element of $B$ with respect to a strict ordering relation $\lt$ is an element $x$ of $B$ that is not greater than any other element in $B$. That is $\forall y \in B: \neg y \lt x$

A well-founded relation is an ordering $\lt$ under $A$ such that any nonempty subset $x$ of $A$ contains a minimal element.

There are many interesting properties of well-founded relations. For example, all well-founded relations do not have any ordering “loops”. That is, they are irreflexive, asymmetric, etc.

Well-founded relations do not have any infinitely descending $<$-chains. Another way to state this is that no function $f$ mapping the natural numbers to well-founded set $A$ where $f(n+1) < f(n)$ for all natural numbers $n$.

Any subset of $A$, even if it is a proper class, must have a minimal element. The proof of this is not as straightforward as it sounds.

We can also prove schemas of well-founded induction and well-founded recursion; the first strongly resembles epsilon induction, while the second defines a function $F(x)$ in terms of a function $G$ of the restriction of $F$ to the initial segment of $x$.

An initial segment or extension of $x$ is the collection of all sets in $A$ less than $x$.

We call a well-founded relation setlike if the initial segments of all the elements of $A$ are elements.

Well-Ordering Relations

A well-ordering relation is a well-founded relation that is also a strict total order. Equivalently, we can also define a well-ordering relation as a well-founded relation that satisfies trichotomy.

The ordinals can be defined as the set of all transitive sets that are well-ordered by the membership relation.

The Well-ordering principle shows that all sets have some well-order associated with them.

All well-ordered sets are order-isomorphic to the ordinals.