Quasitransitive relation

A binary relation T over a set X is quasitransitive if for all a, b, and c in X the following holds:

: $(a\backslash operatorname\{T\}b)\; \backslash wedge\; \backslash neg(b\backslash operatorname\{T\}a)\; \backslash wedge\; (b\backslash operatorname\{T\}c)\; \backslash wedge\; \backslash neg(c\backslash operatorname\{T\}b)\; \backslash Rightarrow\; (a\backslash operatorname\{T\}c)\; \backslash wedge\; \backslash neg(c\backslash operatorname\{T\}a).$

If the relation is also antisymmetric, T is transitive.

Alternately, for a relation T, define the asymmetric or "strict" part P:

:$(a\backslash operatorname\{P\}b)\; \backslash Leftrightarrow\; (a\backslash operatorname\{T\}b)\; \backslash wedge\; \backslash neg(b\backslash operatorname\{T\}a).$

Then T is quasitransitive if and only if P is transitive.

Preferences are assumed to be quasitransitive (rather than transitive) in some economic contexts. The classic example is a person indifferent between 7 and 8 grams of sugar and indifferent between 8 and 9 grams of sugar, but who prefers 9 grams of sugar to 7.{{cite journal | url=https://www.imbs.uci.edu/files/personnel/luce/pre1990/1956/Luce_Econometrica_1956.pdf | author=Robert Duncan Luce | author-link=Robert Duncan Luce | title=Semiorders and a Theory of Utility Discrimination | journal=Econometrica | volume=24 | number=2 | pages=178–191 | date=Apr 1956 | doi=10.2307/1905751| jstor=1905751 }} Here: p.179; Luce's original example consists in 400 comparisons (of coffee cups with different amounts of sugar) rather than just 2. Similarly, the Sorites paradox can be resolved by weakening assumed transitivity of certain relations to quasitransitivity.

• A relation R is quasitransitive if, and only if, it is the disjoint union of a symmetric relation J and a transitive relation P.The naminig follows {{harvtxt|Bossert|Suzumura|2009}}, p.2-3. — For the only-if part, define xJy as xRy ∧ yRx, and define xPy as xRy ∧ ¬yRx. — For the if part, assume xRy ∧ ¬yRx ∧ yRz ∧ ¬zRy holds. Then xPy and yPz, since xJy or yJz would contradict ¬yRx or ¬zRy. Hence xPz by transitivity, ¬xJz by disjointness, ¬zJx by symmetry. Therefore, zRx would imply zPx, and, by transitivity, zPy, which contradicts ¬zRy. Altogether, this proves xRz ∧ ¬zRx. J and P are not uniquely determined by a given R;For example, if R is an equivalence relation, J may be chosen as the empty relation, or as R itself, and P as its complement. however, the P from the only-if part is minimal.Given R, whenever xRy ∧ ¬yRx holds, the pair (x,y) can't belong to the symmetric part, but must belong to the transitive part.
• As a consequence, each symmetric relation is quasitransitive, and so is each transitive relation.Since the empty relation is trivially both transitive and symmetric. Moreover, an antisymmetric and quasitransitive relation is always transitive.The antisymmetry of R forces J to be coreflexive; hence the union of J and the transitive P is again transitive.
• The relation from the above sugar example, {(7,7), (7,8), (7,9), (8,7), (8,8), (8,9), (9,8), (9,9)}, is quasitransitive, but not transitive.
• A quasitransitive relation needn't be acyclic: for every non-empty set A, the universal relation A×A is both cyclic and quasitransitive.
• A relation is quasitransitive if, and only if, its complement is.
• Similarly, a relation is quasitransitive if, and only if, its converse is.

• Intransitivity
• Reflexive relation

{{reflist}}

• {{cite journal | last=Sen | first=A. | author-link=Amartya Sen | title=Quasi-transitivity, rational choice and collective decisions | zbl=0181.47302 | journal=Rev. Econ. Stud. | volume=36 | pages=381–393 | year=1969 | issue=3 | doi=10.2307/2296434 | jstor=2296434 }}
• {{cite journal | jstor=186166 | author=Frederic Schick | title=Arrow's Proof and the Logic of Preference | journal=Philosophy of Science | volume=36 | number=2 | pages=127–144 | date=Jun 1969 | doi=10.1086/288241| s2cid=121427121 }}
• {{cite book | author=Amartya K. Sen | title=Collective Choice and Social Welfare | publisher=Holden-Day, Inc. | year=1970 }}
• {{cite journal | url=https://www.ihs.ac.at/publications/eco/visit_profs/blume/sen.pdf | author=Amartya K. Sen | title=Choice Functions and Revealed Preference | journal=The Review of Economic Studies | volume=38 | number=3 | pages=307–317 | date=Jul 1971 | doi=10.2307/2296384| jstor=2296384 }}
• {{cite journal | url=https://pdfs.semanticscholar.org/f66c/6beda52f00373ca04509fd9ad27e6763055f.pdf | archive-url=https://web.archive.org/web/20180412082300/https://pdfs.semanticscholar.org/f66c/6beda52f00373ca04509fd9ad27e6763055f.pdf | url-status=dead | archive-date=2018-04-12 | author=A. Mas-Colell and H. Sonnenschein | title=General Possibility Theorems for Group Decisions | journal=The Review of Economic Studies | volume=39 | pages=185–192 | year=1972 | issue=2 | doi=10.2307/2296870| jstor=2296870 | s2cid=7295776 }}
• {{cite journal | author=D.H. Blair and R.A. Pollak | title=Acyclic Collective Choice Rules | journal=Econometrica | volume=50 | pages=931–943 | year=1982 | issue=4 | doi=10.2307/1912770| jstor=1912770 }}
• {{cite report | url=http://faculty.arts.ubc.ca/pnorman/CETC/Papers/bossert.pdf | first1=Walter | last1=Bossert | first2=Kotaro | last2=Suzumura | title=Rational Choice on Arbitrary Domains: A Comprehensive Treatment | institution=Université de Montréal, Hitotsubashi University Tokyo | type=Technical Report | date=Apr 2005 }}
• {{cite journal | url=https://pdfs.semanticscholar.org/240e/97a4f812ff51317a68c7b72d0f1e84eb8266.pdf | archive-url=https://web.archive.org/web/20180412082302/https://pdfs.semanticscholar.org/240e/97a4f812ff51317a68c7b72d0f1e84eb8266.pdf | url-status=dead | archive-date=2018-04-12 | first1=Walter | last1=Bossert | first2=Kotaro | last2=Suzumura | title=Quasi-transitive and Suzumura consistent relations | journal=Social Choice and Welfare | institution=Université de Montréal, Waseda University Tokyo | type=Technical Report | date=Mar 2009 | volume=39 | issue=2–3 | pages=323–334 | doi=10.1007/s00355-011-0600-z | s2cid=38375142 }}
• {{cite book | title=Consistency, choice and rationality | first1=Walter | last1=Bossert | first2=Kōtarō | last2=Suzumura | publisher=Harvard University Press | year=2010 | isbn=978-0674052994 }}
• {{cite report | url=http://econ.haifa.ac.il/~admiller/ArrowWithoutTransitivity.pdf | author=Alan D. Miller and Shiran Rachmilevitch | title=Arrow's Theorem Without Transitivity | institution=University of Haifa | type=Working paper | date=Feb 2014 }}

Category:Properties of binary relations

Category:Social choice theory