Foundational Relation is Asymmetric

From ProofWiki
Jump to: navigation, search

Theorem

Let $(S, \mathcal R)$ be a relational structure, where $S$ is a set or a proper class.

Let $\mathcal R$ be a foundational relation.


Then $\mathcal R$ is asymmetric.


Proof

Let $p, q \in S$ and suppose that $p \mathrel{\mathcal R} q$.

Then $\{ p, q \} \ne \varnothing$ and $\{ p, q \} \subseteq S$.

By the definition of foundational relation, $\{ p, q \}$ has an $\mathcal R$-minimal element.

Since $p \mathrel{\mathcal R} q$, $q$ is not an $\mathcal R$-minimal element of $\{ p, q \}$.

Thus $p$ is an $\mathcal R$-minimal element of $\{ p, q \}$.

Thus $q \not\mathrel{\mathcal R} p$.

Since for all $p, q \in S$, $p \mathrel{\mathcal R} q \implies q \not\mathrel{\mathcal R} p$, $\mathcal R$ is asymmetric.

$\blacksquare$