Übungen
Übung 1
Sei A eine Menge. Zeigen Sie, dass sowohl die echte Inklusion ⊂ als auch die umgekehrte echte Inklusion ⊃ partielle Ordnungen auf der Potenzmenge ℘(A) = { B | B ⊆ A } von A sind.
Übung 2
Betrachten Sie die Hasse-Diagramme zur Teilbarkeitsrelation. Welche allgemeinen Eigenschaften können Sie feststellen? Beweisen Sie diese Eigenschaften. Welche Eigenschaften gelten auch für ein Hasse-Diagramm der Teilbarkeitsrelation auf ℕ*?
Übung 3
Seien (A, <), (B, <) partielle Ordnungen. Wir setzen für alle (a, b), (c, d) ∈ A × B:
(a, b) < (c, d) falls a < c ∧ b < d.
(a) | Zeigen Sie, dass < eine partielle Ordnung auf A × B ist. |
(b) | Zeichnen Sie ein Diagramm zur Illustration der Konstruktion. |
(c) | Ist < auf A × B linear, falls die Ordnungen auf A und B linear sind? |
Übung 4
Sei A eine Menge, und sei
R = { ∼ | ∼ ist eine Äquivalenzrelation auf A }.
Wir setzen für alle ∼1, ∼2 ∈ R:
∼1 ≤ ∼2 falls ∼1 ist eine Verfeinerung von ∼2.
Zeigen Sie, dass ≤ eine partielle Ordnung auf R ist.
Übung 5
Seien (A, <), (B, <) lineare Ordnungen. Zeigen Sie, dass die lexikographischen Ordnung <lex eine lineare Ordnung auf A × B ist.
Übung 6
Sei A eine Menge, und sei SeqA die Menge aller endlichen Folgen in A. Zeigen Sie, dass die echte Anfangsstückrelation ⊲ eine partielle Ordnung auf SeqA ist.
Übung 7
Zeigen Sie, dass die lineare Ordnung <lex auf der Menge Seqℤ aller endlichen Folgen in ℤ dicht ist.
Übung 8
Sei (A, <) eine Ordnung, und sei Aℕ = { (an)n ∈ ℕ | an ∈ A für alle n } die Menge aller unendlichen Folgen in A. Wir setzen für alle (an)n ∈ ℕ, (bn)n ∈ ℕ:
(an)n ∈ ℕ < (bn)n ∈ ℕ falls an < bn für alle n ∈ ℕ.
Zeigen Sie, dass < eine partielle Ordnung auf Aℕ ist.
Übung 9
Sei G = (E, K) ein gerichteter kreisfreier Graph. Wir setzen für alle a, b ∈ E:
a ≤ b falls es gibt einen Weg von a nach b in G.
Zeigen Sie, dass ≤ eine partielle Ordnung auf E ist.
Übung 10
Sei A eine Menge. Wir ordnen ℘(A) durch die Inklusion ⊆. Zeigen Sie, dass für alle 𝒜 ⊆ ℘(A) gilt:
sup(𝒜) = ⋃ 𝒜 = { a ∈ A | es gibt ein B ∈ 𝒜 mit a ∈ B },
inf (𝒜) = ⋂ 𝒜 = { a ∈ A | für alle B ∈ 𝒜 gilt a ∈ B }.
Übung 11
Zeigen Sie, dass die folgenden Mengen unter den üblichen linearen Ordnungen auf den Zahlen dicht sind:
A = { x ∈ ℝ | x ist irrational },
B = { q ∈ ℚ | x besitzt eine endliche Dezimaldarstellung },
C = { q ∈ ℚ | x besitzt keine endliche Dezimaldarstellung }.
Übung 12
Seien R, S, T Relationen auf A. Zeigen Sie:
(R ∘ S) ∘ T = R ∘ (S ∘ T).
Übung 13
Eine Funktion f : A → B ist als Menge von geordneten Paaren eine Relation auf C = A ∪ B, da f = { (a, f (a)) | a ∈ A } ⊆ C2. Wie hängt die Komposition von Funktionen mit der Komposition von Relationen zusammen?
Übung 14
Sei A eine Menge, und sei R eine reflexive Relation auf A. Zeigen Sie:
R0 ⊆ R1 ⊆ … ⊆ Rn ⊆ …
Übung 15
Sei R eine Relation auf einer endlichen Menge A, und sei n = |A|. Zeigen Sie:
(a) | R+ = ⋃1 ≤ k ≤ n Rk. |
(b) | Ist R reflexiv, so gilt R* = R+ ∪ R0 = R+ = Rn − 1. |
Ist R+ ≠ ⋃1 ≤ k < n Rk in (a) möglich?
Übung 16
Sei A eine Menge, und sei R eine Präordnung auf A, d. h. eine reflexive und transitive Relation auf A. Wir setzen für alle a, b ∈ A:
a ∼ b falls a R b und b R a.
Zeigen Sie, dass ∼ eine Äquivalenz auf A ist.
Übung 17
Seien A, R, ∼ wie in der vorangehenden Übung. Wir definieren nun eine Relation ≤ auf der Faktorisierung A/∼ = { [ a ] | a ∈ A } durch
[ a ] ≤ [ b ] falls a R b.
(a) | Zeigen Sie, dass ≤ eine partielle Ordnung (vom nichtstrikten Typ) auf A/∼ definiert. |
(b) | Zeichnen Sie ein Diagramm zur Illustration. |
(c) | Führen Sie die Konstruktion für die Teilbarkeitsrelation auf ℤ durch. |
Übung 18
Seien G, U ⊆ ℕ die Mengen der geraden bzw. ungeraden natürlichen Zahlen. Wir ordnen ℕ = G ∪ U durch
n < m falls n ∈ G und m ∈ U oder n, m haben gleiche Parität und n < m.
Zeigen Sie, dass < eine Wohlordnung auf ℕ ist. Welcher Form der vollständigen Induktion entspricht diese Wohlordnung?
Übung 19
Seien (A, <) und (B, <) Wohlordnungen. Zeigen Sie, dass die lexikographischen Ordnungen <lex und <lex Wohlordnungen auf A × B sind.