3.3 Relationen 39
Oft lassen sich die Tupel der Relation durch Angabe einer Eigenschaft spezifizieren. Wir
bilden zunächst:
M
2
M
2
= {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}
Hierauf definieren wir die Relation R
<
mit der Bedeutung xRy ist erfüllt, wenn x kleiner als y
ist:
R
<
= {(1, 2), (1, 3), (2, 3)} M
2
M
2
Sei M = {1, 2, 4, 6, 12}, damit wäre |M M| = |M| |M| = 25. Wir definieren nun R
3
wie
folgt
R
3
= {(x, y) | (x, y) M
2
x teilt y ganzzahlig ohne Rest}.
R
3
enthält damit die folgenden Paare:
R
3
= {(1, 1), (1, 2), (1, 4), (1, 6), (1, 12), (2, 2), (2, 4), (2, 6), (2, 12), (4, 4),
(4, 12), (6, 6), (6, 12), (12, 12)}
3.3.2 Äquivalenz- und Ordnungsrelationen
Für Relationen können gewisse Eigenschaften angegeben werden, die von diesen erfüllt oder
nicht erfüllt werden. Im Folgenden eine tabellarische Übersicht der wichtigsten Eigenschaf-
ten von Relationen:
Bezeichnung Bedeutung
1. Reflexiv
x M gilt xRx
2. Irreflexiv
x M mit xRx
3. Symmetrisch
x, y M gilt xRy yRx
4. Asymmetrisch
x, y M gilt xRy yRx
5. Antisymmetrisch
x, y M gilt xRy yRx x = y
6. Transitiv
x, y, z M gilt: aus xRy yRz xRz
7. Linear
x, y M gilt: xRy yRx
8. Konnex
x, y M gilt: x y xRy yRx
Tab. 3.4: Eigenschaften von Relationen
Obige Eigenschaften können dazu verwendet werden, eine Systematik innerhalb der Menge
aller Relationen aufzubauen. Wir definieren und unterscheiden zunächst die Äquivalenz- von
den Ordnungsrelationen, bevor wir in einem weiteren Abschnitt den Abbildungen als spe-
ziellen Relationen unsere Aufmerksamkeit widmen.
Manchmal ist es wichtig, innerhalb einer Menge die Elemente so in Teilmengen aufzuteilen,
dass in jeder Teilmenge die Elemente zusammengefasst sind, die in Bezug auf die Erfüllung
gewisser Eigenschaften als gleich oder gleichwertig anzusehen sind. Betrachten wir hierzu
40 3 Mengen, Relationen und Abbildungen
folgendes Beispiel: Ein Dorf verfügt über eine Grundschule mit angeschlossenem Kindergar-
ten, den die Kinder ab einem Alter von 3 Jahre besuchen. Zur Abschätzung der Größe der
Schulklassen in den kommenden Jahren ist es von Interesse, die Kinder nach Altersstufen
einzuteilen. Wir definieren folgende Relation:
M = {x | x ist Kind im Kindergarten}
R
1
= {(x, y) | (x, y) M
2
x ist so alt wie y}
Untersuchen wir nun diese Relation im Hinblick auf die oben definierten Eigenschaften so
können wir festhalten, dass die Relation
1. Reflexiv ist, da jedes Kind so alt ist wie es selbst.
2. Symmetrisch ist, denn wenn Anna so alt wie Paul ist, dann ist auch Paul so alt wie
Anna.
3. Transitiv ist, denn wenn Anna so alt wie Paul ist und Paul so alt wie Petra, dann ist
auch Anna so alt wie Petra.
Wir haben hier den Grundtypus einer Äquivalenzrelation. Eine Äquivalenzrelation teilt eine
Grundmenge in Äquivalenzklassen ein. Die Äquivalenzklasse enthält somit alle Elemente
einer Grundmenge, die in dieser Relation zueinander stehen. Im obigen Fall sind dies die
Kinder einer Altersstufe. Wir definieren:
Äquivalenzrelation
Eine reflexive, symmetrische und transitive Relation heißt Äquivalenzrelation.
Ordnungsrelationen
Bei Ordnungsrelationen finden keine Klasseneinteilungen statt, sondern es erfolgt eine An-
ordnung der Elemente einer Grundmenge aufgrund gewisser Kriterien. Die Systematisierung
der ordnungstheoretischen Grundbegriffe ist jedoch etwas komplexer. Wir beschränken uns
auf die Erläuterung der Quasi-, Halb- und Vollordnungen.
Quasiordnungen
Bleiben wir zunächst bei dem Beispiel mit dem Kindergarten. Im Rahmen einer Theaterauf-
führung sollen die Kinder nach aufsteigender Körpergröße aufgestellt werden. Wir definieren
folgende Relation auf der Menge der Kindergartenkinder:
M = {x | x ist Kind im Kindergarten}
R
2
= {(x, y) | (x, y) M
2
x ist größer als y}
Wir stellen fest, dass obige Relation folgende Eigenschaften erfüllt:

Get Logik und Algebra, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.