Grundbegriffe der Mathematischen Logik
WS 2005/2006
Prüfung:
Der Prüfungsstoff umfaßt:
-
Mengenlehre:
-
Die Definition von |A|<|B| und einfache Äquivalenzen/Folgerungen.
-
Die Größen bestimmter konkreter Mengen
(z.B. endliche Teilmengen von N) .
-
Rekursionstheorie:
-
Allgemeine Eigenschaften der p.r. Funktionen.
Bsp: Das Maximum zweier p.r. Funktionen ist p.r.
(Dabei ist das Maximum natürlich undefiniert, wenn eine der
Funktionen undefiniert ist).
-
Allgemeine Eigenschaften von r.e. und rekursiven Mengen
Bsp: Wenn zwei Mengen r.e. sind, dann auch ihre Vereinigung.
-
Feststellen, ob bestimmte konkrete Mengen r.e. oder rekursiv sind.
Bsp: {n: dom(phi_n) ist endlich}
-
Aussagenlogik:
Feststellen ob bestimmte Formeln erfüllbar oder Tautologie sind.
-
Prädikatenlogik:
-
Feststellen ob bestimmte Formeln erfüllbar oder gültig sind.
-
Interpretation bestimmter konkreter Formeln
Bsp: Welche Formel besagt, dass das Universum genau 2 Elemente hat.
-
Gültigkeit in einer Struktur und semantische Folgerung aus einer Satzmenge
Isomorphie und elementare Äquivalenz
-
Anzahl der Modelle einer Theorie (modulo Isomorphie).
Bsp: Signatur enthält nur einstelliges Prädikatensymbol R,
Theorie besagt daß das Universum genau 100 Elemente enthält.
-
Beispiele kategorischer und nicht-kategorischer Theorien.
-
Berechenbarkeit der first-order Folgerung:
Wann sind die Menge der Folgerungen einer Theorie r.e., wann rekursiv?
Wie hängt das mit der Menge der (endlich) erfüllbaren Sätze zusammen,
(d.h. der Sätze die ein (endliches) Modell haben?
-
Folgerungen des Vollständigkeitssatzes:
Kompaktheitssatz, Skolem Löwenheim,
Zusammenhang von beliebig grossen endlichen Modellen mit unendlichen.
Kombinationen dieser drei Sätze.
Bsp: Wenn jede endliche Teilmenge
von Sigma beliebig grosse endliche Modelle hat, dann hat
Sigma ein überabzählbares Modell.
Die Ergebnisse der schriftlichen Prüfungen:
| Termin | Sehr Gut | Gut | Befriedigend | Genügend | Nicht Genügend | gesamt |
|---|
| 2006-01-27 | 1 | 1 | 1 | 3 | 3 | 9 |
| 2006-03-03 | 2 | 1 | 2 | 3 | 4 | 12 |
| Vorlesung Zeit: |
Mittwoch 11:10-12:50 |
| Ort: |
HS 1, UZA 2 |
| Erstes Vorlesung: |
2005-10-05 |
Die Vorlesung stellt eine elementare Einführung in grundlegende
Begriffe der klassischen mathematischen Logik (d.h. Prädikatenlogik
erster Stufe) dar.
Aus dem Inhalt:
- Berechenbarkeit/Entscheidbarkeit/Komplexität:
Maschinenmodelle (Registermaschine, μ-Rekursion),
rekursiv aufzählbar im Gegensatz zu entscheidbar,
universelle Programme (Interpreter), Unentscheidbarkeit des
Halteproblems.
- Logische Sprachen: Aussagenlogik und Prädikatenlogik 1. Stufe:
Syntax und Semantik,
Kompaktheit- und Vollständigkeitssätze, Entscheidbarkeit bzw.
Komplexität.
- Arithmetik; der Gödel'sche Unvollständigkeitssatz.
- Mengenlehre:
Naive Mengenlehre (Diagonalisierung, Auswahlaxiom), ZFC.
- Falls noch Zeit ist: P/NP,
Kontinuumshypothese: Unabhängigkeit/Unbeweisbarkeit in der
Mengentheorie.
Zurück zum Seitenanfang
Zu der Vorlesung gibt es ein Proseminar, geleitet von
Heike Mildenberger.
| Proseminar Zeit: |
Dienstag 11:15-12:00 |
| Ort: |
C207 |
| Erstes Proseminar: |
2005-10-04 |
Der Besuch des Proseminars wird dringend empfohlen!
Weitere Informationen (und Übungsangaben)
Sie auf Heike Mildenbergers
Lehre-Webseite.
Zurück zum Seitenanfang
Der Hörsaal 1 des UZA 2 ist in der Ebene 1 (UG) des Geozentrums,
gleich beim Eingang Althanstraße 14, 1090 Wien.
Zurück zum Seitenanfang
Termine:
Freitag, 27. Jänner 2006 um 16:30 und Freitag, 3. März 2006 um 11:00.
Die Prüfungen sind schriftlich (multiple choice) plus
einer kurzen Besprechung (die die schriftliche
Note nicht verschlechtert). Sie haben für die Prüfung
maximal 3h (d.h. de facto beliebig lange) Zeit.
Es sind keine Unterlagen erlaubt. Die Prüfungen
finden am KGRC statt.
Man kann
die Vorlesungsprüfung bis zum Sommersemester 2007 ablegen.
Die nächste Vorlesung Grundbegriffe der Mathematischen Logik
wird vermutlich im Wintersemester 2006 von Agatha Walczak-Typke
abgehalten.
Zurück zum Seitenanfang
Formal wird nur
Mittelschulmathematik (z.B. Induktion) vorausgesetzt.
Allerdings ist zum Verständnis und vor allem zur Motivation
(wozu ist das Ganze gut?)
ein gewisses mathematisches
Grundverständnis unbedingt nötig (insbesondere ein
Gefühl für den Begriff Algorithmus und die Bedeutung des Beweises
in der Mathematik).
Es wäer auch gut, schon einmal ein Computerprogramm
geschrieben zu haben (völlig egal in welcher Programmiersprache),
und man sollte wissen, daß es überabzählbar viele
reelle, aber nur abzählbar viel natürliche Zahlen gibt.
-
Die Teilnahme am Proseminar wird dringend empfohlen.
Das Rechnen von Beispielen erleichtert das Verstehen (und damit das
Bestehen der Prüfung) enorm.
-
Diplomstudium Mathematik: Die Vorlesung (aber nicht
das Proseminar) ist Pflichtfach im 2. Abschnitt.
Das Proseminar ist ein Wahlfach.
Man kann die Vorlesung natürlich auch gerne schon im
1. Abschnitt besuchen (wenn man sich die Voraussetzungen zutraut).
Die Vorlesung wird dann aber erst für den 2. Abschnitt angerechnet.
-
Unterrichtsfach Mathematik:
Die Vorlesung ist ein Wahlfach im 2. Abschnitt.
Das Proseminar kann (wie jede Mathematik LVA)
als freies Wahlfach verwendet werden.
Die Inhalte der Vorlesung sind hervorragend für die Schule geeignet
(für interessiertere SchülerInnen und für Veranstaltungen die
über den Pflichtstoff hinausgehen, z.B. Projektwochen, Referate,
Mathematik Olympiade).
Ein Grund ist daß sich viele überraschende und
starke Resultate ohne Vorkenntnisse völlig intuitiv formulieren
und argumentieren lassen (z.B. die Unentscheidbarkeit des
Halteproblems). Auch sind einige Resultate,
vor allem der Gödel'sche Unvollständigkeitssatz, recht populär (z.B.
durch Hofstadters Buch Gödel, Escher, Bach.)
Daher wird die Vorlesung für das Unterrichtsfach Mathematik nachdrücklich
empfohlen. (Sie ist aber vermutlich aufwändiger bzw.
schwieriger als andere Wahlfächer.)
-
Philosophie- und InformatikstudentInnen
sind sehr willkommen, es wird aber wie gesagt eine gewisse Kenntnis
der Mathematik vorausgesetzt. Mit Fragen bezüglich der
Anrechenbarkeit für Ihr Studium wenden Sie sich bitte an die für Sie
zuständige Studienkommission.
-
Es wird in der Vorlesung ein
Skriptum
verteilt (gegen einen Kopierkostenbeitrag).
Dieses Skriptum beinhaltet einerseits Stichworte zum
in der Vorlesung vorgetragenen Stoff, andererseits Beweise
und Definitionen, die in der Vorlesung aus Zeitgründen nicht
im Detail vorgetragen werden können.
Das Skriptum ist also nur eine Ergänzung
zur Vorlesung und kann die eigene Mitschrift (oder alternativ
entsprechende Literatur) nicht ersetzen.
-
In der Vorlesung werden (aus Zeitmangel) viele Sätze (insbesondere der
Unvollständigkeitssatz)
nicht formal bzw. vollständig bewiesen (bei einem formal rigorosen
Aufbau käme man ansonsten kaum über Trivialitäten wie aussagenlogische
Normalformen etc. hinaus).
Stattdessen werde ich üblicherweise nur die Beweisideen
vorstellen. Mehr Details findet sich in der Literatur, oder in
weiterführenden Vorlesungen an unserem Institut, insbesondere
Mathematische Logik 1 und 2.
Es wird leider auch keine Zeit sein, in der Vorlesung
ausgiebig auf Fragen einzugehen.
Ich bin aber gerne bereit unmittelbar nach der Vorlesung bzw. in
meiner Sprechstunde (nach Voranmeldung, am besten per email) Unklares
zu erklären, Details auszuführen bzw weiterführende Fragen zu
behandeln.
Zurück zum Seitenanfang
Empfohlene ergänzende Literatur (kann vor der bzw. parallel zur Vorlesung
gelesen werden):
-
George S. Boolos, (John P. Burgess) und Richard Jeffrey:
Computability and Logic.
Ein wunderschönes, voraussetzungsfreies Einführungsbuch.
-
Paul Halmos: Naive Mengenlehre.
Eine sehr kurze und
einfache Einführung in die naive (d.h. "logikfreie") Mengenlehre (z.B.
Äquivalenz von Auswahlaxiom und Zornschem Lemma etc.).
Empfohlene weiterführende Literatur:
-
Kenneth Kunen: Set Theory.
Eine wundervolle, gründliche und elegante Einführung in die
Mengenlehre und insbesondere Forcing.
-
Die Einführungskapitel des Handbook of Mathematical Logic
(J. Barwise, Ed.).
Einführungen in z.B. Modelltheorie oder Beweistheorie.
Zurück zum Seitenanfang
| 05.10.2005 | 1. Vorlesung: Einführung |
| 12.10.2005 | 2. Vorlesung: Auswahlaxiom, Rekursionstheorie
|
| 19.10.2005 | 3. Vorlesung: universelle Maschinen,
Gödelnummern, rekursiv aufzählbar |
| 26.10.2005 | keine Vorlesung
(Nationalfeiertag) |
| 02.11.2005 | keine Vorlesung
(Allerseelen) |
| 09.11.2005 | 4. Vorlesung: r.e./rekursiv, Aussagenlogik |
| 16.11.2005 | 5. Vorlesung: Abschluß von
Rekursionstheorie und Aussagenlogik |
| 23.11.2005 | 6. Vorlesung: Syntax der Prädikatenlogik |
| 30.11.2005 | 7. Vorlesung: Semantik der Prädikatenlogik |
| 07.12.2005 | 8. Vorlesung: ein Kalkül der
Prädikatenlogik |
| 14.12.2005 | 9. Vorlesung: Beweis des
Vollständigkeitssatzes |
| 11.01.2006 | 10. Vorlesung: Folgerungen des
Vollständigkeitssatzes: Kompaktheit, Skolem-Löwenheim. |
| 18.01.2006 | 11. Vorlesung: Lineare Ordnungen, reell
abgeschlossene Körper, Peano Arithmetik |
| 25.01.2006 | 12. Vorlesung: Axiomatische Mengenlehre |
Zurück zum Seitenanfang
Achtung: Die Texte, die man hier herunterladen
kann sind unaktuell und haben teileise nicht
korrigierte Fehler. Verbesserte und korrigierte Inhalte
finden sich im Skriptum.
- 2005-01-26
- Ab sofort ist der 3. und letzte Teil des Skriptums
kostenlos erhältlich.
- Falls Sie an einer der
Prüfungen teilnehmen wollen,
melden Sie sich bitte per email (mit Matrikelnummer und
Studienkennzahl) an. Termine:
Freitag, 27. Jänner 2006 um
16:30
und Freitag, 3. März 2006 um
11:00.
- 11. Vorlesung, 2005-01-18
-
Handouts zur heutigen Vorlesung.
- 2006-01-10
- Die Übungsstunde vom 31.1.2006 wird auf den 19.1.2006 um 14.15
in Raum D107 verlegt.
- 2005-12-14
- Skriptum:
Die Teile 1 und 2 des Skriptums sind ab sofort um jeweils 3 Euro im
Sekretariat des
KGRC erhältlich. (Öffnungszeiten
Mo-Mi 9-12,13-16, Do 9-12 13-18, Fri 9-12.)
- 7. Vorlesung, 2005-11-30
-
Modifikation der Übungsaufgabe 29
(Proseminar Blatt 7 vom 29.11.2005).
-
Handouts zur heutigen Vorlesung.
- 6. Vorlesung, 2005-11-23
-
Handouts zur heutigen Vorlesung.
- 5. Vorlesung, 2005-11-16
-
Handouts zur heutigen Vorlesung.
(Im Übrigen: Bevorzugen Sie den Tafelvortrag oder Beamer?)
- 4. Vorlesung, 2005-11-09
-
Die Screenshots des heutigen Vortrags zum Herunterladen:
-
Die nächste Übung (2005-11-15) findet statt (üblicher Ort/Zeit),
allerdings nicht von Heike Mildenberger geleitet sondern von
mir.
-
Zusätzlich zum von Heike Mildenberger auf
ihrer Webseite
bereitgestellten Übungsblatt gibt es noch einige
leichte "Bonusübungen" zur Aussagenlogik:
pdf-file (43KB).
- 2005-10-24
-
Der erste Teil des Skriptums
(mit den Kapiteln naive Mengenlehre,
Einführung in die Logik und Rekursionstheorie, sowie
Beispiele für Prüfungsfragen)
wird ab sofort gegen einen Kopierkostenbeitrag von 3 EUR
ausgegeben:
in der nächsten Übungsstunde (2005-10-24),
in den Vorlesungen und im Sektretariat des Gödel Centers.
-
In der nächsten Vorlesung (2005-11-09) werde ich doch
noch einmal Rekursionstheorie wiederholen.
Den Abschnitt weiterführenden Themen des Kapitles
Rekursionstheorie werde ich aus Zeitmangel auslassen müssen.
Am Ende der nächsten oder in der übernächsten
Stunde werde ich mit den nächsten Kapitel,
Aussagenlogik, beginnen (das wird dann wesentlich leichter
und gründlicher.)
- 2005-10-23
-
Eine vorläufige Version des Kaptitels
über Rekursionstheorie steht online zur Verfügung:
2005-10-23_ch_rek.pdf 127KB, pdf (Adobe Acrobat).
-
Der erste Teil des Skriptums (mit einer überarbeiteten
Version des Kaptitels über Rekursionstheorie) wird
in der nächsten Übungsstunde und danach in den Vorlesungen
gegen einen Kopierkostenbeitrag ausgegeben
(0.1 EUR pro Seite, d.h. ca 3 EUR).
-
In der nächsten Vorlesung (2005-11-09) werde ich doch
noch einmal Rekursionstheorie wiederholen.
Die weiterführenden Themen werde ich auslassen.
Am Ende der nächsten oder in der übernächsten
Stunde werde ich mit den nächsten Kapitel,
Aussagenlogik, beginnen. Das wird dann wesentlich leichter.
- 2005-10-18
- Die Übungen finden ab sofort (d.h. ab 2005-10-25)
nicht mehr im Hörsaal 1, sondern
im Raum C207 statt (selbe Zeit).
- Nächste und übernächste Woche fällt die Vorlesung wegen
Feiertage aus. Ich empfehle sehr, in dieser Zeit die
Übungen zu besuchen, um den bis dahin behandelten Stoff
zu vertiefen.
In der 4. Vorlesungsstunde (2005-11-09) werden wir ein neues Kapitel
(Aussagenlogik) beginnen.
- 2. Vorlesung (2005-10-12):
- Ab sofort wird die Vorlesung um 5min verschoben: neue
Zeit 11:10-12:50 (weiterhin Mittwoch).
- Für Fragen zu Übung wenden Sie sich bitte an
Heike Mildenberger. Die Übungsangaben finden Sie auf
ihrer Webseite.
-
Die Screenshots des heutigen Vortrags zum Herunterladen:
- 1. Vorlesung (2005-10-05):
- Ich ersuche das Problem mit dem
Beamer zu entschuldigen, es wird angeblich bald behoben.
-
Die Screenshots des heutigen Vortrags zum Herunterladen:
Diese Seiten stellen nicht das richtige Skriptum dar
(das habe ich nocht nicht fertig).
-
Nächste Stunde werde ich den Stoff beginnend mit
Rekursionstheorie wiederholen.
-
Man kann mir gerne Rückmeldungen und Kommentare zukommen lassen
(der erste Kommentar war: zu schnell. Ich werde in den nächsten
Stunden etwas langsamer vorgehen.)
Zurück zum Seitenanfang