Quantorenelimination

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.

DefinitionBearbeiten

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

Einfaches KriteriumBearbeiten

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.

BeispieleBearbeiten

Unendliche MengenBearbeiten

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 BeispieleBearbeiten

Viele weitere Theorien besitzen Quantorenelimination, darunter die folgenden:

AnwendungenBearbeiten

VollständigkeitBearbeiten

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 GeometrieBearbeiten

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 AnwendungenBearbeiten

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]

LiteraturBearbeiten

WeblinksBearbeiten

EinzelnachweiseBearbeiten

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