Quantorenelimination

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Quantorenelimination bezeichnet in der Modelltheorie eine bestimmte Eigenschaft von Theorien: Man sagt, eine Theorie habe Quantorenelimination, wenn jede Formel innerhalb der Theorie zu einer Formel ohne Quantoren äquivalent ist. So ist beispielsweise in einem Körper (also etwa in den reellen Zahlen) die Formel , die besagt, dass ein multiplikatives inverses Element besitzt, äquivalent zu , also dazu, dass . In kommen keine Quantoren mehr vor. Lässt sich jede Formel in eine solche quantorenfreie Formel umformen, so besitzt die Theorie Quantorenelimination. In Theorien mit Quantorenelimination können also beliebige Formeln in quantorenfreie und damit einfachere Formeln umgeformt werden.

Definition[Bearbeiten | Quelltext bearbeiten]

Sei eine Sprache und eine Theorie (also eine Aussagenmenge). Dann hat Quantorenelimination, falls für alle -Formeln eine quantorenfreie -Formel existiert mit .

Einfaches Kriterium[Bearbeiten | Quelltext bearbeiten]

Um zu überprüfen, ob eine Theorie Quantorenelimination besitzt, genügt es, dies nur für eine einfache Art von Formeln nachzuweisen: Der Allquantor kann mit Hilfe einer doppelten Negation in einen Existenzquantor überführt werden. Diese kann man induktiv von innen nach außen entfernen, sodass nur für Formeln der Gestalt mit quantorenfreiem nachgewiesen werden muss, dass sie äquivalent zu einer quantorenfreien Formel sind.

Bringt man in disjunktive Normalform und zieht den Existenzquantor an der Disjunktion vorbei nach innen, so sieht man, dass man sich dabei auf solche Formeln beschränken kann, die aus einer Konjunktion elementarer Formeln oder Negationen solcher Formeln bestehen. Formeln der Form , bei denen diese Gestalt hat, nennt man auch primitive Existenzformeln.

Beispiele[Bearbeiten | Quelltext bearbeiten]

Unendliche Mengen[Bearbeiten | Quelltext bearbeiten]

Die Theorie unendlicher Mengen lässt sich in einer Sprache ohne Konstanten-, Funktions- und Relationssymbole formulieren: Die Formel besagt, dass es mindestens Elemente gibt. axiomatisiert daher unendliche Mengen. Eine primitive Existenzformel hat die Gestalt , wobei quantorenfrei ist und beliebige freie Variablen besitzt. Ist , so ist die Formel zu äquivalent. Denn die Formel sagt aus, dass ein gesucht ist, das mit allen übereinstimmt, sodass nur noch eine Möglichkeit für bleibt. Ist dagegen , so ist die Formel äquivalent zu , da ein von allen verschiedenes gesucht ist, das nach den Axiomen der Theorie unendlicher Mengen immer existiert. Somit ist jede primitive Existenzformel zu einer quantorenfreien Formel äquivalent; die Theorie besitzt Quantorenelimination.

Weitere Beispiele[Bearbeiten | Quelltext bearbeiten]

Viele weitere Theorien besitzen Quantorenelimination, darunter die folgenden:

Anwendungen[Bearbeiten | Quelltext bearbeiten]

Vollständigkeit[Bearbeiten | Quelltext bearbeiten]

Eine konsistente Theorie ohne Konstanten, die Quantorenelimination besitzt, ist automatisch vollständig, das heißt, sie beweist für jede Aussage entweder selbst oder . Dies sieht man folgendermaßen ein: Jede Aussage ist in der Theorie äquivalent zu einer quantorenfreien Aussage. Da es aber keine Konstanten gibt, sind die einzigen quantorenfreien Aussagen die wahre () und die falsche () Aussage. Damit beweist die Theorie entweder oder . Ein Beispiel für diesen Fall ist die obige Theorie unendlicher Mengen.

Allgemein gilt: Eine Theorie mit Quantorenelimination ist modellvollständig: Sind zwei Modelle von , so ist eine elementare Erweiterung, die Theorien und von und stimmen überein. Wegen der Quantorenelimination muss dies nur für quantorenfreie Formeln nachgewiesen werden, solche gelten aber genau dann in , wenn sie in gelten, da Unterstruktur von ist.

Algebraische Geometrie[Bearbeiten | Quelltext bearbeiten]

In der algebraischen Geometrie beschäftigt man sich mit algebraischen Varietäten, den Nullstellenmengen von Polynomen. Von Chevalley stammt der Satz, dass die Projektion einer solchen Varietät auf einen Unterraum wieder durch Polynome beschrieben werden kann, falls der Grundkörper algebraisch abgeschlossen ist. Dies lässt sich beweisen, indem man die Quantorenelimination der Theorie der algebraisch abgeschlossenen Körper verwendet: Sei die Varietät definiert als die Nullstellenmenge der Polynome für . Die Projektion auf die ersten Koordinaten ist dann gegeben durch . Diese Formel ist äquivalent zu einer quantorenfreien Formel, welche eine boolesche Kombination von elementaren Formeln der Art „Polynome = 0“ ist, die Projektion ist also eine boolesche Kombination von Varietäten.

Weitere Anwendungen[Bearbeiten | Quelltext bearbeiten]

Auch der Hilbertsche Nullstellensatz hat einen Beweis, der auf der Quantorenelimination der Theorie algebraisch abgeschlossener Körper beruht.[1] Für Hilberts siebzehntes Problem existiert ein Beweis, der auf der Quantorenelimination der Theorie reell abgeschlossener Körper beruht.[1]

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Eric W. Weisstein: Quantifier Elimination. In: MathWorld (englisch).

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b Martin Ziegler: Skript Modelltheorie 1 (PDF; 649 kB) S. 43ff.