Kap. 1 : Grundlagen

§ 1. Relationen

Relationen

Relationen stellen Beziehungen zwischen den Elementen zweier Mengen her. Beispiele: 1) M sei die Menge aller Menschen. Für x, y ∈ M bedeute x ∼ y , daß x mit y verwandt ist 2) M sei die Menge aller Männer und F die aller Frauen. Für x ∈ M und y ∈ F bedeute

x ∼ y, daß x mit y verheiratet ist. Ein “Ehepaar” ist also ein Paar (x, y) mit x ∼ y. Die Menge E := {(x, y) | x ∈ M, y ∈ F, x ∼ y} ⊆ M × F ist dann eine Teilmenge von M × F, durch die die Relation ”verheiratetsein”vollständig beschrieben ist.

3) x, y ∈ ℝ : x ≤ y ”Kleiner–gleich–Beziehung”.

4) m, n ∈ ℤ : m|n (d.h. ∃ k ∈ ℤ : n = k m) “Teilbarkeitsbeziehung”

5) U, V ∈ P(M) : U ⊆ V “Enthaltenseins–Beziehung”

6) G sei die Menge aller Geraden in der Ebene und es seien g, h ∈ G : g ∥ h oder g ⊥ h .

7) M sei eine beliebige Menge, x, y ∈ M : x = y ”Gleichheit”. Mathematisch gesehen wird eine Relation vollständig bestimmt durch eine Teilmenge eines kartesischen Produktes, so ist z.B. die Teilbarkeitsbeziehung in 4) beschrieben durch die Menge:

{(m, n) | m, n ∈ ℤ, m|n} ⊆ ℤ × ℤ

\underline{\underline{(1.1) DEF:}} M und N seien Mengen. Eine Teilmenge ρ ⊆ M × N heißt eine Relation zwischen M und N. Im Falle M = N heißt ρ eine Relation auf M. Für (x, y) ∈ ρ schreibt man auch \underline{x ρ y} und sagt: ”\underline{x steht in Relation ρ zu y}”.

Zu Beispiel 7): Die Menge Δ_{M} := {(x, x) | x ∈ M} heißt Diagonale von M. Δ_{M} ⊆ M × M ist dann eine Relation auf M. Es gilt: ∀ (x, y) ∈ M × M : (x, y) ∈ Δ_{M} ⟺ x = y , d.h. Δ_{M} beschreibt gerade die Gleichheitsbeziehung zwischen den Elementen von M.

Abbildungen

Eine Abbildung f : M ⟶ N ist vollständig durch ihren Graphen

{ (x, f(x)) | x ∈ M } ⊆ M × N

beschrieben. Daher ist eine Abbildung im Grunde genommen einen Relation zwischen den beiden Mengen M und N .

\underline{\underline{(1.2) DEF:}} Eine Abbildung f : M ⟶ N von der Menge M in die Menge N ist eine Relation f ⊆ M × N mit folgenden Eigenschaften:

a) f ist linkstotal, d.h. ∀ x ∈ M ∃y ∈ N : (x, y) ∈ f

b) f ist rechtseindeutig, d.h. ∀x ∈ M ∀y, y′ ∈ N : (x, y) ∈ f ∧ (x, y′) ∈ f ⟹ y = y′.

Setzt man y = f(x) :⟺ (x, y) ∈ f , so erkennt man hier unsere alte Definition für eine Abbildung wieder.

Auf einer Menge M kann es sehr viele Relationen geben (genausoviele wie Teilmengen von M ×M). Deshalb werden nur Relationen mit zusätzlichen Eigenschaften von Interesse sein. Bei der Auswahl dieser Eigenschaften orientieren wir uns an wichtigen mathematischen Beispielen, die wir z.T. schon kennengelernt haben.

Ordnungsrelationen

Wir betrachten zunächst zwei schon bekannte Beispiele:

(ℝ, ≤)  (P(M), ⊆)
0) ≤ ist eine Relation auf ℝ  ⊆ ist eine Relation auf P(M)
1)  x ≤ x  U ⊆ U
2)  x ≤ y ∧ y ≤ x ⟹ x = y  U ⊆ V ∧ V ⊆ U ⟹ U = V
3)  x ≤ y ∧ y ≤ z ⟹ x ≤ z  U ⊆ V ∧ V ⊆ W ⟹ U ⊆ W
4) es gilt stets x ≤ y oder y ≤ x i.a. nichts entsprechendes

Wir nehmen dies zum Anlaß für die folgende Definition:

\underline{\underline{(1.3) DEF:}} Sei M eine Menge. Eine Relation ρ ⊆ M × M heißt eine Ordnungsrelation (oder partielle Ordnung oder Halbordnung) auf M, wenn gilt:

O_{1}) ∀ x ∈ M : x ρ x (ρ ist reflexiv)
O_{2}) ∀ x, y ∈ M : (x ρ y ∧ y ρ x) ⟹ x = y (ρ ist antisymmetrisch)
O_{3}) ∀ x, y, z ∈ M : (x ρ y ∧ yρz) ⟹ xρz (ρ ist transitiv)

(M, ρ) heißt dann auch eine geordnete Menge.

Beispiele: (ℝ, ≤) , (P(M), ⊆) , (ℕ, |) , (M, =)

Während in (ℝ, ≤) je zwei Elemente bzgl. ≤ vergleichbar sind, ist dies bei (P(M), ⊆) i.a. nicht der Fall: Für M := {1, 2} gilt etwa {1} ⊈ {2} und {2} ⊈ {1}.

\underline{\underline{(1.4) DEF:}} Eine Ordnung ρ auf einer Menge M heißt lineare Ordnung (oder totale Ordnung), wenn gilt:

O_{4}) ∀ x, y ∈ M : (x ρ y ∨ y ρ x) (M, ρ) heißt dann eine linear geordnete Menge .

Beispiele: (ℝ, ≤) ist linear geordnet, (P({1, 2}), ⊆) und (ℕ, |) sind nicht linear geordnet.

Äquivalenzrelationen

Eine weitere wichtige Klasse von Relationen bilden die sog. Äquivalenzrelationen, die eng mit dem Abstraktionsprozeß in der Mathematik zusammenhängen.

\underline{\underline{(1.5) DEF:}} Eine Relation ρ auf einer Menge M heißt Äquivalenzrelation auf M,wenn gilt: Ä_{1}) ∀ x ∈ M : x ρ x (Reflexivität)

Ä_{2}) ∀ x, y ∈ M : x ρ y ⟹ y ρ x (Symmetrie)
Ä_{3}) ∀ x, y, z ∈ M : (x ρ y ∧ yρz) ⟹ xρz (Transitivität)

Der Unterschied zu einer Ordnungsrelation liegt nur in einer Bedingung: beide Relationen sind reflexiv und transitiv, eine Äquivalenzrelation ist symmetrisch, wohingegen eine Ordnungsrelation antisymmetrisch ist. Trotzdem werden wir wesentliche Unterschiede feststellen. Gilt x ρ y, so sagt man auch, daß \underline{x äquivalent ist zu y bzgl. ρ}.

Beispiele für Äquivalenzrelationen:

6) Parallelität von Geraden der Ebene

7) Gleichheitsbeziehung zwischen den Elementen einer Menge 8) Äquivalenz von Matrizen

9) Ähnlichkeit von Matrizen

10) Gleichmächtigkeit auf einer Menge von Mengen

11) Isomorphie auf einer Menge von Gruppen

12) Kongruenzrelation modulo n auf ℤ Für eine natürliche Zahl n ist die Kongruenzrelation K_{n} modulo n auf ℤ definiert durch

a K_{n} b :⟺ n | (a − b) (für alle a, b ∈ ℤ)

Diese ist eine Äquivalenzrelation auf ℤ . Wir schreiben auch

a K_{n} b :⟺ a ≡ b (mod n)

In der Restklasse [a]_{n} von a ∈ ℤ modulo n liegen alle ganzen Zahlen, die bei Division durch n denselben Rest haben, d.h.

[a]_{n} = a + ℤn = { b | b ∈ ℤ , b ≡ a (mod n) } = { b | b ∈ ℤ , b K_{n}a }

Da es bei Division durch n die n nichtnegativen Reste 0, 1, 2, …, n − 1 gibt, sind

[0]_{n}, [1]_{n}, [2]_{n}, …, [n − 1]_{n}

alle Restklassen modulo n. Diese Bildung der Restklassen übertragen wir auf beliebige Äquivalenzrelationen:

\underline{\underline{(1.6) DEF:}} ρ sei eine Äquivalenzrelation auf einer Menge M. Für ein Element x ∈ M heißt

die Menge [ x]_{ρ} := { y | y ∈ M ∧ y ρ x } ⊆ M

aller Elemente von M, die zu x bzgl. ρ äquivalent sind, die Äquivalenzklasse von x bzgl. ρ. Die Menge M/ρ := { [ x]_{ρ} | x ∈ M } aller Äquivalenzklassen von Elementen aus M bzgl. ρ heißt die Quotientenmenge von M nach ρ.

Ein vollständiges Repräsentantensystem von M/ρ enthält aus jeder Äquivalenzklasse genau ein Element.

Die Menge {0, 1, 2, …, n − 1} enthält aus jeder Äquivalenzklasse von ℤ/K_{n} = ℤ_{n} genau ein Element, ist also ein vollständiges Repräsentantensystem von ℤ_{n}. Hier gibt es unendlich viele solcher Systeme!

Wenn aus dem Zusammenhang klar ist, um welche Äquivalenzrelation es sich handelt, so schreibt man auch nur [ x] für die Äquivalenzklasse von x. Man mache sich klar:

[ x] ∈ P(M) und M/ρ ⊆ P(M)