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“<ref>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).</ref> gilt.
Definition
Eine binäre Relation <math>R</math> auf einer Menge <math>X</math> heißt euklidisch (oder auch rechts-euklidisch), wenn für beliebige Elemente <math>a, b, c</math> in <math>X</math> die folgende Bedingung erfüllt ist: steht <math>a</math> zu <math>b</math> und <math>a</math> zu <math>c</math> in gleicher Beziehung, so steht auch <math>b</math> zu <math>c</math> in dieser Beziehung.<ref name="fagin">{{#invoke:Vorlage:Literatur|f}}</ref> Dies lässt sich auch prädikatenlogisch ausdrücken mit <math>\forall a, b, c \in X (aRb \land aRc \implies bRc)</math>.
Dual dazu heißt eine Relation <math>R</math> auf <math>X</math> links-euklidisch, wenn für beliebige <math>a, b, c</math> in <math>X</math> gilt: stehen sowohl <math>b</math> als auch <math>c</math> in Beziehung zu <math>a</math>, dann steht auch <math>b</math> in Beziehung zu <math>c</math>, formal <math>\forall a, b, c \in X (bRa \land cRa \implies bRc)</math>.
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,<ref>Da z. B. <math>0\le 2</math> und <math>0\le 1</math> gilt, aber nicht <math>2\le 1</math>.</ref> während die durch <math>xRy :\Leftrightarrow 0 \leq x \leq y+1 \leq 2</math> definierte Relation <math>R</math> auf den natürlichen Zahlen nicht transitiv,<ref>Da z. B. <math>2 R 1</math> und <math>1 R 0</math> gilt, aber nicht <math>2 R 0</math>.</ref> 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. <math>xRy</math> definiert durch <math>y</math>=0.
- Eine Relation, die sowohl rechts-euklidisch als auch reflexiv ist, ist notwendig auch symmetrisch und damit eine Äquivalenzrelation.<ref name="fagin" /><ref>Denn aus <math>xRy</math> und <math>xRx</math> folgt <math>yRx</math>.</ref> Ebenso ist jede links-euklidische und reflexive Relation notwendig eine Äquivalenz.
- Der Bildbereich einer rechts-euklidischen Relation ist stets eine Teilmenge<ref>Gleichheit von Urbild- und Bildbereich ist nicht notwendig: die Relation <math>xRy</math> definiert durch <math>y=\min\{ x,2\}</math> ist rechts-euklidisch auf den natürlichen Zahlen und ihr Bildbereich <math>\{0,1,2\}</math> ist eine echte Teilmenge ihres Urbildbereichs ℕ.</ref> ihres Urbildbereichs. Die Einschränkung einer rechts-euklidischen Relation auf ihren Bildbereich ist stets reflexiv<ref>Wenn <math>y</math> im Bildbereich von <math>R</math> liegt, dann folgt aus <math>xRy \land xRy</math> für geeignetes <math>x</math>, dass <math>yRy</math>. Dies zeigt auch, dass <math>y</math> im Urbildbereich von <math>R</math> liegt.</ref> 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 <math>R</math> ist links- und rechts-euklidisch genau dann, wenn ihr Urbild- und ihr Bildbereich übereinstimmen und <math>R</math> auf dieser Menge eine Äquivalenzrelation ist.<ref>Die "<math>\Rightarrow</math>"-Richtung folgt aus dem vorherigen Absatz. — Für die "<math>\Leftarrow</math>"-Richtung nimm an, dass <math>aRb</math> und <math>aRc</math> gelten, dann liegen <math>a, b, c</math> im Urbild- und im Bildbereich von <math>R</math>; also folgt <math>bRc</math> wegen Symmetrie und Transitivität. Die links-euklidische Eigenschaft von <math>R</math> folgt analog.</ref>
- Eine rechts-euklidische Relation ist stets quasitransitiv,<ref>Wenn <math>xRy \land \neg yRx \land yRz \land \neg zRy</math> gilt, dann liegen sowohl <math>y</math> als auch <math>z</math> im Bildbereich von <math>R</math>. Da <math>R</math> auf dieser Menge eine Äquivalenz ist, folgt aus <math>yRz</math> schon der Widerspruch <math>zRy</math>.</ref> ebenso eine links-euklidische Relation.<ref name="analog Urbild">Mit einem analogen Argument, das die Lage von <math>x</math> und <math>y</math> im Urbildbereich von <math>R</math> verwendet.</ref>
- Eine konnexe rechts-euklidische Relation ist stets auch transitiv,<ref>Wenn <math>xRy \land yRz</math> gilt, dann liegen <math>y</math> und <math>z</math> im Bildbereich von <math>R</math>. Da <math>R</math> konnex ist, gilt <math>xRz</math> oder <math>zRx</math> oder <math>x=z</math>.</ref> ebenso eine konnexe links-euklidische Relation.<ref name="analog Urbild" />
- Wenn <math>X</math> mindestens 3 Elemente hat, kann eine konnexe rechts-euklidische Relation <math>R</math> auf <math>X</math> nicht antisymmetrisch sein,<ref>Da <math>R</math> konnex ist, liegen in ihrem Bildbereich mindestens zwei verschiedene Elemente <math>x</math> und <math>y</math>, für die gilt <math>xRy \lor yRx</math>. Es gilt sogar <math>xRy \land yRx</math>. Dies widerspricht der Antisymmetrie.</ref> gleiches gilt für eine konnexe links-euklidische Relation auf <math>X</math>.<ref name="analog Urbild" /> Auf der zweielementigen Menge <math>X = \{ 0, 1 \}</math> ist z. B. die durch <math>xRy :\Leftrightarrow y=1</math> definierte Relation konnex, rechts-euklidisch und antisymmetrisch; <math>xRy :\Leftrightarrow x=1</math> ist auf dieser Menge konnex, links-euklidisch und antisymmetrisch.
Einzelnachweise und Anmerkungen
<references />