Algebraische Strukturen und logische Kalküle Fr 11.15 Uhr II. Sitzung Def: 〈 A , ∩ , ∪〉 Verband Ein Teilverband ist eine Algebra 〈 A1, ∩ , ∪〉 falls A1⊆ A und A1 abgeschlossen bzgl. ∩ , ∪ ist. D.h. a , b∈ A1 ⇒ a∩b & a∪b∈ A1 Halbordnungen Def: Eine algebraische Struktur 〈 A , ≤〉 heißt Halbordnung, falls für sie gilt: i. Reflexivität: a≤a ii. Transitivität: a≤b & b≤c ⇒ a≤c iii.Antisymmetrie: a≤b & b≤a ⇒ a=b Bsp: • • • • 〈ℕ , ≤〉 , 〈ℕ , ≥〉 und 〈ℕ , =〉 〈℘ A , ≤ 〉 〈 FOR /≡ , ⇔ 〉 und 〈 FOR /≡ , ⇒ 〉 〈{a , b , c}, {a , a ,b , b ,c , c ,a , c ,b , c}〉 c a≤c & b≤c a b Satz: Sei V ein Verband 〈 M , ∩ , ∪〉 . Dann ist H V =〈 M , ≤ 〉 , wobei a≤b ⇔ a∪b=b bzw. a≤b ⇔ a∩b=a , eine Halbordnung. Bew: i. Reflexivität a∪a=a ⇒ a≤a ii. Transitivität a≤b , b≤c ⇒ a∪b=b & b∪c=c ⇒ a∪c=a∪b∪c =a∪b∪c =b∪c =c ⇒ a≤c iii.Antisymmetrie a≤b , b≤a ⇒ a∪ b=b = b∪a=a Seite 1 von 3 Institut für Logik und Wissenschaftstheorie Algebraische Strukturen und logische Kalküle Fr 11.15 Uhr II. Sitzung Was beschreibt a∩b ? a∩b beschreibt das Infimum von a und b bzgl. ≤ Def: Gilt ∀ m∈M : s≤m , so heißt s untere Schranke von M. Die größte untere Schranke inf M  heißt Infimum. Ist s untere Schranke von {a , b} , so ist s≤inf {a , b} . Folg: 1) a∩b≤a a∩b≤b 2) Ist s≤a und s≤b , so s≤a∩b Bew: 1) a∩b∩a=b∩a∩a=b∩a∩a=b∩a=a∩b≤a 2) Es gelte s∩a=s und s∩b=s Betrachte s∩a∩b= s∩a∩b=s∩b=s Folglich gilt s≤a∩b=inf a , b Was beschreibt a∪b ? a∪b beschreibt das Supremum sup{a , b} bzgl. ≤ und ist dual zu Infimum. H V  ist eine Halbordung, in der a, b stets ein Infimum und ein Supremum haben. Def: Gilt ∀ m∈M : m≤s , so heißt s obere Schranke von M. Die kleinste obere Schranke sup  M  heißt Supremum. Ist s obere Schranke von {a , b} , so ist sup{a , b}≤s . Satz: Sei H =〈 M , ≤ 〉 eine Halbordung, wo für beliebige a, b stets inf {a , b} und sup{a , b} existieren. Dann ist V  H =〈 M , ∩ , ∪ 〉 , mit a∩b=inf {a , b} und a∪b=sup{a , b} bzgl. ≤ , ein Verband. Bew: ✔ ✔ ✔ a∩b=b∩a Kommutativität inf {a , b}=inf {a , b} a∩b∩c=a∩b∩c Assoziativität inf {a , inf {b , c}}=inf {a , b , c}=inf {inf {a , b} , c} a∩b∪a=a Adjektivität Bem: V H V =V und unter Umständen auch H V  H =H Seite 2 von 3 Institut für Logik und Wissenschaftstheorie Algebraische Strukturen und logische Kalküle Fr 11.15 Uhr II. Sitzung Bsp: spezielle Verbände 1 2 3 4 4 5 5 5 5 5 Seite 3 von 3 Institut für Logik und Wissenschaftstheorie