Return to 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$

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.

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

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$

Here is a positive way to interpret your question, and I think this is probably what you had intended to ask about.

Theorem. If $L$ is a language with infinitely many unary predicate symbols, then there is no computable model $M$ on domain $\mathbb{N}$ in such a way that every computable relation is interpreted as one of the predicate symbols.

Proof. What is meant by a computable model is that there is a computable presentation of the language signature and the atomic diagram of the model is computably decidable, so that we have a uniform procedure to decide the truth of any atomic statement. Suppose the unary relation symbols are $U_0$, $U_1$, $U_2$, and so forth, as given by the computable signature, and suppose these relations are interpreted in a computable model $M=\langle\mathbb{N},U_0^M,U_1^M,\ldots\rangle$ in such a way that every computable relation arises as the extension of some $U_i$. Consider the relation $U(n)\iff \neg U_n^M(n)$. This is computable, since the model is computable, but it cannot be realized as $U_n$ for any $n$, since we have diagonalized against it. Contradiction. $\Box$

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