Connected relation

<h2 id="formal-definition">Formal definition</h2>
A relation 
 
 
 
 R
 
 
 {\displaystyle R}
 
 on a set 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is called connected when for all 
 
 
 
 x
 ,
 y
 ∈
 X
 ,
 
 
 {\displaystyle x,y\in X,}

if 
        
        x
        ≠
        y
        
           then 
        
        x
        
          R
        
        y
        
        
          or
        
        
        y
        
          R
        
        x
        ,
      
    
    {\displaystyle {\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
        ∈
        X
        ,
      
    
    {\displaystyle x,y\in X,}

x
        
          R
        
        y
        
        
          or
        
        
        y
        
          R
        
        x
        
        
          or
        
        
        x
        =
        y
        .
      
    
    {\displaystyle 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
 ∈
 X
 ,
 
 
 {\displaystyle x,y\in X,}

x
        
          R
        
        y
        
        
          or
        
        
        y
        
          R
        
        x
      
    
    {\displaystyle x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R} x}

is called strongly connected.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a><a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h3>Terminology</h3>
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.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
Thus, total is used more generally for relations that are connected or strongly connected.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> However, this notion of "total relation" must be distinguished from the property of being <a href="/facts/Serial_relation/XDNWHWH9">serial</a>, which is also called total. Similarly, connected relations are sometimes called complete,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> although this, too, can lead to confusion: The <a href="/facts/Universal_relation/wh0QoWzS">universal relation</a> is also called complete,<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> and "<a href="/facts/Completeness_(order_theory)/06m5lcIQ">complete</a>" has several other meanings in <a href="/facts/Order_theory/gn6fM3oJ">order theory</a>.
Connected relations are also called connex<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> or said to satisfy trichotomy<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> (although the more common definition of <a href="/facts/Trichotomy_(mathematics)/o3mHmLka">trichotomy</a> is stronger in that exactly one of the three options 
 
 
 
 x
 
 R
 
 y
 ,
 y
 
 R
 
 x
 ,
 x
 =
 y
 
 
 {\displaystyle 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 weakly connected and connected,<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> complete and strongly complete,<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> total and complete,<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> semiconnex and connex,<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> or connex and strictly connex,<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> respectively, as alternative names for the notions of connected and strongly connected as defined above.

<h2 id="characterizations">Characterizations</h2>
Let 
 
 
 
 R
 
 
 {\displaystyle R}
 
 be a <a href="/facts/Homogeneous_relation/wh0QoWzS">homogeneous relation</a>. The following are equivalent:<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

<ul><li>
 
 
 
 R
 
 
 {\displaystyle R}
 
 is strongly connected;</li>
<li>
 
 
 
 U
 ⊆
 R
 ∪
 
 R
 
 ⊤
 
 
 
 
 {\displaystyle U\subseteq R\cup R^{\top }}
 
;</li>
<li>
 
 
 
 
 
 R
 ¯
 
 
 ⊆
 
 R
 
 ⊤
 
 
 
 
 {\displaystyle {\overline {R}}\subseteq R^{\top }}
 
;</li>
<li>
 
 
 
 
 
 R
 ¯
 
 
 
 
 {\displaystyle {\overline {R}}}
 
 is <a href="/facts/Asymmetric_relation/rUdVRwuI">asymmetric</a>,</li></ul>
where 
 
 
 
 U
 
 
 {\displaystyle U}
 
 is the <a href="/facts/Universal_relation/wh0QoWzS">universal relation</a> and 
 
 
 
 
 R
 
 ⊤
 
 
 
 
 {\displaystyle R^{\top }}
 
 is the <a href="/facts/Converse_relation/EVGlRSz7">converse relation</a> of 
 
 
 
 R
 .
 
 
 {\displaystyle R.}

The following are equivalent:<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>

<ul><li>
 
 
 
 R
 
 
 {\displaystyle R}
 
 is connected;</li>
<li>
 
 
 
 
 
 I
 ¯
 
 
 ⊆
 R
 ∪
 
 R
 
 ⊤
 
 
 
 
 {\displaystyle {\overline {I}}\subseteq R\cup R^{\top }}
 
;</li>
<li>
 
 
 
 
 
 R
 ¯
 
 
 ⊆
 
 R
 
 ⊤
 
 
 ∪
 I
 
 
 {\displaystyle {\overline {R}}\subseteq R^{\top }\cup I}
 
;</li>
<li>
 
 
 
 
 
 R
 ¯
 
 
 
 
 {\displaystyle {\overline {R}}}
 
 is <a href="/facts/Antisymmetric_relation/YhuqG4z8">antisymmetric</a>,</li></ul>
where 
 
 
 
 
 
 I
 ¯
 
 
 
 
 {\displaystyle {\overline {I}}}
 
 is the <a href="/facts/Complement_(set_theory)/yWUePIYY">complementary relation</a> of the <a href="/facts/Identity_relation/wh0QoWzS">identity relation</a> 
 
 
 
 I
 
 
 {\displaystyle I}
 
 and 
 
 
 
 
 R
 
 ⊤
 
 
 
 
 {\displaystyle R^{\top }}
 
 is the <a href="/facts/Converse_relation/EVGlRSz7">converse relation</a> of 
 
 
 
 R
 .
 
 
 {\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 the <a href="/facts/Serial_relation/XDNWHWH9">generating relation</a>.— <a href="/facts/Bertrand_Russell/SRpwNX2U">Bertrand Russell</a>, <a href="/facts/The_Principles_of_Mathematics/Vd3bSkkt">The Principles of Mathematics</a>, page 239
<h2 id="properties">Properties</h2>
<ul><li>The edge relation<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> 
 
 
 
 E
 
 
 {\displaystyle E}
 
 of a <a href="/facts/Tournament_(graph_theory)/SVj5jWWE">tournament</a> graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is always a connected relation on the set of 
 
 
 
 G
 
 
 {\displaystyle G}
 
's vertices.</li>
<li>If a strongly connected relation is <a href="/facts/Symmetric_relation/ekCWDIAH">symmetric</a>, it is the <a href="/facts/Universal_relation/wh0QoWzS">universal relation</a>.</li>
<li>A relation is strongly connected if, and only if, it is connected and reflexive.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a></li>
<li>A connected relation on a set 
 
 
 
 X
 
 
 {\displaystyle X}
 
 cannot be <a href="/facts/Antitransitive/eRDjvMDo">antitransitive</a>, provided 
 
 
 
 X
 
 
 {\displaystyle X}
 
 has at least 4 elements.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a> On a 3-element set 
 
 
 
 {
 a
 ,
 b
 ,
 c
 }
 ,
 
 
 {\displaystyle \{a,b,c\},}
 
 for example, the relation 
 
 
 
 {
 (
 a
 ,
 b
 )
 ,
 (
 b
 ,
 c
 )
 ,
 (
 c
 ,
 a
 )
 }
 
 
 {\displaystyle \{(a,b),(b,c),(c,a)\}}
 
 has both properties.</li>
<li>If 
 
 
 
 R
 
 
 {\displaystyle R}
 
 is a connected relation on 
 
 
 
 X
 ,
 
 
 {\displaystyle X,}
 
 then all, or all but one, elements of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 are in the <a href="/facts/Image_(mathematics)/KANefMAl">range</a> of 
 
 
 
 R
 .
 
 
 {\displaystyle R.}
 
<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a> Similarly, all, or all but one, elements of 
 
 
 
 X
 
 
 {\displaystyle X}
 
 are in the domain of 
 
 
 
 R
 .
 
 
 {\displaystyle R.}
 
</li></ul>
<h2 id="notes">Notes</h2>

Proofs

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Clapham, Christopher; Nicholson, James (2014-09-18). "connected". The Concise Oxford Dictionary of Mathematics. Oxford University Press. ISBN 978-0-19-967959-1. Retrieved 2021-04-12. <a href="978-0-19-967959-1" target="_blank">978-0-19-967959-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Nievergelt, Yves (2015-10-13). Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications. Springer. p. 182. ISBN 978-1-4939-3223-8. <a href="978-1-4939-3223-8" target="_blank">978-1-4939-3223-8</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Causey, Robert L. (1994). Logic, Sets, and Recursion. Jones & Bartlett Learning. ISBN 0-86720-463-X., p. 135 <a href="0-86720-463-X" target="_blank">0-86720-463-X</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Paul R. Halmos (1968). Naive Set Theory. Princeton: Nostrand. Here: Ch.14. Halmos gives the names of reflexivity, anti-symmetry, and transitivity, but not of connectedness. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Patrick Cousot (1990). "Methods and Logics for Proving Programs". In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 841–993. ISBN 0-444-88074-7. Here: Sect.6.3, p.878 <a href="0-444-88074-7" target="_blank">0-444-88074-7</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Infinite Dimensional Analysis: A Hitchhiker's Guide. Springer. ISBN 978-3-540-32696-0., p. 6 <a href="978-3-540-32696-0" target="_blank">978-3-540-32696-0</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Makinson, David (2012-02-27). Sets, Logic and Maths for Computing. Springer. ISBN 978-1-4471-2500-6., p. 50 <a href="978-1-4471-2500-6" target="_blank">978-1-4471-2500-6</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Whitehead, Alfred North; Russell, Bertrand (1910). Principia Mathematica. Cambridge: Cambridge University Press. <a href="/wiki/Alfred_North_Whitehead" target="_blank">/wiki/Alfred_North_Whitehead</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Wall, Robert E. (1974). Introduction to Mathematical Linguistics. Prentice-Hall. page 114. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Carl Pollard. "Relations and Functions" (PDF). Ohio State University. Retrieved 2018-05-28. Page 7. <a href="http://www.ling.ohio-state.edu/~pollard/680/chapters/relations.pdf" target="_blank">http://www.ling.ohio-state.edu/~pollard/680/chapters/relations.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Kunen, Kenneth (2009). The Foundations of Mathematics. College Publications. ISBN 978-1-904987-14-7. p. 24 <a href="978-1-904987-14-7" target="_blank">978-1-904987-14-7</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Fishburn, Peter C. (2015-03-08). The Theory of Social Choice. Princeton University Press. p. 72. ISBN 978-1-4008-6833-9. <a href="978-1-4008-6833-9" target="_blank">978-1-4008-6833-9</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Roberts, Fred S. (2009-03-12). Measurement Theory: Volume 7: With Applications to Decisionmaking, Utility, and the Social Sciences. Cambridge University Press. ISBN 978-0-521-10243-8. page 29 <a href="978-0-521-10243-8" target="_blank">978-0-521-10243-8</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Infinite Dimensional Analysis: A Hitchhiker's Guide. Springer. ISBN 978-3-540-32696-0., p. 6 <a href="978-3-540-32696-0" target="_blank">978-3-540-32696-0</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. ISBN 978-3-642-77970-1. <a href="978-3-642-77970-1" target="_blank">978-3-642-77970-1</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Ganter, Bernhard; Wille, Rudolf (2012-12-06). Formal Concept Analysis: Mathematical Foundations. Springer Science & Business Media. ISBN 978-3-642-59830-2. p. 86 <a href="978-3-642-59830-2" target="_blank">978-3-642-59830-2</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. ISBN 978-3-642-77970-1. <a href="978-3-642-77970-1" target="_blank">978-3-642-77970-1</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. ISBN 978-3-642-77970-1. <a href="978-3-642-77970-1" target="_blank">978-3-642-77970-1</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Defined formally by 
 
 
 
 v
 E
 w
 
 
 {\displaystyle vEw}
 
 if a graph edge leads from vertex 
 
 
 
 v
 
 
 {\displaystyle v}
 
 to vertex 
 
 
 
 w
 
 
 {\displaystyle w}
 <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">For the only if direction, both properties follow trivially. — For the if direction: when 
 
 
 
 x
 ≠
 y
 ,
 
 
 {\displaystyle x\neq y,}
 
 then 
 
 
 
 x
 
 R
 
 y
 ∨
 y
 
 R
 
 x
 
 
 {\displaystyle x\mathrel {R} y\lor y\mathrel {R} x}
 
 follows from connectedness; when 
 
 
 
 x
 =
 y
 ,
 
 
 {\displaystyle x=y,}
 
 
 
 
 
 x
 
 R
 
 y
 
 
 {\displaystyle x\mathrel {R} y}
 
 follows from reflexivity. <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Jochen Burghardt (Jun 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036. Bibcode:2018arXiv180605036B. Lemma 8.2, p.8. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">If 
 
 
 
 x
 ,
 y
 ∈
 X
 ∖
 ran
 ⁡
 (
 R
 )
 ,
 
 
 {\displaystyle x,y\in X\setminus \operatorname {ran} (R),}
 
 then 
 
 
 
 x
 
 R
 
 y
 
 
 {\displaystyle x\mathrel {R} y}
 
 and 
 
 
 
 y
 
 R
 
 x
 
 
 {\displaystyle y\mathrel {R} x}
 
 are impossible, so 
 
 
 
 x
 =
 y
 
 
 {\displaystyle x=y}
 
 follows from connectedness. <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
</ol>

Connected relation open-in-new

Connected relation