Quasitransitive relation

The mathematical notion of quasitransitivity is a weakened version of transitivity that is used in social choice theory and microeconomics. Informally, a relation is quasitransitive if it is symmetric for some values and transitive elsewhere. The concept was introduced by Sen (1969) to study the consequences of Arrow's theorem.

Formal definition

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

(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 antisymmetric, T is transitive.

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

(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.

Examples

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.^[1] Similarly, the Sorites paradox can be resolved by weakening assumed transitivity of certain relations to quasitransitivity.

Properties

A relation R is quasitransitive if, and only if, it is the disjoint union of a symmetric relation J and a transitive relation P.^[2] J and P are not uniquely determined by a given R;^[3] however, the P from the only-if part is minimal.^[4]
As a consequence, each symmetric relation is quasitransitive, and so is each transitive relation.^[5] Moreover, an antisymmetric and quasitransitive relation is always transitive.^[6]
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.

References

[1]
Robert Duncan Luce (Apr 1956). "Semiorders and a Theory of Utility Discrimination". 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.
[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.
[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.
[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.
[5]
Since the empty relation is trivially both transitive and symmetric.
[6]
The antisymmetry of R forces J to be coreflexive; hence the union of J and the transitive P is again transitive.

Sen, A. (1969). "Quasi-transitivity, rational choice and collective decisions". Rev. Econ. Stud. 36 (3): 381–393. doi:10.2307/2296434. JSTOR 2296434. Zbl 0181.47302.
Frederic Schick (Jun 1969). "Arrow's Proof and the Logic of Preference". Philosophy of Science. 36 (2): 127–144. doi:10.1086/288241. JSTOR 186166. S2CID 121427121.
Amartya K. Sen (1970). Collective Choice and Social Welfare. Holden-Day, Inc.
Amartya K. Sen (Jul 1971). "Choice Functions and Revealed Preference" (PDF). The Review of Economic Studies. 38 (3): 307–317. doi:10.2307/2296384. JSTOR 2296384. Archived from the original (PDF) on 2016-09-10. Retrieved 2018-04-11.
A. Mas-Colell and H. Sonnenschein (1972). "General Possibility Theorems for Group Decisions" (PDF). The Review of Economic Studies. 39 (2): 185–192. doi:10.2307/2296870. JSTOR 2296870. S2CID 7295776. Archived from the original (PDF) on 2018-04-12.
D.H. Blair and R.A. Pollak (1982). "Acyclic Collective Choice Rules". Econometrica. 50 (4): 931–943. doi:10.2307/1912770. JSTOR 1912770.
Bossert, Walter; Suzumura, Kotaro (Apr 2005). Rational Choice on Arbitrary Domains: A Comprehensive Treatment (PDF) (Technical Report). Université de Montréal, Hitotsubashi University Tokyo. Archived from the original (PDF) on 2018-04-12. Retrieved 2018-04-11.
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.
Bossert, Walter; Suzumura, Kōtarō (2010). Consistency, choice and rationality. Harvard University Press. ISBN 978-0674052994.
Alan D. Miller and Shiran Rachmilevitch (Feb 2014). Arrow's Theorem Without Transitivity (PDF) (Working paper). University of Haifa.

Quasitransitive relation

Formal definition

Examples

Properties

See also

References

Related Articles

Timelines

Top Qs

Fact Checks