Euklidische Relation

Eine euklidische Relation ist in der Mathematik eine binäre Relation, für die Euklids Axiom „Was demselben gleich ist, ist auch einander gleich“^[1] gilt.

Definition

Eine binäre Relation ${\displaystyle R}$ auf einer Menge ${\displaystyle X}$ heißt euklidisch (oder auch rechts-euklidisch), wenn für beliebige Elemente ${\displaystyle a,b,c}$ in ${\displaystyle X}$ die folgende Bedingung erfüllt ist: steht ${\displaystyle a}$ zu ${\displaystyle b}$ und ${\displaystyle a}$ zu ${\displaystyle c}$ in gleicher Beziehung, so steht auch ${\displaystyle b}$ zu ${\displaystyle c}$ in dieser Beziehung.^[2] Dies lässt sich auch prädikatenlogisch ausdrücken mit ${\displaystyle \forall a,b,c\in X(aRb\land aRc\implies bRc)}$.

Dual dazu heißt eine Relation ${\displaystyle R}$ auf ${\displaystyle X}$ links-euklidisch, wenn für beliebige ${\displaystyle a,b,c}$ in ${\displaystyle X}$ gilt: stehen sowohl ${\displaystyle b}$ als auch ${\displaystyle c}$ in Beziehung zu ${\displaystyle a}$, dann steht auch ${\displaystyle b}$ in Beziehung zu ${\displaystyle c}$, formal ${\displaystyle \forall a,b,c\in X(bRa\land cRa\implies bRc)}$.

Eigenschaften

• Die Eigenschaft euklidisch zu sein unterscheidet sich von der Transitivität. Zum Beispiel ist die Relation ≤ auf den natürlichen Zahlen transitiv, doch nicht rechts-euklidisch,^[3] während die durch ${\displaystyle xRy:\Leftrightarrow 0\leq x\leq y+1\leq 2}$ definierte Relation ${\displaystyle R}$ auf den natürlichen Zahlen nicht transitiv,^[4] jedoch rechts-euklidisch ist.

• Für eine symmetrische Relation sind die Eigenschaften Transitivität, rechts- und links-euklidisch koinzident. Doch kann auch eine nicht-symmetrische Relation sowohl transitiv als auch rechts-euklidisch sein, z. B. ${\displaystyle xRy}$ definiert durch ${\displaystyle y}$=0.

• Eine Relation, die sowohl rechts-euklidisch als auch reflexiv ist, ist notwendig auch symmetrisch und damit eine Äquivalenzrelation.^[2][5] Ebenso ist jede links-euklidische und reflexive Relation notwendig eine Äquivalenz.

• Der Bildbereich einer rechts-euklidischen Relation ist stets eine Teilmenge^[6] ihres Urbildbereichs. Die Einschränkung einer rechts-euklidischen Relation auf ihren Bildbereich ist stets reflexiv^[7] und somit eine Äquivalenzrelation. Ebenso ist der Urbildbereich einer links-euklidischen Relation stets eine Teilmenge ihres Bildbereichs, und die Beschränkung einer links-euklidischen Relation auf ihren Urbildbereich eine Äquivalenz.

• Eine Relation ${\displaystyle R}$ ist links- und rechts-euklidisch genau dann, wenn ihr Urbild- und ihr Bildbereich übereinstimmen und ${\displaystyle R}$ auf dieser Menge eine Äquivalenzrelation ist.^[8]

• Eine rechts-euklidische Relation ist stets quasitransitiv,^[9] ebenso eine links-euklidische Relation.^[10]

• Eine konnexe rechts-euklidische Relation ist stets auch transitiv,^[11] ebenso eine konnexe links-euklidische Relation.^[10]

• Wenn ${\displaystyle X}$ mindestens 3 Elemente hat, kann eine konnexe rechts-euklidische Relation ${\displaystyle R}$ auf ${\displaystyle X}$ nicht antisymmetrisch sein,^[12] gleiches gilt für eine konnexe links-euklidische Relation auf ${\displaystyle X}$.^[10] Auf der zweielementigen Menge ${\displaystyle X=\{0,1\}}$ ist z. B. die durch ${\displaystyle xRy:\Leftrightarrow y=1}$ definierte Relation konnex, rechts-euklidisch und antisymmetrisch; ${\displaystyle xRy:\Leftrightarrow x=1}$ ist auf dieser Menge konnex, links-euklidisch und antisymmetrisch.

Einzelnachweise und Anmerkungen

1. ↑ Das Buch I der Elemente von Euklid enthält einleitend eine axiomatische Grundlegung, in der dieser Grundsatz als 1. Axiom allgemeiner Regeln der Gleichheit aufgeführt ist („Τὰ τῷ αὐτῷ ἴσα καὶ ἀλλήλοις ἐστὶν ἴσα“); siehe hierzu W.-D. Geyer: Euklid: Die Elemente – eine Übersicht. Vorlesung über antike Mathematik, SS 2001, S. 3 (PDF; 275 kB).
2. ↑ ^{a b} Ronald Fagin: Reasoning About Knowledge. MIT Press, 2003, ISBN 978-0-262-56200-3, S. 60 (englisch, eingeschränkte Vorschau in der Google-Buchsuche). 
3. ↑ Da z. B. ${\displaystyle 0\leq 2}$ und ${\displaystyle 0\leq 1}$ gilt, aber nicht ${\displaystyle 2\leq 1}$.
4. ↑ Da z. B. ${\displaystyle 2R1}$ und ${\displaystyle 1R0}$ gilt, aber nicht ${\displaystyle 2R0}$.
5. ↑ Denn aus ${\displaystyle xRy}$ und ${\displaystyle xRx}$ folgt ${\displaystyle yRx}$.
6. ↑ Gleichheit von Urbild- und Bildbereich ist nicht notwendig: die Relation ${\displaystyle xRy}$ definiert durch ${\displaystyle y=\min\{x,2\}}$ ist rechts-euklidisch auf den natürlichen Zahlen und ihr Bildbereich ${\displaystyle \{0,1,2\}}$ ist eine echte Teilmenge ihres Urbildbereichs ℕ.
7. ↑ Wenn ${\displaystyle y}$ im Bildbereich von ${\displaystyle R}$ liegt, dann folgt aus ${\displaystyle xRy\land xRy}$ für geeignetes ${\displaystyle x}$, dass ${\displaystyle yRy}$. Dies zeigt auch, dass ${\displaystyle y}$ im Urbildbereich von ${\displaystyle R}$ liegt.
8. ↑ Die "${\displaystyle \Rightarrow }$"-Richtung folgt aus dem vorherigen Absatz. — Für die "${\displaystyle \Leftarrow }$"-Richtung nimm an, dass ${\displaystyle aRb}$ und ${\displaystyle aRc}$ gelten, dann liegen ${\displaystyle a,b,c}$ im Urbild- und im Bildbereich von ${\displaystyle R}$; also folgt ${\displaystyle bRc}$ wegen Symmetrie und Transitivität. Die links-euklidische Eigenschaft von ${\displaystyle R}$ folgt analog.
9. ↑ Wenn ${\displaystyle xRy\land \neg yRx\land yRz\land \neg zRy}$ gilt, dann liegen sowohl ${\displaystyle y}$ als auch ${\displaystyle z}$ im Bildbereich von ${\displaystyle R}$. Da ${\displaystyle R}$ auf dieser Menge eine Äquivalenz ist, folgt aus ${\displaystyle yRz}$ schon der Widerspruch ${\displaystyle zRy}$.
10. ↑ ^{a b c} Mit einem analogen Argument, das die Lage von ${\displaystyle x}$ und ${\displaystyle y}$ im Urbildbereich von ${\displaystyle R}$ verwendet.
11. ↑ Wenn ${\displaystyle xRy\land yRz}$ gilt, dann liegen ${\displaystyle y}$ und ${\displaystyle z}$ im Bildbereich von ${\displaystyle R}$. Da ${\displaystyle R}$ konnex ist, gilt ${\displaystyle xRz}$ oder ${\displaystyle zRx}$ oder ${\displaystyle x=z}$.
12. ↑ Da ${\displaystyle R}$ konnex ist, liegen in ihrem Bildbereich mindestens zwei verschiedene Elemente ${\displaystyle x}$ und ${\displaystyle y}$, für die gilt ${\displaystyle xRy\lor yRx}$. Es gilt sogar ${\displaystyle xRy\land yRx}$. Dies widerspricht der Antisymmetrie.