Relation is Connected iff Union with Inverse and Diagonal 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 connected relation if and only if:

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

where $\mathcal R^{-1}$ is the inverse of $\mathcal R$ and $\Delta_S$ is the diagonal relation.


Proof

Necessary Condition

Let $\mathcal R$ be a connected relation.

By definition of relation:

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

So from Union is Smallest Superset (and indeed, trivially):

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


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

Suppose $a = b$.

Then $\left({a, b}\right) \in \Delta_S$ by definition of the diagonal relation.

Then by Set is Subset of Union:

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


Suppose otherwise, that is, that $a \ne b$.

As $\mathcal R$ is connected, either:

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

or:

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


From the definition of inverse relation, either:

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

or:

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

That is:

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

Again by Set is Subset of Union:

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


So, by definition of subset:

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


Hence, by definition of set equality:

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

$\Box$


Sufficient Condition

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

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


Suppose $a \ne b$.

By definition of diagonal relation:

$\left({a, b}\right) \notin \Delta_S$


So, 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 \mathcal R$

or:

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


So by definition $\mathcal R$ is connected.

$\blacksquare$


Also see

Retrieved from "https://proofwiki.org/w/index.php?title=Relation_is_Connected_iff_Union_with_Inverse_and_Diagonal_is_Trivial_Relation&oldid=341139"