Woche 05, Relationen

03.11.2026

Nu’ is’es nur so: Mengen alleine machen keine Sachen. Du kannst zwei Elemente aus einer Menge auswählen und auf verschiedene Eigenschaften prüfen und dann darüber Aussagen treffen, zum Beispiel Gleichheit oder Ordnung, aber es wäre auch irgendwie cool wenn man nicht jedes Mal formal zwei Elemente aus einem Menge dazu definieren müsste..

Enter Relationen

1.6 Relationen

Relationen definieren Zusammenhänge zwischen zwei oder mehr Mengen. Eine Relation zwischen genau zwei Mengen nennen wir auch binäre Relation.

Sind $A$ und $B$ Mengen, dann ist $R\subseteq A\times B$ eine binäre Relation zwischen A und B. Falls $A=B$ ist $R\subseteq A\times A$ eine Relation auf A.

Für $(a,b)\in R$ sagen wir $a$ und $b$ sind, bezüglich $R$, in Relation zueinander: $a R b$.

Beispiele für Relationen auf $\mathbb{N}$

• Gleichheitsrelation $"=":\{(1,1), (2,2), ...\}$
• Kleinergleichrelation $"\le":\{(1,1), (1,2), ..., (2,2), (2,3), ...\}$
• Teilbarkeit $"\vert":\{(1,1),(1,2),...,(2,2),(2,4),...(3,3),(3,6),...\}$

Eigenschaften von Relationen (auf A)

• reflexiv: $\forall a\in A:(a,a)\in R$ bzw. $a R a$
• symmetrisch: $\forall a,b\in A: (a,b)\in R\Rightarrow (b,a)\in R$
• antisymmetrisch: $\forall a,b\in A: (a,b)\in R\land (b,a)\in R\Rightarrow a=b$
• transitiv: $\forall a,b,c\in A:(a,b)\in R\land(b,c)\in R\Rightarrow(a,c)\in R$

	$=$	$\le$
reflexiv	✅	✅
symmetrisch	✅	❌
antisymmetrisch	✅	✅
transitiv	✅	✅

Spezielle Relationen

• Quasiordnung: reflexiv und transitiv,
• Partialordnung: reflexiv, antisymmetrisch, transitiv
• Äquivalenzrelation: reflexiv, symmetrisch, transitiv

Beispiel: Teilbarkeitsrelation

$$ R=\{(x,y)\in\mathbb{N}^2\mid y=kx,\; k\in\mathbb{N}\} $$

• reflexiv: ja, denn $y=kx$ für $k=1$,
• symmetrisch: nein, denn für $3\vert6$ gilt nicht auch $6\vert3$ (zumindest nicht in den natürlichen und ganzen Zahlen).
• antisymmetrisch: ja, denn $x\vert y$ und $y\vert x$ gilt nur wenn $x=y$,
• transitiv: ja, denn $y=kx$ und $z=my$, dann $z=my=mkx$ durch einsetzen

Und damit haben wir actually schon gezeigt, dass die Teilbarkeitsrelation eine Partialordnung ist.

Graphische Darstellung

Gegeben ist die Relation $R$ über $\{1,2,3,4,5\}$ mit $R=\{(1,2),(2,1),(2,3),(2,4),(3,2),(4,2),(4,5),(5,4)\}$

(1) als Matrix

• Element von $A\rightarrow$ Zeilen Element von $B\rightarrow$ Spalten
• “x” oder 1 wenn $(a,b)\in R$ “-” oder 0 sonst

Falls alle Elemente auf der blauen Hauptdiagonale gekreuzt wären, also die Tupel in der Relation, wäre die Relation reflexiv. Ist sie aber nicht.

Die gegebene Relation ist dafür aber symmetrisch. In dieser Darstellung an der Spiegelung an der Hauptdiagonalen zu erkennen.

Antisymmetrisch kann diese Relation nicht sein, da für $(2,3)\in R\land (3,2)\in R$ nicht folgt das $2=3$ wäre.

Transitiv ist die gegebene Relation ebenfalls nicht, da für $(1,2)\in R\land (2,1)\in R$ auch $(1,1)\in R$ sein müsste, ist es aber nicht.

(2) als Graph

• zeichne Elemente der Menge als Knoten/Vertecies in der Ebene
• verbinde zwei Elemente $a\rightarrow b$ falls $(a,b)\in R$

Äquivalenzrelationen

Äquivalenzrelationen sind “eine ganz tolle Erfindung und wir werden uns noch viel mit ihnen beschäftigen in der Mathematik”. Prinzipiell ist es aber nur eine Abstraktion der Gleichheit. I.e: eine Relation die alle Elemente vom gleichen Typ, bzw. mit einem oder mehreren gleichen Eigenschaften zusammenfasst.

Ist $X$ die Menge aller Dreiecke in der Ebene mit der Kongruenzrelation, das heißt zwei Dreiecke stehen in Relation falls sie deckungsgleich sind. Diese Relation ist reflexiv, symmetrisch und transitiv.

Wir können hier nicht vernünftig argumentieren warum das so ist, das Modul heißt ja auch “Mathematik IT-1” und nicht Elementargeometrie.

Äquivalenzklassen

Für eine Äquivalenzrelation $R$ auf $X$ und $a\in X$ heißt eine Menge

$$E_a:=\{x\in X\mid aRx\}=\{x\in X\mid xRa\}$$

die Äquivalenzklasse von $a$.

Wir können hier die Elemente $x$ und $a$ beliebig vertauschen, weil die Äquivalenzrelation ja reflexiv ist und die Äquivalenzklasse eines Elementes “andere gleiche” Elemente angibt. ($\frac12,\frac24,\frac48$ gehören alle zur gleichen Äquivalenzklasse.)

Wir nennen $a$ und jedes Elemente der Äquivalenzklasse $E_a$ einen Vertreter/Repräsentanten der Äquivalenzklasse.

Partialordnung

Partialordnungen sind nach Definition (i) reflexiv, (ii) antisymmetrisch und (iii) transitiv. Wir schreiben

$$ x\le_R y. $$

Eine partiell geordnete Menge (partially sorted set/poset) ist ein Tupel $(S,\le)$ wobei $\le$ eine partielle Ordnung über $S$ ist.

Beispiele

1. Teilbarkeitsrelation auf $\mathbb{N}$,
2. auf $\mathcal{P}(A)$ ist die Teilmengenrelation (Inklusionsrelation) $\subseteq$ eine partielle Ordnung,
3. Menge der Wörter (Strings) mit lexikographischer Ordnung vergleicht Wörter Zeichen-für-Zeichen.

Beispiel lexikographischer Ordnung über Alphabet $A=\{a,b,c\}$

• $abc\le aca$
• $aba\le ac$
• $abc\le abc$

Beobachtung: In (3) sind alle Paare von Wörtern paarweise miteinander vergleichbar, das nennt sich totale Ordnung, in (2) muss das nicht zwangsweise so sein (Gegenbeispiel: $A=\{1,2,3\},B=\{2,3,4\}$).

Totale Ordnung

Für eine gegebene Relation $R$ müssen alle Elemente stets vergleichbar sein.

$$ \forall(v,w)\in R:v\le w\lor w\le v $$

Last edited: 03.11.2026