Strictly Well-Founded Relation is Asymmetric
Jump to navigation
Jump to search
Theorem
Let $\struct {S, \RR}$ be a relational structure, where $S$ is a set or a proper class.
Let $\RR$ be a strictly well-founded relation.
Then $\RR$ is asymmetric.
Proof
Let $p, q \in S$ and suppose that $p \mathrel \RR q$.
Then $\set {p, q} \ne \O$ and $\set {p, q} \subseteq S$.
By the definition of strictly well-founded relation, $\set {p, q}$ has a strictly minimal element under $\RR$.
Since $p \mathrel \RR q$, $q$ is not an $\RR$-minimal element of $\set {p, q}$.
Thus $p$ is a strictly minimal element under $\RR$ of $\set {p, q}$.
Thus $q \not \mathrel \RR p$.
Since for all $p, q \in S$, $p \mathrel \RR q \implies q \not \mathrel \RR p$, $\RR$ is asymmetric.
$\blacksquare$