# Union of Antisymmetric Relation with Inverse is Antisymmetric iff Diagonal

## Theorem

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

Then:

$\RR \cup \RR^{-1}$ is antisymmetric
$\RR = \Delta_S$

where:

$\RR^{-1}$ denotes the inverse of $\RR$
$\Delta_S$ denotes the diagonal relation
$\cup$ denotes set union.

## Proof

As asserted, let $\RR$ be an antisymmetric relation.

### Necessary Condition

Let $\RR = \Delta_S$.

$\RR^{-1} = \Delta_S$

Hence:

$\RR \cup \RR^{-1} = \Delta_S$

From Relation is Reflexive Symmetric and Antisymmetric iff Diagonal Relation, we have that the diagonal relation $\Delta_S$ is antisymmetric.

Hence if $\RR = \Delta_S$, then $\RR \cup \RR^{-1}$ is antisymmetric.

$\Box$

### Sufficient Condition

Let $\RR \cup \RR^{-1}$ be antisymmetric.

Let $\tuple {x, y} \in \RR$.

By definition of inverse relation:

$\tuple {x, y} \in \RR^{-1}$

Thus by definition of set union:

$\tuple {x, y} \in \RR \cup \RR^{-1}$

and

$\tuple {y, x} \in \RR \cup \RR^{-1}$

As $\RR \cup \RR^{-1}$ is antisymmetric:

$x = y$

Hence:

$\forall \tuple {x, y} \in \RR: x = y$

and it follows that:

$\RR = \Delta_S$

$\blacksquare$