Cartesian Product of Preimage with Image of Relation is Correspondence

From ProofWiki
Jump to: navigation, search

Theorem

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

Then the restriction of $\mathcal R$ to $\Preimg {\mathcal R} \times \Img {\mathcal R}$ is a correspondence.


Proof

By the definition of a correspondence it will be shown that $\mathcal R$ is both left-total and right-total.


$\mathcal R$ is left-total iff:

$\forall x \in S: \exists y \in T: x \mathcal R y$

By the definition of the pre-image of $\mathcal R$:

$\Preimg {\mathcal R} = \set {x \in S: \exists y \in T: x \mathcal R y}$

Therefore $\mathcal R$ is left-total.


$\mathcal R$ is right-total if and only if:

$\forall x \in T: \exists y \in S: x \mathcal R y$

By the definition of the image of $\mathcal R$:

$\Img {\mathcal R} = \set {x \in T: \exists y \in S: x \mathcal R y}$

Therefore $\mathcal R$ is right-total.


Hence $\mathcal R$ is a correspondence.

$\blacksquare$