4
$\begingroup$

Let $T$ be an incomplete theory, in the sense that there is a formula $\phi$ of the language of $T$ and there are two models of $T$, $M$ and $M'$, such that $\phi$ is true in $M$ and $\neg \phi$ is true in $M'$. Suppose that $T$ is interpretable in a theory $T'$, in the sense that there is a translation from the language of $T$ to the language of $T'$ which preserves logical form and such that theorems of $T$ are mapped to theorems of $T'$.

Does it follow, in general, that $T'$ is incomplete?

$\endgroup$
1
  • $\begingroup$ I updated my answer with a bit more information. $\endgroup$ Jan 27 at 18:05

1 Answer 1

4
$\begingroup$

No. For example, let $T'$ be your favorite complete theory, and let $T$ be the empty theory in the same language (with no axioms). $T$ is incomplete.

But there is a trivial interpretation of $T$ in $T'$: take the identity translation from the language of $T$ to the language of $T'$. Every theorem of $T$ (which are just the first-order validities) translates to a theorem of $T'$.

In general, the operation of "forgetting axioms" is an interpretation (where the theory with fewer axioms is interpreted in the theory with more axioms).


Maybe I should add that there is a notion of an "essentially undecidable theory". This is a theory $T$ such that for any theory $T'$ interpreting $T$, the set of consequences of $T'$ is undecidable.

In particular, $T$ is incomplete, and if $T'$ is a computably enumerable theory interpreting $T$, then $T'$ is incomplete (since the set of consequences of a complete computably enumerable theory is decidable).

The classic example of an essentially undecidable theory is Robinson's Q.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.