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.

## 1 Answer

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.

2more comments