Is the reduction correct?

Question

Is the following formulation of the reduction correct?

EDIT:

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 everything correct? Could I improve something at the formulation?

$\phi$ is a formula of $T$, or not?

Answer 1

I'm not quite sure what you mean by "interpretation" - really, a reduction of $T$ to $T'$ should just be a function $f$ from the sentences in the language of $T$ to the sentences in the language of $T'$, such that $T$ proves $\varphi$ iff $T'$ proves $f(\varphi)$. This is much broader than a (computable) interpretation.

Regardless of exactly how you define interpretation, your second argument is wrong: saying "$T$ is reducible to $T'$" means that $T$ is no more complicated than $T'$. In particular, $T'$ can be extremely complicated and $T$ can be extremely simple. The only way to get a contradiction is to interpret a complicated theory inside a simple theory.

Answer 2

It would be best not to use the technical term reduction. For what you are working with, the following is a reasonable formulation of the strategy. Let $E$ be the set of existential sentences in some language, and let $T$ be the set of sentences of $E$ that are true in some specified structure $M$. We are interested in showing that there is no decision procedure to determine membership in $T$.

We usually find a recursive set $E'$ of sentences, and a structure $M'$, with the following properties:

(i) It is known that there is no algorithm for determining whether a sentence of $E'$ is true in $M'$, and

(ii) There is an algorithm which, given as input any sentence $\phi'$ of $E'$, produces a sentence $\phi$ of $E$ such that $\phi'$ is true in $M'$ if and only if $\phi$ is true in $M$.

For existential (or positive existential) sentences we can be more specific. Ever since the result of Matijasevich, the set $E'$ used has been, directly or indirectly, the set of existential sentences in the usual language of arithmetic, and the structure $M'$ has been the natural numbers.