Definition:Connected Relation

From ProofWiki
Jump to navigation Jump to search

This page is about connected relations. For other uses, see Definition:Connected.


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

Then $\mathcal R$ is connected if and only if:

$\forall a, b \in S: a \ne b \implies \tuple {a, b} \in \mathcal R \lor \tuple {b, a} \in \mathcal R$

That is, if and only if every pair of distinct elements is related (either or both ways round).

Also known as

Some sources use the term weakly connected, using the term strictly connected relation for what is defined on $\mathsf{Pr} \infty \mathsf{fWiki}$ as total relation.

Also see

  • Definition:Total Relation: a connected relation which also insists that $\tuple {a, b} \in \mathcal R \lor \tuple {b, a} \in \mathcal R$ even for $a = b$
  • Results about connected relations can be found here.