Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2017 / Logik und Diskrete Strukturen / Material / K03 Ordnungen und Verbände


Inhaltsbereich

K03 Ordnungen und Verbände

Entspricht Kapitel 1.4 aus A.Steger: Ordnungen, Verbände, Hasse-Diagramm, Supremum, Infimum

Plain Text icon K03_Ordnungen_Verbände.txt — Plain Text, 9 KB (9673 bytes)

Dateiinhalt

Persönliche Notizen zur Vorbereitung der LDS Vorlesung. Diese Notizen waren ursprünglich nicht zur Herausgabe gedacht und sind entsprechend mit Vorsicht zu genießen. Es wird dringend empfohlen, dass Buch zu verwenden:

Angelika Steger: Diskrete Strukturen. 
Band 1: Kombinatorik, Graphentheorie, Algebra.
2. Auflage, Springer 2007, 978-3-540-46660-4


 Ordnungen und Verbände (Buch Kapitel 1.4)
==========================================  

Definition:
 Eine Relation R ⊆ AxA auf einer Menge A heißt 
 _partielle_Ordnung_, wenn R reflexiv, transitiv, antisymmetrisch ist.
 (engl. auch "poset" für "partially ordered set")

Notation:
  Partielle Ordnungen werden meist in Infix notiert,
  insbesondere duch Symbole ≺, ⊑, ≤ 
  
Beispiele:
  "≤" auf N
  "⊆" auf Mengen, z.B. Pot({1,2,3})
 
 
Definition: Transitive Hülle
  Ist R⊆AxA eine beliebige Relation, so ist die 
  _transitive_Hülle_ R⁺ ⊆ AxA von R definiert durch 
  R⁺ = {(a,c) | Es gibt n∈N Element aus A mit aRz1, z1Rz2, ... znRc }
  
Beispiel:
  R ={(a,b),(b,c),(c,d),(c,e)}
  R⁺={(a,b),(b,c),(c,d),(c,e),(a,c),(a,d),(a,e),(b,d),(b,e)}
  
  
Definition: Reflexive, transitive Hülle
  Die _reflexiv-transitive_Hülle_ ist definiert durch
  R* = R⁺ ∪ {(a,a) | a∈A}
  
Es gilt:
  R⁺ ist immer transitiv
  R* ist immer reflexiv und transitiv
  
Es gilt:
  Ist S⊆AxA transitiv und R⊆S so folgt dass R⁺⊆S. 
  Man sagt: R⁺ ist kleinste transitive Relation, welche R umfasst,
  
  
Achtung: reflexiv, transitive Hülle einer antisymmetrische Relation
         ist nicht notwendigerweise antisymmetrisch! (↯ Buch)

Bsp.:   R={(1,2),(2,3),(3,1)} ist antisymmetrisch, aber R⁺ ist es nicht mehr
  


Hasse Diagramme dienen der Veranschaulichung eine partiellen Ordnung.
(Helmut Hasse (*1898; †1979), deutscher Algebraiker und Zahlentheoretiker)

Linien zeigen an, welche Elemente in Relation stehen, wobei "kleinere" Elemente weiter "unten" sind: 
         y
(x,y)∈R: |  
         x
Transitivität und Reflexivität werden nicht eingezeichnet, da ohnehin leicht zu sehen.

NB: Dies geht, denn wegen der Antisymmetrie der Relation gibt es keine "Zyklen": 
    Angenommen xRy, yRz und zRx dann wegen der Transitivität
    folgt xRz und mit zRx folgt x=z 
    aufgrund der Antisymmetrie (und auch x=y).

Beispiele: 
  ① Hasse-Diagramm von "⊆" auf Pot({1,2,3})
  ② A = {2,3,4,5,6,24,25,75} mit xRy ↔ x|y (Teilbarkeit}  
    Dies ist eine partielle Ordnung! 
            24     75
            /  \   / | 
            4  6  / 25
            | /\ /   |
            2   3    5
            
NB: Hasse-Diagramm ist nicht eindeutig. Je nachdem, wie es gezeichnet wird, kann man Symmetrien sehen oder auch nicht.


Definition: 
  Eine partielle Ordnung ⊑ ⊆ AxA ist eine
  _totale_ oder _lineare_ Ordnung, falls gilt:
  ∀x,y∈A , x⊑y ∨ x⊒y 

Beispiele:
  N, ≥
                                                                                   
NB: Bezeichnung "lineare" Ordnung aufgrund des Hasse Diagramms einer totalen Ordnung:  |
                                                                                   
                                                                                                                                                                      
Definition:
    ≺= ist _lineare_Erweiterung_ einer partiellen Ordnung ⊑ wenn
    ≺= eine totale Ordnung ist und ≺= die Ordnung ⊑ erweitert, d.h. "⊑" ⊆ "≺="
NB: Im Allgemeinen gibt es mehrere Erweiterung.

Beispiel: 
  x|y (Teilbarkeit) wird von x≤y linear erweitert.

  
Definition:
  Sei ⊑ eine partielle Ordnung auf A.
  x∈A heißt _maximales_ Element falls es kein y∈A gibt mit x⊑y.
  Analog:
  x∈A heißt _minimales_ Element falls es kein y∈A gibt mit y⊑x.
                                
Definition:                                                                                    
  Sei ⊑ eine partielle Ordnung auf A.
  x∈A heißt größtest Element (_Maximum_),
  wenn für alle y∈A gilt: y⊑x.
  Analog dazu: kleinstes Element (_Minimum_)
  
Bemerkung:
  Das größte Element einer partiellen Ordnung ist eindeutig bestimmt,
  ebenso das kleinste Element.
  
Beweis:
  Seien x,x' ∈ beide "größte" Elemente,
  d.h. ∀y∈A.y⊑x ∧ ∀y∈A.y⊑x' (H1)
  Aus H1.1 folgt x'⊑x       (H2)
  Aus H1.2 folgt x⊑x'       (H3)
  Aus H2 und H3 folgt mit der Antisymmetrie x=x'
  
Beispiele: 
  * {1,2,3}  ist  Maximum in (⊆,Pot({1,2,3}))
  * 75 ist _kein_ Maximum (|,{2,3,4,5,6,24,25,75})

  
Definition:
  Sei ⊑ eine partielle Ordnung auf A und x,y,∈A, 
  ein z∈A heisst _obere_Schranke_ von x und y, wenn x⊑z und y⊑z.
  
  Ein z∈A heisst _kleinste_obere_Schranke_ 
  (auch: Supremum, LeastUpperBound, ∨) von x und y, wenn  
    - z ist obere Schranke von x,y
    - Für jede obere Schranke w von x und y gilt z⊑w
    
  Analog dazu:
  Ein z∈A heißt _untere_Schranke von x und y, wenn x⊒z und y⊒z.
  Ein z∈A heißt _größte_untere_Schranke_ 
  (auch: Infimum, GreatestLowerBound, ∧) von x und y, wenn
    - z ist untere Schranke von x,y
    - Für jede untere Schranke w von x und y gilt w⊑z                       
    
Es gilt: 
  Suprema und Infima sind eindeutig bestimmt, falls sie existieren.
                  
  Wir schreiben auch x⊔y oder sup(x,y) oder x∨y für das Supremum z                       
                     x⊓y oder inf(x,y) oder x∧y für das Infimum z

[Übung: Zeige das Suprema eindeutig bestimmt sind
  Es seien s₁ und s₂ Suprema für x und y.
  s₁,s₂ sind obere Schranken, d.h. x⊑s₁, y⊑s₁, x⊑s₂, y⊑s₂ 
  s₁,s₂ sind kleinste obere Schranken, d.h. s₁⊑s₂ und s₁⊒s₂
  Aus Antisymmetrie folgt s₁=s₂
]
                     
Beweisprinzipien direkt aus der Definition:
  S1) x ⊑ x⊔y    ( x ⊑ sup(x,y) )
  S2) y ⊑ x⊔y 
  S3) x⊑z ∧ y⊑z ⇒ x⊔y ⊑ z
   
  I1) x⊓y ⊑ x    ( inf(x,y) ⊑ x )
  I2) x⊓y ⊑ y
  I3) z⊑x ∧ z⊑y ⇒ z ⊑ x⊓y
   
   
Definition:
  Ein _Verband_ (lattice) ist eine partielle Ordnung ⊑ auf A,
  welche größtes und kleinestes Element besitzt  (⊤,⊥)
  und Supremum und Infimum von je zwei Elementen x,y∈A existieren.

NB: In der Literatur (z.B. A.Steger) wird manchmal auf ⊤,⊥ verzichtet. 
Manchmal werden auch ⊓ (Infimum) und ⊔ (Supremum) als grundlegend angenommen, welche den Gesetzen für Assoziativität, Kommutativität und Absorption genügen (in diesem Fall kann man die Ordnungsrelation ableiten x⊑y gdw. x⊓y=x; wir haben Relation ⊑ als grundlegend angenommen).
  
Beispiel: 
  * (⊆,Pot({1,2,3})) ist ein _Verband_mit 
    ⊤={1,2,3}, ⊥={}, sup(x,y)=x∪y und inf(x,y)=x∩y

  * jeder Mengenverband mit ⊂ ∩ ∪
    
  * (|,Teilermenge eine Zahl, z.B. 60 oder 60)
    ⊤=60, ⊥=1, sup(x,y)=kgV(x,y), inf(x,y)= ggT(x,y)
    
    60=2*2*3*5 {1,2,3,4,5,6,10,12,15,20,30,60}
    
                                   24
    24=1*2*3*4*6*8*12             /  \
                                  8  12
                                  |/ |
                                  4  6
                                  |/ |
                                  2  3
                                   \/
                                   1
                                   
Satz:
  In jedem Verband sind inf(,) und sup(,) assoziativ und kommutativ.
  Außerdem gilt:
    sup(⊥,x)=x  sup(⊤,x)=⊤
    inf(⊥,x)=⊥  inf(⊤,x)=x  
    
Beweis:
  Zu zeigen: inf(x,inf(y,z)) = inf(inf(x,y),z)
  1) Zeige inf(x,inf(y,z)) ⊑ inf(inf(x,y),z)
  Mit Beweisprinzip 3:     
    inf(x,inf(y,z)) ⊑ inf(x,y)
      Mit Beweisprinzip 3:
        inf(x,inf(y,z)) ⊑ x  nach Beweisprinzip 1
        inf(x,inf(y,z)) ⊑ inf(y,z) ⊑ y nach Beweisprinzip 1 und mit Transitivität
    inf(x,inf(y,z)) ⊑ z 
        inf(x,inf(y,z)) ⊑ inf(y,z) ⊑ z nach Beweisprinzip 1 und mit Transitivität
  
  2) Zeige inf(x,inf(y,z)) ⊒ inf(inf(x,y),z)  
    (Folgt analog)
   

Absorbtion:
  sup(x,inf(x,y)) = x
  inf(x,sup(x,y)) = x
  
   
Definition
  Ein Verband heißt _distributiv_, falls gilt
    * x⊓(y⊔z) = (x⊓y)⊔(x⊓z)
    * sup(x,inf(y,z)) = inf(sup(x,y),sup(x,z))
  Beide Aussagen sind gleichwertig, d.h. aus der einen folgt die andere Aussage.   
   
Beispiele
  * Potenzmengenverbände sind distributiv
  * Teilermengenverbände sind distributiv

Nicht jeder Verband ist distributiv:  
  Beweisversuch:
    Zeige zunächt: x⊔(y⊓z) ⊑ (x⊔y)⊓(x⊔z)   (diese Richtung geht)
    Die gilt mit S3, falls wir 
    x⊑(x⊔y)⊓(x⊔z) und y⊓z⊑(x⊔y)⊓(x⊔z) zeigen können.
      Ersteres folgt mit I3 aus x⊑x⊔y und x⊑x⊔z, 
      welche jeweils aus S1 folgen.
      Das Zweite folgt mit I3 aus y⊓z⊑x⊔y und y⊓z⊑x⊔z,
        Aus I1 folgt y⊓z⊑y und aus S2 y⊑x⊔y,
        damit folgt y⊓z⊑x⊔y ais der Transitivität von ⊑.
        Es verbleibt noch y⊓z⊑x⊔z zu zeigen, welches
        ebenfalls aus der Transitivität, y⊓z⊑z (I2) und z⊑x⊔z (S2) folgt.
                   
    Zeige noch: (x⊔y)⊓(x⊔z) ⊑ x⊔(y⊓z)   
      (diese Richtung scheitert)
  
Beispiele nicht-distributiver Verbände:
  N5       M3
  
   ⊤        ⊤
  / \      /|\
  a  c    a b c   
  |  |     \|/
  |  b      ⊥
  \ /
   ⊥
   
N5:  inf(sup(b,a),sup(b,c)) = inf(⊤,c) = c NICHT ⊑ b = sup(b,⊥) = sup(b,inf(a,c)) ↯ 
     inf(c,sup(b,a)) = inf(c,⊤) = c ≠ b = sup(b,⊥) = sup(inf(c,b),inf(c,a))
     
M3:  inf(a,sup(b,c))= inf(a,⊤) = a
     sup(inf(a,b),inf(a,c)) = sup(⊥,⊥) = ⊥
   
Satz:   
Jeder nicht-distributiver Verband enthält N5 oder M3 als Unterverband 

  

Artikelaktionen


Funktionsleiste