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