Connected relation
Transitive binary relations | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() ![]() All definitions tacitly require the homogeneous relation be transitive: for all if and then |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/40px-Wiktionary-logo-en-v2.svg.png)
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
Every pair of elements is either in R or in the converse relation RT.
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
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 ↔ U ⊆ R ∪ RT ↔ R ⊆ RT ↔ R is asymmetric,
- where U is the universal relation and RT is the converse relation of R.[1]
- R is semiconnex ↔ I ⊆ R ∪ RT ↔ R ⊆ RT ∪ I ↔ R is antisymmetric,
- where I is the complementary relation of the identity relation I and RT 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
(help); Unknown parameter|contributionurl=
|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.