Equivalence of Definitions of Dual Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Dual Relation are equivalent:

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

Inverse of Complement

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


Then the dual of $\mathcal R$ is denoted $\mathcal R^d$ and is defined as:

$\mathcal R^d := \left({\overline{\mathcal R}}\right)^{-1}$

where:

$\overline {\mathcal R}$ denotes the complement of $\mathcal R$
$\left({\overline{\mathcal R}}\right)^{-1}$ denotes the inverse of the complement of $\mathcal R$.


Complement of Inverse

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


Then the dual of $\mathcal R$ is denoted $\mathcal R^d$ and is defined as:

$\mathcal R^d := \overline{\left({\mathcal R^{-1}}\right)}$

where:

$\mathcal R^{-1}$ denotes the inverse of $\mathcal R$
$\overline{\left({\mathcal R^{-1}}\right)}$ denotes the complement of the inverse of $\mathcal R$.


Proof

Let $\left({x, y}\right) \in \left({\overline{\mathcal R}}\right)^{-1}$.


Then:

\(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \overline{\mathcal R}\)
\(\displaystyle \iff \ \ \) \(\displaystyle \left({y, x}\right)\) \(\in\) \(\displaystyle \overline{\mathcal R}\) Definition of Inverse Relation
\(\displaystyle \iff \ \ \) \(\displaystyle \left({y, x}\right)\) \(\notin\) \(\displaystyle \mathcal R\) Definition of Complement of Relation
\(\displaystyle \iff \ \ \) \(\displaystyle \left({x, y}\right)\) \(\notin\) \(\displaystyle \mathcal R^{-1}\) Definition of Inverse Relation
\(\displaystyle \iff \ \ \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \overline {\left({\mathcal R^{-1} }\right)}\) Definition of Complement of Relation

$\blacksquare$