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

[AS] A. Agarwal and J. Spencer. Undecidable statements and the Zero-One Law in Random Geometric Graphs. Accepted at Discrete and Computational Geometry.
[BCR99] E. A. Bender, K. J. Compton, and L. B. Richmond. 0-1 laws for maps. Random Structures and Algorithms, vol. 14(3), pp. 215-237, 1999.
[BEH81] A. Blass, G. Exoo, and F. Harary. Paley Graphs Satisfy All First-Order Adjacency Axioms. Journal of Graph Theory, vol. 5, pp. 435–439, 1981.
[BH79] A. Blass and F. Harary. Properties of Almost All Graphs and Complexes. Journal of Graph Theory, vol. 3(3), pp. 225–240, 1979.
[CHS87] K. Compton, C. Henson, and S. Shelah. Nonconvergence, undecidability, and intractability in asymptotic problems. Annals of Pure and Applied Logic, vol. 36, pp. 207–224, 1987.
[Com89] K. J. Compton. A logical approach to asymptotic combinatorics II: Monadic second-order properties. Journal of Combinatorial Theory Series A, vol. 50(1), pp. 110–131, 1989.
[DG95] A. Dawar and E. Grädel. Generalized Quantifiers and 0-1 Laws. In Proceedings of 10th IEEE Symposium on Logic in Computer Science, LICS `95, San Diego, pp. 54–64, 1995.
[EF95] H. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, 1995.
[GGM07] R. H. Gilman, Y. Gurevich, and A. Miasnikov. A Geometric Zero-One Law. Technical Report. Microsoft Research, 2007.
[Gra83] E. Grandjean. Complexity of the First-Order Theory of Almost All Structures. Information and Control, vol. 57, pp. 180–204, 1983.
[KV00] P. G. Kolaitis and M. Y. Vardi. 0-1 Laws for Fragments of Existential Second-Order Logic: A Survey. In Proceedings of MFCS 2000, pp. 84-98, 2000.
[KV90] P. G. Kolaitis and M. Y. Vardi. 0-1 Laws and Decision Problems for Fragments of Second-Order Logic. Information and Computation, vol. 87(1–2), pp. 302–338, 1990.
[KV92] P. G. Kolaitis and M. Y. Vardi. Infinitary Logics and 0-1 Laws. Information and Computation, vol. 98(2), pp. 258–294, 1992.
[Kau88] M. Kaufmann. A Counterexample to the 0-1 Law for Existential Monadic Second-Order Logic. Internal Note, Computational Logic Inc., 1988.
[LeB98] J. Le Bars. Fragments of existential second-order logic without 0-1 laws. In Proceedings of LICS 1998, pp. 525-536, 1998.
[Lyn80] J. F. Lynch. Almost sure theories. Annals of Mathematical Logic, vol. 18(2), pp. 91–135, 1980.
[Lyn85] J. F. Lynch. Probabilities of First-Order Sentences about Unary Functions. Transactions of the American Mathematical Society, vol. 287(2), pp. 543–568, 1985.

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