Beziehungen zwischen Objekten
Äquivalenzrelation – Objekte mit bestimmten Eigenschaften werden als gleich angesehen
Ordnungsrelation – Objekte ordnen hinsichtlich Größe, Schlüsselwert, lexikographisch
Kartesisches Produkt – Kreuzprodukt
Seien A und B nicht leere MengenIst a ∈ A und b ∈ B so ist (a,b) ein geordnetes Paar, geordentes 2-Tupel, geordnetes Tupel, Tupel
A X B := {(a,b): a ∈ A und b ∈B} ist die Menge aller geordneten Paare, das kartesische Produkt von A und B
Ist A =B so schreibt man A X B als A²
Seien n ∈ N und X1, X2, …, Xn nichtleere Mengen
∏Xi := X1 x X2 x … x Xn = {(x1,…,xn): xi ∈ Xi für 1 ≤ i ≤ n}
Die Elemente (x1, … , xn) von ∏Xi heißen geordnete n-Tupel.
Definition: Relation
Binäre Relation / 2stellige Relation
Seien A und B nichtleere Mengen. Eine Teilmenge R ⊆ A x B ist eine binäre Relation mit Urmenge domR = A und Bildmenge ranR = B.
Ist R ⊆ A x A sagt man R ist eine Relation auf A / in A.
N-Stellige Relation
Seien n ∈ N und X1, X2, …, Xn nichtleere Mengen.
Eine Teilmenge R ∈ X1 x X2 x … x Xn ist eine n-stellige Relation.
Definition: Eigenschaften von Relationen
Sei R eine Relation auf A, Dann heißt R
reflexiv , wenn aRa für alle a ∈ A
irreflexiv, wenn a/Ra für alle a ∈ Asymmetrisch,
wenn aus aRb folgt, das bRa für a,b ∈ Aasymmetrisch,
wenn aus aRb folgt, dass b/Ra für a,b ∈ Aantisymmetrisch,
wenn aus aRb und bRa folgt, dass a=b für a,b ∈ Atransitiv,
wenn aus aRb und bRc folgt, dass aRc für a,b,c ∈ A
Äquivalenzrelation
R reflexiv, symmetrisch und transistiv
Äquivalenzklassem, Repräsentanten, Quotientemenge
Jede Äquivalenzrelation ~ auf A definiert eine eindeutige Partition von A in Blocks Ai – die Äquivalenzklassen
[a]:=[a]~ := {b ∈ A:b~a}
Jedes b ∈ [a] nennt man Repräsentant der Äquivalenzklasse [a]
Partition : Menge der Äquivalenzklassen; Quotientenmenge von A bzgl. ~ – A/R bzw. A/~
Ordnungen
Eine binäre Relation auf eine Menge X heisst partielle Ordnung, wenn sie
- reflexiv
- antisymmetrisch und
- transitiv ist.
Gilt zusätzlich ∀a,b ∈ X entweder a≤ b oder b≤ a nennt man ≤ eine totale oder lineare Ordnung.
Man schreibt x < y, falls x ≤ y und x ≠ y
Bsp. lexikographische Ordnung
∑ Menge von Zeichen / Buchstaben; das Alphabet
∑* Menge aller endlichen Zeichenfolgen, das freie Monoid über ∑
a1 … ak ≤ b1 … bs
∃j ∈ {0, … , min ( k, s )} mit ai = bi ∀ i ≤ j und
entweder j = k
oder j ≤ min ( k, s ) und aj+1 <. bj+1
–> Gleichlaut der Worte bis ein Buchstabe „gewinnt“