Induction on a Well-Ordered Set

From ProofWiki

Jump to: navigation, search

Theorem

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

Let $T \subseteq S$ be a subset of $S$ such that:

$\forall s \in S: \left({\forall t \in S: t \preceq s \implies t \in T}\right) \implies s \in T$

Then $T = S$.

Suppose $T \ne S$.

Then $S \setminus T \ne \varnothing$, where $S \setminus T$ denotes set difference.

Let $s$ be the minimal element of the non-empty set $S \setminus T$.

Such an element will always exist because $S \setminus T \subseteq S$ from Set Difference Subset and the definition of well-ordered set.

Let $m$ be the minimal element of $S$.

By definition, $m \preceq s$ and so by the properties of $T$ it follows that $m \in T$.

Now $s \ne m$ as we have defined $s$ such that $s \notin T$.

But we have chosen $s$ so that $t \preceq s \implies t \in T$.

So by hypothesis, $s \in T$ and so $s \notin S \setminus T$.

So from this contradiction we see that $S \setminus T = \varnothing$ and so $S = T$.

$\blacksquare$