Connected relation

<table><tbody><tr><th><a href="/facts/Transitive_relation/9r90y50r">Transitive</a> <a href="/facts/Binary_relation/r9BwGgaK">binary relations</a> <ul><li>v</li><li>t</li><li>e</li></ul></th></tr><tr><td><table><tbody><tr><td></td><td> <a href="/facts/Symmetric_relation/ekCWDIAH">Symmetric</a></td><td> <a href="/facts/Antisymmetric_relation/YhuqG4z8">Antisymmetric</a></td><td> Connected</td><td> <a href="/facts/Well-founded_relation/zyRRyJ4M">Well-founded</a></td><td> <a href="/facts/Join_and_meet/cYcLhRIR">Has joins</a></td><td> <a href="/facts/Join_and_meet/cYcLhRIR">Has meets</a></td><td> <a href="/facts/Reflexive_relation/NzTytEg9">Reflexive</a></td><td> <a href="/facts/Reflexive_relation/NzTytEg9">Irreflexive</a></td><td> <a href="/facts/Asymmetric_relation/rUdVRwuI">Asymmetric</a></td></tr><tr><td></td><td></td><td></td><td> Total, Semiconnex</td><td></td><td></td><td></td><td></td><td> Anti-reflexive</td><td></td></tr><tr><td> <a href="/facts/Equivalence_relation/1MQ5rtkW">Equivalence relation</a></td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Preorder/uubzHSWm">Preorder (Quasiorder)</a></td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Partial_order/qb4a3FAX">Partial order</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Total_preorder/LmaM9lSs">Total preorder</a></td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Total_order/xnTtmuYJ">Total order</a></td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Prewellordering/EMhoWkMU">Prewellordering</a></td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Well-quasi-ordering/suQavGN9">Well-quasi-ordering</a></td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Well-order/GrWEBWlW">Well-ordering</a></td><td> ✗</td><td> Y</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Lattice_(order)/5ak6ufky">Lattice</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Join-semilattice/kW5po0rp">Join-semilattice</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> Y</td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Meet-semilattice/kW5po0rp">Meet-semilattice</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td></tr><tr><td> <a href="/facts/Strict_partial_order/qb4a3FAX">Strict partial order</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td></tr><tr><td> <a href="/facts/Weak_ordering/LmaM9lSs">Strict weak order</a></td><td> ✗</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td></tr><tr><td> <a href="/facts/Strict_total_order/xnTtmuYJ">Strict total order</a></td><td> ✗</td><td> Y</td><td> Y</td><td> ✗</td><td> ✗</td><td> ✗</td><td> ✗</td><td> Y</td><td> Y</td></tr><tr><td></td><td> <a href="/facts/Symmetric_relation/ekCWDIAH">Symmetric</a></td><td> <a href="/facts/Antisymmetric_relation/YhuqG4z8">Antisymmetric</a></td><td> Connected</td><td> <a href="/facts/Well-founded_relation/zyRRyJ4M">Well-founded</a></td><td> <a href="/facts/Join_and_meet/cYcLhRIR">Has joins</a></td><td> <a href="/facts/Join_and_meet/cYcLhRIR">Has meets</a></td><td> <a href="/facts/Reflexive_relation/NzTytEg9">Reflexive</a></td><td> <a href="/facts/Reflexive_relation/NzTytEg9">Irreflexive</a></td><td> <a href="/facts/Asymmetric_relation/rUdVRwuI">Asymmetric</a></td></tr><tr><td> Definitions, for all                     a        ,        b              {\displaystyle a,b}   and                     S        ≠        ∅        :              {\displaystyle S\neq \varnothing :}  </td><td>                                                                                       a                R                b                                                                    ⇒                                                                            b                R                a                                                          {\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}  </td><td>                                                                         a                R                b                                   and                                                             b                R                a                                                                    ⇒                a                =                                                                            b                                                          {\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}  </td><td>                                                                         a                ≠                                                                            b                ⇒                                                                    a                R                b                                   or                                                             b                R                a                                                          {\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}  </td><td>                                                                         min                S                                                                                      exists                                                                          {\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}  </td><td>                                                                         a                ∨                b                                                                                      exists                                                                          {\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}  </td><td>                                                                         a                ∧                b                                                                                      exists                                                                          {\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}  </td><td>                     a        R        a              {\displaystyle aRa}  </td><td>                               not                 a        R        a              {\displaystyle {\text{not }}aRa}  </td><td>                                                                         a                R                b                ⇒                                                                                      not                                 b                R                a                                                          {\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}  </td></tr></tbody></table></td></tr><tr><td>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 by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. <p>All definitions tacitly require the <a href="/facts/Homogeneous_relation/wh0QoWzS">homogeneous relation</a>                     R              {\displaystyle R}   be <a href="/facts/Transitive_relation/9r90y50r">transitive</a>: for all                     a        ,        b        ,        c        ,              {\displaystyle a,b,c,}   if                     a        R        b              {\displaystyle aRb}   and                     b        R        c              {\displaystyle bRc}   then                     a        R        c        .              {\displaystyle aRc.}   A term's definition may require additional properties that are not listed in this table.</p></td></tr></tbody></table>
<p>In mathematics, a <a href="/facts/Relation_on_a_set/r9BwGgaK">relation on a set</a> is called connected or complete or total if it relates (or "compares") all distinct pairs of elements of the set in one direction or the other while it is called strongly connected if it relates all pairs of elements.  As described in the 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 
  
    
      
        x
        ∈
        X
      
    
    {\displaystyle x\in X}
  
 there is a 
  
    
      
        y
        ∈
        X
      
    
    {\displaystyle y\in X}
  
 so that 
  
    
      
        x
        
          R
        
        y
      
    
    {\displaystyle x\mathrel {R} y}
  
 (see <a href="/facts/Serial_relation/XDNWHWH9">serial relation</a>).
</p><p>Connectedness features prominently in the definition of <a href="/facts/Total_order/xnTtmuYJ">total orders</a>: a total (or linear) order is a <a href="/facts/Partial_order/qb4a3FAX">partial order</a> in which any two elements are comparable; that is, the order relation is connected. Similarly, a <a href="/facts/Strict_partial_order/qb4a3FAX">strict partial order</a> that is connected is a strict total order.
A relation is a total order <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> it is both a partial order and strongly connected. A relation is a <a href="/facts/Strict_total_order/xnTtmuYJ">strict total order</a> 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).
</p><p>Some authors do however use the term <i>connected</i> with a much looser meaning, which applies to precisely those orders whose <a href="/facts/Comparability_graph/dLht35EJ">comparability graphs</a> are <a href="/facts/Connected_graph/FSNjsYhz">connected graphs</a>. This applies for instance to the <a href="/facts/Fence_(mathematics)/0CRvxLoY">fences</a>, of which none of the nontrivial examples are total orders.
</p>

Connected relation open-in-new

Connected relation