Ein Verfahren oder eine Eigenschaft einer prädikatenlogischen Theorie bzw. eines formalen Sprachsystems, durch die jede Formel mit Existenz- oder Allquantoren in eine äquivalente quantorenfreie Formel überführt wird, bezogen auf die Semantik der Theorie.

Prinzip

Wenn eine Theorie Quantorenelimination zulässt, dann existiert für jede Formel φ(x) eine quantorenfreie Formel ψ(x), so dass φ und ψ in jedem Modell der Theorie dieselben Mengen definieren; das Verfahren schreibt quantifizierte Ausdrücke systematisch mit den Primitiven der Sprache und den Axiomen der Theorie um.

Demonstration

In der Theorie der echt abgeschlossenen Körper wandelt Tarskis Verfahren (praktisch oft durch zylindrische Algebrazerlegung realisiert) eine Formel mit polynomiellen Ungleichungen und Quantoren in eine äquivalente quantorenfreie boolesche Kombination von Polynomvorzeichen um, wodurch die Wahrheit von Aussagen über reelle Zahlen entschieden werden kann.

Fehlanwendung

Vorauszusetzen, Quantorenelimination sei für beliebige Theorien verfügbar (etwa Peano-Arithmetik) oder eine 'Quantorenelimination' anzuwenden, die nur Erfüllbarkeit statt Äquivalenz erhält; oder die Prozedur anzuwenden, ohne zu prüfen, ob die Ziel‑Sprache die eliminierte Formel ausdrücken kann, was zu ungültigen Umformungen führt.

Konsequenz

Erfolgreich angewendet liefert Quantorenelimination ein effektives Entscheidungsverfahren für Sätze, Beschreibungen der definierbaren Mengen und vereinfachte Formeln für Modellkonstruktion und Abfragen; sie kann jedoch zu starkem Größenzuwachs der Formeln oder hoher Rechenkomplexität führen.

Umkehrung

Das Einführen von Quantoren (oder ihr Wiedereinführen) erhöht die Ausdruckskraft und erlaubt kompakte Beschreibungen von Familien von Strukturen oder unendlichem Verhalten, die quantorenfreie Formeln nicht erfassen; die Umkehrung zeigt Verlust an Kürze oder Definitionskomfort.

Abgrenzung

Trifft auf prädikatenlogische Rahmen zu und hängt von der jeweiligen Theorie und Sprache ab; manche Theorien erlauben vollständige Eliminierung, andere nur partielle oder relative Eliminierung; höherstufige Logiken oder Theorien mit nicht interpretierten Symbolen können keine Eliminierung zulassen. Praktische Grenzen sind Repräsentierbarkeit und Rechenaufwand.

Semantische Spannung

Spannung besteht zwischen Quantorenelimination und Skolemierung: Skolemierung entfernt Existenzquantoren durch Einführung von Funktionssymbolen, bewahrt aber nur Erfüllbarkeit, nicht Äquivalenz; Quantorenelimination wahrt Äquivalenz, verlangt jedoch oft reichere boolesche oder algebraische Konstruktionen.

Synthese

Quantorenelimination ist sowohl eine semantische Eigenschaft einer Theorie als auch eine Klasse syntaktischer Verfahren, die quantifizierte Beschreibungen durch äquivalente quantorenfreie Formeln ersetzen; ihr Vorhandensein führt zu Entscheidbarkeit und konkreten Beschreibungen definierbarer Mengen, ihr Fehlen weist auf expressive oder rechnerische Schranken hin.