Seminar 0-1-Gesetze in der Mathematischen Logik

SS 2008

Aktuelles

  • Die Zuteilung der Themen zu den Betreuern steht nun fest.
  • Die Themenverteilung und der Zeitplan für das Seminar sind nun einsehbar.

Organisation

Die Veranstaltung wird als Blockseminar durchgeführt. Die Vorbesprechung fand am Donnerstag, den 28. Februar um 11 Uhr in Raum 4116 (Seminarraum des Lehrstuhls) statt. Die Vorträge finden voraussichtlich am 11. und 12. Juni statt und können wahlweise auf deutsch oder englisch gehalten werden.

Zeitplan

25.03. Gliederung
28.04. Ausarbeitung
19.05. Endgültige Fassung
26.05. Folien
11./12.06. Vorträge

Inhalt

Eine Logik erfüllt ein 0-1-Gesetz auf einem Bereich D von Strukturen, wenn jeder Satz der Logik in fast allen oder in fast keiner Struktur in D gilt, d.h. falls für ein bestimmtes Wahrscheinlichkeitsmaß die Menge der Modelle des Satzes in D das Maß 0 oder 1 hat. Ein prominentes Beispiel ist das 0-1-Gesetz für die Prädikatenlogik auf dem Bereich der endlichen Strukturen, welches besagt, dass für jeden FO-Satz die Wahrscheinlichkeit, dass eine zufällig gewählte Struktur mit n Elementen Modell dieses Satzes ist, mit wachsendem n gegen 0 oder 1 strebt.

Gilt ein 0-1-Gesetz für eine Logik, so lassen sich daraus interessante Konsequenzen ziehen. Zum einen erhalten wir ein weiteres Hilfsmittel, um zu zeigen, dass bestimmte Eigenschaften in solchen Logiken nicht definierbar sind — z.B. existiert kein FO-Satz, der innerhalb der Klasse der endlichen Strukturen diejenigen mit einer geraden Anzahl von Elementen axiomatisiert. (Die Wahrscheinlichkeit, dass eine zufällig gewählte Struktur mit n Elementen einen solchen Satz erfüllen würde, ist 0 falls n ungerade ist bzw. 1 falls n gerade ist. Diese Folge besitzt also keinen Grenzwert.) Zum anderen erhalten wir aus weiterführenden Überlegungen Aussagen, die uns weitere Einsichten in Eigenschaften bestimmter Strukturklassen ermöglichen, wie z.B. dass fast kein endlicher Graph planar ist oder dass fast alle endlichen Graphen starr sind.

Ziel des Seminars ist es, verschiedene Formen von 0-1-Gesetzen kennenzulernen, Logiken daraufhin zu untersuchen, ob für sie 0-1-Gesetze gelten, und Konsequenzen daraus zu erarbeiten.

Themen

Thema Vortragende(r) Betreuer(in) Literatur
Das 0-1-Gesetz für FO Alexander Neumann M. Ummels [EF95, Kapitel 4, Gra83]
Erweiterungsaxiome und verallgemeinerte Quantoren Jan Hendrik Hosang M. Ummels [BH79, BEH81, DG95]
0-1-Gesetze für infinitäre Logiken Simon Robert Leßenich D. Fischer [KV92]
Fragmente von ∃SO mit 0-1-Gesetz Benjamin Brink Ł. Kaiser [KV90, KV00]
Fragmente von ∃SO ohne 0-1-Gesetz Ergang Song Ł. Kaiser [LeB98, KV00]
Asymptotische Wahrscheinlichkeiten von MSO-Sätzen Christian Druyen D. Berwanger [Kau88, Com89]
0-1-Gesetze für in die Ebene einbettbare Graphen Benjamin Ries D. Berwanger [BCR99]
Asymptotische Wahrscheinlichkeiten von FO-Sätzen über geometrischen Graphen Florian Bade D. Fischer [AS]
Geometrische 0-1-Gesetze Achim Lindt T. Ganzow [GGM07]
Asymptotische Wahrscheinlichkeiten von FO-Sätzen über geordneten Graphen Faried Abu Zaid D. Berwanger [CHS87]
Asymptotische Wahrscheinlichkeiten von FO-Sätzen über einstelligen Funktionen Wolfgang Mehner D. Fischer [Lyn85]
0-1-Gesetze auf unendlichen Strukturen Albert Zeyer T. Ganzow [Lyn80]

Literatur

Zuordnung

  • Informatik (D)/Hauptstudium/Theoretische Informatik
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Voraussetzungen

Rückfragen

Erich Grädel, Dietmar Berwanger, Diana Fischer, Tobias Ganzow, Łukasz Kaiser, Michael Ummels