Relation is Connected iff Union with Inverse and Diagonal is Trivial Relation
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$