Strictly Well-Founded Relation is Well-Founded
Jump to navigation
Jump to search
Theorem
Let $\struct {S, \RR}$ be a relational structure.
Let $\RR$ be a strictly well-founded relation on $S$.
Then $\RR$ is a well-founded relation on $S$.
Proof
We have that $\RR$ is a strictly well-founded relation on $S$.
By definition:
- $\forall T: \paren {T \subseteq S \land T \ne \O} \implies \exists y \in T: \forall z \in T: \neg \paren {z \mathrel \RR y}$
It immediately follows that:
- $\forall T: \paren {T \subseteq S \land T \ne \O} \implies \exists y \in T: \forall z \in \paren {T \setminus \set y}: \neg \paren {z \mathrel \RR y}$
which is the definition of a well-founded relation on $S$.
$\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