Satz von Gaifman

Der Satz v​on Gaifman i​st ein Satz a​us der mathematischen Logik. Er s​agt aus, d​ass alle Sätze d​er Prädikatenlogik erster Stufe i​n endlichen, relationalen Strukturen i​n einem gewissen Sinne n​ur lokale Aussagen treffen können. Der Satz g​eht auf Haim Gaifman zurück u​nd stammt a​us dem Jahre 1981.[1]

Einführung

Es sei eine relationale Sprache der Prädikatenlogik erster Stufe. Dabei bedeutet relational, dass die Signatur nur aus endlich vielen Relationssymbolen besteht. Modelle bzw. Strukturen dieser Sprache werden -Strukturen genannt. Ein wichtiges Beispiel ist , wobei ein zweistelliges Relationssymbol ist. Eine -Struktur ist dann eine Menge mit einer zweistelligen Relation auf als Interpretation von . Derartige Strukturen sind nichts anderes als Graphen, wobei bedeutet, dass die Knoten durch eine Kante verbunden sind.

Die Idee, in Graphen kürzeste Wege zwischen Knoten als Abstände zu verwenden, überträgt man auf allgemeine endliche -Strukturen mit Universum und Interpretation , indem man zum sogenannten Gaifman-Graphen übergeht. Dieser Graph hat die Knotenmenge und zwei verschiedene Knoten sind genau dann durch eine Kante verbunden, wenn es eine Relation mit Stelligkeit und Elemente mit und gibt, wobei die Interpretation von unter ist. Kurz, sind durch eine Kante verbunden, wenn sie in einer Relation zueinander stehen. Der Abstand ist dann die Länge eines kürzesten Weges von nach im Gaifman-Graphen. Mittels dieses Abstandes kann man dann für und wie folgt die r-Kugel um definieren:

.

Beachte dazu, dass weder der Abstand , noch der Vergleich , noch die natürliche Zahl r Bestandteil von sind. Dennoch kann man in über den Abstand und die r-Kugeln sprechen. Genauer gibt es -Formeln mit

.

Diese werden rekursiv w​ie folgt definiert:

  d. h. Knoten mit Abstand 0 sind gleich.

Wegen der vorausgesetzten Endlichkeit von handelt es sich tatsächlich um -Formeln. Die Definition der Kantenrelation im Gaifman-Graphen zeigt, dass sie das Verlangte leisten. Damit hat man auch

.

Für Variablen definiere

.

Offenbar gilt

,

das heißt auch über die r-Kugeln kann man in sprechen.

Lokale Sätze

Wir werden lokale Formeln im Wesentlichen dadurch definieren, dass sie in einem hier zu präzisierenden Sinne auf r-Kugeln eingeschränkt sind. Zunächst erklären wir die Relativierung einer Formel dadurch, dass wir die in auftretenden Quantoren unter Verwendung obiger entsprechend einschränken, das heißt wir setzen rekursiv

falls atomar ist.
  und entsprechend für .

Das i​st eine rekursive Definition über d​en Formelaufbau d​er Prädikatenlogik erster Stufe. Die rechten Seiten dieser Definitionen verwenden s​tets Relativierungen bereits erklärter u​nd einfacher aufgebauter Formeln.

Die Definitionen s​ind offenbar s​o angelegt, dass

,

das heißt erfüllt die relativierte Formel genau dann, wenn bereits die r-Kugel ein Modell für ist.

Eine Formel heißt n​un eine lokale Basisformel, w​enn sie d​ie Gestalt

hat, wobei eine Formel erster Stufe ist. Diese Formel drückt also aus, dass es in jedem Model Elemente gibt, die einen Abstand haben, so dass sich die r-Kugeln um die nicht schneiden, und dass die durch beschriebene Eigenschaft lokal ist, genauer, dass bereits die r-Kugel um jedes Element ein Modell für diese Eigenschaft ist.

Schließlich heißt eine Formel lokal, wenn sie eine boolesche Kombination lokaler Basisformeln ist, das heißt mittels aus lokalen Basisformeln zusammengesetzt ist.[2]

Formulierung des Satzes

Der Satz v​on Gaifman lautet:

Ist eine endliche relationale Signatur, so ist jeder -Satz in endlichen Modellen logisch äquivalent zu einem lokalen Satz.[3]

Bemerkungen

Ist der Quantorenrang des -Satzes , das heißt die maximale Verschachtelungstiefe von Existenz- und Allquantoren in diesem Satz ist maximal , so kann man die r-Kugeln der im Satz von Gaifman auftretenden lokalen Basissätze mit wählen.

Allgemeiner ist jede Formel erster Stufe mit freien Variablen logisch äquivalent zu einer booleschen Kombination aus Formeln der Form und lokalen Sätzen.[4]

Aus dem Satz von Gaifman ergibt sich die Gaifman-Lokalität der Prädikatenlogik erster Stufe. Allerdings ist die Abschätzung für das kleinste , das man für die lokalen Basissätze im Satz von Gaifman wählen kann, schwächer als die im unten angegebenen Lehrbuch von Leonid Libkin oder im Artikel zur Gaifman-Lokalität angegebenen Abschätzungen.

Einzelnachweise

  1. Haim Gaifman: On local and non-local properties, Proceedings Herbrand Symposium, Logic Colloquium ´81, North Holland Verlag (1982)
  2. Heinz-Dieter Ebbinghaus, Jörg Flum: Finite Model Theory, Springer-Verlag 1999, ISBN 3-540-28787-6, Seite 31
  3. Heinz-Dieter Ebbinghaus, Jörg Flum: Finite Model Theory, Springer-Verlag 1999, ISBN 3-540-28787-6, Satz 2.5.1. Gaifman's Theorem
  4. Leonid Libkin: Elements of Finite Model Theory, Springer-Verlag (2004), ISBN 3-540-21202-7, Theorem 4.22
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.