Welche ist die existentielle Formel?

25.08.2015, 11:57	mariem	Auf diesen Beitrag antworten »
Welche ist die existentielle Formel? Hallo, ich lese den folgenden Ausschnitt von einen Paper: [attach]38968[/attach] Ich habe folgendes nicht verstanden... Wir sagen dass von den Lemma 2, hat $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ die Eigenschaft der Teilbarkeit. Kommen wir zu diesen Ergebniss weil dieses Lemma als eine existentielle Formel geschrieben werden kann die in $\begin{eqnarray} F[t,t^{-1}] \end{eqnarray}$ gilt? Aber in der Sprache ist die Teilbarkeit nicht erhalten. Welche ist die existentielle Formel?
25.08.2015, 12:45	ollie3	Auf diesen Beitrag antworten »
RE: Welche ist die existentielle Formel? hallo, ja selbstverständlich kann man die teilbarkeit auch in F[t,t^(-1)] darstellen. t^(n-1) \| t^(m-1) heisst nichts anderes als es gibt ein a el.von F[t,t^(-1)], für das gilt a*t^(n-1)=t^(m-1). gruss ollie3
26.08.2015, 19:46	mariem	Auf diesen Beitrag antworten »
RE: Welche ist die existentielle Formel? Ich verstehe... Vielen Dank!!
30.08.2015, 22:56	mariem	Auf diesen Beitrag antworten »
Bei den Beweis wollen die existentielle Theorie von $\begin{eqnarray} F[t, t^{-1}] \end{eqnarray}$ zu der existentiellen Theorie von $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ mit der Eigenschaft der Addition, Teilbarkeit, und der Relation $\begin{eqnarray} (\exists s\in\mathbb{Z})m=p^sn \end{eqnarray}$ reduzieren oder umgekehrt?
31.08.2015, 00:58	mariem	Auf diesen Beitrag antworten »
Also ist der Beweis der folgende? Wir behaupten dass die existentielle Theorie von $\begin{eqnarray} F[t,t^{-1}] \end{eqnarray}$ entscheidbar ist, also gibt es einen Algorithmus der existentielle Fragen in $\begin{eqnarray} F[t,t^{-1}] \end{eqnarray}$ antwortet. Wir wollen die existentielle Theorie von $\begin{eqnarray} F[t, t^{-1}] \end{eqnarray}$ zu der existentiellen Theorie von $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ mit der Eigenschaft der Addition, Teilbarkeit und der Relation $\begin{eqnarray} (\exists s\in\mathbb{Z})m=p^sn \end{eqnarray}$ reduzieren, die unentscheidbar ist. Die Abbildung der Reduktion ist $\begin{eqnarray} t^n\mapsto n \end{eqnarray}$ . Von den Lemma 1, dass jedes Element $\begin{eqnarray} x \in F[t, t^{-1}] \end{eqnarray}$ als eine Potenz von t ist, kann man als eine existentielle Formel schreiben $\begin{eqnarray} \phi (x) \ \ : \ \ (\exists y)(\exists z)((xy=1) \land (x-1=(t-1)z)) \end{eqnarray}$ Wir haben dass $\begin{eqnarray} t^mt^n=t^{m+n} \mapsto m+n \end{eqnarray}$ , also hat das $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ die Eigenschaft der Addition. Von Lemma 4 haben wir dass $\begin{eqnarray} n \mid m \Leftrightarrow t^n-1 \mid t^m-1 \end{eqnarray}$ und da $\begin{eqnarray} t^n-1 \mid t^m-1 \Leftrightarrow \exists a \in F[t, t^{-1}] : a(t^n-1)=t^m-1 \end{eqnarray}$ haben wir dass die Relation $\begin{eqnarray} n \mid m \end{eqnarray}$ existentiell definierbar ist. Also hat das $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ die Eigenschaft der Teilbarkeit. Von den Lemma 5 haben wir dass $\begin{eqnarray} (\exists s \in \mathbb{Z} ) m=np^s \Leftrightarrow (t^m-1)/(t^n-1) \end{eqnarray}$ ein Quadrat in $\begin{eqnarray} F[t, t^{-1}] \end{eqnarray}$ ist $\begin{eqnarray} \Leftrightarrow \exists b \in F[t, t^{-1}] : t^m-1 =b^2(t^n-1) \end{eqnarray}$ . Also die Relation $\begin{eqnarray} (\exists s \in \mathbb{Z} ) m=np^s \end{eqnarray}$ ist existentiell definierbar, also hat das $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ die Eigenschaft der Relation $\begin{eqnarray} (\exists s \in \mathbb{Z} ) m=np^s \end{eqnarray}$ . Also wenn man einen Algorithmus hat dass auf existentielle Fragen von $\begin{eqnarray} F[t, t^{-1}] \end{eqnarray}$ antwortet, kann man diesen zu einen Algorithmus umändern das auf existentielle Fragen von $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ mit der Eigenschaft der Addition, Teilbarkeit und der Relation $\begin{eqnarray} (\exists s\in\mathbb{Z})m=p^sn \end{eqnarray}$ antwortet. Da die existentielle Theorie von $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ mit der Eigenschaft der Addition, Teilbarkeit und der Relation $\begin{eqnarray} (\exists s\in\mathbb{Z})m=p^sn \end{eqnarray}$ unentscheidbar ist, kommen wir zum Ergebnis dass die existentielle Theorie von $\begin{eqnarray} F[t, t^{-1}] \end{eqnarray}$ unentscheidbar ist. Habe ich den Beweis richrig verstanden? Kann man etwas bei meiner Formulierung des Beweises verbessern?
31.08.2015, 09:52	ollie3	Auf diesen Beitrag antworten »
hallo, ja, soweit ich das beurteilen kann, sieht das alles sehr gut und logisch aus. Ich bin aber kein profi und kann dir keine garantie für alles geben. Ich nehme an, das es sich um eine abschlussarbeit (vielleicht schon doktorarbeit) an der universität handelt. Ich wünsche dir alles gute! gruss ollie3
Anzeige

06.09.2015, 23:41	mariem	Auf diesen Beitrag antworten »
Ich lese diesen Paper wegen meiner Masterarbeit. Ich habe noch eine Frage... Um zu zeigen dass die positive existentielle Theorie unentscheidbar ist, kann man einfach in den Theorem und in den Beweis das "existential theory" zu "positive existential theory" umändern? Der Unterschied zwischen "existentiell" und "positiv existentiell" ist dass die Formeln in der positiv existentielle Theorie kein Negation inhalten, oder nicht? Die Formeln in den Beweis sind alle positive existentiell definiert. Ist das richtig?
10.09.2015, 18:36	mariem	Auf diesen Beitrag antworten »
Ich habe noch eine Frage... Warum gilt das Theorem nicht für $\begin{eqnarray} p=2 \end{eqnarray}$ ?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »