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 comparable.

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.

A set on which $\RR$ is connected can be referred to as an $\RR$-connected set.

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.