Definition:Connected Relation

From ProofWiki
Jump to navigation Jump to search

This page is about Connected Relation in the context of Relation Theory. For other uses, see Connected.


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

Then $\RR$ is connected if and only if:

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

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 \RR \lor \tuple {b, a} \in \RR$ even for $a = b$
  • Results about connected relations can be found here.