# Antitransitive Relation is Antireflexive

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