Foundational Relation is Asymmetric

From ProofWiki
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 foundational 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 foundational relation, $\set {p, q}$ has an $\RR$-minimal element.

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

Thus $p$ is an $\RR$-minimal element 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$