Skip to main content
Commonmark migration
Source Link

$\def\pa{\mathit{PA}}\def\rfn{\mathrm{RFN}}\def\pr{\mathrm{Pr}}\def\num#1{\ulcorner#1\urcorner}\def\Th{\mathrm{Th}}$ $\Th_{\Pi_2}(\pa)$ certainly does not prove $\pa$:

Theorem: For any constant $k$, there is no consistent $\Pi_k$-axiomatized theory $T$ such that $T\vdash\pa$.

 

More generally, if $S$ is a sequential theory that proves full induction, then $S$ is not derivable from any consistent theory $T$ axiomatized by formulas of restricted quantifier complexity.

(So, for example, $\mathit{ZF}$ is not derivable from any consistent theory axiomatized by $\Pi_k$-sentences in the Levy hierarchy.)

The reason is that $\pa$ proves the uniform reflection principles $$\rfn_Q(\Pi_k)=\forall x\,(\pr_Q(x)\land x\in\Pi_k\to\mathrm{Tr}_k(x)),$$ where $\mathrm{Tr}_k$ is the truth predicate for $\Pi_k$-sentences, $\mathrm{Pr}_Q$ is the provability predicate for $Q$, and $Q$ could really stand for any fixed finitely axiomatized subtheory of $\pa$ (the choice does not matter much).

So, if $T$ is a $\Pi_k$-axiomatized theory that proves $\pa$, then there is a finitely axiomatized subtheory $T_0\subseteq T$ that proves $\rfn_Q(\Pi_{k+1})$, and (say) $I\Sigma_1$. Let $\psi=\bigwedge T_0$. Then $$\pr_Q(\num{\neg\psi})\to\neg\psi$$ is an instance of $\rfn_Q(\Pi_{k+1})$, which implies that $T_0$ proves its own consistency. By Gödel’s theorem, $T_0$ is inconsistent, hence so is $T$.

As for constructing submodels of $M\models\pa$ satisfying $\Th_{\Pi_2}(\pa)$ but not $\pa$, there is the following general result due to McAloon [1]:

Theorem (McAloon): Let $T$ be a recursively axiomatizable $\Sigma_1$-sound extension of $I\Sigma_1$. Then for any countable nonstandard model $M\models I\Delta_0$, there is a nonstandard cut $N\subseteq M$ such that $N\models T$.

This was generalized to $M\models IE_1$ by Wilmers [2].

McAloon’s argument relies on the indicator theory, hence one may consider it a combinatorial construction.

In order to get $N\models\Th_{\Pi_2}(\pa)$, $N\not\models\pa$, we can apply this theorem to $$T=I\Sigma_1+\Th_{\Pi_2}(\pa)+\neg\rfn_Q(\Pi_4).$$ We only need to check that $T$ is $\Sigma_1$-sound. In fact, $T$ is $\Pi_4$-conservative over the (sound) theory $I\Sigma_1+\Th_{\Pi_2}(\pa)$.

To see this, let $\phi$ be a $\Pi_4$-sentence provable in $T$. Notice that $I\Sigma_1+\Th_{\Pi_2(\pa)}$ is $\Pi_3$-axiomatizable, hence there exists a $\Pi_3$-sentence $\psi$ derivable in $I\Sigma_1+\Th_{\Pi_2(\pa)}$ such that $$\psi\land\neg\phi\vdash\rfn_Q(\Pi_4).$$ As before, an instance of $\rfn$ for the $\Pi_4$-sentence $\neg(\psi\land\neg\phi)$ shows $$\psi\land\neg\phi\vdash\mathrm{Con}_{\psi\land\neg\phi},$$ hence $\psi\land\neg\phi$ is inconsistent by Gödel’s theorem, i.e., $$I\Sigma_1+\Th_{\Pi_2}(\pa)\vdash\psi\vdash\phi.$$

[1] Kenneth McAloon, On the complexity of models of arithmetic, Journal of Symbolic Logic 47 (1982), no. 2, pp. 403–415.

[2] George Wilmers, Bounded existential induction, Journal of Symbolic Logic 50 (1985), no. 1, pp. 72–90.

$\def\pa{\mathit{PA}}\def\rfn{\mathrm{RFN}}\def\pr{\mathrm{Pr}}\def\num#1{\ulcorner#1\urcorner}\def\Th{\mathrm{Th}}$ $\Th_{\Pi_2}(\pa)$ certainly does not prove $\pa$:

Theorem: For any constant $k$, there is no consistent $\Pi_k$-axiomatized theory $T$ such that $T\vdash\pa$.

 

More generally, if $S$ is a sequential theory that proves full induction, then $S$ is not derivable from any consistent theory $T$ axiomatized by formulas of restricted quantifier complexity.

(So, for example, $\mathit{ZF}$ is not derivable from any consistent theory axiomatized by $\Pi_k$-sentences in the Levy hierarchy.)

The reason is that $\pa$ proves the uniform reflection principles $$\rfn_Q(\Pi_k)=\forall x\,(\pr_Q(x)\land x\in\Pi_k\to\mathrm{Tr}_k(x)),$$ where $\mathrm{Tr}_k$ is the truth predicate for $\Pi_k$-sentences, $\mathrm{Pr}_Q$ is the provability predicate for $Q$, and $Q$ could really stand for any fixed finitely axiomatized subtheory of $\pa$ (the choice does not matter much).

So, if $T$ is a $\Pi_k$-axiomatized theory that proves $\pa$, then there is a finitely axiomatized subtheory $T_0\subseteq T$ that proves $\rfn_Q(\Pi_{k+1})$, and (say) $I\Sigma_1$. Let $\psi=\bigwedge T_0$. Then $$\pr_Q(\num{\neg\psi})\to\neg\psi$$ is an instance of $\rfn_Q(\Pi_{k+1})$, which implies that $T_0$ proves its own consistency. By Gödel’s theorem, $T_0$ is inconsistent, hence so is $T$.

As for constructing submodels of $M\models\pa$ satisfying $\Th_{\Pi_2}(\pa)$ but not $\pa$, there is the following general result due to McAloon [1]:

Theorem (McAloon): Let $T$ be a recursively axiomatizable $\Sigma_1$-sound extension of $I\Sigma_1$. Then for any countable nonstandard model $M\models I\Delta_0$, there is a nonstandard cut $N\subseteq M$ such that $N\models T$.

This was generalized to $M\models IE_1$ by Wilmers [2].

McAloon’s argument relies on the indicator theory, hence one may consider it a combinatorial construction.

In order to get $N\models\Th_{\Pi_2}(\pa)$, $N\not\models\pa$, we can apply this theorem to $$T=I\Sigma_1+\Th_{\Pi_2}(\pa)+\neg\rfn_Q(\Pi_4).$$ We only need to check that $T$ is $\Sigma_1$-sound. In fact, $T$ is $\Pi_4$-conservative over the (sound) theory $I\Sigma_1+\Th_{\Pi_2}(\pa)$.

To see this, let $\phi$ be a $\Pi_4$-sentence provable in $T$. Notice that $I\Sigma_1+\Th_{\Pi_2(\pa)}$ is $\Pi_3$-axiomatizable, hence there exists a $\Pi_3$-sentence $\psi$ derivable in $I\Sigma_1+\Th_{\Pi_2(\pa)}$ such that $$\psi\land\neg\phi\vdash\rfn_Q(\Pi_4).$$ As before, an instance of $\rfn$ for the $\Pi_4$-sentence $\neg(\psi\land\neg\phi)$ shows $$\psi\land\neg\phi\vdash\mathrm{Con}_{\psi\land\neg\phi},$$ hence $\psi\land\neg\phi$ is inconsistent by Gödel’s theorem, i.e., $$I\Sigma_1+\Th_{\Pi_2}(\pa)\vdash\psi\vdash\phi.$$

[1] Kenneth McAloon, On the complexity of models of arithmetic, Journal of Symbolic Logic 47 (1982), no. 2, pp. 403–415.

[2] George Wilmers, Bounded existential induction, Journal of Symbolic Logic 50 (1985), no. 1, pp. 72–90.

$\def\pa{\mathit{PA}}\def\rfn{\mathrm{RFN}}\def\pr{\mathrm{Pr}}\def\num#1{\ulcorner#1\urcorner}\def\Th{\mathrm{Th}}$ $\Th_{\Pi_2}(\pa)$ certainly does not prove $\pa$:

Theorem: For any constant $k$, there is no consistent $\Pi_k$-axiomatized theory $T$ such that $T\vdash\pa$.

More generally, if $S$ is a sequential theory that proves full induction, then $S$ is not derivable from any consistent theory $T$ axiomatized by formulas of restricted quantifier complexity.

(So, for example, $\mathit{ZF}$ is not derivable from any consistent theory axiomatized by $\Pi_k$-sentences in the Levy hierarchy.)

The reason is that $\pa$ proves the uniform reflection principles $$\rfn_Q(\Pi_k)=\forall x\,(\pr_Q(x)\land x\in\Pi_k\to\mathrm{Tr}_k(x)),$$ where $\mathrm{Tr}_k$ is the truth predicate for $\Pi_k$-sentences, $\mathrm{Pr}_Q$ is the provability predicate for $Q$, and $Q$ could really stand for any fixed finitely axiomatized subtheory of $\pa$ (the choice does not matter much).

So, if $T$ is a $\Pi_k$-axiomatized theory that proves $\pa$, then there is a finitely axiomatized subtheory $T_0\subseteq T$ that proves $\rfn_Q(\Pi_{k+1})$, and (say) $I\Sigma_1$. Let $\psi=\bigwedge T_0$. Then $$\pr_Q(\num{\neg\psi})\to\neg\psi$$ is an instance of $\rfn_Q(\Pi_{k+1})$, which implies that $T_0$ proves its own consistency. By Gödel’s theorem, $T_0$ is inconsistent, hence so is $T$.

As for constructing submodels of $M\models\pa$ satisfying $\Th_{\Pi_2}(\pa)$ but not $\pa$, there is the following general result due to McAloon [1]:

Theorem (McAloon): Let $T$ be a recursively axiomatizable $\Sigma_1$-sound extension of $I\Sigma_1$. Then for any countable nonstandard model $M\models I\Delta_0$, there is a nonstandard cut $N\subseteq M$ such that $N\models T$.

This was generalized to $M\models IE_1$ by Wilmers [2].

McAloon’s argument relies on the indicator theory, hence one may consider it a combinatorial construction.

In order to get $N\models\Th_{\Pi_2}(\pa)$, $N\not\models\pa$, we can apply this theorem to $$T=I\Sigma_1+\Th_{\Pi_2}(\pa)+\neg\rfn_Q(\Pi_4).$$ We only need to check that $T$ is $\Sigma_1$-sound. In fact, $T$ is $\Pi_4$-conservative over the (sound) theory $I\Sigma_1+\Th_{\Pi_2}(\pa)$.

To see this, let $\phi$ be a $\Pi_4$-sentence provable in $T$. Notice that $I\Sigma_1+\Th_{\Pi_2(\pa)}$ is $\Pi_3$-axiomatizable, hence there exists a $\Pi_3$-sentence $\psi$ derivable in $I\Sigma_1+\Th_{\Pi_2(\pa)}$ such that $$\psi\land\neg\phi\vdash\rfn_Q(\Pi_4).$$ As before, an instance of $\rfn$ for the $\Pi_4$-sentence $\neg(\psi\land\neg\phi)$ shows $$\psi\land\neg\phi\vdash\mathrm{Con}_{\psi\land\neg\phi},$$ hence $\psi\land\neg\phi$ is inconsistent by Gödel’s theorem, i.e., $$I\Sigma_1+\Th_{\Pi_2}(\pa)\vdash\psi\vdash\phi.$$

[1] Kenneth McAloon, On the complexity of models of arithmetic, Journal of Symbolic Logic 47 (1982), no. 2, pp. 403–415.

[2] George Wilmers, Bounded existential induction, Journal of Symbolic Logic 50 (1985), no. 1, pp. 72–90.

Source Link
Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209

$\def\pa{\mathit{PA}}\def\rfn{\mathrm{RFN}}\def\pr{\mathrm{Pr}}\def\num#1{\ulcorner#1\urcorner}\def\Th{\mathrm{Th}}$ $\Th_{\Pi_2}(\pa)$ certainly does not prove $\pa$:

Theorem: For any constant $k$, there is no consistent $\Pi_k$-axiomatized theory $T$ such that $T\vdash\pa$.

More generally, if $S$ is a sequential theory that proves full induction, then $S$ is not derivable from any consistent theory $T$ axiomatized by formulas of restricted quantifier complexity.

(So, for example, $\mathit{ZF}$ is not derivable from any consistent theory axiomatized by $\Pi_k$-sentences in the Levy hierarchy.)

The reason is that $\pa$ proves the uniform reflection principles $$\rfn_Q(\Pi_k)=\forall x\,(\pr_Q(x)\land x\in\Pi_k\to\mathrm{Tr}_k(x)),$$ where $\mathrm{Tr}_k$ is the truth predicate for $\Pi_k$-sentences, $\mathrm{Pr}_Q$ is the provability predicate for $Q$, and $Q$ could really stand for any fixed finitely axiomatized subtheory of $\pa$ (the choice does not matter much).

So, if $T$ is a $\Pi_k$-axiomatized theory that proves $\pa$, then there is a finitely axiomatized subtheory $T_0\subseteq T$ that proves $\rfn_Q(\Pi_{k+1})$, and (say) $I\Sigma_1$. Let $\psi=\bigwedge T_0$. Then $$\pr_Q(\num{\neg\psi})\to\neg\psi$$ is an instance of $\rfn_Q(\Pi_{k+1})$, which implies that $T_0$ proves its own consistency. By Gödel’s theorem, $T_0$ is inconsistent, hence so is $T$.

As for constructing submodels of $M\models\pa$ satisfying $\Th_{\Pi_2}(\pa)$ but not $\pa$, there is the following general result due to McAloon [1]:

Theorem (McAloon): Let $T$ be a recursively axiomatizable $\Sigma_1$-sound extension of $I\Sigma_1$. Then for any countable nonstandard model $M\models I\Delta_0$, there is a nonstandard cut $N\subseteq M$ such that $N\models T$.

This was generalized to $M\models IE_1$ by Wilmers [2].

McAloon’s argument relies on the indicator theory, hence one may consider it a combinatorial construction.

In order to get $N\models\Th_{\Pi_2}(\pa)$, $N\not\models\pa$, we can apply this theorem to $$T=I\Sigma_1+\Th_{\Pi_2}(\pa)+\neg\rfn_Q(\Pi_4).$$ We only need to check that $T$ is $\Sigma_1$-sound. In fact, $T$ is $\Pi_4$-conservative over the (sound) theory $I\Sigma_1+\Th_{\Pi_2}(\pa)$.

To see this, let $\phi$ be a $\Pi_4$-sentence provable in $T$. Notice that $I\Sigma_1+\Th_{\Pi_2(\pa)}$ is $\Pi_3$-axiomatizable, hence there exists a $\Pi_3$-sentence $\psi$ derivable in $I\Sigma_1+\Th_{\Pi_2(\pa)}$ such that $$\psi\land\neg\phi\vdash\rfn_Q(\Pi_4).$$ As before, an instance of $\rfn$ for the $\Pi_4$-sentence $\neg(\psi\land\neg\phi)$ shows $$\psi\land\neg\phi\vdash\mathrm{Con}_{\psi\land\neg\phi},$$ hence $\psi\land\neg\phi$ is inconsistent by Gödel’s theorem, i.e., $$I\Sigma_1+\Th_{\Pi_2}(\pa)\vdash\psi\vdash\phi.$$

[1] Kenneth McAloon, On the complexity of models of arithmetic, Journal of Symbolic Logic 47 (1982), no. 2, pp. 403–415.

[2] George Wilmers, Bounded existential induction, Journal of Symbolic Logic 50 (1985), no. 1, pp. 72–90.