Inverse of Right-Total Relation is Left-Total

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\mathcal R^{-1} \subseteq T \times S$ be the inverse of $\mathcal R$.


Then:

$\mathcal R$ is right-total if and only if $\mathcal R^{-1}$ is left-total.


Proof

Sufficient Condition

Let $\mathcal R$ be right-total.

Then by definition:

$\forall t \in T: \exists s \in S: \tuple {s, t} \in \mathcal R$

By definition of the inverse of $\mathcal R$, it follows that:

$\forall t \in T: \exists s \in S: \tuple {t, s} \in \mathcal R^{-1}$

So by definition $\mathcal R^{-1}$ is left-total.

$\Box$


Necessary Condition

Let $\mathcal R^{-1}$ is left-total.

Then by definition:

$\forall t \in T: \exists s \in S: \tuple {t, s} \in \mathcal R^{-1}$

and so:

$\forall t \in T: \exists s \in S: \tuple {s, t} \in \mathcal R$

So by definition $\mathcal R$ is right-total.

$\blacksquare$