Relation is Antisymmetric iff Intersection with Inverse is Coreflexive
Theorem
Let $\RR$ be a relation on $S$.
Then:
- $\RR$ is antisymmetric
- $\RR \cap \RR^{-1}$ is coreflexive
where $\RR^{-1}$ is the inverse of $\RR$.
That is, if and only if:
- $\RR \cap \RR^{-1} \subseteq \Delta_S$
Proof
Necessary Condition
Let $\RR$ be an antisymmetric relation.
Let $\tuple {a, b} \in \RR \cap \RR^{-1}$.
That means:
- $\tuple {a, b} \in \RR$
and
- $\tuple {a, b} \in \RR^{-1}$
which means, by definition of inverse relation:
- $\tuple {b, a} \in \RR$
But as $\RR$ is antisymmetric, that means $a = b$.
Thus:
- $\tuple {a, b} = \tuple {a, a}$
and so:
- $\tuple {a, b} \in \Delta_S$
where $\Delta_S$ is the diagonal relation.
Thus from the definition of subset:
- $\RR \cap \RR^{-1} \subseteq \Delta_S$
Hence, by definition, $\RR$ is coreflexive.
$\Box$
Sufficient Condition
Let $\RR \cap \RR^{-1}$ be coreflexive.
Hence by definition of coreflexive:
- $\RR \cap \RR^{-1} \subseteq \Delta_S$
Let $\tuple {a, b} \in \RR$ and $\tuple {b, a} \in \RR$.
That is, by definition of inverse relation:
- $\tuple {a, b} \in \RR$
and
- $\tuple {a, b} \in \RR^{-1}$
That is:
- $\tuple {a, b} \in \RR \cap \RR^{-1}$
But as $\RR \cap \RR^{-1} \subseteq \Delta_S$ it follows that $a = b$.
So by definition $\RR$ is antisymmetric.
$\blacksquare$
Sources
- 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 14$: Order