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

Formal definition

A relation ${\displaystyle R}$ on a set ${\displaystyle X}$ is called connected 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 called strongly connected.

Terminology

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. Thus, total is used more generally for relations that are connected or strongly connected. However, this notion of "total relation" must be distinguished from the property of being serial, which is also called total. Similarly, connected relations are sometimes called complete, although this, too, can lead to confusion: The universal relation is also called complete, and "complete" has several other meanings in order theory. Connected relations are also called connex or said to satisfy trichotomy (although the more common definition of trichotomy is stronger in that exactly 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 as weakly connected and connected, complete and strongly complete, total and complete, semiconnex and connex, or connex and strictly connex, respectively, as alternative names for the notions of connected and strongly connected as defined above.