16
$\begingroup$

By not interpreting arithmetic, I mean it does not interprets enough arithmetic for Godel's argument (coding the syntax, finding the fix point) to work through. In other words, is there any other methods to prove that a theory does not have a computable consistent complete extension, or can we prove the converse that every such theory interprets arithmetic?

Related, is there a class of structures whose first-order theory is not computable and arithmetic is not interpreted in it?

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "arithmetic" here? PA, Robinson's Q,...? $\endgroup$ – Wojowu Sep 8 '17 at 17:38
  • $\begingroup$ Godel's theorem was proved several years earlier by Emil Leon Post. The proofs were not identical. Just in case, one could learn the Post's proof. $\endgroup$ – Wlod AA Aug 17 at 10:05
21
$\begingroup$

Any theory that can represent all recursive functions has no consistent decidable extension, however there are such theories that do not interpret even as weak an arithmetic as Robinson’s theory $R$, see my paper Recursive functions and existentially closed structures (arXiv:1710.09864 [math.LO], to appear in Journal of Mathematical Logic).

You don’t even need to represent all recursive functions. Fix a recursively inseparable pair of r.e. predicates $A,B\subseteq\mathbb N$. Let $L$ be the language consisting of one unary predicate $P$, and constants $\overline n$ for every $n\in\mathbb N$, and let $T$ be the (recursively axiomatizable) theory axiomatized by $P(\overline n)$ for $n\in A$, and $\neg P(\overline n)$ for $n\in B$. Then $T$ has no decidable consistent extension, and it does not interpret much of anything (in particular, if $S$ is a theory in a finite language interpretable in $T$, then $S$ is also interpretable in a finite-language fragment of $T$, and as such does have a decidable extension).

$\endgroup$
  • $\begingroup$ Well, I guess however we would like to understand the word "arithmetic" would include $R$... also, very nice specific example! $\endgroup$ – Wojowu Sep 8 '17 at 17:40
  • $\begingroup$ Very nice point. Thank you! Still, more more "natural" examples are welcome. :-) $\endgroup$ – Ruizhi Yang Sep 8 '17 at 17:49
4
$\begingroup$

Another example is the theory $\text{Th}(\mathcal{P}(\mathbb{R}),\subset,<)$ of subsets of the reals, where $S$ is less than $S'$ iff every element of $S$ is less than every element of $S'$.

The theory is consistent and complete by definition. Shelah proved that it is not decidable, which means it also has no decidable extension, and Gurevich and Shelah jointly proved that it does not interpret arithmetic.

To be more precise, Gurevich and Shelah work with a variant of the theory where $<$ applies only to singletons, and they prove that it does not interpret even the weak set theory of null set, singleton and union: \begin{align} \exists y \forall z &[z \notin y]\\ \forall x \exists y \forall z &[z \in y\leftrightarrow z=x]\\ \forall w \forall x \exists y \forall z &[z \in y\leftrightarrow z \in w \text{ or } z \in x]\\ \end{align} The two results on undecidability and non-interpretability are both difficult, but these questions of mine have more details.

$\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.