Transitive binary relations v t e
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder(Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all${\displaystyle a,b}$ and${\displaystyle S\ne \varnothing :}$ ${\displaystyle \begin{array}{r}minS\\ \text{exists}\end{array}}$ ${\displaystyle \begin{array}{r}a\vee b\\ \text{exists}\end{array}}$ ${\displaystyle \begin{array}{r}a\wedge b\\ \text{exists}\end{array}}$ ${\displaystyle aRa}$ ${\displaystyle \text{not }aRa}$ ${\displaystyle \begin{array}{r}aRb\Rightarrow \\ \text{not }bRa\end{array}}$
Y indicates that the column's property is always true for the row's term (at the very left), while✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated byY in the "Symmetric" column and✗ in the "Antisymmetric" column, respectively. All definitions tacitly require thehomogeneous relation${\displaystyle R}$ betransitive: for all${\displaystyle a,b,c,}$ if${\displaystyle aRb}$ and${\displaystyle bRc}$ then${\displaystyle aRc.}$ A term's definition may require additional properties that are not listed in this table.

In mathematics, arelation on a set is calledconnected orcomplete ortotal if it relates (or "compares") alldistinct pairs of elements of the set in one direction or the other while it is calledstrongly connected if it relatesall pairs of elements. As described in theterminology 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${\displaystyle x\in X}$ there is a${\displaystyle y\in X}$ so that${\displaystyle xRy}$ (seeserial relation).

Connectedness features prominently in the definition oftotal orders: a total (or linear) order is apartial order in which any two elements are comparable; that is, the order relation is connected. Similarly, astrict partial order that is connected is a strict total order.A relation is a total orderif and only if it is both a partial order and strongly connected. A relation is astrict 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 termconnected with a much looser meaning, which applies to precisely those orders whosecomparability graphs areconnected graphs. This applies for instance to thefences, of which none of the nontrivial examples are total orders.

A relation${\displaystyle R}$ on a set${\displaystyle X}$ is calledconnected when for all${\displaystyle x,y\in X,}$$${\displaystyle \text{ if }x\ne y\text{ then }xRy\text{or}yRx,}$$or, equivalently, when for all${\displaystyle x,y\in X,}$$${\displaystyle xRy\text{or}yRx\text{or}x=y.}$$

A relation with the property that for all${\displaystyle x,y\in X,}$$${\displaystyle xRy\text{or}yRx}$$is calledstrongly connected.^[1][2][3]

The main use of the notion of connected relation is in the context of orders, where it is used to define total, or linear, orders. In this context, the property is often not specifically named. Rather, total orders are defined as partial orders in which any two elements are comparable.^[4][5]Thus,total is used more generally for relations that are connected or strongly connected.^[6] However, this notion of "total relation" must be distinguished from the property of beingserial, which is also called total. Similarly, connected relations are sometimes calledcomplete,^[7] although this, too, can lead to confusion: Theuniversal relation is also called complete,^[8] and "complete" has several other meanings inorder theory.Connected relations are also calledconnex^[9][10] or said to satisfytrichotomy^[11] (although the more common definition oftrichotomy is stronger in thatexactly one of the three options${\displaystyle xRy,yRx,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 asweakly connected andconnected,^[12]complete andstrongly complete,^[13]total andcomplete,^[6]semiconnex andconnex,^[14] orconnex andstrictly connex,^[15] respectively, as alternative names for the notions of connected and strongly connected as defined above.

Let${\displaystyle R}$ be ahomogeneous relation. The following are equivalent:^[14]

• ${\displaystyle R}$ is strongly connected;
• ${\displaystyle U\subseteq R\cup R^{\mathrm{\top }}}$;
• ${\displaystyle \overline{R}\subseteq R^{\mathrm{\top }}}$;
• ${\displaystyle \overline{R}}$ isasymmetric,

where${\displaystyle U}$ is theuniversal relation and${\displaystyle R^{\mathrm{\top }}}$ is theconverse relation of${\displaystyle R.}$

The following are equivalent:^[14]

• ${\displaystyle R}$ is connected;
• ${\displaystyle \overline{I}\subseteq R\cup R^{\mathrm{\top }}}$;
• ${\displaystyle \overline{R}\subseteq R^{\mathrm{\top }}\cup I}$;
• ${\displaystyle \overline{R}}$ isantisymmetric,

where${\displaystyle \overline{R}}$ is thecomplementary relation of${\displaystyle R}$,${\displaystyle I}$ is theidentity relation and${\displaystyle R^{\mathrm{\top }}}$ is theconverse relation of${\displaystyle R}$.

Introducing progressions, Russell invoked the axiom of connection:

Whenever a series is originally given by a transitive asymmetrical relation, we can express connection by the condition that any two terms of our series are to have thegenerating relation.

• Theedge relation^{[note 1]}${\displaystyle E}$ of atournament graph${\displaystyle G}$ is always a connected relation on the set of${\displaystyle G}$'s vertices.
• If a strongly connected relation issymmetric, it is theuniversal relation.
• A relation is strongly connected if, and only if, it is connected and reflexive.^{[proof 1]}
• A connected relation on a set${\displaystyle X}$ cannot beantitransitive, provided${\displaystyle X}$ has at least 4 elements.^[16] On a 3-element set${\displaystyle \{a,b,c\},}$ for example, the relation${\displaystyle \{(a,b),(b,c),(c,a)\}}$ has both properties.
• If${\displaystyle R}$ is a connected relation on${\displaystyle X,}$ then all, or all but one, elements of${\displaystyle X}$ are in therange of${\displaystyle R.}$^{[proof 2]} Similarly, all, or all but one, elements of${\displaystyle X}$ are in the domain of${\displaystyle R.}$

Proofs

• Properties of binary relations

• Articles with short description
• Short description is different from Wikidata