Let $L$ be a countable language and $M$ be a model of $L^N$ (the realization of $L$ in the natural numbers $N$) in which every recursive unary relation is expressible. Show that $M$ is not recursive.
$\begingroup$
$\endgroup$
7
-
5$\begingroup$ A more specific title (than "Natural numbers") would be useful (here, or at MathSE if the question is more suitable there). In which context did the question arise? $\endgroup$– YCorCommented Apr 23 at 10:06
-
11$\begingroup$ It’s unclear what $L^N$ means, but under any sensible reading, the standard model of arithmetic $(\mathbb N,+,\cdot)$ is a counterexample (it is a recursive structure, and all recursive relations are definable in it). $\endgroup$– Emil JeřábekCommented Apr 23 at 10:19
-
$\begingroup$ @EmilJeřábek I think I give a sensible reading of the question, where the claim is correct. Namely, you can't have a computable model where every recursive relation appears as one of the predicates. $\endgroup$– Joel David HamkinsCommented Apr 23 at 12:49
-
$\begingroup$ The question could be improved by speaking of the unary relations as being realized as the extension of one of the predicates, rather than merely "expressible". $\endgroup$– Joel David HamkinsCommented Apr 23 at 13:04
-
$\begingroup$ @JoelDavidHamkins If you don't allow "expressing" predicates other than the basic relations, then there is no point in talking about models at all. The assertion then degenerates to just that there is no uniformly decidable enumeration of all decidable sets. $\endgroup$– Emil JeřábekCommented Apr 23 at 14:17
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
Here is a positive way to interpret your question, and I think this is probably what you had intended to ask about.
Theorem. There is no computable model $M$ on domain $\mathbb{N}$ in a language $L$ including infinitely many unary predicate symbols, such that every computably decidable set is realized as the extension of one of the predicates in $M$.
Proof. Suppose that $M=\langle\mathbb{N},U_0^M,U_1^M,\ldots\rangle$ is a computable model in a language $L$ that includes infinitely many unary predicate symbols $U_i$. What this means is that there is a computable presentation of the language signature and a computable procedure to decide the truth or falsity in $M$ of any atomic assertion in this language. Assume toward contradiction that every computable subset of $\mathbb{N}$ arises as the extension of some $U_i$ in $M$.
Consider the relation $U$ defined by $$U(n)\iff \neg U_n^M(n).$$ This is a computable set, since the model is computable. But it cannot be realized as $U_n^M$ for any $n$, since we have diagonalized against it, so that $U$ and $U_n^M$ disagree on the point $n$. Contradiction. $\Box$
The argument is fundamentally the same as the claim that there is no computably decidable subset of the plane $U\subseteq\mathbb{N}\times\mathbb{N}$ such that every computably decidable set appears as a section $U_n=\{i\mid (n,i)\in U\}$. The reason is that the diagonal set $\neg U(n,n)$ is computable, but cannot arise as any section.
answered Apr 23 at 12:45