Quasitransitive relation
From HandWiki
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:
- [math]\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). }[/math]
If the relation is also antisymmetric, T is transitive.
Alternately, for a relation T, define the asymmetric or "strict" part P:
- [math]\displaystyle{ (a\operatorname{P}b) \Leftrightarrow (a\operatorname{T}b) \wedge \neg(b\operatorname{T}a). }[/math]
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.
See also
References
- ↑ Robert Duncan Luce (Apr 1956). "Semiorders and a Theory of Utility Discrimination". Econometrica 24 (2): 178–191. doi:10.2307/1905751. https://www.imbs.uci.edu/files/personnel/luce/pre1990/1956/Luce_Econometrica_1956.pdf. Here: p.179; Luce's original example consists in 400 comparisons (of coffee cups with different amounts of sugar) rather than just 2.
- ↑ The naminig follows (Bossert Suzumura), 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.
- ↑ 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.
- ↑ Given R, whenever xRy ∧ ¬yRx holds, the pair (x,y) can't belong to the symmetric part, but must belong to the transitive part.
- ↑ Since the empty relation is trivially both transitive and symmetric.
- ↑ 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.
- Frederic Schick (Jun 1969). "Arrow's Proof and the Logic of Preference". Philosophy of Science 36 (2): 127–144. doi:10.1086/288241.
- Amartya K. Sen (1970). Collective Choice and Social Welfare. Holden-Day, Inc..
- Amartya K. Sen (Jul 1971). "Choice Functions and Revealed Preference". The Review of Economic Studies 38 (3): 307–317. doi:10.2307/2296384. https://www.ihs.ac.at/publications/eco/visit_profs/blume/sen.pdf.
- A. Mas-Colell and H. Sonnenschein (1972). "General Possibility Theorems for Group Decisions". The Review of Economic Studies 39 (2): 185–192. doi:10.2307/2296870. https://pdfs.semanticscholar.org/f66c/6beda52f00373ca04509fd9ad27e6763055f.pdf.
- D.H. Blair and R.A. Pollak (1982). "Acyclic Collective Choice Rules". Econometrica 50 (4): 931–943. doi:10.2307/1912770.
- Bossert, Walter; Suzumura, Kotaro (Apr 2005). Rational Choice on Arbitrary Domains: A Comprehensive Treatment (Technical Report). http://faculty.arts.ubc.ca/pnorman/CETC/Papers/bossert.pdf.
- Bossert, Walter; Suzumura, Kotaro (Mar 2009). Quasi-transitive and Suzumura consistent relations (Technical Report). doi:10.1007/s00355-011-0600-z. https://pdfs.semanticscholar.org/240e/97a4f812ff51317a68c7b72d0f1e84eb8266.pdf.
- 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 (Working paper). http://econ.haifa.ac.il/~admiller/ArrowWithoutTransitivity.pdf.
 |
