Satz von Gaifman

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Satz von Gaifman ist ein Satz aus der mathematischen Logik. Er sagt aus, dass alle Sätze der Prädikatenlogik erster Stufe in endlichen, relationalen Strukturen in einem gewissen Sinne nur lokale Aussagen treffen können. Der Satz geht auf Haim Gaifman zurück und stammt aus dem Jahre 1981.[1]

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 wie 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.

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 ist eine rekursive Definition über den Formelaufbau der Prädikatenlogik erster Stufe. Die rechten Seiten dieser Definitionen verwenden stets Relativierungen bereits erklärter und einfacher aufgebauter Formeln.

Die Definitionen sind offenbar so 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 nun eine lokale Basisformel, wenn sie die 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

[Bearbeiten | Quelltext bearbeiten]

Der Satz von Gaifman lautet:

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

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

[Bearbeiten | Quelltext bearbeiten]
  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