1.3 Relationen
Definition (Relation)
(a) | Eine Menge R heißt eine (zweistellige) Relation, falls jedes Element von R ein geordnetes Paar ist. Gilt (x, y) ∈ R, so schreiben wir auch x R y. |
(b) | Gilt R ⊆ M × M, so nennen wir R eine Relation auf der Menge M. |
Eine Relation R auf { 1, 2, 3, 4 }. Es gilt
1 R 1, 1 R 2, 2 R 1, 2 R 4, 3 R 2, 4 R 3.
Relationen tauchen in der Mathematik in so vielen Formen auf, dass eine sehr allgemeine Definition angemessen ist. Obige Definition versucht gar nicht, die möglichen Beziehungen wie „größer“, „kleiner“, „äquivalent“, „umfassender“ oder „verwandt“, die zwischen zwei Objekten bestehen können, in ihrem Wesen zu beschreiben, sondern sie fängt alle möglichen Beziehungen durch eine einfache Struktureigenschaft ein. Dass x in einer bestimmten Relation R zu y steht, wird einfach durch (x, y) ∈ R ausgedrückt.
Statt R wird oft ein Symbol wie ≤, <, ≡ , ∼ verwendet. Dann wird die zu „(x, y) ∈ R“ gleichwertige Notation „x R y“ zur vertrauten Schreibweise
x ≤ y, x < y, x ≡ y, x ∼ y.
Neu und oft schwierig für Anfänger ist, dass eine Relation als eine Menge aufgefasst wird, die beliebig bezeichnet werden kann.
Beispiele
(1) | Für alle a, b ∈ ℤ setzen wir: a | b, falls a ein Teiler von b ist, d. h. falls ein d ∈ ℤ existiert mit a d = b. Dann gilt z. B. 4|4, 4|−8, 10|100, −3|9, 0|0, 4|0. |
(2) | Sei m ∈ ℕ*. Dann setzen wir für alle a, b ∈ ℤ: a ≡ m b, falls m|(a − b). (Kongruenz modulo m) Es gilt a ≡ m b, falls a und b bei Division durch m den gleichen Rest haben. So ist etwa 2 ≡ 7 9 ≡ 7 − 5 und { a ∈ ℤ | a ≡ 7 5 } = { …, −9, −2, 5, 12, 19, … }. |
Die obige Relation R in Pfeildarstellung.
In der diskreten Mathematik spricht man
von einem gerichteten Graphen.
Eine Relation R lässt sich manchmal durch Pfeildiagramme veranschaulichen. Wir verbinden alle x, y mit x R y durch einen Pfeil von x nach y. Gilt x R x, so führt ein Pfeil von x zu sich selbst. Gilt x R y und y R x, so sind x und y durch zwei Pfeile verbunden. Man kann dies graphisch vereinfachen, indem man x und y durch eine Linie verbindet. Die „x-y-Straße“ ist dann in beiden Richtungen befahrbar.
Für eine Relation R auf ℝ bietet sich eine andere Visualisierung an: Wir markieren alle Punkte (x, y) der Ebene, für die x R y gilt. R erscheint dann als eine Punktwolke der Ebene.
noch einmal obige Relation R
R = { (x, y) ∈ A | 1 ≤ x2 − y3 ≤ 3 }
R = { (x, y) ∈ A | 1/2 ≤ cos(x) + y2 ≤ 2 }
Wir stellen Eigenschaften von Relationen tabellarisch zusammen.
Eine Relation R auf M heißt … | falls … |
reflexiv | für alle x ∈ M gilt x R x |
irreflexiv | für kein x ∈ M gilt x R x |
symmetrisch | für alle x, y ∈ M gilt: x R y impliziert y R x |
antisymmetrisch | für alle x, y ∈ M gilt: x R y und y R x impliziert x = y |
transitiv | für alle x, y, z ∈ M gilt: x R y und y R z impliziert x R z |
„Reflexiv“ bedeutet für Pfeildiagramme, dass von jedem x ein Pfeil zu x führt, sowie für Punktwolken, dass die Diagonale zur Punktwolke gehört. „Symmetrisch“ bedeutet für Pfeildiagramme, dass Pfeile zwischen zwei Punkten stets in beiden Richtungen verlaufen (und also durch Linien ersetzt werden können), sowie für Punktwolken, dass die Spiegelung an der Diagonale { (x, x) | x ∈ ℝ } die Punktwolke unverändert lässt.
Beispiele
(1) | Die Teilbarkeitsrelation | auf ℤ ist reflexiv und transitiv. Sie ist nicht antisymmetrisch, da z. B. −3|3 und 3|−3, aber 3 ≠ −3 gilt. |
(2) | Für jedes m ∈ ℕ* ist die Kongruenz ≡ m modulo m reflexiv, symmetrisch und transitiv. (Relationen mit diesen drei Eigenschaften heißen Äquivalenzrelationen.) |
(3) | Die Relationen ≤ und ≥ auf ℝ sind reflexiv, antisymmetrisch und transitiv, die Relationen < und > auf ℝ sind irreflexiv und transitiv. Die Gleichheit = auf ℝ ist reflexiv, symmetrisch und transitiv. |
Für alle reellen Zahlen x ≥ 0 gilt zum Beispiel:
7/8 x ≤ 2 x < 1 + 2 x ≤ 1 + 2 x + x2 = (1 + x)2.
Die Abschätzungskette zeigt, dass 7/8 x < (1 + x)2 für alle x ≥ 0 gilt.