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<n} \chi_{\ulcorner\mathrm{Th}(\mathfrak{M_i})\urcorner}(n) $$ 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.


1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .