# A true but unprovable sentence $\theta$ that is not a $\Pi$-sentence

Question $$4$$ from Section $$7.7.3$$ in "A Friendly Introduction to Mathematical Logic" (Christopher C. Leary and Lars Kristiansen; $$2$$nd edition):

Let $$A = \{\phi \mid \phi \text{ is a } \Pi\text{-sentence and } \mathfrak{R} \vDash \phi \}$$. (Note that all the axioms of $$N$$ are elements of the set $$A$$.) Prove that there exists an $$\mathcal{L}_{NT}$$-sentence $$\theta$$ such that $$\mathfrak{R} \vDash \theta$$ and $$A \nvdash \theta$$. [...]

A note about notation: The language (of number theory) $$\mathcal{L}_{NT}$$ is $$\{0, S, +, \cdot, E, \lt\}$$, where $$0$$ is a constant symbol, $$+$$, $$\cdot$$, and $$E$$ are $$2$$-ary function symbols, $$S$$ is a $$1$$-ary function symbol, and $$\lt$$ is a $$2$$-ary relation symbol (in this book, the equality symbol is a $$2$$-ary relation assumed always to be a part of a language). $$N$$ is a version of the axioms of arithmetic. $$\mathfrak{R}$$ is the standard interpretation of the axioms $$N$$ (as statements about natural numbers). The set of $$\Pi$$-sentences is the smallest set of $$\mathcal{L}_{NT}$$-formulas which contains all atomic formulas and their negations, and is closed under bounded quantifiers, the universal quantifier, and the connectives the $$\land$$ and $$\lor$$.

Gödel's First Incompleteness Theorem (at least as presented in Leary and Kristiansen's book) provides a $$\Pi$$-sentence that is true-in-$$\mathfrak{R}$$ but not provable by $$A$$ for any consistent, semi-computable set of axioms $$A$$. Obviously that will not work here, as $$A$$ is the set of all true-in-$$\mathfrak{R}$$ $$\Pi$$-sentences. Somewhere in the formula there will need to be an existential quantifier, and a universal quantifier as well (as true-in-$$\mathfrak{R}$$ $$\Sigma$$-sentences (replace universal quantifier by existential quantifier in the definition of a $$\Pi$$-sentence) are all provable by $$N$$, and so by $$A$$). Maybe the solution has something to do with the sentence $$\psi$$ such that $$\mathfrak{R} \vDash \psi$$, but $$N \nvdash \psi$$? How do I approach this problem?

Note that $$\{\varphi: A\vdash\varphi\}$$ is definable in $$\mathfrak{R}$$; this is because $$A$$ itself is definable, and the deductive closure of a definable set of sentences is again definable (this latter point is essentially part of the proof of Godel's theorem). By Tarski's undefinability theorem, this means that cannot coincide with $$Th(\mathfrak{R})$$ (= $$\{\varphi:\mathfrak{R}\models\varphi\}$$) itself.
The subtle point here, of course, is that $$A$$ is indeed definable in $$\mathfrak{R}$$. This takes a bit of care; the point is that, Tarski notwithstanding, we do have "local" truth definitions in $$\mathfrak{R}$$, in the sense that every "bounded" complexity class has a corresponding definable truth predicate. In particular, there is a formula $$\tau_\Pi$$ defining in $$\mathfrak{R}$$ the set of true-in-$$\mathfrak{R}$$ $$\Pi$$-sentences (we can even have this $$\tau_\Pi$$ itself be a $$\Pi$$-formula!).
• Could you further explain what this formula $\tau_{\Pi}$ looks like? Aug 18, 2022 at 14:16
• @sanguine One approach is to use Kleene's $T$-predicate. This is an arithmetic (indeed, $\Delta^0_0$) formula $T(e,i,x)$ whose intended meaning is "$x$ is a witness for the halting of the $e$th Turing machine on input $i$." Now the point is that $\Pi^0_1$ statements (in your notation, $\Pi$-statements) can always be thought of as asserting that a certain Turing machine doesn't halt on input $0$ (say), and so we can whip up an appropriate $\tau_\Pi$ in this manner. Aug 22, 2022 at 21:47