"Modelltheorie der Fixpunktlogik 001.ps.gz" - читать интересную книгу автора

Zur Modelltheorie der Fixpunktlogik

Uwe Bosse

Dissertation zur Erlangung der Doktorw"urde an der Mathematischen Fakult"at

der Albert-Ludwigs Universit"at

Freiburg i. Brsg.

November 1994

Dekan der mathematischen Fakult"at: Professor Dr. Victor Bangert Betreuer der Dissertation und erster Referent: Professor Dr. J"org Flum Zweiter Referent:

Datum der Promotion:

Inhaltsverzeichnis Einleitung 1 1 Wichtige Hilfsmittel und Definitionen 3

1.1 Schreibweisen und Vereinbarungen . . . . . . . . . . . . . . . . . . 3 1.2 Grundlegende Eigenschaften der Fixpunktlogik . . . . . . . . . . . 4

1.2.1 Der Satz von L"owenheim und Skolem f"ur FP . . . . . . . . 7 1.2.2 Relativierung von Fixpunktformeln . . . . . . . . . . . . . 10

2 In der Spielh"olle der Logiker 12

2.1 Ehrenfeucht-Fra"iss'e-Spiele f"ur die Fixpunktlogik . . . . . . . . . . 12

2.1.1 Eine Vereinfachung der Spielregeln . . . . . . . . . . . . . 18 2.1.2 Ein Spielerischer Zugang zu A j= ' . . . . . . . . . . . . . 20 2.1.3 Das Spiel SLk1! (A; B) zum Nachweis von A jLFPk B . . . 23 2.1.4 Verspielte Sprechweisen . . . . . . . . . . . . . . . . . . . . 26

3 Ergebnisse f"ur endliche Strukturen 27

3.1 Eine Quantorenhierarchie in SFP . . . . . . . . . . . . . . . . . . 27

3.1.1 Ein Ehrenfeucht-Fra"iss'e-Spiel f"ur SFP . . . . . . . . . . . 28 3.1.2 Die Quantorenhierarchie . . . . . . . . . . . . . . . . . . . 29 3.1.3 SFP 6= FP . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.2 Zwei monadische Fixpunkte sehen mehr als einer . . . . . . . . . . 36

I

II Inhaltsverzeichnis 4 Zur Ausdrucksst"arke von MFP und MSO auf Ordnungen 42