Relation Isomorphism preserves Well-Ordering

Theorem

Let $\struct {A, \RR}$ and $\struct {B, \SS}$ be relational structures which are relationally isomorphic.

Let $\struct {A, \RR}$ be a well-ordered set.

Then $\struct {B, \SS}$ is also a well-ordered set.

Let $\struct {A, \RR}$ be a well-ordered set.

The ordering $\preceq$ is a well-ordering on $S$ if and only if every non-empty subset of $S$ has a smallest element under $\preceq$:

$\forall T \subseteq S, T \ne \O: \exists a \in T: \forall x \in T: a \preceq x$

$\SS$ is a total ordering on $B$.

Let $\phi: \struct {A, \RR} \to \struct {B, \SS}$ be a relation isomorphism.

Let $A' \subseteq A$.

As $\struct {A, \RR}$ is a well-ordered set:

$\exists m_1 \in A': \forall a \in A': a = m_1 \lor \neg \paren {a \mathrel \RR m_1}$

Now consider the image $m_2$ of $m_1$ in $B$:

$m_2 = \map \phi {m_1}$

Aiming for a contradiction, suppose $\struct {B, \SS}$ is not a well-ordered set.

Let there exist $B' \subseteq B$ such that:

$\exists x \in B': x \ne m_2, x \mathrel \SS m_2$

Hence:

$\map {\phi^{-1} } x \ne \map {\phi^{-1} } {m_2}, \map {\phi^{-1} } x \mathrel \SS \map {\phi^{-1} } {m_2}$

But this contradicts the fact that $\struct {A, \RR}$ is well-ordered.

Hence by Proof by Contradiction $\struct {B, \SS}$ must be a well-ordered set.

$\blacksquare$

1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.10$