MHB Is this a correct application of the reduction method?

[mathmari]

Hey!

Is the following formulation of the reduction correct? Undecidability of an (positive) existential theory $T$ is proved often by reduction, i.e., by interpreting another (positive) existential theory $T'$, known to be undecidable, in $T$.

Each formula $\phi'$ of the language of $T'$ is translated into a formula $\phi$ of the language of $T$.

So, the (positive) existential theory $T'$ is reduced to the (positive) existential theory $T$.

Since $T'$ is undecidable, $T$ is also undecidable.
An other way to apply the reduction is the following: We suppose that the (positive) existential theory $T$ is decidable. We want to interpret $T$ in another (positive) existential theory $T'$, known to be undecidable.

Each formula $\phi$ of the language of $T$ is translated into a formula $\phi'$ of the language of $T'$.

So, the (positive) existential theory $T$ is reduced to the (positive) existential theory $T'$.

Since $T'$ is undecidable and we have supposed that $T$ is decidable, we aget a contradiction.

So, $T$ is also undecidable.

Is everything correct? Could I improve something at the formulation?

 

[mathmari]

I changed the formulation...

Undecidability of an (positive) existential theory $T$ is proved often by reducing an other (positive) existential theory $T'$, which is known to be undecidable,to $T$, i.e., by a mapping from the (positive) existential sentences in the language of $T'$ to the (positive) existential sentences in the language of $T$, $$\phi' \mapsto \phi$$ such that $T'$ proves $\phi'$ iff $T$ proves $\phi$.
Is the formulation now correct? Could I improve something?

 

[Evgeny.Makarov]

I agree. Of course, the mapping $\phi'\mapsto\phi$ has to be computable. I also don't think that "positive" and "existential" are important here; this construction works for any fragment of $T'$ and $T$.

 

[mathmari]

Ok... Thanks a lot! (Smile)