Lema 1.
Para cualquier $x$ en el ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: los polinomios en la $t$ $t^{-1}$ con coeficientes en el campo $F$), $x$ es un poder de $t$ si y sólo si $x$ divide $1$ $t-1$ divide $x-1$ (el divisibilities se refería, por supuesto, en $F[t, t^{-1}]$).
Lema 2.
$t^n-1$ divide $t^m-1$ en $F[t, t^{-1}]$ ($F[t,t^{-1}]$: los polinomios en la $t$ $t^{-1}$ con coeficientes en el campo de $F$) si y sólo si $n$ divide $m$$\mathbb{Z}$.
Lema 3.
Suponga que la característica de $F$$p$$p>2$. A continuación, $(t^m-1)/(t^n-1)$ es un cuadrado en $F[t, t^{-1}]$ ($F[t,t^{-1}]$: los polinomios en la $t$ $t^{-1}$ con coeficientes en el campo de $F$) si y sólo si $(\exists s \in \mathbb{Z}) m=np^s$.
TEOREMA.
Suponga que $F$ tiene características de las $p>2$. A continuación, el existencial de la teoría de la $F[t, t^{-1}]$ es indecidible.
PRUEBA.
Pensamos de los poderes de la $t$ como la representación de los números enteros; por lo tanto, $t^n$ representa el entero $n$. Por el Lema $1$, el conjunto de poderes de $t$ es existencialmente definibles.
La suma de enteros $m+n$ corresponde a la multiplicación de los correspondientes poderes de $t$, $t^mt^n$.
Por el Lema $2$, de la relación "$n$ divide $m$ " ($n$$m$se dan a través de sus correspondientes potencias $t^n$$t^m$) es existencialmente definibles.
Por otra parte, la relación $(\exists s \in \mathbb{Z})m=p^sn$, por el Lema $3$, también es existencialmente definibles.
Por lo tanto, si tenemos un algoritmo para responder a preguntas existenciales sobre $F[t, t^{-1}]$, se podría convertir en un algoritmo para responder a preguntas existenciales en $\mathbb{Z}$ con la estructura de la adición, la divisibilidad, y la relación $(\exists s \in \mathbb{Z})m=p^sn$.
En otro documento se muestra que la última estructura indecidible positivo existencial de la teoría (de forma más precisa, se puede definir la multiplicación positiva de modo existencial en ella, y por lo tanto, la complejidad de su positivo existencial de la teoría es la misma que la complejidad de la positiva existencial de la teoría de la $\mathbb{Z}$ con la adición y la multiplicación).
De ello se sigue que la teoría existencial de $F[t, t^{-1}]$ es indecidible.
$$$$
¿Cómo llegamos a la conclusión de los lemas para el siguiente? Realmente no he entendido... ¿Podría explicar a mí?
Por lo tanto, si tenemos un algoritmo para responder a preguntas existenciales sobre $F[t, t^{-1}]$, se podría convertir en un algoritmo para responder a preguntas existenciales en $\mathbb{Z}$ con la estructura de la adición, la divisibilidad, y la relación $(\exists s \in \mathbb{Z})m=p^sn$.
$$$$
EDIT1 :
El lenguaje es $\{+,\cdot , 0,1,t\}$.
Leí de nuevo la prueba y me undetstood la siguiente:
Suponemos que el existencial de la teoría de la $F[t,t^{-1}]$ es decidable, que significa que existe un algoritmo que responde a las preguntas existenciales sobre $F[t,t^{-1}]$.
Queremos reducir a la teoría existencial de $\mathbb{Z}$ con la estructura de la adición, la divisibilidad, y la relación $(\exists s\in\mathbb{Z})m=p^sn$, que es indecidible.
Para ello, hacemos lo siguiente:
Una parte de la "traducción" de la reducción es la asignación de $t^n\mapsto n$.
Así, el conjunto de "las potencias de t" corresponde a "enteros".
Por lo tanto, tenemos que ser capaces de "filtrar" los poderes de la $t$ de todos los otros elementos de la $F[t, t^{-1}]$, de un modo existencial, según el Lema $1$, permitidas por el lenguaje.
Tenemos que $t^mt^n=t^{m+n}\mapsto m+n$ $\mathbb{Z}$ tiene la estructura de adición.
Por el Lema $2$ , $\mathbb{Z}$ tiene la estructura de la divisibilidad.
Y por Lema $3$, $\mathbb{Z}$ tiene la estructura de la relación $(\exists s\in \mathbb{Z})m=np^s$.
Es que la idea de la reducción? He entendido correctamente?
$$$$
EDIT2:
Estoy leyendo de nuevo la prueba y me quedé atrapado en el siguiente punto:
Nos dicen que por el Lema $2$, $\mathbb{Z}$ tiene la estructura de la divisibilidad.
¿Llegamos a la conclusión de que, debido a este lema se puede escribir como una fórmula existencial que es verdadero en $F[t,t^{-1}]$ ?
Pero el lenguaje no consiste de la divisibilidad. Cómo es esta última fórmula?
$$$$
EDIT3:
¿Por qué no el teorema de pie también para $p=2$ ?
