Definition:Connected Relation

This page is about connected relation in the context of relation theory. For other uses, see connected.

Definition

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.

Examples

Greater Than on $\N$

The greater than relation on the natural numbers $\N$ is an example of a connected relation.

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 a 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$

• Relation is Connected and Reflexive iff Total

• Definition:Trichotomy

• Results about connected relations can be found here.

Sources

• 1993: Keith Devlin: The Joy of Sets: Fundamentals of Contemporary Set Theory (2nd ed.) ... (previous) ... (next): $\S 1$: Naive Set Theory: $\S 1.5$: Relations
• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): connected relation
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): connected relation
• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): connected (of a relation)