Lektion 4.2

Eigenschaften von Relationen

15 min Lesezeit

Nicht alle Relationen sind gleich. Die "kleiner als"-Relation verhält sich anders als die "gleich"-Relation. Um diese Unterschiede zu beschreiben, definieren wir verschiedene Eigenschaften, die eine Relation haben kann.

Definition

Reflexivität

Eine Relation $R$ auf $A$ heißt reflexiv, wenn jedes Element zu sich selbst in Relation steht:

Für alle $a \in A$ gilt: $aRa$

Beispiele:
- $=$ ist reflexiv: $a = a$ für alle $a$
- $\leq$ ist reflexiv: $a \leq a$ für alle $a$
- $<$ ist nicht reflexiv: $a < a$ gilt nie

\text{reflexiv: } \forall a \in A: aRa

Definition

Symmetrie

Eine Relation $R$ auf $A$ heißt symmetrisch, wenn gilt:

Wenn $aRb$ , dann auch $bRa$ .

Beispiele:
- $=$ ist symmetrisch: $a = b \Rightarrow b = a$
- "ist verheiratet mit" ist symmetrisch
- $<$ ist nicht symmetrisch: $1 < 2$ , aber nicht $2 < 1$

\text{symmetrisch: } aRb \Rightarrow bRa

Definition

Transitivität

Eine Relation $R$ auf $A$ heißt transitiv, wenn gilt:

Wenn $aRb$ und $bRc$ , dann auch $aRc$ .

Beispiele:
- $<$ ist transitiv: $a < b$ und $b < c$ impliziert $a < c$
- $=$ ist transitiv: $a = b$ und $b = c$ impliziert $a = c$
- "ist direkter Vorgesetzter von" ist nicht transitiv

\text{transitiv: } (aRb \land bRc) \Rightarrow aRc

Beispiel

Eigenschaften überprüfen

Sei $A = \{1, 2, 3\}$ und $R = \{(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)\}$ .

Reflexiv? Ja! $(1,1), (2,2), (3,3) \in R$

Symmetrisch? Nein! $(1,2) \in R$ , aber $(2,1) \notin R$

Transitiv? Ja! $(1,2)$ und $(2,3)$ in $R$ $\Rightarrow$ $(1,3) \in R$ (stimmt!)

Zusammenfassung

Reflexiv: Jedes Element steht zu sich selbst in Relation
Symmetrisch: Wenn $aRb$ , dann auch $bRa$
Transitiv: Wenn $aRb$ und $bRc$ , dann auch $aRc$

Übungen

Aufgabe 1Multiple Choice

Welche Eigenschaft hat die "kleiner gleich"-Relation $\leq$ auf $\mathbb{N}$ ?

Nur reflexiv

Reflexiv und transitiv

Reflexiv, symmetrisch und transitiv

Nur transitiv

Eigenschaften von Relationen

Definition

Reflexivität

Eine Relation $R$ auf $A$ heißt reflexiv, wenn jedes Element zu sich selbst in Relation steht:

Für alle $a \in A$ gilt: $aRa$

Beispiele:
- $=$ ist reflexiv: $a = a$ für alle $a$
- $\leq$ ist reflexiv: $a \leq a$ für alle $a$
- $<$ ist nicht reflexiv: $a < a$ gilt nie

\text{reflexiv: } \forall a \in A: aRa

Definition

Symmetrie

Eine Relation $R$ auf $A$ heißt symmetrisch, wenn gilt:

Wenn $aRb$ , dann auch $bRa$ .

Beispiele:
- $=$ ist symmetrisch: $a = b \Rightarrow b = a$
- "ist verheiratet mit" ist symmetrisch
- $<$ ist nicht symmetrisch: $1 < 2$ , aber nicht $2 < 1$

\text{symmetrisch: } aRb \Rightarrow bRa

Definition

Transitivität

Eine Relation $R$ auf $A$ heißt transitiv, wenn gilt:

Wenn $aRb$ und $bRc$ , dann auch $aRc$ .

Beispiele:
- $<$ ist transitiv: $a < b$ und $b < c$ impliziert $a < c$
- $=$ ist transitiv: $a = b$ und $b = c$ impliziert $a = c$
- "ist direkter Vorgesetzter von" ist nicht transitiv

\text{transitiv: } (aRb \land bRc) \Rightarrow aRc

Beispiel

Eigenschaften überprüfen

Sei $A = \{1, 2, 3\}$ und $R = \{(1,1), (2,2), (3,3), (1,2), (2,3), (1,3)\}$ .

Reflexiv? Ja! $(1,1), (2,2), (3,3) \in R$

Symmetrisch? Nein! $(1,2) \in R$ , aber $(2,1) \notin R$

Transitiv? Ja! $(1,2)$ und $(2,3)$ in $R$ $\Rightarrow$ $(1,3) \in R$ (stimmt!)

Zusammenfassung

Reflexiv: Jedes Element steht zu sich selbst in Relation
Symmetrisch: Wenn $aRb$ , dann auch $bRa$
Transitiv: Wenn $aRb$ und $bRc$ , dann auch $aRc$

—