# 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$