QUANTORENELIMINATION VON ℂ UND ℝ NACH KREISEL–KRIVINE

MARTIN ZIEGLER

Ich gebe eine verbesserte Version des Verfahrens in [1].

1. Die komplexen Zahlen

Äquivalenz von Formeln bedeutet Äquivalenz in ℂ.

Lemma 1.1. Jede quantorenfreie Formel ϕ(x̄) ist äquivalent zu einer Disjunktion von Formeln der Form

p_{1}(x̄) =^{.} 0 ∧ ⋯ ∧ p_{m}(x̄) =^{.} 0 ∧ ¬q(x̄) =^{.} 0.

Dabei sind die p_{i} und q Polynome aus ℤ[x̄]. □

Wir fixieren eine Variable x und verstehen unter dem Grad deg(p) von p den Grad von p in x. Wenn p = ∑ x^{i}s_{i}(ȳ), sei p ≡ 0 die Formel ⋀_{i} s_{i} =^{.} 0.

Lemma 1.2. Jede Konjunktion p_{1}(x, ȳ) =^{.} 0 ∧ ⋯ ∧ p_{m}(x, ȳ) =^{.} 0 ist äquivalent zu einer Disjunktion von Formeln der Form

δ(ȳ) ∧ p(x, ȳ) =^{.} 0.

Dabei ist δ quantorenfrei und der Grad von p beschränkt durch den größten Grad der p_{i}.

Beweis. Wir nehmen an, daß die p_{i} alle ungleich Null sind, und beweisen den Satz durch Induktion über die Summe der Grade der p_{i}. Sei k der Grad von p_{1}, der kleinste vorkommende Grad. Wir schreiben p_{1}(x, ȳ) = x^{k}s(ȳ) + t(x, ȳ) für ein t mit kleinerem Grad als k. Für genügend großes N können wir alle s^{N}p_{i} durch p_{1} mit Rest dividieren:

s^{N}p_{i} = f_{i}p_{1} + p̄_{i},

wobei deg(p̄_{i}) < k. Dann ist ⋀_{i=1}^{m} p_{i} =^{.} 0 äquivalent zur Disjunktion von

s =^{.} 0 ∧ (t =^{.} 0 ∧ ⋀_{i=2}^{m} p_{i} =^{.} 0)

und

¬s =^{.} 0 ∧ (p_{1} =^{.} 0 ∧ ⋀_{i=2}^{m} p̄_{i} =^{.} 0)

Auf beide Klammerausdrücke können wir Induktion anwenden. □

Folgerung 1.3. Jede quantorenfreie Formel χ(x, ȳ) ist äquivalent zu einer Disjunktion von Formeln der Form

δ(ȳ) ∧ p(x, ȳ) =^{.} 0 ∧ ¬q(x, ȳ) =^{.} 0.

Datum 23.4.2009.

Skript zur Logik für Informatiker SS02.

Lemma 1.4. Für alle Polynome p(x, ȳ) und q(x, ȳ) gibt es eine quantorenfreie Formel div(p, q)(ȳ), die auf c̄ ∈ ℂ genau dann zutrifft, wenn p(x, c̄) in ℂ[x] ein Teiler von q(x, c̄) ist.

Beweis. Wenn p das Nullpolynom ist, nimmt man q ≡ 0 für div(p, q). Sonst schreiben wir p = x^{k}s + t und s^{N}q = gp + q̄ wie oben. Dann ist p(x, c̄) | q(x, c̄) äquivalent zur Disjunktion von

s(c) =^{.} 0 ∧ t(x, c̄) | q(x, c̄)

und

¬s(c) =^{.} 0 ∧ q̄(x, c̄) ≡ 0

und die Behauptung folgt durch Induktion über den Grad von p. □

Satz 1.5. ℂ hat Quantorenelimination.

Beweis. Wir müssen zeigen, daß ∃x (p =^{.} 0 ∧ ¬q =^{.} 0) quantorenfrei ist. Das ist aber in algebraisch abgeschlossenen Körpern, für genügend großes N, äquivalent zu ¬div(p, q^{N}). □

2. Die reellen Zahlen

Äquivalenz von Formeln bedeutet Äquivalenz in ℝ. Man beachte, daß Lemma 1.2 für beliebige Körper, also auch für ℝ, gilt.

Lemma 2.1. Jede quantorenfreie Formel ϕ(x̄) ist äquivalent zu einer Disjunktion von Formeln der Form

p_{1}(x̄) =^{.} 0 ∧ ⋯ ∧ p_{m}(x̄) =^{.} 0 ∧ q_{1}(x̄) > 0 ∧ ⋯ ∧ q_{n}(x̄) > 0.

Dabei sind die p_{i} und q_{i} Polynome aus ℤ[x̄]. □

Wir fixieren eine Variable x und verstehen unter dem Grad deg(p) von p den Grad von p in x. Der Grad einer Disjunktion der oben beschriebenen Form ist das Maximum aller deg(p_{i}) und deg(q_{i}) + 1.

Folgerung 2.2. Jede quantorenfreie Formel ist äquivalent zu einer Disjunktion von Formeln der Form

δ(ȳ) ∧ p =^{.} 0 ∧ q_{1} > 0 ∧ ⋯ ∧ q_{n} > 0,

die höchstens denselben Grad hat.

Beweis. Lemma 1.2. □

Lemma 2.3. Sei p(x, ȳ) vom Grad k ≥ 0 und χ(x, ȳ) quantorenfrei. Dann ist ¬p ≡ 0 ∧ p =^{.} 0 ∧ χ äquivalent zu einer quantorenfreien Formel von höchstens dem Grad k.

Beweis. Durch Induktion über k. Für k = 0 ist, ist die Formel ¬p ≡ 0 ∧ p =^{.} 0 ∧ χ immer falsch. Also ist alles klar.

Wenn k > 0, schreiben wir p(x, ȳ) = x^{k}s(ȳ)+t(x, ȳ) für ein t mit kleinerem Grad als k. Nach Folgerung 2.2 können wir annehmen, daß χ die Form r =^{.} 0∧⋀_{i=0}^{n} q_{i} > 0 hat.

Für genügend großes geradzahliges N dividieren wir s^{N}r und alle s^{N}q_{i} durch p:

s^{N}r = fp + r̄
s^{N}q_{i} = g_{i}p + q̄_{i},

wobei deg(r̄) < k und deg(q̄_{i}) < k. ¬p ≡ 0 ∧ p =^{.} 0 ∧ χ ist dann äquivalent zur Disjunktion von

s =^{.} 0 ∧ (¬t ≡ 0 ∧ t =^{.} 0 ∧ χ) (1)

und

¬s =^{.} 0 ∧ (p =^{.} 0 ∧ r̄ =^{.} 0 ∧ ⋀_{i=1}^{n} q̄_{i} > 0) (2)

Das Disjunktionsglied (2) hat schon die gewünschte Form. Wenn in (1) t Null ist, ist (1) immer falsch und wir sind fertig. Sonst können wir Induktion auf die Klammer in (1) anwenden (t in der Rolle von p.). □

Lemma 2.4. Für jedes Polynom p(x, ȳ) gibt es eine quantorenfreie Formel Q_{p}^{+}(u, ȳ), die auf a und c̄ ∈ ℝ genau dann zutrifft, wenn p(x, c̄) in einer Umgebung von a rechts von a nur positive Werte annimmt.

Beweis. Sei k der Grad von p. Setze

Q_{p}^{+}(u, ȳ) = ⋁_{i=0}^{k}(p^{(i)}(u, ȳ) > 0 ∧ ⋀_{j<i} p^{(j)}(u, ȳ) =^{.} 0)

□

Man definiert entsprechend Q_{p}^{−}, ^{+}Q_{p} und ^{−}Q_{p}.

Lemma 2.5. Für jede quantorenfreie Formel ϕ(x, ȳ) ist ∃x ∈ (a, b) ϕ äquivalent zu einer quantorenfreien Formel χ(a, b, ȳ).

Beweis. Wir beweisen die Behauptung durch Induktion über den Grad k von ϕ. Nach Folgerung 2.2 können wir annehmen, daß für n > 0 und nicht–verschwindendes p einer der drei folgenden Fälle vorliegt

ϕ = q_{1} > 0 ∧ ⋯ ∧ q_{n} > 0
ϕ = p =^{.} 0
ϕ = p =^{.} 0 ∧ q_{1} > 0 ∧ ⋯ ∧ q_{n} > 0

Wir verwenden die Notation Q(u) für ⋀_{i=1}^{n} Q_{q_{i}}(u, ȳ)^{+}.

Sei P os(a, b) = P os(a, b, ȳ) die Formel, die ausdrückt, daß alle q_{i} in (a, b) nur positive Werte annehmen. P os(a, b) ist äquivalent zu

Q(a) ∧ ⋀_{i=1}^{n} ¬∃x ∈ (a, b) q_{i}(x) =^{.} 0.

Aus der Induktionsvoraussetzung folgt also, daß P os(a, b) äquivalent zu einer quantorenfreien Formel ist.

\underline{Fall 1} ∃x ∈ (a, b) ⋀_{i=1}^{n} q_{i} > 0 ist äquivalent zu

Q(a) ∨ ⋁_{i=1}^{n}(∃u ∈ (a, b) q_{i}(u) =^{.} 0 ∧ Q(u))

Weil Q(u) impliziert, daß ¬q_{i} ≡ 0, können wir q_{i}(u) =^{.} 0 ∧ Q(u) durch ¬q_{i} ≡ 0 ∧ q_{i}(u) =^{.} 0 ∧ Q(u) ersetzen. Diese Formel hat aber nach Folgerung 2.3 (o.E.) kleineren Grad als k. Die Behauptung folgt jetzt aus der Induktionsvoraussetzung.

\underline{Fall 2} ∃x ∈ (a, b) p =^{.} 0 ist äquivalent zur Disjunktion der Formeln

p ≡ 0
Q_{p}^{+}(a) ∧^{−}Q_{p}(b)
Q_{p}^{−}(a) ∧^{+}Q_{p}(b)
Q_{p}^{+}(a) ∧^{+}Q_{p}(b) ∧ ∃x ∈ (a, b) (p′(x) = 0 ∧ p(x) ≤ 0)
Q_{p}^{−}(a) ∧^{−}Q_{p}(b) ∧ ∃x ∈ (a, b) (p′(x) = 0 ∧ p(x) ≥ 0)

Die Formeln sind alle zu quantorenfreien äquivalent. Die letzte Formel zum Beispiel impliziert, daß p nicht konstant ist, wir können also p′(x) = 0 ∧ p(x) ≥ 0 durch ¬p′ ≡ 0 ∧ p′(x) = 0 ∧ p(x) ≥ 0 ersetzen. Das erlaubt die Anwendung von Folgerung 2.3 und der Induktion.

Wir schreiben P N(a, b, ȳ) für die quantorenfreie Formel, die ausdrückt, daß P os(a, b) und ∃x ∈ (a, b) p =^{.} 0. Beachte, daß diese Formel ¬q_{i} ≡ 0 impliziert.

\underline{Fall 3} ∃x ∈ (a, b) (p =^{.} 0 ∧ ⋀_{i=1}^{n} q_{i} > 0) ist äquivalent zur Disjunktion der Formeln

P N(a, b)

⋁_{i=0}^{n} ∃u ∈ (a, b) (q_{i}(u) =^{.} 0 ∧ P N(u, b))

⋁_{j=0}^{n} ∃v ∈ (a, b) (q_{j}(v) =^{.} 0 ∧ P N(a, v))

⋁_{i,j=0}^{n} ∃u ∈ (a, b) (q_{i}(u) =^{.} 0 ∧ ∃v ∈ (u, b) (q_{j}(v) =^{.} 0 ∧ P N(u, v)))

Diese Formeln sind alle zu quantorenfreien Formeln äquivalent. Zum Beispiel die letzte Formel: Weil P N(u, v) impliziert, daß ¬q_{j} ≡ 0, ist q_{j}(v) =^{.} 0 ∧ P N(u, v) zu einer quantorenfreien Formel χ_{1}(u, v) von kleinerem Grad als k äquivalent (Folgerung 2.3). Nach Induktion ist ∃v ∈ (u, b) χ_{1}(u, v) zu einer quantorenfreien Formel χ_{2}(u, b) äquivalent. Weil χ_{2}(u, b) impliziert, daß ¬q_{j} ≡ 0, ist q_{i}(u) =^{.} 0 ∧ χ_{2}(u, b) zu einer quantorenfreien Formel χ_{3}(u, b) vom Grad kleiner als k äquivalent. Induktion liefert, daß ∃u ∈ (a, b)χ_{3}(u, b) quantorenfrei ist. □

Satz 2.6. ℝ hat Quantorenelimination.

Beweis. ∃xϕ(x) ist äquivalent zur Disjunktion der Formeln

∃x ∈ (−1, 1)ϕ(x)
ϕ(−1) ∨ ϕ(1)

∃x ∈ (−1, 1)(¬x =^{.} 0 ∧ ϕ(x^{−1}))

□

Das hier angegebene Quantoreneliminationverfahren ist sehr ineffektiv. In [2] findet man ein Verfahren, das Formeln der Länge n in 2^{2^{n}} Schritten in eine äquivalente quantorenfreie umwandelt. Man weiß, daß es kein Verfahren gibt, das weniger als 2^{n} Schritte braucht.

Literatur

[1] Kreisel, Georg und Jean-Louis Krivine: Modelltheorie. Eine Einführung in die mathematische Logik und Grundlagentheorie. Springer, 1972.

[2] Specker, Ernst und Volker Strassen (Herausgeber): Komplexität von Entscheidungsproblemen, Band 43 der Reihe Lecture Notes in Computer Science. Springer, 1976.