Quasitransitive_relation

Quasitransitive relation

Quasitransitive relation

Add article description

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.

The quasitransitive relation x≤5/4y. Its symmetric and transitive part is shown in blue and green, respectively.

Formal definition

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

If the relation is also antisymmetric, T is transitive.

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

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

  1. [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.
  2. [2]
    The naminig 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. [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. [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. [5]
    Since the empty relation is trivially both transitive and symmetric.
  6. [6]
    The antisymmetry of R forces J to be coreflexive; hence the union of J and the transitive P is again transitive.
Share this article:

This article uses material from the Wikipedia article Quasitransitive_relation, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.