Antisymmetric Relation Intersection Inverse is Subset of Diagonal

Theorem

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

Then $\mathcal R$ is antisymmetric iff:

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

where:

• $\mathcal R^{-1}$ is the inverse of $\mathcal R$
• $\Delta_S$ is the diagonal relation on $S$.

Proof

Necessary Condition

Let $\mathcal R$ be an antisymmetric relation.

Let $\left({a, b}\right) \in R \cap \mathcal R^{-1}$.

That means:

$\left({a, b}\right) \in R$

and

$\left({a, b}\right) \in R^{-1}$

which means, by definition of inverse relation:

$\left({b, a}\right) \in R$

But as $\mathcal R$ is antisymmetric, that means $a = b$.

Thus $\left({a, b}\right) = \left({a, a}\right)$ and so $\left({a, b}\right) \in \Delta_S$.

Thus from the definition of subset:

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

$\Box$

Sufficient Condition

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

Let $\left({a, b}\right) \in R$ and $\left({b, a}\right) \in R$.

That is, by definition of inverse relation:

$\left({a, b}\right) \in R$

and

$\left({a, b}\right) \in R^{-1}$.

That is:

$\left({a, b}\right) \in R \cap \mathcal R^{-1}$

But as $R \cap \mathcal R^{-1} \subseteq \Delta_S$ it follows that $a = b$.

So by definition $\mathcal R$ is antisymmetric.

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 14$: Order