Complement of Symmetric Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Then $\mathcal R$ is symmetric if and only if its complement $\relcomp {S \times S} {\mathcal R} \subseteq S \times S$ is also symmetric.


Proof

Let $\mathcal R \subseteq S \times S$ be symmetric.

Then from Symmetry of Relations is Symmetric:

$\tuple {x, y} \in \mathcal R \iff \tuple {y, x} \in \mathcal R$


Aiming for a contradiction, suppose $\relcomp {S \times S} {\mathcal R} \subseteq S \times S$ is not symmetric.

Then:

$\exists \tuple {x, y} \in \relcomp {S \times S} {\mathcal R}: \tuple {y, x} \notin \relcomp {S \times S} {\mathcal R}$

But then by definition of complement of $\mathcal R$:

$\tuple {y, x} \in \mathcal R$

As $\mathcal R$ is symmetric it follows that:

$\tuple {x, y} \in \mathcal R$

This contradicts the premise that $\tuple {x, y} \in \relcomp {S \times S} {\mathcal R}$.

Hence by Proof by Contradiction it follows that $\relcomp {S \times S} {\mathcal R}$ is symmetric.

$\blacksquare$


The converse follows similarly.