If a set $T$ of sentences in the language of arithmetic

  • is deductively closed under the usual inference rules of first order logic, and
  • includes all true $\Sigma_1$ sentences and all true $\Pi_1$ sentences, and
  • includes no false sentences;

is $T$ necessarily the complete first-order theory of $\mathbb{N}$?

  • 2
    $\begingroup$ This question just has a problem statement, without any background information (where did you encounter the problem, what else do you already know) and without any description of what you have tried. That additional information is important for people who try to answer the question. $\endgroup$ – Carl Mummert May 2 '13 at 12:20

The set $T$ is computable in $0''$. The theory of $\mathbb{N}$ contains the entire arithmetical hierarchy. Therefore $T$ can't be the theory of $\mathbb{N}$.

In response to the comment I'll show how to construct a sentence that is independent of $T$. There might be a better way, but this is the easiest that I can see.

$T$ is computably enumerable in $0'$, so by Post's theorem there is a $\Sigma_2$ formula $\phi(x)$ such that for any sentence $\psi$, $\mathbb{N} \models \phi(\ulcorner \psi \urcorner)$ if and only if $\psi \in T$. Then, I think the proof of Gödel's incompleteness theorem still applies using $\phi$ as a provability predicate, so we can construct a sentence independent of $T$ by diagonalization.

  • 2
    $\begingroup$ It is the second Turing jump of the empty set (ie $0^{(2)}$ in the linked article). $\endgroup$ – aws May 2 '13 at 11:58
  • $\begingroup$ Ah, I didn't see Andreas' answer before editing, never mind. $\endgroup$ – aws May 2 '13 at 13:00

The consistency of $T$ is a true arithmetical sentence yet is not provable in $T$. This observation depends on two well-known facts: First, one can define, in the language of arithmetic, the notion of a "true $\Sigma_1$ or $\Pi_1$ sentence". (In fact, although there is no arithmetical truth definition for the entire language of arithmetic, there are truth definitions for any bounded part of the arithmetical hierarchy.) So one can define what $T$ is and then formalize "$T$ is consistent" in the language of arithmetic. Second, Gödel's second incompleteness theorem (about the unprovability of consistency), though often stated only for recursively axiomatized theories, can be extended to more general arithmetically definable theories like $T$.

  • $\begingroup$ Hmmm, okay. Forgive my ignorance, but why is $T$ not $\Pi_1$? I thought sentences of the form, "so and so is consistent" were always $\Pi_1$. $\endgroup$ – goblin May 2 '13 at 12:44
  • $\begingroup$ Sorry, I mean, why is the statement "$T$ is consistent" not $\Pi_1$. $\endgroup$ – goblin May 2 '13 at 12:50
  • 1
    $\begingroup$ Because it refers to the truth definition for $\Sigma^0_1$ sentences, which requires additional quantifiers. Consistency statements for effective theories are $\Pi^0_1$ but the theory in question is not effective. You should review the construction of the Gödel sentence and see where the complexity of the theory affects the complexity of the consistency statement. $\endgroup$ – Carl Mummert May 2 '13 at 13:03
  • $\begingroup$ Could you give a reference for the claim that Gödel's second incompleteness theorem can be extended to arithmetically definable theories? I believe the assumption that $T$ be $\Sigma^0_1$ is best possible in the arithmetical hierarchy, i.e. that there are consistent $\Pi^0_1$ theories $T$ containing PA for which both Con$(T)$ and Pf$_T($Con$(T))$ hold. $\endgroup$ – Marcel Besixdouze Dec 30 '13 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.