La teoría existencial es indecidible

Question

Lema 1.

Para cualquier $x$ en el ring $F[t,t^{-1}]$ ( $F[t,t^{-1}]$ los polinomios en $t$ y $t^{-1}$ con coeficientes en el campo $F$ ), $x$ es una potencia de $t$ sólo si $x$ divide $1$ y $t-1$ divide $x-1$ (las divisibilidades se entienden, por supuesto, en $F[t, t^{-1}]$ ).

Lema 2.

Supongamos que la característica de $F$ es cero. Entonces para cualquier $n$ en el ring $F[t, t^{-1}]$ ( $F[t,t^{-1}]$ los polinomios en $t$ y $t^{-1}$ con coeficientes en el campo $F$ ), $n$ es un número entero distinto de cero si y sólo si $n$ divide $1$ y $n-1$ divide $1$ o $n+1$ divide $1$ y hay un poder $x$ de $t$ de modo que $(x-1)/(t-1) \equiv n \pmod {t-1}$ .

TEOREMA.

Supongamos que la característica de $F$ es cero. Entonces la teoría existencial de $F[t, t^{-1}]$ en el idioma $\{+, \cdot , 0, 1, t\}$ es indecidible.

PRUEBA.

Por el Lemma 1, podemos expresar el hecho de que un elemento $x$ en $F[t, t^{-1}]$ es una potencia de $t$ mediante una fórmula existencial $\phi(x)$ .

Por esto y el Lemma 2, podemos expresar el hecho de que un elemento $n$ de $F[t, t^{-1}]$ es un número entero por la fórmula existencial $$(\exists x)(\exists y) [\phi (x) \wedge x-1 = (t-1)n+y(t-1)^2] \wedge (\exists z)(\exists w) (nz =1 \wedge ((n+1)w=1 \text{ or } (n-1)w=1)$$ Llama a la última fórmula $\psi(n)$ .

Supongamos, en aras de la contradicción, que la teoría existencial del $F[t, t^{-1}]$ es decidible.

Entonces podemos examinar algorítmicamente la resolubilidad de una ecuación diofántica en los enteros racionales de la siguiente manera:

si $P(X_1, \dots , X_n)=0$ es una ecuación diofántica dada, consideramos la fórmula existencial $$(\exists x_1) \dots (\exists x_n) P(x_1, \dots , x_n)=0 \wedge \psi(x_1) \wedge \dots \psi(x_n)$$

Evidentemente, la ecuación de si esta frase es cierta en $F[t, t^{-1}]$ es equivalente a la pregunta de si $P=0$ tiene soluciones integrales. Pero esto contradice la respuesta negativa al Décimo Problema de Hilbert; por lo tanto, el teorema se deduce.

$$$$

---

¿Podría explicarme la fórmula $\psi(n)$ ?

¿Podría explicarme la reducción al Décimo Probelma de Hilbert? Realmente no lo he entendido...

$$$$

---

$$$$

EDITAR:

¿Podemos cambiar el teorema y su demostración de la siguiente manera?

TEOREMA.

Suponemos que la característica de $F$ es cero. Entonces el positivo teoría existencial del $F[t, t^{-1}]$ en el idioma $\{+, \cdot , 0, 1, t\}$ es indecidible.

Prueba. Queremos demostrar que no existe ningún algoritmo, que dado un positivo sentencia existencial $\gamma$ responde si $\gamma$ es cierto en el ring $F[t, t^{-1}$ o no. Según Matijasevic, no hay ningún algoritmo que con la entrada de un polinomio $P(x_1, \dots , x_n)$ con coeficientes enteros, decide siempre si la ecuación $P(X-1, \dots , x_n)=0$ tiene una solución entera. Según el lema $1$ un elemento $x \in F[t, t^{-1}]$ es una potencia de $t$ si $$x \mid 1 \ \ \land \ \ t-1 \mid x-1$$ Así podemos expresar el hecho de que un elemento $x \in F[t, t^{-1}]$ es una potencia de $t$ con el positivo fórmula existencial $$\phi (x) \ \ : \ \ \exists y \exists z ((xy=1) \land (x-1=(t-1)z))$$ Según el lema $3$ , $n$ es un número entero distinto de cero si

• $n \mid 1 \ \ : \ \ (\exists z)(nz=1)$
• $n-1 \mid 1 \lor n+1 \mid 1 \ \ : \ \ (\exists w)((n+1)w=1 \text{ or } (n-1)w=1)$
• hay un poder $x$ de $t$ $\ \ : \ \ (\exists x) \phi (x)$
• $(x-1)/(t-1) \equiv n \pmod {t-1} \ \ : \ \ (\exists y)((x-1)/(t-1)-n =y(t-1)) \Rightarrow (\exists y)(x-1-n(t-1)=y(t-1)^2) \Rightarrow (\exists y)(x-1=n(t-1)+y(t-1)^2)$

Así podemos expresar el hecho de que un elemento $n \in F[t, t^{-1}]$ es un número entero con el valor positivo fórmula existencial $$\psi (n) \ \ : \ \ (\exists x)(\exists y)[\phi(x) \land x-1=(t-1)n+y(t-1)^2] \land (\exists z)(\exists w)(nz=1 \land ((n+1)w=1 \text{ or } (n-1)w=1)$$ Suponemos que el positivo fórmula existencial de $F[t, t^{-1}]$ es decidible, por lo que existe un algoritmo que decide si un positivo frase existencial es verdadera en $F[t, t^{-1}]$ . Entonces el problema de si una ecuación diofantina tiene una solución entera es decidible: la ecuación diofantina $P(x_1, \dots , x_n)=0$ tiene una solución entera si positivo sentencia existencial $$(\exists x_1) \dots (\exists x_n) ((\psi (x_1) \land \dots \land \psi (x_n)) \land P(x_1, \dots , x_n)=0)$$ es cierto en $F[t, t^{-1}]$ . Pero la respuesta a la $10^{th}$ El problema de Hilbert, es decir, si existe un algoritmo que decida si la ecuación diofantina tiene una solución entera, es negativo. Así que tenemos una contradicción. Eso significa que el positivo teoría existencial del $F[t, t^{-1}]$ es indecidible.

Answer 1

Explicamos la reducción, y más tarde, si surgen dudas, explicamos $\psi$ .

Una fórmula $\alpha(x_1,x_2,\dots, x_k)$ es existencial si tiene la forma $$\exists t_1\exists t_2\cdots \exists t_l\beta(x_1,\dots,x_k, t_1,\dots,t_l),\tag{1}$$ donde la fórmula $\beta(x_1,\dots,x_k, t_1,\dots,t_l)$ es sin cuantificador . A veces, de manera informal, como en la definición que cita de $\psi(n)$ el término fórmula existencial se utiliza para fórmulas que se pueden poner mecánicamente en la forma (1). (Nótese que, tal como están dadas, los cuantificadores existenciales no están todos delante).

Sea $F$ sea un campo de característica $0$ . Queremos demostrar que existe sin algoritmo que, dado cualquier sentencia existencial $\gamma$ nos dirá si $\gamma$ es cierto en el ring $F[t,t^{-1}]$ .

Por el resultado que culminó en el trabajo de Matijasevic, no existe ningún algoritmo que, cuando se le da como entrada un polinomio $P(X_1,\cdots,X_n)$ con coeficientes enteros, determinará siempre si la ecuación $P(X_1,\dots,X_n)=0$ tiene solución en números enteros.

Demostramos que si hubiera un algoritmo para determinar la verdad en $F[t,t^{-1}]$ de sentencias existenciales, entonces existiría un algoritmo para determinar la resolubilidad de ecuaciones diofánticas en los números enteros. Pero no existe tal algoritmo.

La estrategia de reducción es, en principio, sencilla. Dada cualquier ecuación diofantina $P(X_1,\dots,X_n)=0$ mostramos cómo construir explícitamente una frase existencial $\alpha_P$ tal que $\alpha_P$ es cierto en $F[t,t^{-1}]$ sólo si $P(X_1,\cdots,X_n)=0$ tiene solución en números enteros. Ahora supongamos que tenemos un algoritmo para determinar la verdad de las sentencias existenciales en $F[t,t^{-1}]$ . A continuación, aplicando el algoritmo a $\gamma_P$ podríamos determinar si la ecuación diofantina $P(X_1,\dots,X_n)=0$ tiene solución, contradiciendo la solución (negativa) de Hilbert $10$ -th Problem.

Por los lemas 1 y 2, existe una fórmula existencial $\psi(w)$ tal que $w\in F[t,t^{-1}]$ cumple la fórmula $\psi$ sólo si $w$ es un número entero ordinario. Así $P(X_1,\dots,X_n)=0$ tiene una solución entera si y sólo si la sentencia $$\exists x_1\cdots,\exists x_n((\psi(x_1)\land\dots\land \psi(x_n))\land P(x_1,\dots,x_n)=0)\tag{2}$$ es cierto en $F[t,t^{1}]$ . En la frase (2), la cuantificación existencial abarca $F[t,t^{-1}]$ . Las subfórmulas $\psi(x_i)$ decir informalmente " $x_i$ es un número entero ordinario".

Obsérvese que las subfórmulas $\psi(x_i)$ son existenciales, implican $4$ cuantificadores existenciales cada uno. Necesitamos utilizar $4n$ distintas variables cuantificadas existencialmente para el $\psi(x_i)$ y necesitamos traerlos al frente en (2) para que la frase resultante sea genuinamente existencial.

Eso es todo lo que hay que reducir. Supongamos además que $-1$ nunca es una suma de cuadrados en el campo $F$ . Esto es especialmente cierto si $F$ es un subcampo de los reales. A continuación, mediante un truco con el que ya estás familiarizado, decimos un poco más. Dado cualquier polinomio $P(X_1,\dots,X_n)$ con coeficientes enteros, podemos construir un polinomio $P^\ast(x_1,\dots, x_n,y_1,\dots,y_m)$ con coeficientes enteros tal que la ecuación diofantina $P(X_1,\dots,X_n)=0$ tiene solución en los números enteros si y sólo si la ecuación $P^\ast(x_1,\dots, x_n,y_1,\dots,y_m)=0$ tiene solución en $F[t,t^{-1}]$ .