# Possible counterexample to $\ulcorner\Delta\urcorner$ is recursive $\iff$ $\mathrm{Th}(\Delta)$ is complete?

I am referring to the notes A Problem Course in Mathematical Logic by Stefan Bilaniuk.

Let $$\mathcal{L}_N = \{0,S,+,\cdot,E\}$$ denote the language of number theory. Given a set of formulas $$\Delta$$, let $$\ulcorner\Delta\urcorner := \{\ulcorner\varphi\urcorner : \varphi \in \Delta\}$$ be the set of Gödel codes of the formulas in $$\Delta$$. Define the theory of $$\Delta$$ as: $$\mathrm{Th}(\Delta) := \{\psi : \Delta \vdash \psi\}$$ Suppose $$\Delta$$ is a recursive set of formulas in the language $$\mathcal{L}_N$$. According to the notes, we have that:

Theorem 16.5(2). $$\ulcorner\mathrm{Th}(\Delta)\urcorner$$ is recursive iff $$\Delta$$ is complete.

My student appears to have found a counterexample to this statement, and I would like to know if it is correct.

Define $$\Delta = \{\forall x \forall y \forall z (x = y \lor x = z \lor y = z)\}$$, so a structure $$\mathfrak{M}$$ satisfies $$\Delta$$ iff its universe has at most two elements. $$\ulcorner\Delta\urcorner$$ is recursive as it is finite. Since any structure satisfying $$\Delta$$ has at most two elements in the universe, there are only finitely many structures satisfying $$\Delta$$, and let's call them $$\mathfrak{M}_0,\dots,\mathfrak{M}_{n-1}$$. By Theorem 26C of Enderton's A Mathematical Introduction to Logic, the theory of any finite model is recursive, so $$\ulcorner\mathrm{Th}(\mathfrak{M}_i)\urcorner$$ is recursive for all $$i < n$$. By completeness/soundness theorem, a sentence $$\varphi$$ is proved by $$\Delta$$ iff all models of $$\Delta$$ satisfy it. Therefore, we have that: $$\chi_{\ulcorner\mathrm{Th}(\Delta)\urcorner}(n) = \prod_{i so $$\ulcorner\mathrm{Th}(\Delta)\urcorner$$ is recursive, Now consider the sentence $$\psi$$ defined as $$\forall x \forall y (x = y)$$. Then $$\mathfrak{M} \models \psi$$ iff $$\mathfrak{M}$$ has exactly one element in the universe. Since there exists a model of $$\Delta$$ with one element, and one with two elements, $$\Delta$$ fails to decide $$\psi$$. Thus, $$\mathrm{Th}(\Delta)$$ is not complete.

Your student is correct (note that the text also requires $$\Delta$$ to be recursive, but your student's example satisfies this as well); this is in my opinion a significant error in the text. The "theorem" does hold, however, if we demand that $$\Delta$$ be consistent with some weak arithmetic such as Robinson's $$\mathsf{Q}$$ (the argument in this old answer of mine gives this as well). Of course this means that 16.5(2) is ultimately vacuous, but that's fine: Godel's incompleteness theorems haven't been proved at this stage in the text, so at this moment in the narrative we still would have a substantive result.