Relation is Total iff Union with Inverse is Trivial Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal R$ be a relation on $S$.


Then $\mathcal R$ is a total relation if and only if:

$\mathcal R \cup \mathcal R^{-1} = S \times S$

where:

$\mathcal R^{-1}$ is the inverse of $\mathcal R$.
$S \times S$ is the trivial relation on $S$.


Proof

Necessary Condition

Let $\mathcal R$ be a total relation.

By definition of relation, both $\mathcal R \subseteq S \times S$ and $\mathcal R^{-1} \subseteq S \times S$.

So from Union is Smallest Superset (and indeed, trivially) $\mathcal R \cup \mathcal R^{-1} \subseteq S \times S$.


Let $\left({a, b}\right) \in S \times S$.

As $\mathcal R$ is total, either:

$\left({a, b}\right) \in \mathcal R$

or:

$\left({b, a}\right) \in \mathcal R$


From the definition of inverse relation, this means that either:

$\left({a, b}\right) \in \mathcal R$

or:

$\left({a, b}\right) \in \mathcal R^{-1}$

That is:

$\left({a, b}\right) \in \mathcal R \cup \mathcal R^{-1}$

and so by definition of subset:

$S \times S \subseteq \mathcal R \cup \mathcal R^{-1}$


Hence, by definition of set equality:

$\mathcal R \cup \mathcal R^{-1} = S \times S$

$\Box$


Sufficient Condition

Let $\mathcal R \cup \mathcal R^{-1} = S \times S$.

Let $\left({a, b}\right) \in S \times S$.


Then by definition of set union:

$\left({a, b}\right) \in \mathcal R$

or:

$\left({a, b}\right) \in \mathcal R^{-1}$


That is, by definition of inverse relation:

$\left({a, b}\right) \in R$

or:

$\left({b, a}\right) \in R$


So by definition $\mathcal R$ is total.

$\blacksquare$


Also see


Sources