Satz von Tarski-Seidenberg. Folgerungen aus dem Projektionssatz


Bachelorarbeit, 2014

18 Seiten, Note: 1,0

Julius Konstantin (Autor:in)


Leseprobe

Inhaltsverzeichnis
1
Semialgebraische Mengen
3
2
Projektionssatz von Tarski-Seidenberg
4
2.1
Relle Nullstellen von Polynomen
. . . . . . . . . . . . . . . . . .
5
3
Folgerungen aus dem Projetionssatz
12
3.1
Angeordnete und reell abgeschlossene Körper . . . . . . . . . . .
13
3.2
Quantorenelimination
. . . . . . . . . . . . . . . . . . . . . . . .
14
3.3
Transferprinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
3.4
Hilbert's 17-tes Problem . . . . . . . . . . . . . . . . . . . . . . .
16

Zusammenfassung
Die vorliegende Arbeit soll einen Beweis des Satzes von Tarski-Seidenberg
mittels der Methode der Hermite Matrizen liefern. Außerdem werden Fol-
gerungen wie Quantorenelimination in reell abgeschlossenen Körpern und
das Transferprinzip vorgestellt, um abschließend die Lösung zum 17-ten
Problem von Hilbert zu geben.
1
Semialgebraische Mengen
Für den Satz von Tarski-Seidenberg benötigen wir zuerst den Begriff der semi-
algebraischen Menge und grundlegende Folgerungen (für weiterführende Lite-
ratur siehe: [1]). Sei dazu A ein unitärer Teilring von R, n N beliebig und
x = (x
1
, ..., x
n
).
Definition 1.1.
(i) Eine Teilmenge des R
n
heißt A-semialgebraisch, wenn sie eine endliche
boolesche Kombination (Vereinigung, Durchschnitt, Komplementbildung)
von Mengen der Gestalt
O
R
(p
1
, ..., p
s
) = O(p
1
, ..., p
s
) = {x R
n
| p
1
(x) > 0, ..., p
s
(x) > 0}
mit p
1
, ..., p
s
A[x] = A[x
1
, ...x
n
] ist. Dabei bezeichnen wir R-semialgebraische
Mengen einfach als semialgebraisch.
(ii) Eine Teilmenge des R
n
heißt A-algebraisch, wenn sie die Gestalt
V
R
(p
1
, ..., p
s
) = V (p
1
, ..., p
s
) = {x R
n
| p
1
(x) = 0, ..., p
s
(x) = 0}
mit p
1
, ...p
s
A[x] = A[x
1
, ...x
n
] hat. Dabei bezeichnen wir R-algebraische
Mengen einfach als algebraisch.
Bemerkung 1.2. Es gelten folgende Eigenschaften:
(i) Jede A-algebraische Menge ist A-semialgebraisch
(ii) Auch boolesche Kombinationen von Mengen der Form {x R
n
| f
0}
mit
{<, >, , , = =} sind A-semialgebraisch
(iii) Jede algebraische Menge ist von der Form V (p) für ein p A[x] (algebrai-
sche Mengen werden bereits von einem Polynom erzeugt)
Beweis.
V (p
1
, ..., p
s
) = V (p
2
1
+ ... + p
2
s
) = R
n
\ (O(p
2
1
+ ... + p
2
s
) O(-(p
2
1
+ ... + p
2
s
)) (1)
Damit sind (i) und (iii) bewisen. Die Beweise für (ii) erfolgen ähnlich.
Lemma 1.3 (Normalform semialgebraischer Mengen). U R
n
ist genau dann
A-semialgebraisch, wenn
U =
m
j=1
(V (p
j
) O(q
j1
, ..., q
jr
))
(2)
mit passenden m, r N und p
j
, q
ji
A[x] (1 j m, 1 i r)
3

Beweis. () Folgt direkt aus Bemerkung 1.2 (i) und der Definition 1.1 (i)
() Eine A-semialgebraische Menge M R
n
ist per Definition eine boolesche
Kombination von Mengen O(q) (q A[x]). Durch Verwendung der Gesetze von
de Morgan und der Distributivgesetze kann M als endliche Vereinigung von
Mengen der Gestalt
k
j=1
{x R
n
| q
j
(x) > 0}
m
j=k+1
{x R
n
| q
j
(x) > 0}
geschrieben werden.
Mit {x R
n
| q
j
(x) > 0} = {x R
n
| (-q
j
(x)) > 0} {x R
n
| q
j
= 0},
nochmaliger Anwendung der Distributivgesetze und Bemerkung 1.2 (iii) ergibt
sich die Behauptung.
Beispiel 1.4.
(i) Die semialgebraischen Mengen in R sind genau die endlichen Vereinigun-
gen von Punkten und offenen Intervallen (beschränkt und unbeschränkt)
(ii) Im R
n
bildet die offene Einheitskugel B
1
(0) eine semialgebraische Menge
{x R
n
| x
2
1
+ x
2
2
+ ... + x
2
n
- 1 < 0}, der Rand B
1
(0) ist sogar algebraisch
{x R
n
| x
2
1
+ x
2
2
+ ... + x
2
n
- 1 = 0}
(iii) Polynomiale Urbilder A-semialgebraischer (bzw. A-algebraischer Mengen)
sind wieder A-semialgebraisch (bzw. A-algebraisch)
Dagegen gilt dies im Allgemeinen nicht für die polynomialen Bilder von alge-
braischen Mengen. Beispielsweise ist das Bild der Kreislinie B
1
(0) im R
2
unter
der Projektion : R
2
R : (x, y) = x gleich dem Intervall [-1, 1], welches
jedoch nicht algebraisch sein kann, da Polynome nur endliche viele Nullstellen
besitzen. Jedoch gilt die Aussage für semialgebraische Mengen. Als Beispiel er-
gibt das Bild der offenen Kreisscheibe unter derselben Abbildung das Intervall
(-1, 1), welches sich als semialgebraische Menge {x R | x
2
- 1 < 0} an-
schreiben lässt. Der Beweis dieser Tatsache führt uns zum Projektionssatz von
Tarski-Seidenberg:
2
Projektionssatz von Tarski-Seidenberg
Satz 2.1 (Projektionssatz). Sei U R
d
× R
n
eine A-semialgebraische Men-
ge und : R
d
× R
n
R
n
: (x , x ) x
die Projektion auf die letzten n
Koordinaten. Dann ist (U ) R
n
wieder A-semialgebraisch.
Beweis. Ohne Beschränkung der Allgemeinheit (o.B.d.A) setzten wir d=1, der
allgemeine Fall folgt daraus durch endliche Iteration. Sei also U R × R
n
eine
A-semialgebraische Menge und (U ) das Bild der Projektion. Aus Lemma 1.3
folgt
U =
m
j=1
(V (p
j
) O(q
j1
, ..., q
jr
))
(3)
4

für gewisse m, r N und p
j
, q
ji
A[x] (1 j m, 1 i r). Für das Bild
gilt nun
(U ) =
m
j=1
(V (p
j
) O(q
j1
, ..., q
jr
))
(4)
da das Bild einer Vereinigung von Mengen gleich der Vereinigung der Bilder ist.
Deswegen genügt es die Aussage des Projektionssatzes nur für
U = V (p) O(q
1
, ..., q
r
) =
(5)
{(t, x) R × R
n
| p(t, x) = 0, q
1
(t, x) > 0, ..., q
r
(t, x) > 0}
(6)
mit p(t, x), q
j
(t, x) A[t, x] (1 j r) zu beweisen. Ein Element x R
n
liegt genau dann im Bild (U ), wenn es ein t R gibt, sodass (t, x) in U
liegt. Da A[t, x] = A[t, x
1
, ..., x
n
] = (A[x
1
, ...x
n
])[t] gilt, fassen wir p, q
1
, ..., q
r
als
Polynome in t mit Koeffizienten in A[x] auf
p := p(t, x) =
k
i=0
a
i
(x)t
i
,
q
j
:= q
j
(t, x) =
k
j
i=0
b
ji
(x)t
i
(7)
mit a
i
, b
ji
A[x]. Wir brauchen also polynomiale Gleichungen und Ungleichun-
gen, welche für jedes x R
n
entscheiden, ob es ein t R gibt, sodass p(t, x) = 0
und q
j
(t, x) > 0 für 1 j r. Dies führt uns zum nächsten Kapitel, wobei wir
anschließend wieder an diese Stelle des Beweises zurückkehren werden.
2.1
Relle Nullstellen von Polynomen
Im Folgenden werden Methoden vorgestellt, welche die Anzahl reeller Nullstellen
von Polynomen (unter Nebenbedingungen) bestimmen. Dies ist hauptsächlich
für den Beweis des Projektionssatzes wichtig, jedoch sind die Ergebnisse an sich
schon lesenswert. Die Beweisidee ist hierbei angelehnt an [4], [6] und [7].
Sei im folgenden Kapitel stets p(t) = t
d
+a
1
t
d-1
+...+a
d
ein beliebiges normiertes
Polynom über R (ungleich dem Nullpolynom) und
1
, ...,
d
die Nullstellen von
p(t) in C (mit Vielfachheit gezählt). Da es beliebig schwierig bis unmöglich ist
1
die Nullstellen eines Polyoms anhand der Koeffizienten zu bestimmen, werden
wir auf die Newtonsummen ausweichen.
Definition 2.2 (Newtonsummen).
Seien
1
, ...,
d
die Nullstellen von p(t) R[t] in C. Wir definieren für s N
die s-te Newtonsumme
s
(p) =
s
1
+ ... +
s
d
(8)
Für ein beliebiges weiteres Polynom q(t) R[t] sei außerdem die s-te verallge-
meinerte Newtonsumme definiert als:
s
(p, q) = q(
1
)
s
1
+ ... + q(
d
)
s
d
(9)
Lemma 2.3. Die (verallgemeinerten) Newtonsummen
s
(p) (
s
(p, q)) sind für
alle s N ganzzahlige Polynome in den Koeffizienten von p (und q).
1
ab Grad 5 gibt es keine explizite Lösungsformel mehr, siehe Abel-Ruffini-Theorem
5

Beweis. Definieren wir zuerst die Begleitmatrix eines Polynoms:
C
p
=
0
0
. . .
-a
d
1
0
. . .
-a
d-1
..
.
. .
.
. .
.
..
.
0
. . .
1
-a
1
(10)
Wir wollen zeigen, dass das charakteristische Polynom von C
p
, det(t · I
d
- C
p
),
genau dem Polynom p entspricht.
det(t · I
d
- C
p
) = det
t
0
. . .
a
d
-1
t
. . .
a
d-1
..
.
. .
.
. .
.
..
.
..
.
0
. . .
-1
t + a
1
=
(11)
(t + a
1
)det
t
0
. . .
0
-1
t
. . .
0
..
.
. .
.
. .
.
..
.
0
. . .
-1
t
+ det
t
0
. . .
a
d
-1
t
. . .
a
d-1
..
.
. .
.
. .
.
..
.
0
. . .
-1
a
2
=
(12)
t
d
+ a
1
t
d-1
+ a
2
t
d-2
+ det
t
0
. . .
a
d
-1
t
. . .
a
d-1
..
.
. .
.
. .
.
..
.
0
. . .
-1
a
3
= ... =
(13)
t
d
+ a
1
t
d-1
+ ... + a
d
= p(t)
(14)
wobei jeweils der Laplace'sche Entwicklungssatz nach der letzten Zeile ange-
wandt wurde. Die Eigenwerte der Begleitmatrix entsprechen also den Nullstel-
len des Polynoms (jeweils in C). Wir benützen nun folgende Eigenschaften von
Matrizen:
(i) Die Spur einer Matrix entspricht der Summe der Eigenwerte (im algebrai-
schen Abschluss und mit Vielfachheit gezählt): tr(C
p
) =
d
i=1
i
(ii) Die Eigenwerte von (C
p
)
j
sind genau
j
1
, ...,
j
d
Daraus folgt für unsere Begleitmatrix C
p
tr((C
p
)
s
) =
s
(p)
(15)
wobei sowohl die Spur (als Summe der Diagonaleinträge), als auch das Produkt
der C
p
als ganzzahlige Polynome in den Koeffizienten von p geschrieben werden
können. Für beliebiges q(t) R[t], q(t) =
m
i=0
c
i
t
i
, folgt die Aussage für die
verallgemeinerte Newtonsumme aus folgender Rechnung:
s
(p, q) =
d
j=1
s
j
·
m
i=0
c
i
i
j
=
d
j=1
·
m
i=0
c
i
s+i
j
=
m
i=0
d
j=1
c
i
s+i
j
=
(16)
m
i=0
c
i
·
d
j=1
s+i
j
=
m
i=0
c
i
·
s+i
(p)
(17)
6
Ende der Leseprobe aus 18 Seiten

Details

Titel
Satz von Tarski-Seidenberg. Folgerungen aus dem Projektionssatz
Hochschule
Universität Wien
Note
1,0
Autor
Jahr
2014
Seiten
18
Katalognummer
V347197
ISBN (eBook)
9783668364844
ISBN (Buch)
9783668364851
Dateigröße
920 KB
Sprache
Deutsch
Schlagworte
Tarski-Seidenberg, Hermite Matrizen, Quantorenelimination, Hilbert's 17. Problem
Arbeit zitieren
Julius Konstantin (Autor:in), 2014, Satz von Tarski-Seidenberg. Folgerungen aus dem Projektionssatz, München, GRIN Verlag, https://www.grin.com/document/347197

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Satz von Tarski-Seidenberg. Folgerungen aus dem Projektionssatz



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden