“Connex relation”的意思、由来-开放百科全书

In mathematics, a binary relation R on a set X is called a connex relation, or a relation having the property of connexity, if it relates all pairs of elements from X in some way. More formally, R is connex when

A relation is called a semi-connex relation, or a relation having the property of semiconnexity, if it relates all distinct elements in some way. Several authors define only the latter property, and call it connex rather than semi-connex.^[1]^[2]^[3]

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; however, this terminology is disadvantageous as it may lead to confusion with, e.g., the unrelated notion of right-totality, a.k.a. surjectivity. Some authors call the connex property of a relation completeness.{{cn|reason=Example citations should be given for all naming variants, 'connex', 'total', 'connexity', and 'complete'.|date=December 2018}}

Formal definition

A connex relation is a homogeneous binary relation R on some set X for which either xRy or yRx holds for any pair (x, y). An equivalent statement in terms of the universal relation X×X is

A relation R is semi-connex when x≠y and (x, y) ∉ R implies (y, x) ∈ R. If I is the identity relation, an alternative characterization of a semi-connex relation is

Properties

References

1. ^{{cite web |url=http://www.cogsci.rpi.edu/~heuveb/teaching/Logic/CompLogic/Web/Handouts/SetsRelationsFunctions.pdf |title=Sets, Relations, Functions |author=Bram van Heuveln |location=Troy, NY |accessdate=2018-05-28}} Page 4.
2. ^{{cite web |url=http://www.ling.ohio-state.edu/~pollard/680/chapters/relations.pdf |title= Relations and Functions |author=Carl Pollard |location=Ohio State University |accessdate=2018-05-28}} Page 7.
3. ^{{cite book |contributionurl=http://procaccia.info/papers/comsoc.pdf |contribution=Tournament Solutions |author1=Felix Brandt |author2=Markus Brill |author3=Paul Harrenstein |title=Handbook of Computational Social Choice |editor=Felix Brandt |editor2=Vincent Conitzer |editor3=Ulle Endriss |editor4=Jérôme Lang |editor5=Ariel D. Procaccia |publisher=Cambridge University Press |date= 2016 |isbn=978-1-107-06043-2 |access-date=22 Jan 2019 |archive-url=https://web.archive.org/web/20171208162812/http://procaccia.info/papers/comsoc.pdf |archive-date=8 Dec 2017 |dead-url=no}} Page 59, footnote 1.
4. ^defined formally by vEw if a graph edge leads from vertice v to vertice w
5. ^For the only if direction, both properties follow trivially. — For the if direction: when x≠y, then xRy ∨ yRx follows from the semi-connex property; when x=y, even xRy follows from reflexivity.
6. ^{{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.
7. ^If x, y∈X\\ran(R), then xRy and yRx are impossible, so x=y follows from the semi-connex property.