[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/connected-relation-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki40\/connected-relation-wikipedia\/","headline":"Connected relation – Wikipedia","name":"Connected relation – Wikipedia","description":"From Wikipedia, the free encyclopedia Property of a relation on a set “Connexity” redirects here. For the comparison shopping company,","datePublished":"2018-05-10","dateModified":"2018-05-10","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki40\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/0\/03\/Green_check.svg\/13px-Green_check.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/0\/03\/Green_check.svg\/13px-Green_check.svg.png","height":"13","width":"13"},"url":"https:\/\/wiki.edu.vn\/en\/wiki40\/connected-relation-wikipedia\/","wordCount":9740,"articleBody":"From Wikipedia, the free encyclopediaProperty of a relation on a set“Connexity” redirects here. For the comparison shopping company, see Connexity Inc.Transitive\u00a0binary relationsY indicates that the column’s property is always true the row’s term (at the very left), while \u2717 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 \u2717 in the “Antisymmetric” column, respectively. All definitions tacitly require the homogeneous relation R{displaystyle R} be transitive: for all a,b,c,{displaystyle a,b,c,} if aRb{displaystyle aRb} and bRc{displaystyle bRc} then aRc.{displaystyle aRc.} A term’s definition may require additional properties that are not listed in this table.In mathematics, a relation on a set 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\u2208X{displaystyle xin X} there is a y\u2208X{displaystyle yin X} so that xRy{displaystyle xmathrel {R} y} (see serial 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).Table of ContentsFormal definition[edit]Terminology[edit]Characterizations[edit]Properties[edit]References[edit]Formal definition[edit]A relation R{displaystyle R} on a set X{displaystyle X} is called connected when for all x,y\u2208X,{displaystyle x,yin X,}\u00a0if\u00a0x\u2260y\u00a0then\u00a0xRyoryRx,{displaystyle {text{ if }}xneq y{text{ then }}xmathrel {R} yquad {text{or}}quad ymathrel {R} x,}or, equivalently, when for all x,y\u2208X,{displaystyle x,yin X,}xRyoryRxorx=y.{displaystyle xmathrel {R} yquad {text{or}}quad ymathrel {R} xquad {text{or}}quad x=y.}A relation with the property that for all x,y\u2208X,{displaystyle x,yin X,}xRyoryRx{displaystyle xmathrel {R} yquad {text{or}}quad ymathrel {R} x}is called strongly connected.[1][2][3]Terminology[edit]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.[4][5]Thus, total is used more generally for relations that are connected or strongly connected.[6] 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,[7] although this, too, can lead to confusion: The universal relation is also called complete,[8] and “complete” has several other meanings in order theory.Connected relations are also called connex[9][10] or said to satisfy trichotomy[11] (although the more common definition of trichotomy is stronger in that exactly one of the three options xRy,yRx,x=y{displaystyle xmathrel {R} y,ymathrel {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,[12]complete and strongly complete,[13]total and complete,[6]semiconnex and connex,[14] or connex and strictly connex,[15] respectively, as alternative names for the notions of connected and strongly connected as defined above.Characterizations[edit]Let R{displaystyle R} be a homogeneous relation. The following are equivalent:[14]R{displaystyle R} is strongly connected;U\u2286R\u222aR\u22a4{displaystyle Usubseteq Rcup R^{top }};R\u00af\u2286R\u22a4{displaystyle {overline {R}}subseteq R^{top }};R\u00af{displaystyle {overline {R}}} is asymmetric,where U{displaystyle U} is the universal relation and R\u22a4{displaystyle R^{top }} is the converse relation of R.{displaystyle R.}The following are equivalent:[14]R{displaystyle R} is connected;I\u00af\u2286R\u222aR\u22a4{displaystyle {overline {I}}subseteq Rcup R^{top }};R\u00af\u2286R\u22a4\u222aI{displaystyle {overline {R}}subseteq R^{top }cup I};R\u00af{displaystyle {overline {R}}} is antisymmetric,where I\u00af{displaystyle {overline {I}}} is the complementary relation of the identity relation I{displaystyle I} and R\u22a4{displaystyle R^{top }} is the converse relation 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 generating relation.Properties[edit]The edge relation[note 1]E{displaystyle E} of a tournament graph G{displaystyle G} is always a connected relation on the set of G{displaystyle G}‘s vertices.If a strongly connected relation is symmetric, it is the universal relation.A relation is strongly connected if, and only if, it is connected and reflexive.[proof 1]A connected relation on a set X{displaystyle X} cannot be antitransitive, provided X{displaystyle X} has at least 4 elements.[16] 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.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 range of R.{displaystyle R.}[proof 2] Similarly, all, or all but one, elements of X{displaystyle X} are in the domain of R.{displaystyle R.}^ Defined formally by vEw{displaystyle vEw} if a graph edge leads from vertex v{displaystyle v} to vertex w{displaystyle w}Proofs^ For the only if direction, both properties follow trivially. \u2014 For the if direction: when x\u2260y,{displaystyle xneq y,} then xRy\u2228yRx{displaystyle xmathrel {R} ylor ymathrel {R} x} follows from connectedness; when x=y,{displaystyle x=y,}  xRy{displaystyle xmathrel {R} y} follows from reflexivity.^ If x,y\u2208X\u2216ran\u2061(R),{displaystyle x,yin Xsetminus operatorname {ran} (R),} then xRy{displaystyle xmathrel {R} y} and yRx{displaystyle ymathrel {R} x} are impossible, so x=y{displaystyle x=y} follows from connectedness.References[edit]^ Clapham, Christopher; Nicholson, James (2014-09-18). “connected”. The Concise Oxford Dictionary of Mathematics. Oxford University Press. ISBN\u00a0978-0-19-967959-1. Retrieved 2021-04-12.^ Nievergelt, Yves (2015-10-13). Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications. Springer. p.\u00a0182. ISBN\u00a0978-1-4939-3223-8.^ Causey, Robert L. (1994). Logic, Sets, and Recursion. Jones & Bartlett Learning. ISBN\u00a00-86720-463-X., p. 135^ 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.^ Patrick Cousot (1990). “Methods and Logics for Proving Programs”.  In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol.\u00a0B. Elsevier. pp.\u00a0841\u2013993. ISBN\u00a00-444-88074-7. Here: Sect.6.3, p.878^ a b Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Infinite Dimensional Analysis: A Hitchhiker’s Guide. Springer. ISBN\u00a0978-3-540-32696-0., p. 6^ Makinson, David (2012-02-27). Sets, Logic and Maths for Computing. Springer. ISBN\u00a0978-1-4471-2500-6., p. 50^ Whitehead, Alfred North; Russell, Bertrand (1910). Principia Mathematica. Cambridge: Cambridge University Press.{{cite book}}:  CS1 maint: date and year (link)^ Wall, Robert E. (1974). Introduction to Mathematical Linguistics. Prentice-Hall. page 114.^ Carl Pollard. “Relations and Functions” (PDF). Ohio State University. Retrieved 2018-05-28. Page 7.^ Kunen, Kenneth (2009). The Foundations of Mathematics. College Publications. ISBN\u00a0978-1-904987-14-7. p. 24^ Fishburn, Peter C. (2015-03-08). The Theory of Social Choice. Princeton University Press. p.\u00a072. ISBN\u00a0978-1-4008-6833-9.^ Roberts, Fred S. (2009-03-12). Measurement Theory: Volume 7: With Applications to Decisionmaking, Utility, and the Social Sciences. Cambridge University Press. ISBN\u00a0978-0-521-10243-8. page 29^ a b c Schmidt, Gunther; Str\u00f6hlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. ISBN\u00a0978-3-642-77970-1.^ Ganter, Bernhard; Wille, Rudolf (2012-12-06). Formal Concept Analysis: Mathematical Foundations. Springer Science & Business Media. ISBN\u00a0978-3-642-59830-2. p. 86^ Jochen Burghardt (Jun 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036. Bibcode:2018arXiv180605036B. Lemma 8.2, p.8."},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki40\/connected-relation-wikipedia\/#breadcrumbitem","name":"Connected relation – Wikipedia"}}]}]