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:

a T b \land \neg b T a \land b T c \land \neg c T b \Rightarrow a T c \land \neg c T a

.

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

Eine alternative Definition verwendet den asymmetrischen oder „strengen“ Teil $P$ von $T$ , definiert durch $a P b \Leftrightarrow a T b \land \neg b T a$ ; 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

Einzelnachweise

↑ Vorlage:Literatur
↑ Vorlage:Literatur
↑ Die Benennung folgt (Bossert, Suzumura 2009), S. 2–3. – " $\Rightarrow$ ": Definiere $x J y : \Leftrightarrow x R y \land y R x$ und $x P y : \Leftrightarrow x R y \land \neg y R x$ , 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 $x R y \land \neg y R x \land y R z \land \neg z R y$ , dann folgt $x P y$ und $y P z$ , da $x J y$ oder $y J z$ den Annahmen $\neg y R x$ oder $\neg z R y$ widersprechen würden. Daher folgt $x P z$ wegen Transitivität, $\neg x J z$ wegen Disjunktheit, $\neg z J x$ wegen Symmetrie. $z R x$ würde daher $z P x$ implizieren und wegen der Transitivität auch $z P y$ , was $\neg z R y$ widerspricht. Insgesamt beweist dies $x R z \land \neg z R x$ .
↑ 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] Vorlage:Literatur

[2] Vorlage:Literatur

[3] Die Benennung folgt (Bossert, Suzumura 2009), S. 2–3. – " $\Rightarrow$ ": Definiere $x J y : \Leftrightarrow x R y \land y R x$ und $x P y : \Leftrightarrow x R y \land \neg y R x$ , 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 $x R y \land \neg y R x \land y R z \land \neg z R y$ , dann folgt $x P y$ und $y P z$ , da $x J y$ oder $y J z$ den Annahmen $\neg y R x$ oder $\neg z R y$ widersprechen würden. Daher folgt $x P z$ wegen Transitivität, $\neg x J z$ wegen Disjunktheit, $\neg z J x$ wegen Symmetrie. $z R x$ würde daher $z P x$ implizieren und wegen der Transitivität auch $z P y$ , was $\neg z R y$ widerspricht. Insgesamt beweist dies $x R z \land \neg z R x$ .

[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]

Quasitransitive Relation

Inhaltsverzeichnis

Beispiele

Formale Definition

Eigenschaften

Literatur

Einzelnachweise

Navigationsmenü

Quasitransitive Relation

Beispiele

Formale Definition

Eigenschaften

Literatur

Einzelnachweise

Navigationsmenü

Suche