Union of Antisymmetric Relation with Inverse is Antisymmetric iff Diagonal
Jump to navigation
Jump to search
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$.
From Inverse of Diagonal Relation,
- $\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$