Quasitransitive Relation

Quasitransitivität i​st eine abgeschwächte Version v​on Transitivität, d​ie in d​er Sozialwahltheorie u​nd der Mikroökonomie verwendet wird. Informell gesagt i​st eine Relation quasitransitiv, w​enn sie für einige Werte symmetrisch u​nd anderswo transitiv ist. Das Konzept w​urde 1969 v​on Amartya K. Sen eingeführt,[1] u​m die Folgen d​es Arrow-Theorems z​u untersuchen.

Die quasitransitive Relation ${\displaystyle x\leq {\frac {5}{4}}y}$. Ihr symmetrischer Teil ist in blau, ihr transitiver in grün dargestellt.

Beispiele

Ökonomische Präferenzen werden b​ei einigen Autoren a​ls quasitransitiv (und n​icht als transitiv) angesehen. Das klassische Beispiel i​st eine Person, d​ie unentschieden zwischen 7 u​nd 8 Gramm Zucker i​st und ebenso unentschieden zwischen 8 u​nd 9 Gramm Zucker, d​ie aber 9 Gramm Zucker gegenüber 7 bevorzugt.[2] Ähnlich k​ann die Sorites-Paradoxie d​urch Abschwächung d​er angenommenen Transitivität bestimmter Relationen z​u Quasitransitivität aufgelöst werden.

Formale Definition

Eine zweistellige Relation ${\displaystyle T}$ über einer Menge ${\displaystyle X}$ ist quasitransitiv, wenn für alle ${\displaystyle a,b,c\in X}$ gilt:

${\displaystyle aTb\wedge \neg bTa\wedge bTc\wedge \neg cTb\Rightarrow aTc\wedge \neg cTa}$.

Wenn d​ie Relation zusätzlich antisymmetrisch ist, i​st T transitiv.

Eine alternative Definition verwendet den asymmetrischen oder „strengen“ Teil ${\displaystyle P}$ von ${\displaystyle T}$, definiert durch ${\displaystyle aPb\Leftrightarrow aTb\wedge \neg bTa}$; damit ist ${\displaystyle T}$ quasitransitiv genau dann, wenn ${\displaystyle P}$ transitiv ist.

Eigenschaften

• Eine Relation ${\displaystyle R}$ ist quasi-transitiv genau dann, wenn sie die disjunkte Vereinigung einer symmetrischen Relation ${\displaystyle J}$ und einer transitiven Relation ${\displaystyle P}$ ist.[3] ${\displaystyle J}$ und ${\displaystyle P}$ sind durch ${\displaystyle R}$ nicht eindeutig bestimmt;[4] allerdings ist das ${\displaystyle P}$ aus dem „${\displaystyle \Rightarrow }$“-Beweisteil minimal.[5]

• Infolgedessen ist jede symmetrische Relation quasi-transitiv, ebenso wie jede transitive Relation.[6] Darüber hinaus ist eine antisymmetrische und quasi-transitive Relation immer auch transitiv.[7]

• Die Relation {(7,7), (7,8), (7,9), (8,7), (8,8), (8,9), (9,8), (9,9)} aus dem obigen Zucker-Beispiel ist quasi-transitiv, aber nicht transitiv.

• Eine quasitransitive Relation muss keinem azyklischen Graphen entsprechen: Für jede nicht leere Menge ${\displaystyle A}$ ist die universelle Relation ${\displaystyle A\times A}$ das kartesische Produkt sowohl zyklisch als auch quasitransitiv.

Referenzen

1. Amartya K. Sen: Quasi-Transitivity, Rational Choice and Collective Decisions. In: The Review of Economic Studies. Band 36, 1969, S. 381–393.
2. Robert Duncan Luce: Semiorders and a Theory of Utility Discrimination. In: Econometrica. Band 24, Nr. 2, April 1956, S. 178–191 (online [PDF]). Hier: S. 179; Luces ursprüngliches Beispiel besteht aus 400 Vergleichen (von Kaffeetassen mit unterschiedlichen Zuckermengen) statt nur 2.
3. Die Benennung folgt (Bossert, Suzumura 2009), S. 2–3. – "${\displaystyle \Rightarrow }$": Definiere ${\displaystyle xJy:\Leftrightarrow xRy\land yRx}$ und ${\displaystyle xPy:\Leftrightarrow xRy\land \lnot yRx}$, dann ist ${\displaystyle J}$ symmetrisch nach Konstruktion und die Transitivität von ${\displaystyle P}$ ist identisch mit der Definition der Quasitransitivität von ${\displaystyle R}$. – "${\displaystyle \Leftarrow }$": Sei ${\displaystyle R}$ die disjunkte Vereinigung aus symmetrischem ${\displaystyle J}$ und transitivem ${\displaystyle P}$ und gelte ${\displaystyle xRy\land \lnot yRx\land yRz\land \lnot zRy}$, dann folgt ${\displaystyle xPy}$ und ${\displaystyle yPz}$, da ${\displaystyle xJy}$ oder ${\displaystyle yJz}$ den Annahmen ${\displaystyle \lnot yRx}$ oder ${\displaystyle \lnot zRy}$ widersprechen würden. Daher folgt ${\displaystyle xPz}$ wegen Transitivität, ${\displaystyle \lnot xJz}$ wegen Disjunktheit, ${\displaystyle \lnot zJx}$ wegen Symmetrie. ${\displaystyle zRx}$ würde daher ${\displaystyle zPx}$ implizieren und wegen der Transitivität auch ${\displaystyle zPy}$, was ${\displaystyle \lnot zRy}$ widerspricht. Insgesamt beweist dies ${\displaystyle xRz\land \lnot zRx}$.
4. Wenn R z. B. eine Äquivalenzrelation ist, kann J als die leere Relation oder als R selbst und P jeweils als Komplement R\J gewählt werden.
5. Wenn xRy ∧ ¬yRx für ein gegebenes R gilt, kann das Paar (x,y) nicht zum symmetrischen Teil gehören, es muss daher in jedem Fall zum transitiven Teil gehören.
6. Da die leere Relation trivialerweise sowohl transitiv als auch symmetrisch ist.
7. Die Antisymmetrie von R macht die Koreflexivität^(en) von J notwendig, daher ist die Vereinigung von J und dem transitiven Teil P wieder transitiv.

• Frederic Schick: Arrow's Proof and the Logic of Preference. In: Philosophy of Science. Band 36, Nr. 2, Juni 1969, S. 127–144, JSTOR:186166 (englisch).
• Walter Bossert, Kotaro Suzumura: Quasi-transitive and Suzumura consistent relations. März 2009 (englisch, Technischer Bericht [PDF] Université de Montréal, Waseda University Tokyo).