Relationen
Definition (Relation)
Eine Menge R heißt eine (zweistellige) Relation, falls jedes Element von R ein geordnetes Paar ist. Gilt R ⊆ A2 für eine Relation R und eine Menge A, so heißt R eine Relation auf der Menge A.
Notation
Statt (a, b) ∈ R schreiben wir oft a R b.
Diese sogenannte Infix-Notation entspricht der vertrauten Form a ≤ b für die Relation „kleiner oder gleich“ auf den reellen Zahlen.
Beispiele
(1) | Die Menge R = { (1, 1), (1, 2), (1, 3), (2, 1), (3, 2) } ist eine Relation auf der Menge A = { 1, 2, 3 }. Es gilt 1 R 1, 1 R 2, 1 R 3, 2 R 1, 3 R 2, nicht(3 R 1), nicht(2 R 2) usw. |
(2) | Die Relation ≤ auf der Menge { 1, 2, 3 } lautet: ≤ = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) }. Sie hat genau 6 Elemente. Die Relation < auf { 1, 2, 3 } hat dagegen nur drei Elemente. Es gilt < = { (1, 2), (1, 3), (2, 3) }. |
(3) | Sei A eine Menge. Dann definiert der Teilmengenbegriff eine Relation auf der Potenzmenge von A, die sogenannte Inklusion auf ℘(A). Wir bezeichnen sie wieder mit ⊆. Für A = { 1, 2, 3, 4, 5, 6 } gilt zum Beispiel { } ⊆ { 1 }, { 1, 2, 4 } ⊆ { 1, 2, 3, 4, 5 }, B ⊆ { 1, …, 6 } für alle B ⊆ A. |
Wir betrachten fünf grundlegende Eigenschaften einer Relation:
Definition (Eigenschaften von Relationen)
Sei R eine Relation auf A. Dann heißt R
| reflexiv (auf A), | falls | ∀a ∈ A a R a |
| irreflexiv, | falls | ∀a ∈ A ¬ (a R a) |
| symmetrisch, | falls | ∀a, b ∈ A (a R b → b R a) |
| antisymmetrisch, | falls | ∀a, b ∈ A (a R b ∧ b R a → a = b) |
| transitiv, | falls | ∀a, b, c ∈ A (a R b ∧ b R c → a R c) |
Kettennotation
Ist R transitiv, so schreiben wir auch a R b R c statt a R b und b R c. Allgemeiner verwenden wir endliche Ketten der Form a1 R a2 R … R an.
Beispiele
(1) | Die Relation ≤ auf den natürlichen Zahlen ist reflexiv, antisymmetrisch und transitiv. Das Gleiche gilt für die Inklusion ⊆ der Potenzmenge der natürlichen Zahlen. Es gilt ∅ ⊆ { 1 } ⊆ { 1, 4 } ⊆ { 1, 2, 4, 6 }. |
(2) | Sei m eine natürliche Zahl größergleich 1. Zwei ganze Zahlen a, b heißen kongruent modulo m, falls a − b durch m teilbar ist. In Zeichen schreiben wir a ≡ m b oder a ≡ b mod(m). Es gilt zum Beispiel 6 ≡ 5 11 und 4 ≡ 3 − 2. Die Kongruenz modulo m ist reflexiv, symmetrisch und transitiv. In Kettennotation gilt etwa −5 ≡ −2 ≡ 1 ≡ 4 ≡ 7 mod(3). |
Eine Relation R auf einer nichtleeren endlichen Menge A können wir durch einen Graphen visualisieren: Wir zeichnen die Elemente von A als benannte Punkte und die Elemente von R als Pfeile zwischen den Punkten. Das Paar (A, R) heißt ein gerichteter Graph. Jedes Element von A nennen wir eine Ecke und jedes Element von R eine gerichtete Kante des Graphen.
Darstellung der Relation
R = { (1, 1), (1, 2), (2, 3), (3, 2), (3, 4), (4, 5), (5, 3), (5, 4) }
auf A = { 1, 2, 3, 4, 5 } als gerichteter Graph.
Anschauliche Beschreibung der fünf Grundeigenschaften
reflexiv: Jede Ecke hat eine Schlinge (einen Pfeil von sich zu sich selbst).
irreflexiv: Der Graph hat keine Schlingen.
symmetrisch: Pfeile treten stets als Doppelpfeile in beiden Richtungen auf. Derartige Doppelpfeile werden der Übersichtlichkeit halber oft durch eine Linie (ungerichtete Kante) ersetzt.
antisymmetrisch: Doppelpfeile gibt es nur als Schlingen. Es kann Schlingen geben oder nicht.
transitiv: Jede Pfeilfolge entspricht einem Pfeil.