Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$?

share|cite|improve this question
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. – Carl Mummert May 2 '13 at 12:20
up vote 8 down vote accepted

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.

share|cite|improve this answer
It is the second Turing jump of the empty set (ie $0^{(2)}$ in the linked article). – aws May 2 '13 at 11:58
Ah, I didn't see Andreas' answer before editing, never mind. – 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$.

share|cite|improve this answer
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$. – goblin May 2 '13 at 12:44
Sorry, I mean, why is the statement "$T$ is consistent" not $\Pi_1$. – goblin May 2 '13 at 12:50
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. – Carl Mummert May 2 '13 at 13:03
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. – Marcel T. Dec 30 '13 at 1:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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