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?


1 Answer 1


Below, for simplicity I'll conflate sentences with their Godel numbers.

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!).

  • $\begingroup$ Could you further explain what this formula $\tau_{\Pi}$ looks like? $\endgroup$
    – sanguine
    Aug 18, 2022 at 14:16
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 22, 2022 at 21:47

You must log in to answer this question.

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