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 $\RR \subseteq S \times T$ be a relation.

Inverse of Complement

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


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

$\RR^d := \paren {\overline \RR}^{-1}$

where:

$\overline \RR$ denotes the complement of $\RR$
$\paren {\overline \RR}^{-1}$ denotes the inverse of the complement of $\RR$.

Complement of Inverse

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


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

$\RR^d := \overline {\paren {\RR^{-1} } }$

where:

$\RR^{-1}$ denotes the inverse of $\RR$
$\overline {\paren {\RR^{-1} } }$ denotes the complement of the inverse of $\RR$.


Proof

Let $\tuple {x, y} \in \paren {\overline \RR}^{-1}$.


Then:

\(\ds \tuple {x, y}\) \(\in\) \(\ds \overline \RR\)
\(\ds \leadstoandfrom \ \ \) \(\ds \tuple {y, x}\) \(\in\) \(\ds \overline \RR\) Definition of Inverse Relation
\(\ds \leadstoandfrom \ \ \) \(\ds \tuple {y, x}\) \(\notin\) \(\ds \RR\) Definition of Complement of Relation
\(\ds \leadstoandfrom \ \ \) \(\ds \tuple {x, y}\) \(\notin\) \(\ds \RR^{-1}\) Definition of Inverse Relation
\(\ds \leadstoandfrom \ \ \) \(\ds \tuple {x, y}\) \(\in\) \(\ds \overline {\paren {\RR^{-1} } }\) Definition of Complement of Relation

$\blacksquare$