Relation is Antisymmetric and Reflexive iff Intersection with Inverse equals Diagonal Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Then $\mathcal R$ is both antisymmetric and reflexive iff:

$\mathcal R \cap \mathcal R^{-1} = \Delta_S$

where $\Delta_S$ denotes the diagonal relation.


Proof

Necessary Condition

Let $\mathcal R$ be both antisymmetric and reflexive.

From Relation is Antisymmetric iff Intersection with Inverse is Coreflexive:

$\mathcal R \cap \mathcal R^{-1} \subseteq \Delta_S$


By definition of reflexive relation:

$\Delta_S \subseteq \mathcal R$

By Inverse of Reflexive Relation is Reflexive:

$\Delta_S \subseteq \mathcal R^{-1}$

By Intersection is Largest Subset:

$\Delta_S \subseteq \mathcal R \cap \mathcal R^{-1}$


Thus by definition of set equality:

$\mathcal R \cap \mathcal R^{-1} = \Delta_S$

$\Box$


Sufficient Condition

Let $\mathcal R$ be such that:

$\mathcal R \cap \mathcal R^{-1} = \Delta_S$

Then by definition of set equality:

$\mathcal R \cap \mathcal R^{-1} \subseteq \Delta_S$

and so by Relation is Antisymmetric iff Intersection with Inverse is Coreflexive, $\mathcal R$ is antisymmetric.

Also by definition of set equality:

$\Delta_S \subseteq \mathcal R \cap \mathcal R^{-1}$

By Intersection is Subset:

$\mathcal R \cap \mathcal R^{-1} \subseteq \mathcal R$

By Subset Relation is Transitive:

$\Delta_S \subseteq \mathcal R$

So, by definition, $\mathcal R$ is reflexive.

$\blacksquare$}