Unentscheidbarkeit der existentiellen Theorie

22.08.2015, 14:09

mariem

Auf diesen Beitrag antworten »

Unentscheidbarkeit der existentiellen Theorie

Hallo,

ich lese den folgenden Ausschnitt von einen Paper:

[attach]38952[/attach]

Ich habe nicht so richtig verstanden wie man in der Beweis von den Theorem 3, zeigt dass $\begin{eqnarray*} F[u, u^{-1}] \end{eqnarray*}$ auch in der Sprache $\begin{eqnarray*} \{0, 1, u+u^{-1}/2, +, \cdot \} \end{eqnarray*}$ unentscheidbar ist.

Könnt ihr mir diesen Teil erklären?

22.08.2015, 14:27

Captain Kirk

Auf diesen Beitrag antworten »

Die identische Anfrage findet sich auch hier:
matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=210716&start=0&lps=1543008#v1543008

22.08.2015, 14:27

Elvis

Auf diesen Beitrag antworten »

Nur den Ausschnitt lesen reicht nicht. Du musst das ganze Paper lesen, vielleicht verstehst Du es dann. Wenn nicht, musst Du die Literatur lesen, auf die sich das Paper bezieht. Wenn das immer noch nicht reicht, musst Du versuchen, die Grundlagen der Literatur zu verstehen.

24.08.2015, 13:39

mariem

Auf diesen Beitrag antworten »

Ich habe den Bedweis noch einmal durchgelesen und ich habe folgendes verstanden:

Die Abbildung der Reduktion ist $\begin{eqnarray*} u \mapsto u-t=:v \end{eqnarray*}$ .
Wir schreiben alle Gleichungen in der Form $\begin{eqnarray*} fv=g \end{eqnarray*}$ wobei $\begin{eqnarray*} f,g \in F[t] \end{eqnarray*}$ und wenn wir den Quadrat der Gleichungen berechnen bekommen wir $\begin{eqnarray*} f^2v^2=g^2 \Rightarrow f^2(t^2-1)=g^2 \end{eqnarray*}$ , also alle diese Gleichungen sind in $\begin{eqnarray*} F[t] \end{eqnarray*}$ , wobei $\begin{eqnarray*} t=(u+u^{-1})/2 \end{eqnarray*}$ .

Ist das richtig?

24.08.2015, 16:49

ollie3

Auf diesen Beitrag antworten »

hallo,
du hast zwar den beweistext einigermassen richtig übersetzt, aber ich hoffe, das
du auch den sinn richtig verstanden hast.
Es geht ja darum zu begründen, wie man von der unentscheidbarkeit in F[u, u^(-1)]
auf die unentscheidbarkeit in F[t] schliessen kann, insbesondere weil u und u^(-1)
nicht direkt in F[t] drin sind. Aber durch den trick mit dem substiruieren, in eine andere
form schreiben und quadrieren kann man dieses problem umgehen und so die
unentscheidbarkeit auch in F[t] begründen... Augenzwinkern

Augenzwinkern

gruss ollie3

25.08.2015, 00:49

mariem

Auf diesen Beitrag antworten »

Ich habe den ganzen Beweis von Theorem 3 folgenderweise verstanden:

Wir wissen dass die existentielle Theorie von $\begin{eqnarray*} F[u, u^{-1}] \end{eqnarray*}$ in der Sprache $\begin{eqnarray*} \{+, \cdot , 0, 1, u\} \end{eqnarray*}$ unentscheidbar ist.

Wir wollen zeigen dass die existentielle Theorie von $\begin{eqnarray*} F[t] \end{eqnarray*}$ in der Sprache $\begin{eqnarray*} \{+, \cdot , 0, 1, t\} \end{eqnarray*}$ auch unentscheidbar ist.

Um das zu zeigen, tun wir folgendes:

Wir setzen $\begin{eqnarray*} u=t+\sqrt{t^2-1} \end{eqnarray*}$ . Also haben wir $\begin{eqnarray*} u^{-1}=t-\sqrt{t^2-1} \end{eqnarray*}$ .

Also haben wir $\begin{eqnarray*} F[u, u^{-1}]=F[t, \sqrt{t^2-1}] \end{eqnarray*}$ . Also ist $\begin{eqnarray*} F[u, u^{-1}] \end{eqnarray*}$ eine Erweiterung von $\begin{eqnarray*} F[t] \end{eqnarray*}$ .
Jedes Element $\begin{eqnarray*} x \end{eqnarray*}$ von $\begin{eqnarray*} F[u, u^{-1}] \end{eqnarray*}$ kann folgenderweise geschrieben werden:
$\begin{eqnarray*} x=a+b\sqrt{t^2-1} \end{eqnarray*}$ , wobei $\begin{eqnarray*} a,b \in F[t] \end{eqnarray*}$

Also die Abbildung der Reduktion ist $\begin{eqnarray*} x \mapsto (a,b) \end{eqnarray*}$ .

$\begin{eqnarray*} + \ \ : \ \ x_1+x_2=a_1+b_1\sqrt{t^2-1}+a_2+b_2\sqrt{t^2-1}=(a_1+a_2)+(b_1+b_2)\sqrt{t^2-1} \mapsto (a_1+a_2, b_1+b_2) \end{eqnarray*}$

$\begin{eqnarray*} \cdot \ \ : \ \ x_1\cdot x_2=(a_1+b_1\sqrt{t^2-1})(a_2+b_2\sqrt{t^2-1})=a_1 \cdot a_2+a_1 \cdot b_2 \sqrt{t^2-1}+a_2 \cdot b_1\sqrt{t^2-1}+b_1 \cdot b_2 (t^2-1)=(a_1 \cdot a_2+b_1 \cdot b_2 (t^2-1))+(a_1 \cdot b_2+a_2 \cdot b_1)\sqrt{t^2-1} \mapsto (a_1 \cdot a_2+b_1 \cdot b_2 (t^2-1), a_1 \cdot b_2+a_2 \cdot b_1) \end{eqnarray*}$

$\begin{eqnarray*} 0\ \ : \ \ 0=0+0 \sqrt{t^2-1} \mapsto (0,0) \end{eqnarray*}$

$\begin{eqnarray*} 1 \ \ : \ \ 1=1+0 \sqrt{t^2-1} \mapsto (1,0) \end{eqnarray*}$

$\begin{eqnarray*} u \ \ : \ \ u \mapsto u-t=:v \end{eqnarray*}$ . Wir schreiben alle Gleichungen in der Form $\begin{eqnarray*} fv=g \end{eqnarray*}$ wobei $\begin{eqnarray*} f,g \in F[t] \end{eqnarray*}$ und wenn wir den Quadrat der Gleichungen berechnen bekommen wir $\begin{eqnarray*} f^2v^2=g^2 \Rightarrow f^2(t^2-1)=g^2 \end{eqnarray*}$ , also alle diese Gleichungen sind in $\begin{eqnarray*} F[t] \end{eqnarray*}$ , wobei $\begin{eqnarray*} t=(u+u^{-1})/2 \end{eqnarray*}$ .

Da die existentielle Theorie von $\begin{eqnarray*} F[u, u^{-1}] \end{eqnarray*}$ in der Sprache $\begin{eqnarray*} \{+, \cdot , 0, 1, u\} \end{eqnarray*}$ unentscheidbar ist, folgt es dass die existentielle Theorie von $\begin{eqnarray*} F[t] \end{eqnarray*}$ in der Sprache $\begin{eqnarray*} \{+, \cdot , 0, 1, t\}] \end{eqnarray*}$ unentscheidbar ist.

Ist das richtig? Kann man in den letzten Satz in der Sprache einfach $\begin{eqnarray*} t \end{eqnarray*}$ anstatt $\begin{eqnarray*} u \end{eqnarray*}$ schreiben?

Anzeige

25.08.2015, 09:24

ollie3

Auf diesen Beitrag antworten »

Hallo,
Heute morgen war eine technische Störung, hatte dir deswegen per E-Mail geantwortet.
Also, du hast den Beweis vollständig und richtig verstanden. Freude

Freude

Und ja, man muss sogar t anstatt u schreiben, das ist ja der Sinn von dem Beweis, das
Man durch die Substitutionen alle Gleichungen mit u und u^(-1) in Gleichungen mit t
Umschreiben kann.
Grüß ollie3

25.08.2015, 11:28

mariem

Auf diesen Beitrag antworten »

Vielen Dank!! smile

smile

26.08.2015, 19:11

mariem

Auf diesen Beitrag antworten »

Ich habe noch eine Frage... Den Lemma 1 haben wir in der Beweis von Theorem 3 nicht benutzt. Oder doch?

29.08.2015, 07:51

ollie3

Auf diesen Beitrag antworten »

Hallo,
Doch, das Lemma braucht man als Voraussetzung, das man jede Zahl aus F[u,u^(-1)] in der Form
x=a+b×sqrt(t^2-1) schreiben kann. Augenzwinkern

Augenzwinkern

Grüß ollie3

29.08.2015, 14:25

mariem

Auf diesen Beitrag antworten »

Kannst du mir das erklären? Warum ist das Lemma 1 die Voraussetzung, dass man jede Zahl aus $\begin{eqnarray*} F[u,u^{-1}] \end{eqnarray*}$ in der Form $\begin{eqnarray*} x=a+b\sqrt{t^2-1} \end{eqnarray*}$ schreiben kann?
Kann man nicht jede Zahl so schreiben weil $\begin{eqnarray*} \{1, \sqrt{t^2-1}\} \end{eqnarray*}$ die Basis von $\begin{eqnarray*} F[u, u^{-1}] \end{eqnarray*}$ über $\begin{eqnarray*} F[t] \end{eqnarray*}$ ist?

29.08.2015, 18:01

ollie3

Auf diesen Beitrag antworten »

hallo,
du hast deine frage eigentlich schon selbst beantwortet Augenzwinkern

Augenzwinkern

, denn in $\begin{eqnarray*} F[u, u^{-1}] \end{eqnarray*}$ sind
viele elemente, die in $\begin{eqnarray*} F[t] \end{eqnarray*}$ nicht drin sind, das liegt daran, das man $\begin{eqnarray*} \sqrt{t^2-1} \end{eqnarray*}$ nicht mit $\begin{eqnarray*} F[t] \end{eqnarray*}$ erzeugen kann. Und das lemma 1 ist die vorausetzung, das man jedes x so aufspalten kann.
gruss ollie3

29.08.2015, 18:55

mariem

Auf diesen Beitrag antworten »

Ich habe immer noch nicht so richtig verstanden warum das Lemma 1 die Voraussetzung ist, dass man jedes x so aufspalten kann.

30.08.2015, 18:28

ollie3

Auf diesen Beitrag antworten »

hallo,
das kann ich dir erklären: Augenzwinkern

Augenzwinkern

Im lemma ist doch die gleichung $\begin{eqnarray*} x_n + \sqrt{t^2-1}y_n=(t+\sqrt{t^2-1})^n \end{eqnarray*}$ .
Auf der linken seite haben wir schon die gewünschte form, und es ist so, das die rechte
seite tatsächlich jeden beliebeigen zahlenwert z annehmen kann.
Das funktioniert so: für alle zahlen ab z gleich 1 kann man ein geeignetes t finden, für alle zahlen zwischen 0 und 1 nimmt man ein negatives n (das ist in dem lemma erlaubt), sodass 1/z wieder grösser als 1 wird, für z =0 setzt man x_n und y_n gleich 0, und für negative z nimmt
man dann einfach - x_n und - y_n. So ist tatsächlich jede zahl in dieser form zerlegbar. Augenzwinkern

Augenzwinkern

gruss ollie3

PS: ich freue mich, das wir diesen anspruchsvollen beweis vollständig klären konnten.

31.08.2015, 14:55

mariem

Auf diesen Beitrag antworten »

Zitat:

Original von ollie3
...das die rechte seite tatsächlich jeden beliebeigen zahlenwert z annehmen kann.
Das funktioniert so: für alle zahlen ab z gleich 1 kann man ein geeignetes t finden, für alle zahlen zwischen 0 und 1 nimmt man ein negatives n (das ist in dem lemma erlaubt), sodass 1/z wieder grösser als 1 wird, für z =0 setzt man x_n und y_n gleich 0, und für negative z nimmt
man dann einfach - x_n und - y_n. So ist tatsächlich jede zahl in dieser form zerlegbar.

Was ist das z für ein Element? Ist es ein Element aus $\begin{eqnarray*} F[t, \sqrt{t^2-1}] \end{eqnarray*}$ ?

31.08.2015, 16:13

ollie3

Auf diesen Beitrag antworten »

hallo,
ja, aber ich glaube mittlerweile, das meine überlegungen prinzipiell falsch sind, denn
die gleichung in dem lemma soll ja für alle t gelten und nicht nur für ein bestimmtes.
Ich werde die ganze sache noch einmal überdenken.
gruss ollie3

31.08.2015, 18:35

mariem

Auf diesen Beitrag antworten »

Die Elemente von $\begin{eqnarray*} F[t, \sqrt{t^2-1}] \end{eqnarray*}$ sind Polynome in $\begin{eqnarray*} t \end{eqnarray*}$ und $\begin{eqnarray*} \sqrt{t^2-1} \end{eqnarray*}$ .

Man kann jedes Element von $\begin{eqnarray*} F[t, \sqrt{t^2-1}] \end{eqnarray*}$ folgenderweise schreiben:

$\begin{eqnarray*} \sum_{i = -n}^n a_i (t+\sqrt{t^2-1})^i \end{eqnarray*}$

Und da (laut den Lemma 1) $\begin{eqnarray*} (t+\sqrt{t^2-1})^n=x_n+\sqrt{t^2-1}y_n \end{eqnarray*}$ haben wir dass jedes Element von $\begin{eqnarray*} F[t, t^{-1}] \end{eqnarray*}$ in der Form $\begin{eqnarray*} a+b\sqrt{t^2-1} \end{eqnarray*}$ geschieben werden kann.

Ist das so richtig?

31.08.2015, 18:54

ollie3

Auf diesen Beitrag antworten »

hallo,
ja, das sieht jetzt sehr gut aus. Freude

Freude

gruss ollie3

31.08.2015, 19:11

mariem

Auf diesen Beitrag antworten »

Von den Lemma 1 haben wir dass $\begin{eqnarray*} (x_n,y_n) \end{eqnarray*}$ die Lösung der Gleichung $\begin{eqnarray*} X^2-(t^2-1)Y^2=1 \end{eqnarray*}$ ist. Welche Information haben wir davon?
Spielt das eine Rolle um jedes Element von $\begin{eqnarray*} F[t, \sqrt{t^2-1}] \end{eqnarray*}$ in der Form $\begin{eqnarray*} a+b\sqrt{t^2-1} \end{eqnarray*}$ zu schreiben?

01.09.2015, 01:07

mariem

Auf diesen Beitrag antworten »

Ich bin jetzt ein bisschen durcheinander...

Schreibt man nicht immer jedes Element von $\begin{eqnarray*} F[t, \sqrt{t^2-1}] \end{eqnarray*}$ in der Form $\begin{eqnarray*} a+b\sqrt{t^2-1} \end{eqnarray*}$ wobei $\begin{eqnarray*} a,b \in F[t] \end{eqnarray*}$ , und nicht wegen den Lemma?

01.09.2015, 08:00

ollie3

Auf diesen Beitrag antworten »

hallo,
ja, ich weiss, du hast jetzt $\begin{eqnarray*} F[u,u^{-1}] \end{eqnarray*}$ und $\begin{eqnarray*} F[t] \end{eqnarray*}$ durcheinander gebracht. Big Laugh

Big Laugh

Aber das macht nichts.
Und zu deiner ursprünglichen frage: die gleichung $\begin{eqnarray*} X^2 - (t^2 -1)Y^2=1 \end{eqnarray*}$
spielt nur indirekt eine rolle, nämlich inwiefern man alle zahlen der form
$\begin{eqnarray*} x_n+ \sqrt(t^2-1)y_n \end{eqnarray*}$ in einen zusammenhang bringen kann.
Man jongliert in diesem beweis sozusagen mit gleichungen, bringt sie in eine
andere form und stellt zusammenhänge her.
gruss ollie3

01.09.2015, 12:41

mariem

Auf diesen Beitrag antworten »

Zitat:

Original von ollie3
die gleichung $\begin{eqnarray*} X^2 - (t^2 -1)Y^2=1 \end{eqnarray*}$
spielt nur indirekt eine rolle, nämlich inwiefern man alle zahlen der form
$\begin{eqnarray*} x_n+ \sqrt(t^2-1)y_n \end{eqnarray*}$ in einen zusammenhang bringen kann.
Man jongliert in diesem beweis sozusagen mit gleichungen, bringt sie in eine
andere form und stellt zusammenhänge her.

Ich habe das jetzt nicht so richtig verstanden...

Da jedes Element von $\begin{eqnarray*} F[t, \sqrt{t^2-1}] \end{eqnarray*}$ in der Form $\begin{eqnarray*} x_n+ \sqrt(t^2-1)y_n \end{eqnarray*}$ geschrieben werden kann, hat man dass jedes Element von $\begin{eqnarray*} F[t, \sqrt{t^2-1}] \end{eqnarray*}$ in der Form $\begin{eqnarray*} X^2-(t^2-1)Y^2=1 \end{eqnarray*}$ geschrieben werden kann?

Wenn man immer jedes Element von $\begin{eqnarray*} F[t, \sqrt{t^2-1}] \end{eqnarray*}$ in der Form $\begin{eqnarray*} a+b\sqrt{t^2-1} \end{eqnarray*}$ schreiben kann, wobei $\begin{eqnarray*} a, b \in F[t] \end{eqnarray*}$ , wie genau hilft uns das Lemma weiter?

01.09.2015, 16:13

ollie3

Auf diesen Beitrag antworten »

hallo,
ich bin inzwischen auch überfragt, ich glaube es ist besser wir brechen das hier erst
mal ab und du fragst einen profi (professor oder dozenten). Ich hoffe, das ich bisher
nicht zuviel unsinn erzählt habe. Augenzwinkern

Augenzwinkern

gruss ollie3

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »