1
$\begingroup$

$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?

$\endgroup$
3
  • 2
    $\begingroup$ If you're not sure which way the reduction works, try working it out. Then you'll know for sure. $\endgroup$ – Yuval Filmus Aug 23 '15 at 17:36
  • 1
    $\begingroup$ I have edited your post to ask a single question. In the future, it's normally best to ask only one question per question. Also, "please check whether my answer is correct" questions are off-topic here, as only "yes/no" answers may remain, helping neither you nor future visitors, so I removed that part. Please read related meta discussions here and here; in the future, you should instead formulate a specific question about a single element of your answer you are uncertain about. $\endgroup$ – D.W. Aug 23 '15 at 18:20
  • 1
    $\begingroup$ Please refer to the explanation of reductions at cs.stackexchange.com/q/9556/755 and cs.stackexchange.com/q/11209/755. It looks to me like that answers your question about which way the reduction needs to go. (possible duplicate?) If it's still unclear, I suggest editing the question to explain why specifically you are unsure about which way the reduction needs to go, given that information. $\endgroup$ – D.W. Aug 23 '15 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.