View source for Connected relation

{{short description|Property of a relation on a set}}
{{redirect|Connexity|the comparison shopping company|Connexity Inc.}}
{{stack|{{Binary relations}}}}
In mathematics, a [[relation on a set]] is called '''connected''' or '''complete''' or '''total''' if it relates (or "compares") all {{em|distinct}} pairs of elements of the set in one direction or the other while it is called '''strongly connected''' if it relates {{em|all}} pairs of elements.  As described in the [[#Terminology|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 <math>x \in X</math> there is a <math>y \in X</math> so that <math>x \mathrel{R} y</math> (see [[serial relation]]).

Connectedness features prominently in the definition of [[total order]]s: 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).

== Formal definition ==

A relation <math>R</math> on a set <math>X</math> is called '''{{em|{{visible anchor|connected|Connected relation}}}}''' when for all <math>x, y \in X,</math> 
<math display=block>\text{ if } x \neq y \text{ then } x \mathrel{R} y \quad \text{or} \quad y \mathrel{R} x,</math>
or, equivalently, when for all <math>x, y \in X,</math>
<math display=block>x \mathrel{R} y \quad \text{or} \quad y \mathrel{R} x \quad \text{or} \quad x = y.</math>

A relation with the property that for all <math>x, y \in X,</math> 
<math display=block>x \mathrel{R} y \quad \text{or} \quad y \mathrel{R} x</math>
is called '''{{em|{{visible anchor|strongly connected|Strongly connected relation}}}}'''.<ref>{{Cite book|publisher=Oxford University Press|isbn=978-0-19-967959-1|last1=Clapham|first1=Christopher|last2=Nicholson|first2=James|title=The Concise Oxford Dictionary of Mathematics|chapter=connected|access-date=2021-04-12|date=2014-09-18|url=http://www.oxfordreference.com/view/10.1093/acref/9780199679591.001.0001/acref-9780199679591-e-598}}</ref><ref>{{Cite book|publisher=Springer|isbn=978-1-4939-3223-8|last=Nievergelt|first=Yves|title=Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications|date=2015-10-13|page=182|url=https://books.google.com/books?id=AInDCgAAQBAJ&pg=PA182}}</ref><ref>{{Cite book|publisher=Jones & Bartlett Learning|isbn=0-86720-463-X|last=Causey|first=Robert L.|title=Logic, Sets, and Recursion|date=1994}}, p. 135</ref>

=== 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.<ref>
{{cite book|author=Paul R. Halmos|title=Naive Set Theory|location=Princeton|publisher=Nostrand|year=1968}} Here: Ch.14. Halmos gives the names of reflexivity, anti-symmetry, and transitivity, but not of connectedness.</ref><ref>
{{cite book|author=Patrick Cousot|chapter=Methods and Logics for Proving Programs|pages=841&ndash;993|isbn=0-444-88074-7|editor=Jan van Leeuwen|title=Formal Models and Semantics|publisher=Elsevier|series=Handbook of Theoretical Computer Science|volume=B|year=1990}} Here: Sect.6.3, p.878</ref>
Thus, {{em|{{visible anchor|total|Total relation}}}} is used more generally for relations that are connected or strongly connected.<ref name="Aliprantis">{{Cite book|publisher=Springer|isbn=978-3-540-32696-0|last1=Aliprantis|first1=Charalambos D.|last2=Border|first2=Kim C.|title=Infinite Dimensional Analysis: A Hitchhiker's Guide|date=2007-05-02}}, p. 6</ref> However, this notion of "total relation" must be distinguished from the property of being [[serial relation|serial]], which is also called total.  Similarly, connected relations are sometimes called {{em|{{visible anchor|complete|Complete relation}}}},<ref>{{Cite book|publisher=Springer|isbn=978-1-4471-2500-6|last=Makinson|first=David|title=Sets, Logic and Maths for Computing|date=2012-02-27}}, p. 50</ref> although this, too, can lead to confusion: The [[universal relation]] is also called complete,<ref>{{Cite book|last1=Whitehead|first1=Alfred North|author-link1=Alfred North Whitehead|last2=Russell|first2=Bertrand|author-link2=Bertrand Russell|url=http://archive.org/details/principiamathema01anwh|title=Principia Mathematica|date=1910|publisher=Cambridge University Press|year=1910|location=Cambridge|language=English}}</ref> and "[[Completeness (order theory)|complete]]" has several other meanings in [[order theory]].
Connected relations are also called {{em|{{visible anchor|connex|Connex relation}}}}<ref>{{Cite book|publisher=Prentice-Hall|last=Wall|first=Robert E.|title=Introduction to Mathematical Linguistics|date=1974}} page 114.</ref><ref>
{{cite web|author=Carl Pollard|url=http://www.ling.ohio-state.edu/~pollard/680/chapters/relations.pdf|title=Relations and Functions|location=Ohio State University|accessdate=2018-05-28}} Page 7.</ref> or said to satisfy {{Em|trichotomy}}<ref>{{Cite book|publisher=College Publications|isbn=978-1-904987-14-7|last=Kunen|first=Kenneth|title=The Foundations of Mathematics|date=2009}} p. 24</ref> (although the more common definition of [[trichotomy (mathematics)|trichotomy]] is stronger in that {{em|exactly one}} of the three options <math>x \mathrel{R} y, y \mathrel{R} x, x = y</math> 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 {{em|{{visible anchor|weakly connected|Weakly connected relation}}}} and {{Em|connected}},<ref>{{Cite book|publisher=Princeton University Press|isbn=978-1-4008-6833-9|last=Fishburn|first=Peter C.|title=The Theory of Social Choice|date=2015-03-08|page=72|url=https://books.google.com/books?id=m2V9BgAAQBAJ&pg=PA72}}</ref> {{Em|complete}} and {{Em|strongly complete}},<ref>{{Cite book|publisher=Cambridge University Press|isbn=978-0-521-10243-8|last=Roberts|first=Fred S.|title=Measurement Theory: Volume 7: With Applications to Decisionmaking, Utility, and the Social Sciences|date=2009-03-12}} page 29</ref> {{Em|total}} and {{Em|complete}},<ref name="Aliprantis" /> {{em|{{visible anchor|semiconnex|Semiconnex relation}}}} and {{em|{{visible anchor|connex|Connex relation}}}},<ref name="Schmidt">{{cite book|last1=Schmidt|first1=Gunther|last2=Ströhlein|first2=Thomas|date=1993|title=Relations and Graphs: Discrete Mathematics for Computer Scientists|url=https://books.google.com/books?id=ZgarCAAAQBAJ|location=Berlin|publisher=Springer|isbn=978-3-642-77970-1|author-link=Gunther Schmidt }}</ref> or {{em|{{visible anchor|connex|Connex relation}}}} and {{em|{{visible anchor|strictly connex|Strictly connex relation}}}},<ref>{{Cite book|publisher=Springer Science & Business Media|isbn=978-3-642-59830-2|last1=Ganter|first1=Bernhard|last2=Wille|first2=Rudolf|title=Formal Concept Analysis: Mathematical Foundations|date=2012-12-06}} p. 86</ref> respectively, as alternative names for the notions of connected and strongly connected as defined above.

== Characterizations ==

Let <math>R</math> be a [[homogeneous relation]]. The following are equivalent:<ref name="Schmidt" />
* <math>R</math> is strongly connected;
* <math>U \subseteq R \cup R^\top</math>;
* <math>\overline{R} \subseteq R^\top</math>;
* <math>\overline{R}</math> is [[Asymmetric relation|asymmetric]],
where <math>U</math> is the [[universal relation]] and <math>R^\top</math> is the [[converse relation]] of <math>R.</math>

The following are equivalent:<ref name="Schmidt" />
* <math>R</math> is connected;
* <math>\overline{I} \subseteq R \cup R^\top</math>;
* <math>\overline{R} \subseteq R^\top \cup I</math>;
* <math>\overline{R}</math> is [[Antisymmetric relation|antisymmetric]],
where <math>\overline{I}</math> is the [[Complement (set theory)|complementary relation]] of the [[identity relation]] <math>I</math> and <math>R^\top</math> is the [[converse relation]] of <math>R.</math>

Introducing progressions, Russell invoked the axiom of connection:
{{blockquote|text=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 the [[serial relation|generating relation]].|author=[[Bertrand Russell]]|title=''[[The  Principles of Mathematics]]'', page 239}}

== Properties ==

* The {{em|edge}} relation<ref group=note>Defined formally by <math>v E w</math> if a graph edge leads from vertex <math>v</math> to vertex <math>w</math></ref> <math>E</math> of a [[Tournament (graph theory)|tournament]] graph <math>G</math> is always a connected relation on the set of <math>G</math>{{'}}s vertices.
* If a strongly connected relation is [[Symmetric relation|symmetric]], it is the [[universal relation]].
* A relation is strongly connected if, and only if, it is connected and reflexive.<ref group=proof>For the {{em|only if}} direction, both properties follow trivially. &mdash; For the {{em|if}} direction: when <math>x \neq y,</math> then <math>x\mathrel{R}y \lor y\mathrel{R}x</math> follows from connectedness; when <math>x = y,</math>  <math>x \mathrel{R} y</math> follows from reflexivity.</ref>
* A connected relation on a set <math>X</math> cannot be [[antitransitive]], provided <math>X</math> has at least 4 elements.<ref>
{{cite report|arxiv=1806.05036|author=Jochen Burghardt|title=Simple Laws about Nonprominent Properties of Binary Relations|type=Technical Report|date=Jun 2018|bibcode=2018arXiv180605036B}} Lemma 8.2, p.8.</ref> On a 3-element set <math>\{ a, b, c \},</math> for example, the relation <math>\{ (a, b), (b, c), (c, a) \}</math> has both properties.
* If <math>R</math> is a connected relation on <math>X,</math> then all, or all but one, elements of <math>X</math> are in the [[Image (mathematics)#Generalization to binary relations|range]] of <math>R.</math><ref group=proof>If <math>x, y \in X \setminus \operatorname{ran}(R),</math> then <math>x \mathrel{R} y</math> and <math>y \mathrel{R} x</math> are impossible, so <math>x = y</math> follows from connectedness.</ref> Similarly, all, or all but one, elements of <math>X</math> are in the domain of <math>R.</math>

== Notes ==

{{reflist|group=note}}

;Proofs

{{reflist|group=proof}}

==References==

{{reflist}}

{{Order theory}}

[[Category:Properties of binary relations]]