# Undecidability of an existential theory

$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$.

Some theorems (from https://math.stackexchange.com/questions/1382120/ft-has-undecidable-positive-existential-theory-in-the-language-cdot) are the following:

Theorem 1.

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.

Theorem 2.

Assume that $F$ has characteristic $p>2$. Then the existential theory of $F[t, t^{-1}]$ is undecidable.

Theorem 3.

If the characteristic of $F$ is other than $2$, then $F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$.

I am looking at the proof of Theorem 3 and trying to understand the last part of it.

I understand that an existential statement of $F[u, u^{-1}]$ in the language $\{+, \cdot , 0, 1, u\}$ is of the form $$\exists x_1, \dots \exists x_n \in F[u,u'] \phi(x_1, \dots , x_n)$$ where $\phi(x_1, \dots , x_n)$ can consist of $0$, $1$ and $u$ and has the operation $+$ and $\cdot$ between $0$, $1$, and $u$.

I have a question that is related to the proof of Theorem $3$.

When we know that the existential theory of $F[u, u^{-1}]$ is undecidable in the language $\{+, \cdot , 0, 1, u\}$ and we want to show that the existential theory of $F[u, u^{-1}]$ is undecidable also in the language $\{+, \cdot , 0, 1, (u+u^{-1})/2\}$, is it correct that we have to reduce the second problem to the first one?

• If you're not sure which way the reduction works, try working it out. Then you'll know for sure. – Yuval Filmus Aug 23 '15 at 17:36