Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2016 / Logik und Diskrete Strukturen / Material / Induktion, Ordnungen, Verbände (Vorlesungsnotizen)


Inhaltsbereich

Induktion, Ordnungen, Verbände (Vorlesungsnotizen)

Vorlesungsnotizen zu Induktion, Ordnungen und Verbänden.

Plain Text icon ordnungen.txt — Plain Text, 12 KB (13101 bytes)

Dateiinhalt

Persönliche Notizen zur Vorbereitung der LDS Vorlesung.
Diese Notizen waren 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

 
 Induktion 
===========

A(0) ∧ (∀n∈N.(A(n)⇒A(n+1))  ⇒  ∀x∈N.A(x)

 | Induktionsanfang / Induktionsverankerung
       | Induktionsschluß
              | Induktionsannahme oder Induktionshypothese (IA oder IH)
         | Induktionsvariable

Verallgemeinerung:         
A(k) ∧ (∀n∈N.(n≥k∧A(n)⇒A(n+1))  ⇒  ∀x∈N.x≥k⇒A(x)

Beispiel zur vollständigen Induktion:

Definition: n-te harmonische Zahl H_n:
       n 
H_n=   Σ  1/i  
      i=1    
...also n-te Partialsumme der haromischen Reihe.    
    
H_0 nicht definiert     
H_1 = 1    
H_2 = 1 + 1/2    
H_3 = 1 + 1/2 + 1/3    
H_4 = 1 + 1/2 + 1/3 + 1/4

Wir zeigen:
  1 + n/2 ≤ H_(2^n)
  
Beweis: 
  P(x) : 1 + n/2 ≤ H_(2^n)
  
Induktionsanfang: P(1)
  Zu zeigen: 1+1/2 ≤ 1 + 1/2 
    Stimmt.
Induktionsschluß:
  Sei n' ∈ N fest, aber beliebig.
  Wir nehmen P(n') an. (H1)
  1 + n'/2 ≤ H_(2^n')    
                                      2^(n'+1)
  Zu zeigen P(n'+1):  1 + (n'+1)/2 ≤  Σ       1/i
                                      i=1
  Es ist
   2^(n'+1)       2^n'     2*2^n'              2*2^n'
    Σ       1/i = Σ 1/i  + Σ 1/i    ≥ 1+n'/2 + Σ 1/i
   i=1            i=1      i=1+2^n'            i=1+2^n'
  
                     2*2^n'
      >= 1 + n'/2 + Σ  1/2*2^n' = 1 + n'2/2 = 2^n'*1/(2*2^n' )     
                     i=1=2^n'        
  
      =  1 + n'/2 + 1/2
      
Anwendungen: 
  * Stapel von Domino-Steinen an der Tischkante stapeln:
      Länge des Auslegers = Bausteinlänge/2 Σ_1^n(1/n)
      d.h. Ausleger kann beliebig weit überhängen 
      aber 2,5-fache Länge bedeutet bereits ~100 Bausteine!
  * Schnecke auf Gummiband der Länge 1m kriecht jede Nacht 10cm  am morgen wird das Band um 1m gedehnt
  
  
  
Erweiterung "Allgemeines Induktionsprinzip":

Man darf die IA nicht nur für n' selbst, sondern
auch für alle k≤n benutzen.

A(0) ∧ (∀n∈N.(∀k∈N. k≤n ⇒ A(k))⇒A(n+1))  ⇒  ∀x∈N.A(x)


Beispiel zur vollständigen Induktion:
  Anzahl der Möglichkeiten Korridor 2xn mit Fliesen 2x1 zu belegen?
  
  Behauptung: Korridor der Länge n erlaubt Fn Möglichkeiten
    wobei 
      F0 = 1
      F1 = 1
      Fn = Fn-1 + Fn-2
    also Fn = n-te Fibonacchi Zahl
 
   1,1,2,3,5,8,13,21,34

  Beweis:
    Induktionsverankerung:
      P(0)=1 trivial
      P(1)=1 trivial
      P(2)=2 trivial, durch Aufzählen
    Induktionsschluß:
      Korridor mit Länge n, mit n f.a.b.
      Für das erste Feld gibt es genau 2 Möglichkeiten:
      Fall 1): Fliese | 
        Damit verringert sich die Länge des Korridors um 1.
        Nach Annahme der Induktionshypothese gibt F(n-1) Möglichkeiten
        in diesem Fall.
      Fall 2): Fliesen =
        Damit verringert sich die Länge des Korridors um 2.
        Nach Annahme der Induktionshypothese gibt F(n-2) Möglichkeiten
        in diesem Fall.
      Die Fälle überlappen nicht, d.h. die Möglichkeiten beider Fälle
      addieren sich für die Anzahl der gesamten Möglichkeiten:
        F(n-1)+F(n-2) 
      Dies ist aber die Definition der n-ten Fibonacchi Zahl, wie benötigt.  

  
Beispiel zur vollständigen Induktion:
  (Turnier aus Buch)
  n Teams spielen jeder gegen jeden.
  Es gebe kein Unentschieden als Ergebnis.
  
  Behauptung: Die Team können angeordnet werden als T1,T2,T3,...,Tn so dass Ti das Team Ti+1 besiegt hat.
  
     A B C D 
   A   ← ^ ←      A >     B > C      
   B ^   ← ^      A > D > B > C
   C ← ^   ^
   D ^ ← ←
  
  Beweis durch allgemeine Induktion:

  Induktionsanfang:
    P(1) ist trivial.
  
  Induktionsschluß:
  Zu zeigen: Sei n∈N f.a.b., P(n+1).
  Induktionsannahme: ∀k≤n.P(k)
    
  Wähle ein Team a aus den n+1 Teams beliebig aus.
  Sei S die Menge der Sieger gegen a und
  sei V die Menge der Verlierter gegen a.
  Es gilt |S|=m≤n und |V|=k≤n
  
  Anwendungen der Induktionsannahme auf S liefert Anordnung S1,S2,..,Sm.
  
  Anwendungen der Induktionsannahme auf V liefert Anordnung V1,V2,..,Vk.
  
  Es gilt Sm > A > V1.
  Damit ist die verlangte Anordnung aller Teams:
  S1,S2,..,Sm,A,V1,V2,..,Vk

  Spezialfälle: k=0 oder m=0.
  
  
  
 Ordnungen und Verbände (Buch Kapitel 1.4)
==========================================  

(Überleitung Ordnungen)

Eine Relation auf A heisst 

. reflexiv, wenn ∀ x∈A.xRx
. symmetrisch, wenn ∀ x,y∈A.xRy=>yRx
* antisymmetrisch, wenn ∀ x,y∈A.xRy=>yRx=>x=y
. transitiv, wenn ∀ x,y,z∈A.xRy=>yRz=>xRz


Beispiele:
 Freundschaft, Größenunterschied<5cm,  ist i.A. nicht transitiv
 Verwandschaft ist i.A. transitiv

Definition:
 Eine Relation R ⊆ AxA auf einer Menge A heisst 
 _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 ={(b,a),(a,c),(c,d),(c,e)}
  R+={(b,a),(a,c),(c,d),(c,e),(b,c),(b,d),(a,d),(a,e),(b,e)}
  
  
  
Definition:
  Reflexive, transitive Hülle
    
  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).

Beispiel: Hasse-Diagramm von "⊆" auf Pot({1,2,3})
  
Beispiel:
  A = {2,3,4,5,6,24,25,75}
  xRy ↔ x|y (Teilbarkeit}
  
  Dies ist eine partielle Ordnung! (überprüfen)

   24     75
  /  \   / | 
  4  6  / 25
  | /\ /   |
  2   3    5


NB: Bild nicht eindeutig, mal sieht man Symmetrie, mal nicht. 
    
=========================
 Ende Vorlesung 26.04.16
=========================

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

Beispiele:
  N, ≥
                                                                                   |
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. "⊑" ⊆ "≺="
                                                                                   
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.
  x,y,∈A 
  z∈A heisst _obere_Schranke von x und y, wenn 
  x⊑z und y⊑z
  
  z∈A heisst _kleinste_obere_Schranke_ (Supremum, LUB) von x und y
    - z ist obere Schranke von x,y
    - Für jede obere Schranke w von x und y gilt z⊑w
  
    
  Analog dazu:
  z∈A heisst _untere_Schranke von x und y, wenn 
  x⊒z und y⊒z
  
  z∈A heißt _größte_untere_Schranke_ (Infimum, GLB) von x und y
    - 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

                     
Beweisprinzipien direkt aus der Definition:
   x ⊑ sup(x,y)
   y ⊑ sup(x,y) 
   x⊑z und y⊑z dann sup(x,y) ⊑ z
   
Analog:
   inf(x,y) ⊑ x
   inf(x,y) ⊑ y
   z⊑x und z⊑y dann z ⊑ inf(x,y)


Definition:
  Ein _Verband_ (lattice) ist eine partiele Ordnung ⊑ auf A,
  welche größtes und kleinestes Element besitzt  (⊤,⊥)
  und Supremum und Infimum von je zwei Elementen x,y∈A existieren.
  
Beispiel: 
  * (⊆,Pot({1,2,3})) ist ein _Verband_mit 
    ⊤={1,2,3} ⊥={}
    sup(x,y) = x∪y  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)
   
   
Definition
  Ein Verband heißt _distributiv_, falls gilt
    * inf(x,sup(y,z)) = sup(inf(x,y),inf(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.   
   
Beispiele
  + Potenzmengenverbände sind distributiv
  + Teilermengenverbände sind distributiv

Nicht jeder Verband ist distributiv:  
  Beweisversuch:
    sup(x,inf(y,z)) ⊑ inf(sup(x,y),sup(x,z))   (diese Richtung geht)
    folgt mit 3 aus x⊑ inf(sup(x,y),sup(x,z)) und inf(y,z)⊑inf(sup(x,y),sup(x,z))
    folgt mit 3 aus x⊑sup(x,y) und x ⊑ sup(x,z) und  inf(y,z) ⊑ sup(x,y) und inf(y,z)⊑sup(x,z)
                      okay          okay           inf(y,z) ⊑ y ⊑ sup(x,y)    inf(y,z) ⊑ z ⊑ sup(x,z)          
                          
    inf(sup(x,y),sup(x,z)) ⊑ sup(x,inf(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(⊥,⊥) = ⊥
   
Jeder nicht-distributiver Verband enthält N5 oder M3 als Unterverband 

Artikelaktionen


Funktionsleiste