Asymmetric Relation is Antireflexive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\RR \subseteq S \times S$ be a relation on $S$.

Let $\RR$ be asymmetric.


Then $\RR$ is also antireflexive.


Proof

Let $\RR$ be asymmetric.

Then, by definition:

$\tuple {x, y} \in \RR \implies \tuple {y, x} \notin \RR$


Aiming for a contradiction, suppose $\tuple {x, x} \in \RR$.

Then:

\(\displaystyle \tuple {x, x} \in \RR\) \(\implies\) \(\displaystyle \tuple {x, x} \notin \RR\) Definition of Asymmetric Relation
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {x, x} \notin \RR\) \(\) \(\displaystyle \) Proof by Contradiction

Thus $\RR$ is antireflexive.

$\blacksquare$


Sources