Inverse of Many-to-One Relation is One-to-Many

From ProofWiki
Jump to navigation Jump to search

Theorem

The inverse of a many-to-one relation is a one-to-many relation, and vice versa.


Proof

From the definition, a many-to-one relation $\mathcal R \subseteq S \times T$ is such that:

$\mathcal R \subseteq S \times T: \forall x \in \Dom {\mathcal R}: \tuple {x, y_1} \in \mathcal R \land \tuple {x, y_2} \in \mathcal R \implies y_1 = y_2$


Also from the definition, a one-to-many relation $\mathcal R \subseteq S \times T$ is such that:

$\mathcal R \subseteq S \times T: \forall y \in \Img {\mathcal R}: \tuple {x_1, y} \in \mathcal R \land \tuple {x_2, y} \in \mathcal R \implies x_1 = x_2$


The inverse of a relation $\mathcal R$ is defined as:

$\mathcal R^{-1} = \set {\tuple {t, s}: \tuple {s, t} \in \mathcal R}$


Also from the definition of inverse relation, we have that:

$\Dom {\mathcal R} = \Rng {\mathcal R^{-1} }$
$\Rng {\mathcal R} = \Dom {\mathcal R^{-1} }$


So, let $\mathcal R$ be a many-to-one relation.

Putting the above all together, we have:

$\mathcal R^{-1} \subseteq T \times S: \forall x \in \Img {\mathcal R^{-1} }: \tuple {y_1, x} \in \mathcal R^{-1} \land \tuple {y_2, x} \in \mathcal R^{-1} \implies y_1 = y_2$

and it can be seen that $\mathcal R^{-1}$ is one-to-many.


Similarly, let $\mathcal R$ be a one-to-many relation.

This gives us:

$\mathcal R^{-1} \subseteq T \times S: \forall y \in \Dom {\mathcal R^{-1} }: \tuple {y, x_1} \in \mathcal R^{-1} \land \tuple {y, x_2} \in \mathcal R^{-1} \implies x_1 = x_2$

and it can be seen that $\mathcal R^{-1}$ is many-to-one.

$\blacksquare$