Subset of Well-Ordered Set is Well-Ordered

From ProofWiki
Jump to navigation Jump to search

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:

a totally ordered set

and:

a well-founded set.

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

Retrieved from "https://proofwiki.org/w/index.php?title=Subset_of_Well-Ordered_Set_is_Well-Ordered&oldid=575181"