Is incompleteness preserved by interpretations?

74 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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.