Quasitransitive relation

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. 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. J and P are not uniquely determined by a given R; however, the P from the only-if part is minimal.
• As a consequence, each symmetric relation is quasitransitive, and so is each transitive relation. Moreover, an antisymmetric and quasitransitive relation is always 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.

References

References

1. Robert Duncan Luce. (Apr 1956). "Semiorders and a Theory of Utility Discrimination". Econometrica.
2. The naming 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''.
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 relation. coreflexive]]; hence the union of ''J'' and the transitive ''P'' is again transitive.