Connected relation

In mathematics, a relation on a set is called connected or complete or total if it relates (or "compares") all pairs of elements of the set in one direction or the other while it is called strongly connected if it relates pairs of elements.

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, a relation on a set is called connected or complete or total if it relates (or "compares") all pairs of elements of the set in one direction or the other while it is called strongly connected if it relates pairs of elements. As described in the terminology section below, the terminology for these properties is not uniform.

This notion of "total" should not be confused with that of a total relation in the sense that for all x \in X there is a y \in X so that x \mathrel{R} y (see serial relation). Connectedness features prominently in the definition of total orders: a total (or linear) order is a partial order in which any two elements are comparable; that is, the order relation is connected.

Similarly, a strict partial order that is connected is a strict total order. A relation is a total order if and only if it is both a partial order and strongly connected. A relation is a strict total order if, and only if, it is a strict partial order and just connected.

A strict total order can never be strongly connected (except on an empty domain). Some authors do however use the term connected with a much looser meaning, which applies to precisely those orders whose comparability graphs are connected graphs.

This applies, for instance, to fences, of which none of the nontrivial examples are total orders. \text{ if } x \neq y \text{ then } x \mathrel{R} y \quad \text{or} \quad y \mathrel{R} x, or, equivalently, when for all x, y \in X, x \mathrel{R} y \quad \text{or} \quad y \mathrel{R} x \quad \text{or} \quad x = y. A relation with the property that for all x, y \in X, x \mathrel{R} y \quad \text{or} \quad y \mathrel{R} x is called . Connected relations are also called or said to satisfy (although the more common definition of trichotomy is stronger in that of the three options x \mathrel{R} y, y \mathrel{R} x, x = y must hold).

When the relations considered are not orders, being connected and being strongly connected are importantly different properties. Sources which define both then use pairs of terms such as and , and , and , and , or and , respectively, as alternative names for the notions of connected and strongly connected as defined above.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1357323844 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001357323844 · captured 2026-06-01 · ledger · version history

Cite this page as: encyclopegia.org, “Connected relation”, snapshot enwiki-001357323844. https://encyclopegia.org/a/connected-relation

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.