Relation is Symmetric and Antisymmetric iff Coreflexive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

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

Then:

$\mathcal R$ is both symmetric and antisymmetric

iff:

$\mathcal R$ is coreflexive.


Proof

Necessary Condition

Let $\mathcal R$ be both symmetric and antisymmetric

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

Then:

$\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$

and:

$\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.

$\Box$


Sufficient Condition

Let $\mathcal R$ be coreflexive.

Then:

\(\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.

$\blacksquare$


Sources