www.wikidata.de-de.nina.az

Quantorenelimination bezeichnet in der Modelltheorie eine bestimmte Eigenschaft von Theorien Man sagt eine Theorie habe

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.

Definition 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

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

Unendliche Mengen 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

Viele weitere Theorien besitzen Quantorenelimination, darunter die folgenden:

Anwendungen Bearbeiten

Vollständigkeit 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

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

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

Literatur Bearbeiten

  • Wilfrid Hodges: Model theory. Cambridge University Press, 1993, ISBN 0-521-30442-3.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. ↑ Martin Ziegler: Skript Modelltheorie 1. (PDF; 649 kB) S. 43 ff.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 aquivalent ist So ist beispielsweise in einem Korper also etwa in den reellen Zahlen die Formel f x y x y 1 displaystyle varphi x exists y x cdot y doteq 1 die besagt dass x displaystyle x ein multiplikatives inverses Element besitzt aquivalent zu r x x 0 displaystyle rho x neg x doteq 0 also dazu dass x 0 displaystyle x neq 0 In r x displaystyle rho x kommen keine Quantoren mehr vor Lasst sich jede Formel in eine solche quantorenfreie Formel umformen so besitzt die Theorie Quantorenelimination In Theorien mit Quantorenelimination konnen also beliebige Formeln in quantorenfreie und damit einfachere Formeln umgeformt werden Inhaltsverzeichnis 1 Definition 2 Einfaches Kriterium 3 Beispiele 3 1 Unendliche Mengen 3 2 Weitere Beispiele 4 Anwendungen 4 1 Vollstandigkeit 4 2 Algebraische Geometrie 4 3 Weitere Anwendungen 5 Literatur 6 Weblinks 7 EinzelnachweiseDefinition BearbeitenSei L displaystyle L nbsp eine Sprache und T displaystyle T nbsp eine Theorie also eine Aussagenmenge Dann hat T displaystyle T nbsp Quantorenelimination falls fur alle L displaystyle L nbsp Formeln f x 1 x n displaystyle varphi x 1 ldots x n nbsp eine quantorenfreie L displaystyle L nbsp Formel r x 1 x n displaystyle rho x 1 ldots x n nbsp existiert mit T x 1 x n f x 1 x n r x 1 x n displaystyle T vdash forall x 1 ldots forall x n varphi x 1 ldots x n leftrightarrow rho x 1 ldots x n nbsp Einfaches Kriterium BearbeitenUm zu uberprufen ob eine Theorie Quantorenelimination besitzt genugt es dies nur fur eine einfache Art von Formeln nachzuweisen Der Allquantor kann mit Hilfe einer doppelten Negation in einen Existenzquantor uberfuhrt werden Diese kann man induktiv von innen nach aussen entfernen sodass nur fur Formeln der Gestalt x r x y 1 y n displaystyle exists x rho x y 1 ldots y n nbsp mit quantorenfreiem r x y 1 y n displaystyle rho x y 1 ldots y n nbsp nachgewiesen werden muss dass sie aquivalent zu einer quantorenfreien Formel sind Bringt man r x y 1 y n displaystyle rho x y 1 ldots y n nbsp in disjunktive Normalform und zieht den Existenzquantor an der Disjunktion vorbei nach innen so sieht man dass man sich dabei auf solche Formeln r x y 1 y n displaystyle rho x y 1 ldots y n nbsp beschranken kann die aus einer Konjunktion elementarer Formeln oder Negationen solcher Formeln bestehen Formeln der Form x r x y 1 y n displaystyle exists x rho x y 1 ldots y n nbsp bei denen r displaystyle rho nbsp diese Gestalt hat nennt man auch primitive Existenzformeln Beispiele BearbeitenUnendliche Mengen Bearbeiten Die Theorie unendlicher Mengen lasst sich in einer Sprache ohne Konstanten Funktions und Relationssymbole formulieren Die Formel f n x 1 x n 1 i lt j n x i x j displaystyle varphi n exists x 1 ldots x n bigwedge 1 leq i lt j leq n neg x i doteq x j nbsp besagt dass es mindestens n displaystyle n nbsp Elemente gibt T f n n N displaystyle T infty varphi n n in mathbb N nbsp axiomatisiert daher unendliche Mengen Eine primitive Existenzformel hat die Gestalt x i I x y i j J x z j r displaystyle exists x bigwedge i in I x doteq y i wedge bigwedge j in J neg x doteq z j wedge rho nbsp wobei r displaystyle rho nbsp quantorenfrei ist und beliebige freie Variablen besitzt Ist I displaystyle I neq emptyset nbsp so ist die Formel zu i j I y i y j i 0 I j J y i 0 z j r displaystyle bigwedge i j in I y i doteq y j wedge i 0 in I wedge bigwedge j in J neg y i 0 doteq z j wedge rho nbsp aquivalent Denn die Formel sagt aus dass ein x displaystyle x nbsp gesucht ist das mit allen y i displaystyle y i nbsp ubereinstimmt sodass nur noch eine Moglichkeit fur x displaystyle x nbsp bleibt Ist dagegen I displaystyle I emptyset nbsp so ist die Formel aquivalent zu r displaystyle rho nbsp da ein von allen z j displaystyle z j nbsp verschiedenes x displaystyle x nbsp gesucht ist das nach den Axiomen der Theorie unendlicher Mengen immer existiert Somit ist jede primitive Existenzformel zu einer quantorenfreien Formel aquivalent die Theorie besitzt Quantorenelimination Weitere Beispiele Bearbeiten Viele weitere Theorien besitzen Quantorenelimination darunter die folgenden die Theorie der algebraisch abgeschlossenen Korper die Theorie der dichten linearen Ordnungen ohne Endpunkte fur einen festen Korper K displaystyle K nbsp die Theorie der unendlichen K displaystyle K nbsp Vektorraume die Theorie der reell abgeschlossenen KorperAnwendungen BearbeitenVollstandigkeit Bearbeiten Eine konsistente Theorie ohne Konstanten die Quantorenelimination besitzt ist automatisch vollstandig das heisst sie beweist fur jede Aussage f displaystyle varphi nbsp entweder f displaystyle varphi nbsp selbst oder f displaystyle neg varphi nbsp Dies sieht man folgendermassen ein Jede Aussage f displaystyle varphi nbsp ist in der Theorie aquivalent zu einer quantorenfreien Aussage Da es aber keine Konstanten gibt sind die einzigen quantorenfreien Aussagen die wahre displaystyle top nbsp und die falsche displaystyle bot nbsp Aussage Damit beweist die Theorie entweder f displaystyle varphi nbsp oder f displaystyle neg varphi nbsp Ein Beispiel fur diesen Fall ist die obige Theorie unendlicher Mengen Allgemein gilt Eine Theorie mit Quantorenelimination ist modellvollstandig Sind A B displaystyle mathcal A subset mathcal B nbsp zwei Modelle von T displaystyle T nbsp so ist A B displaystyle mathcal A prec mathcal B nbsp eine elementare Erweiterung die Theorien T h A displaystyle Th mathcal A nbsp und T h B displaystyle Th mathcal B nbsp von A displaystyle mathcal A nbsp und B displaystyle mathcal B nbsp stimmen uberein Wegen der Quantorenelimination muss dies nur fur quantorenfreie Formeln nachgewiesen werden solche gelten aber genau dann in A displaystyle mathcal A nbsp wenn sie in B displaystyle mathcal B nbsp gelten da A displaystyle mathcal A nbsp Unterstruktur von B displaystyle mathcal B nbsp ist Algebraische Geometrie Bearbeiten In der algebraischen Geometrie beschaftigt man sich mit algebraischen Varietaten den Nullstellenmengen von Polynomen Von Chevalley stammt der Satz dass die Projektion einer solchen Varietat auf einen Unterraum wieder durch Polynome beschrieben werden kann falls der Grundkorper algebraisch abgeschlossen ist Dies lasst sich beweisen indem man die Quantorenelimination der Theorie der algebraisch abgeschlossenen Korper verwendet Sei die Varietat definiert als die Nullstellenmenge der Polynome f i x 1 x n displaystyle f i x 1 ldots x n nbsp fur i 1 m displaystyle i 1 ldots m nbsp Die Projektion auf die ersten k displaystyle k nbsp Koordinaten ist dann gegeben durch f x 1 x k x k 1 x n f 1 x 1 x n 0 f m x 1 x n 0 displaystyle varphi x 1 ldots x k exists x k 1 ldots x n f 1 x 1 ldots x n doteq 0 wedge ldots wedge f m x 1 ldots x n doteq 0 nbsp Diese Formel ist aquivalent zu einer quantorenfreien Formel welche eine boolesche Kombination von elementaren Formeln der Art Polynome 0 ist die Projektion ist also eine boolesche Kombination von Varietaten Weitere Anwendungen Bearbeiten Auch der Hilbertsche Nullstellensatz hat einen Beweis der auf der Quantorenelimination der Theorie algebraisch abgeschlossener Korper beruht 1 Fur Hilberts siebzehntes Problem existiert ein Beweis der auf der Quantorenelimination der Theorie reell abgeschlossener Korper beruht 1 Literatur BearbeitenWilfrid Hodges Model theory Cambridge University Press 1993 ISBN 0 521 30442 3 Weblinks BearbeitenEric W Weisstein Quantifier Elimination In MathWorld englisch Einzelnachweise Bearbeiten a b Martin Ziegler Skript Modelltheorie 1 PDF 649 kB S 43 ff Abgerufen von https de wikipedia org w index php title Quantorenelimination amp oldid 193195438