Relation
Definition:
Eine Teilmenge des cartesischen Produkts nennt man -stellige Relation:
Typen (von 2-stelligen Relationen):
- Global (für alle Elemente der Grundmenge):
- Reflexiv:
- Linear:
- Lokal (für alle Paare der Relation):
- Symmetrisch:
- Antisymmetrisch:
- Bzw. als Bedingung:
- Transitiv:
Äquivalenzrelation
Definition:
Eine Äquivalenzrelation beschreibt eine Gleichheitsstruktur zwischen den Elementen einer Menge.
Eine Äquivalenzrelation über eine Menge ist eine Relation im cartesischen Produkt , für die gilt:
- ist reflexiv:
- ist symmetrisch:
- ist transitiv:
Statt wird oft geschrieben:
Wenn eine Äquivalenzrelation vorliegt, kann man die Elemente in Gruppen (Äquivalenzklassen) aufteilen.
Äquivalenzklassen
Definition:
Die Äquivalenzklasse eines Elements ist die Menge aller Elemente, die zu äquivalent sind:
Gleichheit:
Zwei Äquivalenzklassen sind genau dann gleich, wenn sie (mindestens) ein gemeinsames Element haben bzw. ein Element einer Äquivalenzklasse äquivalent zu einem Element einer anderen Äquivalenzklasse ist:
Somit sind zwei Äquivalenzklassen disjunkt, wenn sie nicht gleich sind:
Vereinigung:
Die Vereinigung aller Äquivalenzklassen (aufgrund der Eigenschaft ) ergibt die ursprüngliche Menge :
Quotientenmenge:
Die Quotientenmenge ist die Menge aller Äquivalenzklasse von :
Ordnungsrelation
Definition:
Eine Ordnungsrelation beschreibt eine Vergleichsstruktur zwischen den Elementen einer Menge.
Typen:
Eine Relation heißt...
- Quasiordnung, wenn reflexiv und transitiv
- Halbordnung, wenn reflexiv, transitiv und antisymmetrisch
- Vollordnung, wenn reflexiv, transitiv, antisymmetrisch und linear
- Auch lineare Ordnung genannt
Statt wird für Ordnungsrelation verwendet: oder mit Mengen:
Minimal/Minimum & Maximal/Maximum Element:
Für gilt, es ist...
- Minimal:
- "Kein anderes Element kommt vor m"
- Minimum:
- "Alle Elemente kommen nach m"
- Maximal:
- "Kein anderes Element kommt nach m"
- Maximum:
- "Alle Elemente kommen vor m"
Minimal/Maximal: können mehrere Elemente sein
Minimum/Maximum: kleinstes/größtes Element
Veranschaulichung:
Eine gute Veranschaulichung der Beziehungen bzw. Struktur der Elemente ist eine graphische Darstellung. Hierbei stellt man jedes Element als Knoten dar und zeichnet einen Pfeil von nach , wenn . Knoten ohne eingehende Pfeile sind minimale Elemente, ohne ausgehende Pfeile sind maximale Elemente. Das Minimum hat Pfeile zu allen Elementen, das Maximum empfängt Pfeile von allen Elementen.