4
$\begingroup$

In (reference)The following result is attributed to Kreisel:

Lemma1(Kreisel) If $T$ is an $\omega$-consistent theory in the language of arithmetic and $\pi$ is a true $\Pi_1$ sentence, then $T+\pi$ is also $\omega$-consistent.

My question is:

Question: If $T$ is an $\omega$-consistent theory in the language of arithmetic, is $T+Th_{\Pi_1}(\mathbb{N})$ also $\omega$-consistent? ($Th_{\Pi_1}(\mathbb{N})$ is the set of all true $\Pi_1$ sentences).

The best i could do is the following result:

lemma2) If $T\supset I\Sigma_1$ is an $\omega$-consistent theory in the language of arithmetic and $A$ an r.e. subset of $Th_{\Pi_1}(\mathbb{N})$, then $T+A$ is also $\omega$-consistent.

proof: if $T_1=T+A$ was $\omega$-inconsistent, then there was a sentence $\exists x \alpha(x)$ such that $T+A\vdash \exists x \alpha(x)$ and also $T+A\vdash \neg \alpha(\overline{n})$ (for all $n$). Let $A=\{\pi_{i}\}_{i \in \mathbb{N}}$. By the compactness theorem, there are indexes $j_{1},\ldots,j_{m}$ such that: $T+\{ \pi_{j_{1}},\ldots,\pi_{j_{m}}\}\vdash \exists x \alpha(x)$. It follows from conservation theorem(reference, theorem 5.2.1) that $T+con(T_{1})\vdash \pi_{i}$ (for every $i\in \mathbb{N}$). Then $T+con(T_{1})\vdash \exists x \alpha(x)$, and by similar reason: $T+con(T_{1})\vdash \neg \alpha(\overline{n})$ (for every $n\in \mathbb{N}$). Then $T_1=T+con(T_{1})$ is an $\omega$-inconsistent theory and it contradicts the lemma1.

$\endgroup$
  • $\begingroup$ You want to use $\mathrm{Con}(Q+A)$, not $\mathrm{Con}(T_1)$; otherwise you’d need an additional (and unnecessary) assumption that $T$ itself is r.e. (Also, $I\Sigma_1$ is an overkill; you only need formalized $\Sigma_1$-completeness, for which $I\Delta_0+\mathit{EXP}$ is enough.) Basically, the argument amounts to the fact that an r.e. set of true $\Pi_1$ sentences is implied by a single true $\Pi_1$ sentence. $\endgroup$ – Emil Jeřábek supports Monica Mar 22 '15 at 22:18
  • $\begingroup$ Yes Emil, your comment is completely correct. $\endgroup$ – Payam Seraji Mar 22 '15 at 22:32
6
$\begingroup$

The property does not hold in general.

First, I’ll recall some basic properties of $\omega$-consistency. Let $T\vdash_1\phi$ denote the relation that $\phi$ is derivable from $T$ using rules of first-order logic, and unnested instances of the $\omega$-rule.

  1. If $T\vdash_1\phi$, then $\phi$ is derivable from $T$ using a single instance of the $\omega$-rule. In particular, $T$ is $\omega$-inconsistent if and only if $T\vdash_1\bot$.

  2. If $T$ is r.e., then $T\vdash_1\phi$ is a $\Sigma_3$ property of $\phi$. Thus, the $\omega$-consistency of $T$ is a $\Pi_3$ statement.

  3. On the other hand, $Q\vdash_1\phi$ for every true $\Sigma_3$ sentence $\phi$: write $\phi=\exists x\,\forall y\,\psi(x,y)$, where $\psi\in\Sigma_1$, and fix $n\in\omega$ such that $\mathbb N\models\forall y\,\psi(\bar n,y)$. Then $Q\vdash\psi(\bar n,\bar m)$ for every $m$ by $\Sigma_1$-completeness of $Q$, hence $Q\vdash_1\forall y\,\psi(\bar n,y)$ using the $\omega$-rule.

  4. Similarly, $Q+\mathrm{Th}_{\Pi_1}(\mathbb N)\vdash_1\phi$ for every true $\Sigma_4$ sentence $\phi$: this follows by the same argument as above, with $\psi\in\Sigma_2$.

  5. If $T$ is an r.e. extension of $I\Delta_0+\mathit{EXP}$ (this can be negotiated down with a bit of care), then $T\vdash_1\phi$ satisfies the Bernays–Löb derivability conditions: that is, if we write $\Box_{T,1}\phi$ for the natural arithmetization of $T\vdash_1\phi$, we have

    • $T\vdash_1\phi\implies T\vdash_1\Box_{T,1}\phi$: this is a consequence of 2 and 3.

    • $T\vdash\Box_{T,1}(\phi\to\psi)\to(\Box_{T,1}\phi\to\Box_{T,1}\psi)$: we can concatenate two proofs.

    • $T\vdash\Box_{T,1}\phi\to\Box_{T,1}\Box_{T,1}\phi$; more generally, if $\psi\in\Sigma_3$, then $T\vdash\psi\to\Box_{T,1}\psi$. This follows by formalizing the argument in 3, using the ordinary formalized $\Sigma_1$-completeness of $Q$.

    See [1] for more information about the provability logic of $\vdash_1$ and related provability predicates.

Now, let $T_0$ be an $\omega$-consistent r.e. extension of $I\Delta_0+\mathit{EXP}$ (such as $I\Sigma_1$ or $\mathit{PA}$), and put

$$T=T_0+\Box_{T_0,1}\bot$$

(that is, $T_0$ + its own formalized $\omega$-inconsistency). The standard proof of the second Gödel incompleteness theorem using the derivability conditions shows that $T$ is $\omega$-consistent. On the other hand, $\neg\Box_{T_0,1}\bot$ is a true $\Pi_3$ sentence, hence

$$T_0+\mathrm{Th}_{\Pi_1}(\mathbb N)\vdash_1\neg\Box_{T_0,1}\bot$$

by 4, thus $T+\mathrm{Th}_{\Pi_1}(\mathbb N)$ is $\omega$-inconsistent.


Kreisel’s lemma can be strengthened in a different direction, namely it holds for a larger class of formulas than $\Pi_1$:

Proposition: If $T\supseteq Q$ is $\omega$-consistent, and $\phi$ is a true $\Sigma_3$ sentence, then $T+\phi$ is $\omega$-consistent.

Proof: Otherwise $T+\phi\vdash_1\bot$, hence $T\vdash_1\neg\phi$. On the other hand, $Q\vdash_1\phi$ by property 3 above, hence $T\vdash_1\bot$, i.e., $T$ is $\omega$-inconsistent.

Corollary: If $T\supseteq I\Delta_0+\mathit{EXP}$ is $\omega$-consistent, and $A$ is an r.e. set of true $\Pi_2$ sentences, then $T+A$ is $\omega$-consistent.

Proof: It suffices to find a true $\Pi_2$ (or $\Sigma_3$) sentence $\phi$ such that $T+\phi\vdash A$. So, let $\alpha(x)$ be a $\Sigma_1$ definition of $A$ in $\mathbb N$, and $\mathrm{Tr}_{\Pi_2}(x)$ a universal $\Pi_2$ formula. Then we can take $\phi=\forall x\,(\alpha(x)\to\mathrm{Tr}_{\Pi_2}(x))$.

Notice that both statements are optimal with respect to arithmetic complexity:

  • The Proposition may fail for true $\Pi_3$ sentences $\phi$: for example, take the $\omega$-consistent theory $T=T_0+\Box_{T_0,1}\bot$ considered above, and $\phi=\neg\Box_{T_0,1}\bot$, which is a true $\Pi_3$ sentence. Then $T+\phi$ is inconsistent.

  • The Corollary may fail for r.e. sets $A$ of true $\Sigma_2$ sentences: continuing the previous example, write $\phi=\forall x\,\psi(x)$ with $\psi\in\Sigma_2$, and put $A=\{\psi(\bar n):n\in\omega\}$. Then $T+A\vdash_1\phi$, while $\neg\phi\in T$, hence $T+A$ is $\omega$-inconsistent.


Reference:

[1] George Boolos, The Logic of Provability, Cambridge University Press 1993.

$\endgroup$
  • $\begingroup$ @PayamSeraji Did you know that you can upvote answers that you find to be helpful? Just click on the uparrow to the left of the answer. It is recommended for knowledgeable people to vote this way, to help the site identify informative questions and answers. (You can also vote on other questions and answers.) Also, it is possible to "accept" an answer, if you find it to satisfactorily answer your question, by clicking on the check symbol. $\endgroup$ – Joel David Hamkins Mar 23 '15 at 15:41
  • $\begingroup$ Dear Professor Hamkins, thanks for guidance and i thank you again for your answer to my previous question. $\endgroup$ – Payam Seraji Mar 23 '15 at 16:40
  • 1
    $\begingroup$ Kreisel’s result can be improved in yet another way. The argument is that if $T$ is $\omega$-consistent, then $T+\phi$ is $\omega$-consistent whenever $T\vdash_1\phi$. Now, Smoryński proved that for $T$ r.e., $T\vdash_1\phi$ iff $\mathrm{Th}_{\Sigma_3}(\mathbb N)+\mathrm{RFN}_T\vdash\phi$. In particular, for finite $T$, $\mathrm{RFN}_T\equiv T+\mathit{PA}$. Therefore: if $T\supseteq Q$ is $\omega$-consistent, then $T+I\Sigma_n$ is $\omega$-consistent for every $n$. (Which also means that the $I\Delta_0+\mathit{EXP}$ assumptions are not needed.) $\endgroup$ – Emil Jeřábek supports Monica Mar 24 '15 at 13:32

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.