Relation is Symmetric and Antisymmetric iff Coreflexive

From ProofWiki
Jump to navigation Jump to search


Let $S$ be a set.

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


$\mathcal R$ is both symmetric and antisymmetric


$\mathcal R$ is coreflexive.


Necessary Condition

Let $\mathcal R$ be both symmetric and antisymmetric

Suppose $\mathcal R \not \subseteq \Delta_S$.


$\exists \left({x, y}\right) \in \mathcal R: x \ne y$

But then as $\mathcal R$ is symmetric:

$\left({y, x}\right) \in \mathcal R$

So we have:

$\left({x, y}\right) \in \mathcal R$


$\left({y, x}\right) \in \mathcal R$

where $x \ne y$.

Thus $\mathcal R$ is not antisymmetric, contrary to hypothesis.

So our assumption that $\mathcal R \not \subseteq \Delta_S$ is false.

That is:

$\mathcal R \subseteq \Delta_S$

The result follows by definition of coreflexive.


Sufficient Condition

Let $\mathcal R$ be coreflexive.


\(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R\)
\(\displaystyle \implies \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle y\) Definition of Coreflexive Relation
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, y}\right)\) \(=\) \(\displaystyle \left({y, x}\right)\) Equality of Ordered Pairs
\(\displaystyle \implies \ \ \) \(\displaystyle \left({y, x}\right)\) \(\in\) \(\displaystyle \mathcal R\)

and so by definition $\mathcal R$ is symmetric.

Let $\left({x, y}\right) \in \mathcal R$ and $\left({y, x}\right) \in \mathcal R$.

From the above, this can happen only when $x = y$.

That is, by definition, $\mathcal R$ is antisymmetric.

So $\mathcal R$ is both symmetric and antisymmetric.

Hence the result.