Relationen

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 Mengen

Ist 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 ∈ A

symmetrisch,
wenn aus aRb folgt, das bRa für a,b ∈ A

asymmetrisch,
wenn aus aRb folgt, dass b/Ra  für a,b ∈ A

antisymmetrisch,
wenn aus aRb und bRa folgt, dass a=b für a,b ∈ A

transitiv,
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“

Related Images: