Logik und Grundlagen
TU Wien, WS 2023/24

Tagebuch

Di 3.10.2022

Satz von Cantor.  Russell-Paradoxon.    Berry-Paradoxon.  Sprache ist wichtig!

Aussagenlogik.  Formeln.  Induktive Definition, "das sind alle", 
Formelaufbaufolge.
Belegungen, Wahrheitsfunktionen.
Eindeutige Fortsetzung von Belegungen zu Wahrheitsfunktionen.
Partielle Belegungen.  

Äquivalenz von Aussagen:  A⇒B.   A⇔B.   Tautologie, Kontradiktion. 

Naive Mengenlehre: {x,y}, {{x},{x,y}}.   Durchschnitt über eine Menge von Mengen.

Do 5.10. 

Wahrheitstabelle, DNF, KNF.
KNF als Menge von Klauseln.  Klausel als Disjunktion von Literalen.
Leere Disjunktion=falsch.  Leere Klausel. 

Vereinigung einer Menge von Mengen. Schnitt. 
Offizielle Sprache der Mengenlehre. 

Di 10.10.
Resolution:  Resolvente zweier Klauseln.
Abschluss einer Klauselmenge M unter Resolution - wird von den gleichen Belegungen erfüllt. 

Satz: Wenn M eine Menge von Klauseln ist, unter Resolution abgeschlossen,
dann ist M genau dann erfüllbar, wenn M nicht die leere Klausel enthält. 
Beweis: "erlaubte" partielle Belegungen induktiv fortsetzen.

Satz:  M unerfüllbar ⇔ Abschluss von M enthält die Leerklausel.

Paare, Relationen, Funktionen in der offiziellen Sprache der Mengenlehre. 
Die natürlichen Zahlen (als kleinste induktive Menge).
endliche und unendliche Folgen.

Do 12.10.
Kompaktheitssatz der Aussagenlogik
ω, Operationen auf ω.    0 hoch 0. 
Wohlordnung
Ordinalzahlen (mit unbewiesenen Sätzen: Vergleichbarkeit)
Ordinalzahlarithmetik (+,*)
Ist (Ord, ∈) eine Ordinalzahl?

Vn, Vω,  Vω+1. 

Sprache der Prädikatenlogik.  Symbole, Terme. 
Darstellung von Termen:  mit Bäumen; Präfix-, Postfixnotation. 

Di 17.10.
Prädikatenlogik.  b, bquer, bdach. M erfüllt phi.  

allgemeingültige Formeln: identitäsaxiome, Leibnizaxiome, Tautologien.

Substitutionsaxiom (unvollständig)

Do 19.10.
(Ein paar Worte zu mehrsortiger Logik und Logik zweiter Stufe. Später mehr dazu)

Substitution.   bdach( phi(x/s) ) =.  ...  

Erlaubte Substitution.  Substitutionsaxiom.  Distributivitätsaxiom.  Existenzaxiome. 

Di 24.10.
Formale Beweise. Beispiel. 
Deduktionstheorem. 
Generalisierunstheorem.
Einführung von Quantoren  - schwach und stark.

Do 26.10.
Feiertag

Di 31.10.
Beweis des Vollständigkeitssatzes: vollständige Theorie, Vervollständigung, Henkintheorie, Henkinisierung. Konstruktion des Henkin-Modells.

Do 2.11.
kein Feiertag, aber schulfrei. 

Di 7.11.
Kompaktheitssatz für Prädikatenlogik. Nonstandardmodell der natürlichen Zahlen. 
Elementares Untermodell.  Beispiel Q, R.  Tarski-Vaught. 
Löwenheim-Skolem. 
Pränexform.   Äquivalente Formel in Pränexform, KNF. 

Do 9.11.
Skolemisierung von Formeln. 
Substitution. Grundterme, Grundinstanzen von Formeln (=ohne freie Variable)
M... Klauseln in allquantifizierter KNF
G(M) = alle Grundinstanzen von Klauseln in M, erzeugt durch Substitution mit Grunddtermen. 
Grundresolution - aussagenlogische Resolution von Klauseln in G(M). 
Satz: M unerfüllbar genau dann, wenn G(M) aussagenlog unerfüllbar.  Herbrand-Modell.

Di 14.11.

prädikatenlogische Resolutionsableitung: Variante, Faktor, Resolvente. 
Hebelemma (unbewiesen) zum Beweis der Vollständigkeit
Berechenbarkeitstheorie: berechenbare Funktionen, entscheidbare und semi-entscheidbare Mengen.  Zusammenhänge. 

Do 16.11.

primitive Rekursion: Definition, Beispiele
mu-Rekursion.  Kleene-Normalform (Beweisskizze)
Sigma_0 Formeln, Sigma_1-Formeln

Di 21.11.
Sigma-1-Formeln sind (mod PA) unter beschränkten Quantoren abgeschlossen. Sigma-1-Mengen, Abschlusseigenschaften.  Sigma-1 Funktionen sind unter mu-Rekursion und prim.Rekursion abgeschlossen, also enthalten alle berechenbaren Funktionen. 

Do 23.11. 

Bildbereich von schwach monotonen Funktionen: entscheidbar, aber nicht uniform. 
Mengenlehre: alles ist Menge. 
Logik zweiter Ordnung?   Nicht kompakt, kein Axiomensystem verfügbar. 
Sprache der Mengenlehre.  Extensionalitätsaxiom. 
Modelle unserer Sprache.  Extension. 
Paarmengenaxiom, Vereinigungsmengenaxiom (groß/klein), Potenzmengenaxiom.
Aussonderungsaxiom.  
Beispiel eines abzählbaren Modells. (N,E). 



Di 28.11. 
Induktive Mengen.  Unendlichkeitsaxiom (mehrere Varianten). 
Formeln X=ω, a∈ω.

endlich/unendlich.  
Dedekind-Unendlichkeit, äquivalent zu "enthält Kopie von ω".

Auswahlaxiom: Potenzmenge, Familie nichtleerer Mengen. 

Lemma von Zorn, Hausdorffs Kettensatz.    Hausdorff ⇒ Zorn. 
Mengen mit endlichem Charakter. Beispiele. Teichmüller-Tukey. 

Do 30.11. 

V_n für n in omega.  V_omega, hereditär endliche Mengen. 
Transitive Hülle.  
Auswahlaxiom für paarweise disjunkte Mengen. Äquivalenz.
Teichmüller-Tukey, endlicher Charakter. 

Zorn ⇒ Teichmüller-Tukey. 
Vergleichbarkeitssatz für Mengen mit TT. 

Wohlordnungen. Anfangsabschnitt.  
W<a := {x in W:  x<a}.  W<∞:=W.

Vergleichbarkeitssatz für Wohlordnungen.  (ohne AC!)
[Lemma: f strikt monoton von W nach W ⇒ ∀x: x≤f(x)]

Di 5.12.

Rekursionssatz: für ω, für beliebige Wohlordnungen. 
f(x) = g( f[W<x] )

Lange Wohlordnungen ⇒ (AC ⇒ Wohlordnungssatz) 

Hartogs: es gibt lange Wohlordungen. 

ω0, ω1, ω2.