Antireflexive and Transitive Relation is Asymmetric

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\RR \subseteq S \times S$ be a relation which is not null.

Let $\RR$ be antireflexive and transitive.


Then $\RR$ is also asymmetric.


Proof

Let $\RR \subseteq S \times S$ be antireflexive and transitive.


That is:

\(\ds \forall x \in S:\) \(\) \(\ds \tuple {x, x} \notin \RR\) Definition of Antireflexive Relation
\(\ds \tuple {x, y} \in \RR \land \tuple {y, z} \in \RR\) \(\implies\) \(\ds \tuple {x, z} \in \RR\) Definition of Transitive Relation


We have that $\RR$ is not null.

Aiming for a contradiction, suppose $\RR$ is not asymmetric.

So, by definition, $\exists \tuple {x, y} \in \RR: \tuple {y, x} \in \RR$.

Then from the transitivity of $\RR$ that would mean $\tuple {x, x} \in \RR$.

But that would contradict the antireflexivity of $\RR$.

Therefore:

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

and $\RR$ has been shown to be asymmetric.

$\blacksquare$


Also see


Sources