Well-Founded Relation is not necessarily Ordering

Theorem

Let $\struct {S, \RR}$ be a relational structure.

Let $\RR$ be a well-founded relation on $S$.

Then it is not necessarily the case that $\RR$ is also either an ordering or a strict ordering.

Proof

Proof by Counterexample:

Let $P$ be the set of all polynomials over $\R$ in one variable with real coefficients.

Let $\DD$ be a relation on $P$ defined as:

$\forall p_0, p_1 \in P: \tuple {p_0, p_1} \in \DD$ if and only if $p_0$ is the derivative of $p_1$.

From Differentiation of Polynomials induces Well-Founded Relation, we have that $\DD$ is a well-founded relation on $P$.

Let $P_a$ be the polynomial defined as:

$P_a = x^3$

Then the derivative of $P_a$ with respect to $x$ is:

$P_a' = \dfrac \d {\d x} x^3 = 3 x^2$

Then the derivative of $P_a$ with respect to $x$ is:

$P_a'' = \dfrac \d {\d x} 3 x^2 = 6 x$

So we have that:

$\tuple {P_a', P_a} \in \DD$

and:

$\tuple {P_a'', P_a'} \in \DD$

but it is not the case that $\tuple {P_a'', P_a} \in \DD$.

That is, $\DD$ is not transitive.

It follows that $\DD$ is neither an ordering nor a strict ordering.

$\blacksquare$

Sources

• 1996: Winfried Just and Martin Weese: Discovering Modern Set Theory. I: The Basics ... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $7$