Relationen

Äquivalenzrelation

Eine Relation $R$ auf einer Menge $A$ ist eine Äquivalenzrelation, wenn sie folgende Bedingungen erfüllt:

Beispiel: Kinder in einer Schulklasse

Wenn $A$ die Menge aller Schüler/innen in der Schule ist, dann kann $R$ 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 $R$ auf einer Menge $A$, die folgende Bedingungen erfüllt:

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

$(a,b)\in R~ \vee~ (b,a)\in R$

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 $a \le b$ oder $b \le a$ (oder beides, aber dann ist aufgrund der Antisymmetrie $a = b$).

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

Beispiel:

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

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

Antisymmetrie: Gilt für $A,B \subseteq M$, dass $A\subseteq B$ und $B\subseteq A$, dann ist $A=B$.

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

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

Funktion

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

Beispiel:

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

Man sagt, dass die Menge $A$ in die Menge $B$ abgebildet wird.

Eine Relation ist also eine Funktion, wenn sie

• total definiert ist (jedes $a\in A$ hat mindestens ein Bild in der Menge $B$)

• eindeutig ist (jedes $a\in A$ hat höchstens ein Bild in der Menge $B$)

Dagegen ist $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 $3$ wird nicht abgebildet, die Relation ist also nicht total definiert.

Schreibweise

Wenn eine Relation $f$ eine Funktion ist, so schreibt man nicht

$f \subseteq A \times B ~~$ sondern $~~ f : A \rightarrow B$

Und man schreibt nicht

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

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