Große Übung 1 - Theoretische Informatik 1

Jede kleinste obere Schranke ist eindeutig.

• Es sei ⟨D,≤⟩ ein Verband.
• Sei A ⊆ D eine Teilmenge, sodass ∐A existiert.
• Sei x ∈ D eine kleinste obere Schranke von A.
• Weil ∐A eine obere Schranke von A ist, gilt x ≤ ∐A.
• Weil x eine obere Schranke von A ist, gilt ∐A ≤ x.
• ≤ ist antisymmetrisch, daher x = ∐A.

Wenn ∐D existiert, dann ist ∏∅ = ∐D.

• Es sei ⟨D,≤⟩ ein Verband mit ⊤ := ∐D ∈ D.
• ⊤ erfüllt unter Anderem ∀a ∈ D: a ≤ ⊤.
• Für ∏∅ soll gelten: (∀a ∈ ∅:∏∅ ≤ a) ∧ (∀d ∈ D: (∀a ∈ ∅: d ≤ a) → d ≤ ∏∅).
• (Nachtrag:) ∀a:(a ∉ ∅ ∨ ∏∅ ≤ a) ∧ ∀d:(d ∉ D ∨ ¬∀a:(a ∉ ∅ ∨ d ≤ a) ∨ d ≤ ∏∅).
• Effektiv soll gelten: ∀d ∈ D: d ≤ ∏∅, denn alle Elemente sind untere Schranken von ∅.
• Weil ⊤ diese Anforderung erfüllt, ist ⊤ eine größte untere Schranke von ∅.
• Durch Eindeutigkeit folgt ∏∅ = ⊤.

Wenn ∐A existiert, dann existiert auch ∐(A ∪ {b}).

• Es sei ⟨D,≤⟩ ein Verband, b ∈ D und A ⊆ D mit ∐A ∈ D.
• ∐A ⊔ b ist eine obere Schranke von A ∪ {b}:
  • ≤ ist transitiv, daher ∀a ∈ A: a ≤ ∐A ≤ ∐A ⊔ b,
  • außerdem b ≤ ∐A ⊔ b.
• Sei x eine obere Schranke von A ∪ {b}.
  • x ist auch eine obere Schranke von A, daher ∐A ≤ x.
  • Zusammen mit b ≤ x schließen wir ∐A ⊔ b ≤ x.
• Also ist ∐A ⊔ b eine kleinste obere Schranke von A ∪ {b}.
• Durch Eindeutigkeit folgt ∐A ⊔ b = ∐(A ∪ {b}).

Wenn A nicht leer, aber endlich ist, existiert ∐A.

• Es sei ⟨D,≤⟩ ein Verband.
• Induktionsanfang:
  • ∐{a} = a (unter anderem weil ≤ reflexiv ist).
• Induktionsschluss:
  • Sei ∅ ≠ B ⊆ D endlich mit ∐B ∈ D und sei c ∈ D.
  • Dann ist ∐(B ∪ {c}) ∈ D, wie oben gezeigt.
• Mit Induktion folgt die Aussage für jedes nicht-leere und endliche A ⊆ D.

Jeder nichtleere endliche Verband ist vollständig.

• Sei ⟨D,≤⟩ ein Verband, D endlich und A ⊆ D.
• A ist endlich.
• Falls A nicht leer ist, folgt ∐A ∈ D und ∏A ∈ D wie oben gezeigt.
• Das schließt D ein.
• Falls A leer ist, gilt ∐∅ = ∏D und ∏∅ = ∐D wie oben gezeigt.
• Folglich existieren ∐A und ∏A für alle A ⊆ D.

⟨Ƥ(M),⊆⟩ ist ein vollständiger Verband.

• ⊆ ist eine partielle Ordnung:
  • reflexiv: X ⊆ X, denn ∀x ∈ X: x ∈ X.
  • antisymmetrisch X ⊆ Y ∧ Y ⊆ X → X = Y, durch Extensionalitäts-Axiom.
  • transitiv X ⊆ Y ∧ Y ⊆ Z → X ⊆ Z, denn mit X ⊆ Y ⊆ Z folgt ∀x ∈ X: x ∈ Y ∧ x ∈ Z.
• Jedes A ⊆ Ƥ(M) hat ∐A ∈ Ƥ(M):
  • ⋃A ist eine obere Schranke von A:
    • Sei B ∈ A, B ⊆ B ∪ ⋃(A \ {B}) = ⋃A.
  • Sei C eine obere Schranke von A. ⋃A ⊆ C:
    • Sei x ∈ ⋃A, dann gibt es B ∈ A mit x ∈ B.
    • B ⊆ C, also x ∈ C.
  • Also ∐A = ⋃A.
• Jedes A ⊆ Ƥ(M) hat ∏A ∈ Ƥ(M):
  • ⋂A ist eine untere Schranke von A:
    • Sei B ∈ A, ⋂A = ⋂(A \ {B}) ∩ B ⊆ B.
  • Sei C eine untere Schranke von A. C ⊆ ⋂A:
    • Sei x ∈ C, dann gilt x ∈ B für alle B ∈ A, weil C ⊆ B, also x ∈ ⋂A.
  • Also ∏A = ⋂A.
• Damit ist ⟨Ƥ(M),⊆⟩ vollständig.