Übungen

Übung 1 (Relationen und ihre Struktureigenschaften, I (L))

Für alle natürlichen Zahlen n, m setzen wir:

n R m, falls |n − m| ist gerade,

n S m, falls |n − m| ist ungerade.

(Hierbei ist |a| der Betrag einer ganzen Zahl a, also |a| = a, falls a ≥ 0, und |a| = − a, falls a < 0.)

Welche Struktureigenschaften haben diese Relationen?

Übung 2 (Relationen und ihre Struktureigenschaften, II)

Sei R eine Relation auf A. Welche Struktureigenschaften vererben sich von R auf R^− 1? Welche Struktureigenschaften besitzt R ∪ R⁻¹?

Übung 3 (Relationen und ihre Struktureigenschaften, III (L))

Sei R eine Relation auf A. Zeigen Sie, dass es eine ⊆-kleinste Relation R* auf A gibt mit R* ⊇ R und R* transitiv.

Übung 4 (Relationen und ihre Struktureigenschaften, IV)

Seien R und S Relationen auf A. Wir definieren eine Verknüpfung ∘ durch

R ∘ S = { (a, c) | es gibt ein b mit a R b und b S c }.

(i)	Untersuchen Sie exemplarisch die Struktureigenschaften von R ∘ S in Abhängigkeit von den Struktureigenschaften von R und S.

(ii)	Wie lässt sich die Transitivität von R mit Hilfe der Verknüpfung ∘ ausdrücken?

(iii)

Zeigen Sie, dass ∘ assoziativ ist, d. h. für alle Relationen R, S, T auf A gilt (R ∘ S) ∘ T = R ∘ (S ∘ T).

Übung 5 (Äquivalenzrelationen, I)

Sei A eine Menge. Wir definieren für alle a, b  ∈  A:

a ∼₁ b, falls a = b,

a ∼₂ b, falls a = a.

Zeigen Sie, dass ∼₁ und ∼₂ Äquivalenzrelationen sind und bestimmen Sie die Äquivalenzklassen.

Übung 6 (Äquivalenzrelationen, II)

Sei ∼ eine Äquivalenzrelation auf A. Zeigen Sie, dass 𝒵 = A/∼ eine Zerlegung von A ist.

Übung 7 (Äquivalenzrelationen, III)

Sei 𝒵 eine Zerlegung von A. Für a, b  ∈  A setzen wir:

a ∼_𝒵 b, falls es gibt ein Z  ∈  𝒵 mit a, b  ∈  Z.

Zeigen Sie, dass ∼_𝒵 eine Äquivalenzrelation mit A/∼_𝒵 = 𝒵 ist.

Übung 8 (Äquivalenzrelationen, IV (L))

Seien ∼₁ und ∼₂ Äquivalenzrelationen auf A. Wir setzen für alle a, b  ∈  A:

a ∼ b, falls a ∼₁ b und a ∼₂ b.

Zeigen Sie, dass ∼ eine Äquivalenzrelation auf A ist und visualisieren Sie die Äquivalenzklassen mit Hilfe von Zerlegungen.

Übung 9 (Äquivalenzrelationen, V)

Seien ∼₁ und ∼₂ Äquivalenzrelationen auf A. Wir setzen für alle a, b  ∈  A:

a R b, falls a ∼₁ b oder a ∼₂ b.

Welche Struktureigenschaften hat diese Relation R?

Übung 10 (Äquivalenzrelationen, VI)

Sei f : A → B eine Funktion, und sei ∼ eine Äquivalenzrelation auf B.

Für alle a, b  ∈  A setzen wir a ≡ b, falls f (a) ∼ f (b). Zeigen Sie, dass ≡ eine Äquivalenzrelation ist und bestimmen Sie die Äquivalenzklassen.

Übung 11 (Äquivalenzrelationen, VII)

Sei R reflexiv und transitiv auf A. Wir definieren für alle a, b  ∈  A:

a ∼ b, falls a R b und b R a.

Zeigen Sie, dass ∼ eine Äquivalenzrelation auf A ist.

Übung 12 (Ordnungen, I (L))

Sei 𝒜 ein Mengensystem auf A. Zeigen Sie, dass die Inklusion eine partielle Ordnung auf 𝒜 ist.

Visualisieren Sie sich diese Ordnung für A = { 1, 2, 3 } und 𝒜 = ℘(A).

Übung 13 (Ordnungen, II)

Sei ≤ eine partielle Ordnung auf A. Wir setzen für alle a, b  ∈  A:

a ≤* b, falls b ≤ a.

Zeigen Sie, dass ≤* eine partielle Ordnung ist, und dass ≤* linear ist, falls dies für ≤ gilt. Sind ≤ und ≤* für lineare Ordnungen immer isomorph?

Übung 14 (Ordnungen, III)

Seien (A, ≤) und (B, ≤) linear geordnet, und es gelte A ∩ B = ∅.

Sei C = A ∪ B. Wir definieren für alle a, b  ∈  C:

a ≤ b, falls (a, b  ∈  A ∧ a ≤ b) ∨ (a, b  ∈  B und a ≤ b) ∨ (a  ∈  A ∧ b  ∈  B).

Zeigen Sie, dass ≤ eine lineare Ordnung auf C ist und visualisieren Sie diese Ordnung.

Übung 15 (Ordnungen, IV)

Seien (A, ≤) und (B, ≤) linear geordnet. Sei C = A × B. Wir definieren für alle (a₁, b₁), (a₂, b₂)  ∈  C:

(a₁, b₁) ≤ (a₂, b₂), falls b₁ ≤ b₂ ∨ (b₁ = b₂ ∧ a₁ ≤ a₂).

Zeigen Sie, dass ≤ eine lineare Ordnung auf C ist und visualisieren Sie diese Ordnung.

Übung 16 (Funktionen, I (L))

Seien f : A → B, g : B → C, h : C → D Funktionen. Zeigen Sie:

h ∘ (g ∘ f) = (h ∘ g) ∘ f.

Übung 17 (Funktionen, II)

Zeigen Sie:

(i)	Ist f : A → B injektiv, so ist f : A → rng(f) bijektiv.

(ii)	Ist f : A → B bijektiv, so gibt es ein g : B → A bijektiv mit g ∘ f = id_A.

(iii)

Ist f : A → B surjektiv, so existiert ein injektives g : B → A.

(iv)	Sind f : A → B, g : B → C bijektiv, so ist g ∘ f : A → C bijektiv.

Übung 18 (Funktionen, III)

Seien f : A → B und g : B → C bijektiv. Zeigen Sie:

(g ∘ f)⁻¹ = f ⁻¹ ∘ g⁻¹.

Übung 19 (Funktionen, IV (L))

Sei f : A → B mit einer nichtleeren Menge A. Zeigen Sie, dass die folgenden Aussagen äquivalent sind:

(i)	f : A → B ist injektiv.

(ii)	Es gibt ein g : B → A mit g ∘ f = id_A.

Formulieren und beweisen Sie eine ähnliche Äquivalenz für Surjektionen.

Übung 20 (Funktionen, V)

Sei f : A → B. Zeigen Sie:

(i)	f [ f ⁻¹[ X ] ] ⊆ X	für alle X ⊆ B,
(ii)	f ⁻¹[ f[ X ] ] ⊇ X	für alle X ⊆ A,
(iii)	f[ X − Y ] ⊇ f[ X ] − f[ Y ]	für alle X, Y ⊆ A,
(iv)	f ⁻¹[ X − Y ] = f ⁻¹[ X ] − f ⁻¹[ Y ]	für alle X, Y ⊆ B,
(v)	f[ ⋂ 𝒳 ] ⊆ ⋂ { f[ X ] \| X  ∈  𝒳 }	für alle 𝒳 ⊆ ℘(A), 𝒳 ≠ ∅,
(vi)	f[ ⋃ 𝒳 ] = ⋃ { f[ X ] \| X  ∈  𝒳 }	für alle 𝒳 ⊆ ℘(A),
(vii)	f ⁻¹[ ⋂ 𝒳 ] = ⋂ { f ⁻¹[ X ] \| X  ∈  𝒳 }	für alle 𝒳 ⊆ ℘(B), 𝒳 ≠ ∅,
(viii)	f ⁻¹[ ⋃ 𝒳 ] = ⋃ { f ⁻¹[ X ] \| X  ∈  𝒳 }	für alle 𝒳 ⊆ ℘(B).

(Zur Vereinfachung können Sie die Aussagen (v) − (viii) zunächst für X ∩ Y und X ∪ Y statt allgemeiner ⋂ 𝒳 und ⋃ 𝒳 formulieren und beweisen.)

Zeigen Sie, dass die Gleichheit in (i), (ii), (iii) und (v) im Allgemeinen nicht gilt. Unter welcher Voraussetzung an X gilt Gleichheit in (i)? Unter welcher Voraussetzung an f gilt Gleichheit in (ii), (iii) und (v)?

Übung 21 (Wohldefiniertheit und Kongruenzrelationen, I (L))

Sei R eine reflexive und transitive Relation auf A, und sei ∼ die wie oben definierte Äquivalenzrelation, d. h. für alle a, b  ∈  A gilt a ∼ b genau dann, wenn a R b und b R a. Wir definieren nun für alle a/∼, b/∼  ∈  A/∼:

a/∼ ≤ b/∼, falls a R b.

Zeigen Sie, dass ≤ eine wohldefinierte partielle Ordnung auf A/∼ ist.

Übung 22 (Wohldefiniertheit und Kongruenzrelationen, II)

Sei m ≥ 1 eine natürliche Zahl. Für ganze Zahlen a, b definieren wir:

a ≡ b, falls |a − b| ist ohne Rest durch m teilbar.

Zeigen Sie, dass ≡ eine Kongruenzrelation für die Addition und die Multiplikation auf den ganzen Zahlen ist.

Übung 23 (Isomorphismen, I (L))

Sei ≤ eine partielle Ordnung auf A. Wir definieren F : A → ℘(A) durch

F(a) = { b  ∈  A | b ≤ a } für alle a  ∈  A.

Sei 𝒜 = rng(F). Zeigen Sie, dass F ein Isomorphismus zwischen (A, ≤) und (𝒜, ⊆) ist.

Übung 24 (Isomorphismen, II)

Sei (A, R, ∘_A, c_A) isomorph zu (B, S, ∘_B, c_B), und sei (B, S, ∘_B, c_B) isomorph zu (C, T, ∘_C, c_C). Zeigen Sie, dass (A, R, ∘_A, c_A) isomorph zu (C, T, ∘_C, c_C) ist.