- #1
mathmari
Gold Member
MHB
- 5,049
- 7
Hey! 
$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$.
Some theorems 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 unecidable. 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\}$.
To clarify something...
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$.
Is this correct?
I have a question that is related to the proof of Theorem $3$: https://drive.google.com/file/d/0B7LyulQBh6efQThrT3p3Y2lQNkE/view .
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\}$, we have to reduce the second problem to the first one, right?
Is the reduction as followed:
We have set $u=t+\sqrt{t^2-1}$ and $u^{-1}=t-\sqrt{t^2-1}$.
The mapping of the reduction is $u \mapsto u-t =:v$.
We write all the equations in the form $fv=g$ where $f,g \in F[t]$ and when we square these equations we get $f^2v^2=g^2 \Rightarrow f^2(t^2-1)=g^2$, so all the equations are in $F[t]$, where $t=(u+u^{-1})/2$.
Is this correct?
$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$.
Some theorems 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 unecidable. 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\}$.
To clarify something...
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$.
Is this correct?
I have a question that is related to the proof of Theorem $3$: https://drive.google.com/file/d/0B7LyulQBh6efQThrT3p3Y2lQNkE/view .
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\}$, we have to reduce the second problem to the first one, right?
Is the reduction as followed:
We have set $u=t+\sqrt{t^2-1}$ and $u^{-1}=t-\sqrt{t^2-1}$.
The mapping of the reduction is $u \mapsto u-t =:v$.
We write all the equations in the form $fv=g$ where $f,g \in F[t]$ and when we square these equations we get $f^2v^2=g^2 \Rightarrow f^2(t^2-1)=g^2$, so all the equations are in $F[t]$, where $t=(u+u^{-1})/2$.
Is this correct?
Last edited by a moderator: