Subset of Well-Founded Relation is Well-Founded

Theorem

Let $\struct {S, \RR}$ be a relational structure.

Let $\RR$ be a well-founded relation on $S$.

Let $\QQ$ be a subset of $\RR$.

Then $\QQ$ is also a well-founded relation on $S$.

Proof

Aiming for a contradiction, suppose $\struct {S, \QQ}$ is not a well-founded set.

By Infinite Sequence Property of Well-Founded Relation there exists an infinite sequence $\sequence {x_n}$ in $S$ such that:

$\forall n \in \N: \tuple {x_{n + 1}, x_n} \in \QQ \text { and } x_{n + 1} \ne x_n$

But then because $\QQ \subseteq \RR$, it follows that:

$\forall n \in \N: \tuple {x_{n + 1}, x_n} \in \QQ \implies \tuple {x_{n + 1}, x_n} \in \RR$

and it follows that:

$\forall n \in \N: \tuple {x_{n + 1}, x_n} \in \RR \text { and } x_{n + 1} \ne x_n$

Hence by Infinite Sequence Property of Well-Founded Relation it follows that $\RR$ is not a well-founded relation on $S$.

The result follows by Proof by Contradiction.

$\blacksquare$

Sources

• 1996: Winfried Just and Martin Weese: Discovering Modern Set Theory. I: The Basics ... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $15 \ \text {(a)}$