Reflexive Reduction of Antisymmetric Relation is Asymmetric

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\RR$ be an antisymmetric relation on $S$.

Let $\RR^\ne$ be the reflexive reduction of $\RR$.


Then $\RR^\ne$ is asymmetric.


Proof

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

That is:

$\exists a, b \in S: a \mathrel {\RR^\ne} b$ and $b \mathrel {\RR^\ne} a$

Then by the definition of reflexive reduction:

$a \mathrel \RR b$, $b \mathrel \RR a$

and $a \ne b$.

But this contradicts the antisymmetry of $\RR$.

Thus, by definition, $\RR^\ne$ is an asymmetric relation.

$\blacksquare$


Sources