The existential theory is undecidable

[mathmari]

Hey! I am reading the theorem below and I have some questions... Lemma 1.

For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and $t-1$ divides $x-1$ (the divisibilities are meant, of course, in $F[t, t^{-1}]$).

Lemma 2.

Assume that the characteristic of $F$ is zero. Then for any $n$ in the ring $F[t, t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $n$ is a nonzero integer if and only if $n$ divides $1$ and either $n-1$ divides $1$ or $n+1$ divides $1$, and there is a power $x$ of $t$, so that $(x-1)/(t-1)
\equiv n \pmod {t-1}$.

THEOREM.

Assume that the characteristic of $F$ is zero. Then the existential theory of $F[t, t^{-1}]$ in the language $\{+, \cdot , 0, 1, t\}$ is undecidable.

PROOF.

By Lemma 1, we can express the fact that an element $x$ in $F[t, t^{-1}]$ is a power of $t$ by an existential formula $\phi(x)$.

By this and Lemma 2, we can express the fact that an element $n$ of $F[t, t^{-1}]$ is an integer by the existential formula $$(\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)$$
Call the last formula $\psi(n)$.

Assume for the sake of contradiction, that the existential theory of $F[t, t^{-1}]$ is decidable.

Then we can algorithmically examine the solvability of a diophantine equation in the rational integers in the following way:

if $P(X_1, \dots , X_n)=0$ is a given diophantine equation, we consider the existential formula $$(\exists x_1) \dots (\exists x_n) P(x_1, \dots , x_n)=0 \wedge \psi(x_1) \wedge \dots \psi(x_n)$$

Clearly, the equation of whether this sentence is true in $F[t, t^{-1}]$ is equivalent to the question of whether $P=0$ has integral solutions.
But this contradicts the negative answer to Hilbert's Tenth Problem; therefore, the theorem follows. Could you explain to me the formula $\psi(n)$ ?

Could you explain to me the reduction to Hilbert's Tenth Probelm? I haven't really understood it...

 

[Valkarie]

The formula $\psi(n)$ is a way of expressing that an element $n$ of $F[t, t^{-1}]$ is an integer. It states that $n$ divides $1$, and either $n-1$ divides $1$ or $n+1$ divides $1$, and there is a power $x$ of $t$, so that $(x-1)/(t-1) \equiv n \pmod {t-1}$. The reduction to Hilbert's Tenth Problem works as follows: the existential theory of $F[t, t^{-1}]$ being decidable means that it is possible to algorithmically examine whether a given sentence containing existential quantifiers is true in $F[t, t^{-1}]$. To do this, we consider the existential formula $$(\exists x_1) \dots (\exists x_n) P(x_1, \dots , x_n)=0 \wedge \psi(x_1) \wedge \dots \psi(x_n)$$ where $P(X_1, \dots , X_n)=0$ is a given diophantine equation. This formula is equivalent to the question of whether $P=0$ has integral solutions, which is the same as asking whether the given diophantine equation has solutions in the rational integers. This contradicts the negative answer to Hilbert's Tenth Problem; therefore, the theorem follows.