Quasitransitive relation

<h2 id="formal-definition">Formal definition</h2>
A <a href="/facts/Binary_relation/r9BwGgaK">binary relation</a> T over a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> X is quasitransitive if for all a, b, and c in X the following holds:

(
        a
        T
        ⁡
        b
        )
        ∧
        ¬
        (
        b
        T
        ⁡
        a
        )
        ∧
        (
        b
        T
        ⁡
        c
        )
        ∧
        ¬
        (
        c
        T
        ⁡
        b
        )
        ⇒
        (
        a
        T
        ⁡
        c
        )
        ∧
        ¬
        (
        c
        T
        ⁡
        a
        )
        .
      
    
    {\displaystyle (a\operatorname {T} b)\wedge \neg (b\operatorname {T} a)\wedge (b\operatorname {T} c)\wedge \neg (c\operatorname {T} b)\Rightarrow (a\operatorname {T} c)\wedge \neg (c\operatorname {T} a).}

If the relation is also <a href="/facts/Antisymmetric_relation/YhuqG4z8">antisymmetric</a>, T is transitive.
Alternately, for a relation T, define the <a href="/facts/Asymmetric_relation/rUdVRwuI">asymmetric</a> or "strict" part P:

(
        a
        P
        ⁡
        b
        )
        ⇔
        (
        a
        T
        ⁡
        b
        )
        ∧
        ¬
        (
        b
        T
        ⁡
        a
        )
        .
      
    
    {\displaystyle (a\operatorname {P} b)\Leftrightarrow (a\operatorname {T} b)\wedge \neg (b\operatorname {T} a).}

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

<h2 id="examples">Examples</h2>
<a href="/facts/Preference/hWCEmfuX">Preferences</a> 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.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> Similarly, the <a href="/facts/Sorites_paradox/T38qQ44U">Sorites paradox</a> can be resolved by weakening assumed transitivity of certain relations to quasitransitivity.

<h2 id="properties">Properties</h2>
<ul><li>A relation R is quasitransitive if, and only if, it is the <a href="/facts/Disjoint_union/x9QSfkr5">disjoint union</a> of a symmetric relation J and a transitive relation P.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> J and P are not uniquely determined by a given R;<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> however, the P from the only-if part is minimal.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>As a consequence, each symmetric relation is quasitransitive, and so is each transitive relation.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> Moreover, an antisymmetric and quasitransitive relation is always transitive.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>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.</li>
<li>A quasitransitive relation needn't be <a href="/facts/Acyclic_relation/c9rrTKWw">acyclic</a>: for every non-empty set A, the <a href="/facts/Universal_relation/wh0QoWzS">universal relation</a> A<a href="/facts/Cartesian_product/BfqBWzdL">×</a>A is both cyclic and quasitransitive.</li>
<li>A relation is quasitransitive if, and only if, its <a href="/facts/Complementary_relation/yWUePIYY">complement</a> is.</li>
<li>Similarly, a relation is quasitransitive if, and only if, its <a href="/facts/Converse_relation/EVGlRSz7">converse</a> is.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Intransitivity/eRDjvMDo">Intransitivity</a></li>
<li><a href="/facts/Reflexive_relation/NzTytEg9">Reflexive relation</a></li></ul>

<ul><li><a href="/facts/Amartya_Sen/R9zxJTMs">Sen, A.</a> (1969). "Quasi-transitivity, rational choice and collective decisions". Rev. Econ. Stud. 36 (3): 381–393. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2296434">10.2307/2296434</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2296434">2296434</a>. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0181.47302">0181.47302</a>.</li>
<li>Frederic Schick (Jun 1969). "Arrow's Proof and the Logic of Preference". Philosophy of Science. 36 (2): 127–144. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1086%2F288241">10.1086/288241</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/186166">186166</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:121427121">121427121</a>.</li>
<li>Amartya K. Sen (1970). Collective Choice and Social Welfare. Holden-Day, Inc.</li>
<li>Amartya K. Sen (Jul 1971). <a href="https://www.ihs.ac.at/publications/eco/visit_profs/blume/sen.pdf">"Choice Functions and Revealed Preference"</a> (PDF). The Review of Economic Studies. 38 (3): 307–317. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2296384">10.2307/2296384</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2296384">2296384</a>.</li>
<li>A. Mas-Colell and H. Sonnenschein (1972). <a href="https://web.archive.org/web/20180412082300/https://pdfs.semanticscholar.org/f66c/6beda52f00373ca04509fd9ad27e6763055f.pdf">"General Possibility Theorems for Group Decisions"</a> (PDF). The Review of Economic Studies. 39 (2): 185–192. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2296870">10.2307/2296870</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2296870">2296870</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:7295776">7295776</a>. Archived from <a href="https://pdfs.semanticscholar.org/f66c/6beda52f00373ca04509fd9ad27e6763055f.pdf">the original</a> (PDF) on 2018-04-12.</li>
<li>D.H. Blair and R.A. Pollak (1982). "Acyclic Collective Choice Rules". Econometrica. 50 (4): 931–943. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F1912770">10.2307/1912770</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/1912770">1912770</a>.</li>
<li>Bossert, Walter; Suzumura, Kotaro (Apr 2005). <a href="http://faculty.arts.ubc.ca/pnorman/CETC/Papers/bossert.pdf">Rational Choice on Arbitrary Domains: A Comprehensive Treatment</a> (PDF) (Technical Report). Université de Montréal, Hitotsubashi University Tokyo.</li>
<li>Bossert, Walter; Suzumura, Kotaro (Mar 2009). <a href="https://web.archive.org/web/20180412082302/https://pdfs.semanticscholar.org/240e/97a4f812ff51317a68c7b72d0f1e84eb8266.pdf">"Quasi-transitive and Suzumura consistent relations"</a> (PDF). Social Choice and Welfare (Technical Report). 39 (2–3). Université de Montréal, Waseda University Tokyo: 323–334. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00355-011-0600-z">10.1007/s00355-011-0600-z</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:38375142">38375142</a>. Archived from <a href="https://pdfs.semanticscholar.org/240e/97a4f812ff51317a68c7b72d0f1e84eb8266.pdf">the original</a> (PDF) on 2018-04-12.</li>
<li>Bossert, Walter; Suzumura, Kōtarō (2010). Consistency, choice and rationality. Harvard University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0674052994.</li>
<li>Alan D. Miller and Shiran Rachmilevitch (Feb 2014). <a href="http://econ.haifa.ac.il/~admiller/ArrowWithoutTransitivity.pdf">Arrow's Theorem Without Transitivity</a> (PDF) (Working paper). University of Haifa.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Robert Duncan Luce (Apr 1956). "Semiorders and a Theory of Utility Discrimination" (PDF). Econometrica. 24 (2): 178–191. 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. <a href="/wiki/Robert_Duncan_Luce" target="_blank">/wiki/Robert_Duncan_Luce</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">The naming follows 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. - Bossert, Walter; Suzumura, Kotaro (Mar 2009). "Quasi-transitive and Suzumura consistent relations" (PDF). Social Choice and Welfare (Technical Report). 39 (2–3). Université de Montréal, Waseda University Tokyo: 323–334. doi:10.1007/s00355-011-0600-z. S2CID 38375142. Archived from the original (PDF) on 2018-04-12. <a href="https://web.archive.org/web/20180412082302/https://pdfs.semanticscholar.org/240e/97a4f812ff51317a68c7b72d0f1e84eb8266.pdf" target="_blank">https://web.archive.org/web/20180412082302/https://pdfs.semanticscholar.org/240e/97a4f812ff51317a68c7b72d0f1e84eb8266.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">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. <a href="/wiki/Equivalence_relation" target="_blank">/wiki/Equivalence_relation</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Given R, whenever xRy ∧ ¬yRx holds, the pair (x,y) can't belong to the symmetric part, but must belong to the transitive part. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Since the empty relation is trivially both transitive and symmetric. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">The antisymmetry of R forces J to be coreflexive; hence the union of J and the transitive P is again transitive. <a href="/wiki/Coreflexive_relation" target="_blank">/wiki/Coreflexive_relation</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Quasitransitive relation open-in-new

Quasitransitive relation