4 Relationen

4.a) Allgemeine Definitionen

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 ∈ IR : x ≤ y ”Kleiner–gleich–Beziehung”.

4) m, n ∈ ZZ : m|n (d.h. ∃ k ∈ ZZ : 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 ∈ ZZ, m|n} ⊆ ZZ × ZZ

\underline{(4.1) DEF:} M und N seien Mengen. Eine Teilmenge R ⊆ M × N heißt eine Relation zwischen M und N. Im Falle M = N heißt R eine Relation auf M. Für (x, y) ∈ R schreibt man auch \underline{x R y} und sagt: ”\underline{x steht in Relation R 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. Aus zwei Relationen läßt sich in geeigneten Fällen eine weitere Relation konstruieren: die Verknüpfung oder Komposition.

\underline{(4.2) DEF:} M, N, P seien Mengen.

a) R ⊆ M × N und S ⊆ N × P seien Relationen. Dann heißt die Relation \underline{S ∘ R} := \{ (m, p) | m ∈ M, p ∈ P, ∃ n ∈ N : (m, n) ∈ R ∧ (n, p) ∈ S \} ⊆ M × P

die Verknüpfung oder Komposition von R und S.

b) Die zu R ⊆ M × N inverse Relation R^{−1} ⊆ N × M ist definiert durch \underline{R^{−1}} := \{ (n, m) | n ∈ N, m ∈ M, (m, n) ∈ R \} ⊆ N × M .

Etwas anschaulicher geschrieben:

S ∘ R := \{ (m, p) | m ∈ M, p ∈ P, ∃ \underline{\underline{n}} ∈ N : mR\underline{\underline{n}} ∧ \underline{\underline{n}}Sp \}

R^{−1} := { (n, m) | n ∈ N, m ∈ M, mRn }

Ist R die ≤–Beziehung, d.h. xRy ⟺ x ≤ y, so ist die inverse Relation R^{−1} definiert durch xR^{−1}y ⟺ yRx ⟺ y ≤ x ⟺ x ≥ y .

\underline{(4.3) SATZ:} Sind M, N, P und Q Mengen und R ⊆ M × N , S ⊆ N × P und T ⊆ P × Q Relationen, so gilt:

a) (T ∘ S) ∘ R = T ∘ (S ∘ R) b) (S ∘ R)^{−1} = R^{−1} ∘ S^{−1} .

Bew: a) Es ist die Gleichheit der beiden Teilmengen (T ∘S)∘R und T ∘(S ∘R) von M ×Q zu zeigen. Nach Definition gilt

(T ∘ S) ∘ R = { (m, q) | m ∈ M, q ∈ Q, ∃ n ∈ N : mRn ∧ n(T ∘ S)q }

und n(T ∘ S)q ⟺ ∃ p ∈ P : nSp ∧ pT q. Für beliebiges (m, q) ∈ M × Q gilt:

(m, q) ∈ (T ∘ S) ∘ R ⟺ ∃ n ∈ N : mRn ∧ n(T ∘ S)q

⟺ ∃ n ∈ N : mRn ∧ (∃ p ∈ P : nSp ∧ pT q) (⋆)

(m, q) ∈ T ∘ (S ∘ R) ⟺ ∃ p ∈ P : m(S ∘ R)p ∧ pT q

⟺ ∃ p ∈ P : (∃ n ∈ N : mRn ∧ nSp) ∧ pT q (⋆⋆)

Die beiden Ausdrücke (⋆) und (⋆⋆) sind äquivalent.

b) Es gilt (S ∘ R)^{−1} ⊆ P × M und R^{−1} ∘ S^{−1} ⊆ P × M. Für ein beliebiges Element (p, m) ∈ P × M folgt dann:

(p, m) ∈ (S ∘ R)^{−1} ⟺ (m, p) ∈ S ∘ R ⟺ ∃ n ∈ N : (m, n) ∈ R ∧ (n, p) ∈ S ⟺

∃ n ∈ N : (p, n) ∈ S^{−1} ∧ (n, m) ∈ R^{−1} ⟺ (p, m) ∈ R^{−1} ∘ S^{−1} .

Damit gilt die behauptete Gleichheit. □

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.

4.b) Ordnungsrelationen

Wir betrachten zunächst zwei schon bekannte Beispiele:

(IR, ≤)  (P(M), ⊆)
≤ ist eine Relation auf IR ⊆ 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  nichts entsprechendes
5)  x < y ⟹ y ≮ x  U ⊂ V ⟹ V ⊄ U

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

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

R_{1}) ∀ x ∈ M : x R x (R ist reflexiv)
R_{2}) ∀ x, y ∈ M : (x R y ∧ y R x) ⟹ x = y (R ist antisymmetrisch)
R_{3}) ∀ x, y, z ∈ M : (x R y ∧ yRz) ⟹ xRz (R ist transitiv)

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

Beispiele: (IR, ≤) , (P(M), ⊆) , (IN, |) , (M, =)

Während in (IR, ≤) 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{(4.5) DEF:} Eine partielle Ordnung R auf einer Menge M heißt lineare oder totale Ordnung, wenn gilt:

R_{4}) ∀ x, y ∈ M : (x R y ∨ y R x) (R ist alternativ).

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

Die <–Beziehung auf IR (oder die ⊂–Relation auf P(M)) erfüllt nicht R_{1}), jedoch R_{3}) und darüberhinaus

R_{5}) ∀ x, y ∈ M : x R y ⟹ ¬ (y R x) (R ist asymmetrisch)

\underline{(4.6) DEF:} Sei M eine Menge. Eine Relation R ⊆ M × M heißt strenge Ordnung auf M, wenn R die Bedingungen R_{3}) und R_{5}) erfüllt,

Beispiele: (IR, <) , (P(M), ⊂) .