Die existentielle Theorie ist unentscheidbar

03.09.2015, 00:41	mariem	Auf diesen Beitrag antworten »
Die existentielle Theorie ist unentscheidbar Hallo, wisst ihr ob es der Beweis dass die existentielle Theorie von $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ mit der Eigenschaft der Addition, Multiplikation und der Relation $\begin{eqnarray} (\exists s \in \mathbb{Z})m=np^s \end{eqnarray}$ unentscheidbar ist, auch irgendwoanders zu finden ist, ausser in den paper von J. Denef "The diophantine problem for polynomial rings of positive characteristic" ? Einige Informationen über diesen Thema: $\begin{eqnarray} \psi \end{eqnarray}$ ist eine $\begin{eqnarray} \exists \end{eqnarray}$ -Formel (existentielle Formel) : $\begin{eqnarray} \psi = \exists x_1 \dots \exists x_n \phi(x_1, \dots , x_n) \end{eqnarray}$ für eine quantorenfreie Formel $\begin{eqnarray} \phi \end{eqnarray}$ . Die existentielle Theorie eines Rings ist unentscheidbar bedeutet dass es keinen Algorithmus gibt der auf existentielle Fragen von den Ring beantwortet, also es gibt kein Algorithmus der gegeben eines existentiellen Satzes, sei $\begin{eqnarray} \gamma \end{eqnarray}$ , immer eine Antwort gibt ob der Satz $\begin{eqnarray} \gamma \end{eqnarray}$ in den Ring wahr ist oder nicht. Um die Unentscheidbarkeit einer existentiellen Theorie zu beweisen reduziert man meistens eine andere existentielle Theorie, bei der es bekannt ist dass sie unentscheidbar ist zu dieser die man beweisen will. Ein bekanntes Problem das unentscheidbar ist, ist das 10. Problem von Hilbert. In diesen Fall wollen wir die Unentscheidbarkeit der existentiellen Theorie von $\begin{eqnarray} \mathbb{Z} \end{eqnarray}$ mit der Eigenschaft der Addition, Multiplikation und der Relation $\begin{eqnarray} (\exists s \in \mathbb{Z})m=np^s \end{eqnarray}$ , beweisen. Wisst ihr wo ich den Beweis finden kann? Zwei Beiträge zusammengefasst. Steffen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »