# Equivalence of Definitions of Well-Ordering

## Theorem

The following definitions of the concept of **Well-Ordering** are equivalent:

Let $\left({S, \preceq}\right)$ be a ordered set.

### Definition 1

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$

### Definition 2

The ordering $\preceq$ is a **well-ordering** on $S$ if and only if $\preceq$ is a well-founded total ordering.

## Proof

### Definition 1 implies Definition 2

Consider $X = \left\{{a, b}\right\}$ where $a, b \in S$.

By hypothesis, $X$ has a smallest element.

So either $\min X = a$ or $\min X = b$.

If $\min X = a$, then $a \preceq b$.

If $\min X = b$, then $b \preceq a$.

So either $a \preceq b$ or $b \preceq a$.

That is, $a$ and $b$ are comparable.

As this applies to all $a, b \in S$, the ordering $\preceq$ is total.

By hypothesis, every subset of $S$ has a smallest element.

By Smallest Element is Minimal it follows that every subset of $S$ has a minimal element.

Thus it follows that $\preceq$ is a well-ordering on $S$ by definition 2.

$\Box$

### Definition 2 implies Definition 1

Let $\preceq$ be a well-ordering on $S$ by definition 2.

That is:

- $\preceq$ is a well-founded total ordering.

By definition of well-founded, every $T \subseteq S$ has a minimal element.

By Minimal Element in Toset is Unique and Smallest, every $T \subseteq S$ has a smallest element.

The result follows.

$\blacksquare$