Connected relation

Transitive binary relations

	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 $a,b$ and $S\neq \varnothing :$	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$	$aRa$	${\text{not }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$

indicates that the column's property is always true 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 by

in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$
A term's definition may require additional properties that are not listed in this table.

In mathematics, a homogeneous relation is called a connex relation,^[1] or a relation having the property of connexity, if it relates all pairs of elements in some way. More formally, the homogeneous relation $R$ over a set $X$ is connex when

\forall x,\ y\in X,\,\,x\ R\ y\ \lor \ y\ R\ x

Every pair of elements is either in $R$ or in the converse relation $R T$ .

A homogeneous relation is called a semiconnex relation,^[1] or a relation having the property of semiconnexity, if it relates all pairs of distinct elements in some way. More formally, the homogeneous relation $R$ over a set $X$ is semiconnex when

\forall x,\ y\in X,\,\,x\neq y\rightarrow x\ R\ y\ \lor \ y\ R\ x

Several authors define only the semiconnex property, and call it connex rather than semiconnex.^[2]^[3]^[4]

The connex properties originated from order theory: if a partial order is also a connex relation, then it is a total order. Therefore, in older sources, a connex relation was said to have the totality property;^{[citation needed]} however, this terminology is disadvantageous as it may lead to confusion with, e.g., the unrelated notion of right-totality, also known as surjectivity. Some authors call the connex property of a relation completeness.^{[citation needed]}

Characterizations

Let $R$ be a homogeneous relation.

$R$ is connex $\leftrightarrow U \subseteq R \cup R T \leftrightarrow R \subseteq R T \leftrightarrow R$ is asymmetric,

where

U

is the universal relation and

R T

is the converse relation of

R

.^[1]

$R$ is semiconnex $\leftrightarrow I \subseteq R \cup R T \leftrightarrow R \subseteq R T \cup I \leftrightarrow R$ is antisymmetric,

where

I

is the complementary relation of the identity relation

I

and

R T

is the converse relation of

R

.^[1]

Properties

The edge relation^[5] $E$ of a tournament graph $G$ is always a semiconnex relation on the set of $G$ 's vertices.
A connex relation cannot be symmetric, except for the universal relation.
A relation is connex if, and only if, it is semiconnex and reflexive.^[6]
A semiconnex relation on a set $X$ cannot be antitransitive, provided $X$ has at least 4 elements.^[7] On a 3-element set ${a, b, c$ }, e.g. the relation ${(a, b), (b, c), (c, a)$ } has both properties.
If $R$ is a semiconnex relation on $X$ , then all, or all but one, elements of $X$ are in the range of $R$ .^[8] Similarly, all, or all but one, elements of $X$ are in the domain of $R$ .

References

^ ^a ^b ^c ^d Schmidt & Ströhlein 1993, p. 12.
^ Bram van Heuveln. "Sets, Relations, Functions" (PDF). Troy, NY. Retrieved 2018-05-28. Page 4.
^ Carl Pollard. "Relations and Functions" (PDF). Ohio State University. Retrieved 2018-05-28. Page 7.
^ Felix Brandt; Markus Brill; Paul Harrenstein (2016). "Tournament Solutions". In Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia (eds.). Handbook of Computational Social Choice. Cambridge University Press. ISBN 978-1-107-06043-2. {{cite book}}: |access-date= requires |url= (help); |archive-url= requires |url= (help); External link in |contributionurl= (help); Unknown parameter |contributionurl= ignored (|contribution-url= suggested) (help) Page 59, footnote 1.
^ defined formally by vEw if a graph edge leads from vertice v to vertice w
^ For the only if direction, both properties follow trivially. — For the if direction: when x≠y, then xRy ∨ yRx follows from the semiconnex property; when x=y, even xRy follows from reflexivity.
^ Jochen Burghardt (Jun 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036. Bibcode:2018arXiv180605036B. Lemma 8.2, p.8.
^ If x, y∈X\ran(R), then xRy and yRx are impossible, so x=y follows from the semiconnex property.

Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer-Verlag. ISBN 978-3-642-77970-1.

[FOOTNOTESchmidtStröhlein199312-1] Schmidt & Ströhlein 1993, p. 12.

[2] Bram van Heuveln. "Sets, Relations, Functions" (PDF). Troy, NY. Retrieved 2018-05-28. Page 4.

[3] Carl Pollard. "Relations and Functions" (PDF). Ohio State University. Retrieved 2018-05-28. Page 7.

[4] Felix Brandt; Markus Brill; Paul Harrenstein (2016). "Tournament Solutions". In Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia (eds.). Handbook of Computational Social Choice. Cambridge University Press. ISBN 978-1-107-06043-2. {{cite book}}: |access-date= requires |url= (help); |archive-url= requires |url= (help); External link in |contributionurl= (help); Unknown parameter |contributionurl= ignored (|contribution-url= suggested) (help) Page 59, footnote 1.

[5] rmally by vEw if a graph edge leads from vertice v to vertice w

[6] For the only if direction, both properties follow trivially. — For the if direction: when x≠y, then xRy ∨ yRx follows from the semiconnex property; when x=y, even xRy follows from reflexivity.

[7] Jochen Burghardt (Jun 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036. Bibcode:2018arXiv180605036B. Lemma 8.2, p.8.

[8] If x, y∈X\ran(R), then xRy and yRx are impossible, so x=y follows from the semiconnex property.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]