6.4. Relationen#
6.4.1. Das Kartesisches Produkt#
Bevor wir Relationen besprechen können benötigen wir noch die Definition des kartesischen Produkts. Es ist eine Operation, welche aus zwei Mengen \(A\) und \(B\) eine neue Menge erzeugt. Dabei wird jedes Element aus \(A\) mit jedem Element aus \(B\) kombiniert. Es wird auch als das sog. Mengenprodukt bezeichnet.
Kartesische Produkt
Das kartesische Produkt \(A \times B\) zweier Mengen \(A\) und \(B\) ist definiert als die Menge aller (geordneter) Paare (2-Tupel) \((a,b)\), wobei \(a\) ein Element aus \(A\) und \(b\) ein Element aus \(B\) ist:
\(\{1,2,3\} \times \{1.2,3.5\} = \{(1,1.2), (1,3.5), (2,1.2), (2,3.5), (3,1.2), (3,3.5)\}\)
\(\mathbb{N} \times \{1,2,3\} = \{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), \ldots \}\)
\(\{1,2,3\} \times \emptyset = \emptyset\)
\(\{\emptyset\} \times \{1,2,3\} = \{(\emptyset, 1), (\emptyset, 2), (\emptyset, 3)\}\)
Exercise 6.1 (Anzahl der Elemente)
Seien die endlichen Mengen \(A\) und \(B\) gegeben und sei \(|A| = m\) und \(|B| = n\). Wie viele Elemente enthält die Menge \(A \times B\)?
Solution to Exercise 6.1 (Anzahl der Elemente)
Es gilt \(|A \times B| = n \cdot m\).
6.4.2. Die Relation#
Eine Relation ist nichts anderes als eine Teilmenge eines kartesischen Produkts.
Relation (Beziehung)
Eine Relation \(R \subseteq A \times B\) ist eine Menge aus (geordneten) Paaren \((a, b) \in R\) mit \(a \in A\) und \(b \in B\), wobei \(A\) und \(B\) Mengen sind.
Stammen die Elemente einer Relation \(R\) aus den Mengen \(A\) und \(B\) so gilt:
Anstatt \((a,b) \in R\) schreibt man auch \(a R b\).
6.4.3. Die Ordnungsrelation#
Eine wichtige Relationen, die uns in der Praxis begegnen wird ist die sog. Ordnungsrelation. Für diese schreibt man anstatt \((a,b) \in R\) auch \(a \leq_R b\) oder \(a \leq b\), falls aus dem Kontext hervorgeht, welche Relation \(R\) gemeint ist.
(Totale) Ordnungsrelation
Eine Ordnungsrelation \(R \subset M \times M\) auf einer Menge \(M\) ist eine Relation mit folgenden Eigenschaften:
Reflexivität: \(\forall a \in M : a \leq_R a\)
Antisymmetrie: \(\forall a, b \in M : a \leq_R b \land b \leq_R a \Rightarrow a = b\)
Transitivität: \(\forall a, b, c \in M : a \leq_R b \in R \land b \leq_R c \Rightarrow a \leq_R c\)
Eine Ordnungsrelation ist total wenn für alle \(a,b \in M\) \(a \leq_R b\) oder \(b \leq_R a\) gilt.
Totale Ordnung
Die kleiner-gleich-Relation \(\leq\) auf den natürlichen Zahlen ist eine totale Ordnung.
Die Ordnungsrelation verallgemeinert / abstrahiert das Konzept des Ordnens von numerischen Werten. Immer dann wenn wir Dinge sortieren wollen, machen wir dies anhand einer Ordnungsrelation (siehe Karten sortieren).