Equivalence of Definitions of Dual Relation
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$