Subset of Well-Ordered Set is Well-Ordered
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 1
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$
Proof 2
By definition of well-ordered set, $\struct {S, \preceq}$ is:
and:
By Subset of Toset is Toset, $\struct {T, \preceq'}$ is a totally ordered set.
By Subset of Well-Founded Relation is Well-Founded, $\preceq'$ is a well-founded relation.
Hence the result.
$\blacksquare$
Proof 3
Let $V$ be a basic universe.
By definition of basic universe, $S$ and $T$ are all elements of $V$.
By the Axiom of Transitivity, $S$ and $T$ are both classes.
Thus $T$ is a subclass of $S$.
We have by hypothesis that $\preceq$ is a well-ordering on $S$.
So from Subclass of Well-Ordered Class is Well-Ordered, $\preceq'$ is a well-ordering on $T$.
Hence the result.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings
- 1968: A.N. Kolmogorov and S.V. Fomin: Introductory Real Analysis ... (previous) ... (next): $\S 3.5$: Well-ordered sets. Ordinal Numbers: Example $2$
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Appendix $\text{A}.6$: Mathematical Induction: Problem Set $\text{A}.6$: $34$