Relationen

Seien A,BA,B Mengen. Dann ist jede Teilmenge RR von A×BA\times B eine Relation. Hierbei ist

A×BA\times B das kartesische Produkt der Mengen AA und BB. Die Relation RR besteht also aus einer Menge geordneter Paare (a,b)(a,b), wobei aAa\in A und bBb\in B ist. Eine Teilmenge von A×AA\times A wird Relation auf A genannt.

                           

Weiter werden nun einige wichtige Klassen von Relationen aufgeführt.

Äquivalenzrelation

Eine Relation RR auf einer Menge AA ist eine Äquivalenzrelation, wenn sie folgende Bedingungen erfüllt:

Bezeichnung

Definition

Erklärung

Reflexivität

Für alle aAa\in A ist (a,a)R(a,a) \in R

Alle Elemente von AA stehen zu sich selbst in Relation.

Symmetrie

Für alle a,bAa,b\in A, für die (a,b)R(a,b)\in R gilt, ist auch (b,a)R(b,a)\in R

Wenn aa zu bb in Relation steht, dann auch umgekehrt bb zu aa.

Transitivität

Für alle a,b,cAa,b,c\in A mit (a,b)R(a,b)\in R und (b,c)R(b,c)\in R ist auch (a,c)R(a,c)\in R

Wenn aa zu bb in Relation steht und bb zu cc, dann steht auch aa zu cc in Relation.

Beispiel: Kinder in einer Schulklasse

Wenn AA die Menge aller Schüler/innen in der Schule ist, dann kann RR als die Relation "gehen in dieselbe Klasse" definiert werden.

Überprüfe die Bedingungen:

  • Reflexivität: erfüllt, denn Felix geht natürlich in dieselbe Klasse wie er selbst.

  • Symmetrie: wahr, denn wenn Elena in derselben Klasse wie Felix ist, dann ist auch Felix in derselben Klasse wie Elena.

  • Transitivität: wahr. Sind Elena und Felix in derselben Klasse, und sind Felix und Anna auch in derselben Klasse, dann sind auch Elena und Anna in derselben Klasse.

Elena, Felix und Anna stehen hier für beliebige Schülerinnen und Schüler - die Bedingungen müssen für alle Schülerinnen und Schüler erfüllt sein.

Halbordnung

Eine Halbordnung oder partielle Ordnung ist eine Relation RR auf einer Menge AA, die folgende Bedingungen erfüllt:

Reflexivität

Für alle aAa \in A gilt (a,a)R(a,a)\in R

Alle Elemente von AA stehen zu sich selbst in Relation.

Antisymmetrie

Für alle a,bAa,b\in A gilt (a,b)R(b,a)Ra=b(a,b) \in R \wedge (b,a) \in R \Rightarrow a=b

Wenn aa zu bb in Relation steht und bb zu aa in Relation steht, dann geht das nur, wenn aa und bb gleich sind.

Transitivität

Für alle a,b,cAa,b,c\in A mit (a,b)R(a,b)\in R und (b,c)R(b,c)\in R ist auch (a,c)R(a,c)\in R

Wenn aa zu bb in Relation steht und bb zu cc in Relation steht, dann steht aa auch in Relation zu cc.

Wieso "Halb"ordnung? Weil nicht gefordert wird, dass je zwei Elemente der Menge AA immer miteinander vergleichbar sind. Eine Halbordnung wird erst dann zu einer Ordnung (oder totalen Ordnung oder linearen Ordnung), wenn für alle a,bAa, b\in A zusätzlich gilt

Du kannst dir eine totale Ordnung vorstellen wie die Relation \le auf der Menge der reellen Zahlen. Je zwei beliebige Zahlen sind miteinander vergleichbar. Entweder ist aba \le b oder bab \le a (oder beides, aber dann ist aufgrund der Antisymmetrie a=ba = b).

Ein Beispiel für eine Halbordnung, die keine totale Ordnung ist, siehst du hier:

Beispiel:

Sei MM eine Menge und seien AA und BB Teilmengen von MM. Die Relation RR, bei der (A,B)R(A,B)\in R genau dann gilt, wenn ABA\subseteq B, wenn also AA eine Teilmenge von BB ist, ist eine Halbordnung. Die nötigen Bedingungen sind erfüllt:

Reflexivität:  Für AMA\subseteq M gilt AAA\subseteq A, also ist die Bedingung erfüllt.

Antisymmetrie: Gilt für A,BMA,B \subseteq M, dass ABA\subseteq B und BAB\subseteq A, dann ist A=BA=B.

Transitivität: Für A,B,CMA,B,C\subseteq M gilt: Wenn ABA \subseteq B und BCB\subseteq C, dann ist auch ACA\subseteq C.

Also ist diese Relation RR eine Halbordnung (auf der Potenzmenge von MM). Aber RR ist keine totale Ordnung, denn im Allgemeinen gibt es Mengen A,BMA,B \subseteq M, die nicht miteinander vergleichbar sind, weder ist ABA \subseteq B noch ist BAB \subseteq A.

Funktion

Eine Funktion (oder Abbildung) ist eine spezielle Relation fA×Bf\subseteq A\times B, bei der es zu jedem aAa\in A genau ein Paar (a,b)f(a,b)\in f gibt.

Beispiel:

A={1,2,3},  B={0,1},  f={(1,1),(2,0),(3,1)}A=\{1{,}2,3\}, ~~ B=\{0{,}1\}, ~~ f=\{(1{,}1), (2{,}0), (3{,}1)\}

Man sagt, dass die Menge AA in die Menge BB abgebildet wird.

Eine Relation ist also eine Funktion, wenn sie

  • total definiert ist (jedes aAa\in A hat mindestens ein Bild in der Menge BB)

  • eindeutig ist (jedes aAa\in A hat höchstens ein Bild in der Menge BB)

Dagegen ist g={(1,0),(1,1),(2,0)}g = \{(1{,}0), (1{,}1), (2{,}0)\} keine Funktion, aus zweierlei Gründen:

  • die 1 wird auf 0 und auf 1 abgebildet, die Relation ist also nicht eindeutig;

  • die 33 wird nicht abgebildet, die Relation ist also nicht total definiert.

Schreibweise

Wenn eine Relation ff eine Funktion ist, so schreibt man nicht

fA×B  f \subseteq A \times B ~~ sondern   f:AB~~ f : A \rightarrow B

Und man schreibt nicht

(a,b)f  (a, b) \in f ~~ sondern   f(a)=b~~ f(a) = b

Folgende Beispielaufgaben beschäftigen sich damit, ob eine Relation eine Funktion ist:


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0.Was bedeutet das?