Quasitransitive Relation

Quasitransitivität ist eine abgeschwächte Version von Transitivität, die in der Sozialwahltheorie und der Mikroökonomie verwendet wird. Informell gesagt ist eine Relation quasitransitiv, wenn sie für einige Werte symmetrisch und anderswo transitiv ist. Das Konzept wurde 1969 von Amartya K. Sen eingeführt,^[1] um die Folgen des Arrow-Theorems zu untersuchen.

Beispiele

Ökonomische Präferenzen werden bei einigen Autoren als quasitransitiv (und nicht als transitiv) angesehen. Das klassische Beispiel ist eine Person, die unentschieden zwischen 7 und 8 Gramm Zucker ist und ebenso unentschieden zwischen 8 und 9 Gramm Zucker, die aber 9 Gramm Zucker gegenüber 7 bevorzugt.^[2] Ähnlich kann die Sorites-Paradoxie durch Abschwächung der angenommenen Transitivität bestimmter Relationen zu Quasitransitivität aufgelöst werden.

Formale Definition

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

aTb\wedge \neg bTa\wedge bTc\wedge \neg cTb\Rightarrow aTc\wedge \neg cTa

.

Wenn die Relation zusätzlich antisymmetrisch ist, ist T transitiv.

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

Eigenschaften

Eine Relation $R$ ist quasi-transitiv genau dann, wenn sie die disjunkte Vereinigung einer symmetrischen Relation $J$ und einer transitiven Relation $P$ ist.^[3] $J$ und $P$ sind durch $R$ nicht eindeutig bestimmt;^[4] allerdings ist das $P$ aus dem „ $\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 $A$ ist die universelle Relation $A\times A$ das kartesische Produkt sowohl zyklisch als auch quasitransitiv.

Literatur

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

Einzelnachweise

↑ Amartya K. Sen: Quasi-Transitivity, Rational Choice and Collective Decisions. In: The Review of Economic Studies. Band 36, 1969, S. 381–393.
↑ Robert Duncan Luce: Semiorders and a Theory of Utility Discrimination. In: Econometrica. Band 24, Nr. 2, April 1956, S. 178–191, hier S. 179 (uci.edu [PDF] Luces ursprüngliches Beispiel besteht aus 400 Vergleichen (von Kaffeetassen mit unterschiedlichen Zuckermengen) statt nur 2).
↑ Die Benennung folgt (Bossert, Suzumura 2009), S. 2–3. – " $\Rightarrow$ ": Definiere $xJy:\Leftrightarrow xRy\land yRx$ und $xPy:\Leftrightarrow xRy\land \lnot yRx$ , dann ist $J$ symmetrisch nach Konstruktion und die Transitivität von $P$ ist identisch mit der Definition der Quasitransitivität von $R$ . – " $\Leftarrow$ ": Sei $R$ die disjunkte Vereinigung aus symmetrischem $J$ und transitivem $P$ und gelte $xRy\land \lnot yRx\land yRz\land \lnot zRy$ , dann folgt $xPy$ und $yPz$ , da $xJy$ oder $yJz$ den Annahmen $\lnot yRx$ oder $\lnot zRy$ widersprechen würden. Daher folgt $xPz$ wegen Transitivität, $\lnot xJz$ wegen Disjunktheit, $\lnot zJx$ wegen Symmetrie. $zRx$ würde daher $zPx$ implizieren und wegen der Transitivität auch $zPy$ , was $\lnot zRy$ widerspricht. Insgesamt beweist dies $xRz\land \lnot zRx$ .
↑ 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.
↑ 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.
↑ Da die leere Relation trivialerweise sowohl transitiv als auch symmetrisch ist.
↑ 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.

[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, hier S. 179 (uci.edu [PDF] 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. – " $\Rightarrow$ ": Definiere $xJy:\Leftrightarrow xRy\land yRx$ und $xPy:\Leftrightarrow xRy\land \lnot yRx$ , dann ist $J$ symmetrisch nach Konstruktion und die Transitivität von $P$ ist identisch mit der Definition der Quasitransitivität von $R$ . – " $\Leftarrow$ ": Sei $R$ die disjunkte Vereinigung aus symmetrischem $J$ und transitivem $P$ und gelte $xRy\land \lnot yRx\land yRz\land \lnot zRy$ , dann folgt $xPy$ und $yPz$ , da $xJy$ oder $yJz$ den Annahmen $\lnot yRx$ oder $\lnot zRy$ widersprechen würden. Daher folgt $xPz$ wegen Transitivität, $\lnot xJz$ wegen Disjunktheit, $\lnot zJx$ wegen Symmetrie. $zRx$ würde daher $zPx$ implizieren und wegen der Transitivität auch $zPy$ , was $\lnot zRy$ widerspricht. Insgesamt beweist dies $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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]