Subset of Well-Ordered Set is Well-Ordered/Proof 1
Theorem
Let $\struct {S, \preceq}$ be a well-ordered set.
Let $T \subseteq S$ be a subset of $S$.
Let $\preceq'$ be the restriction of $\preceq$ to $T$.
Then the relational structure $\struct {T, \preceq'}$ is a well-ordered set.
Proof
First suppose that $T = \O$.
From Empty Set is Subset of All Sets, $T$ is a subset of $S$.
By Empty Set is Well-Ordered, $\struct {\O, \preceq'}$ is a well-ordered set.
Otherwise, let $T$ be non-empty.
Let $X \subseteq T$ such that $X \ne \O$ be arbitrary.
Such a subset exists, as from Set is Subset of Itself, $T$ itself is a subset of $T$.
By Subset Relation is Transitive, $X \subseteq S$.
By the definition of a well-ordered set, $X$ has a smallest element under $\preceq$.
That is:
- $\forall y \in S: x \preceq y$
Hence as $T \subseteq S$:
- $\forall y \in T: x \preceq y$
Because $\preceq'$ is the restriction of $\preceq$ to $T$:
- $\forall y \in T: x \preceq' y$
and so $x$ is the smallest element of $X$ under $\preceq'$.
It follows by definition that $\struct {T, \preceq'}$ is a well-ordered set.
$\blacksquare$