Antitransitive Relation is Antireflexive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\mathcal R \subseteq S \times S$ be a relation on $S$.

Let $\mathcal R$ be antitransitive.


Then $\mathcal R$ is also antireflexive.


Proof

Suppose $\mathcal R \subseteq S \times S$ is not antireflexive.

Then $\exists x \in S: \left({x, x}\right) \in \mathcal R$. (In the case of $\mathcal R$ being reflexive, the property holds for all $x \in S$.)

Thus $\mathcal R$ is not antitransitive:

\(\displaystyle \) \(\) \(\displaystyle \left({x, x}\right) \in \mathcal R \land \left({x, x}\right) \in \mathcal R\)
\(\displaystyle \) \(\implies\) \(\displaystyle \left({x, x}\right) \in \mathcal R\) Rule of Idempotence

... which means $\exists x \in S$ such that the condition for antitransitivity is broken.

So $\mathcal R \subseteq S \times S$ has to be antireflexive.

$\blacksquare$


Sources