Hat die Theorie erster Ordnung einer endlichen Struktur einen begrenzten Quantifiziererrang?

11

Sei eine beliebige endliche Struktur. Hat seine Theorie erster Ordnung T : = T H ( A ) einen begrenzten Quantifiziererrang in dem Sinne, dass es ein q ∈ N gibt, so dass es für alle φ ∈ T mit q r ( φ ) > q ein φ ′ ∈ T gibt mit q r ( φ ′ ) ≤ q und φ ′ ≡ φ ?AT:=TH(A)q∈Nφ∈Tqr(φ)>qφ′∈Tqr(φ′)≤qφ′≡φ

co.combinatorics lo.logic relational-structures D. Rusin
quelle
Ist das nicht eher eine Frage für Mathoverflow als für die CS-Theorie?
Andrej Bauer
6
@Andrej, endliche Modelltheorie und deskriptive Komplexität werden ebenfalls als Teil von TCS betrachtet.
Kaveh
1
Ausgezeichnet, so wie es Bob Harper einmal gesagt hat: Mathematik ist ein Sonderfall der Informatik.
Andrej Bauer
Informatik ist auch ein Sonderfall der Mathematik, und beide sind auch Sonderfälle der Logik und umgekehrt.
Fhyve

Antworten:

12

Die Theorie jeder endlichen Struktur ist modellvoll. Tatsächlich ist leicht zu erkennen, dass jede Formel einer existenziellen Formel mit einem Quantifizierer pro Element der Struktur entspricht, wonach alle Quantifizierer der ursprünglichen Formel durch Konjunktionen und Disjunktionen simuliert werden können. Insbesondere ist die Anzahl der Quantifizierer (daher der Quantifiziererrang) durch die Größe der Struktur begrenzt.

Emil Jeřábek 3.0
quelle
Tatsächlich wird ein zusätzlicher universeller Quantifizierer benötigt, mit dem ausgedrückt werden kann, dass keine weiteren Elemente vorhanden sind. In allen Antworten gibt es eine Annahme, die explizit gemacht werden sollte: das Vorhandensein von Ungleichheit, dh, dass x = y eine erlaubte Atomformel ist.
Thomas S
Es wird kein zusätzlicher Quantifizierer benötigt. Denken Sie daran, wir versuchen nicht, die Theorie der Struktur zu axiomatisieren, sondern eine Formel zu finden, die einer bestimmten Modulo der Theorie entspricht. Und das Vorhandensein von Gleichheit ist ein universeller Standard für die klassische Logik erster Ordnung. Ihre Abwesenheit müsste angegeben werden.
Emil Jeřábek 3.0
Ah. Du hast recht. "Modulo-Theorie". In Bezug auf Gleichheit: Da wir versuchen, Menschen außerhalb von Logic einfache Dinge zu erklären, schadet es nicht, den Rahmen explizit zu machen. Noch eine Bemerkung: Das Ersetzen von Quantifizierern durch Konjunktionen und Disjunktionen ist vollkommen gut. Es gibt jedoch Alternativen: Da eine Formel mit beispielsweise m freien Variablen eine m-ary-Beziehung von A definiert, kann die neue Formel nach Erraten aller Elemente und Überprüfen, welche welche ist (Modulo-Automorphismen), auch alle explizit "aufzählen" Tupel, für die die alte Formel "wahr" ergibt.
Thomas S
3

Um das, was Emil sagte, etwas konkreter zu machen: Betrachten Sie die Formel, die die Existenz von k verschiedenen Objekten ausdrückt. Das zeigt, dass wir eine unbegrenzte Anzahl von Quantifizierern benötigen.

Jetzt haben Sie eine Formel mit q Quantifizierern und Ihr Modell enthält k Objekte. Sie können die Formel ausdrücken, indem Sie angeben, dass k verschiedene Objekte existieren und die Beziehung zwischen ihnen als CNF ausgedrückt werden kann.

Kaveh
quelle