3 reference for Lindström's theorem

$\def\zfc{\mathrm{ZFC}}\def\pa{\mathrm{PA}}$First, there is no consistent recursively axiomatizable theory extending Robinson’s arithmetic which has the property of having existential witnesses as described by Sridhar Ramesh. Let $\pi=\forall x\,\theta(x)$ be a true but $T$-unprovable $\Pi^0_1$ sentence with $\theta$ bounded, which exists by Gödel’s theorem. Then $\exists y\,(\theta(y)\to\forall x\,\theta(x))$ is a tautology, but there is no $n\in\omega$ such that $T\vdash\theta(n)\to\forall x\,\theta(x)$: since $\pi$ is true, $\theta(n)$ is provable in Robinson’s arithmetic, hence $T$ would prove $\pi$.

In fact, an iteration of the same idea shows that the only consistent theory with the property of having existential witnesses is the true arithmetic $\mathrm{Th}(\mathbb N)$.

The situation with goodness is more complicated: there are good theories, such as any consistent theory axiomatizable over $\pa$ by a set of $\Pi^0_1$ sentences. Nevertheless, neither $\zfc$ nor any its recursively axiomatized extension is good.

Let $T=\zfc$, or more generally, let $T$ be any recursively axiomatizable extension of $\pa$ which proves the local $\Sigma^0_1$-reflection principle for $\pa$. Let $\Box_\pa$ denote the provability predicate for $\pa$, and $T_{\Pi^0_1}$ the set of all $\Pi^0_1$ theorems of $T$. By a theorem of Lindström, there exists a $\Pi^0_1$ sentence $\pi$ such that $\pa+\pi$ is a $\Sigma^0_1$-conservative extension of $\pa+T_{\Pi^0_1}$. $T$ proves the reflection principle $\tag{*}\Box_\pa(\neg\pi)\to\neg\pi$ which can be written as a $\Sigma^0_2$ sentence, hence assuming $T$ is good, $(*)$ is provable in $\pa+T_{\Pi^0_1}$, and a fortiori in $\pa+\pi$. But then $\pa+\pi$ proves its own consistency, hence by Gödel’s theorem, it is inconsistent. By $\Sigma^0_1$-conservativity, $\pa+T_{\Pi^0_1}$ is also inconsistent, hence $T$ is inconsistent, contradicting its goodness.

Reference:

Per Lindström, On partially conservative sentences and interpretability, Proc. AMS 91 (1984), no. 3, pp. 436–443.

2 corrections

$\def\zfc{\mathrm{ZFC}}\def\pa{\mathrm{PA}}$ First, \def\zfc{\mathrm{ZFC}}\def\pa{\mathrm{PA}}$First, there is no consistent recursively axiomatizable theory extending Robinson’s arithmetic which has the property of having existential witnesses as described by Sridhar Ramesh. Let$\pi=\forall x\,\theta(x)$be a true but$T$-unprovable$\Pi^0_1$sentence with$\theta$bounded, which exists by Gödel’s theorem. Then$\exists y\,(\theta(y)\to\forall x\,\theta(x))$is a tautology, but there is no$n\in\omega$such that$T\vdash\theta(n)\to\forall x\,\theta(x)$: since$\pi$is true,$\theta(n)$is provable in Robinson’s arithmetic, hence$T$would prove$\pi$. In fact, an iteration of the same idea shows that the only consistent theory with the property of having existential witnesses is the true arithmetic$\mathrm{Th}(\mathbb N)$. The situation with goodness is more complicated: there are good theories, such as any consistent theory axiomatizable over$\pa$by a set of$\Pi^0_1$sentences. Nevertheless, neither$\zfc$nor any its recursively axiomatized extension is good. Let$T=\zfc$, or more generally, let$T$be any recursively axiomatizable extension of$\pa$which proves the local$\Sigma^0_1$-reflection principle for$\pa$. Let$\Box_\pa$denote the provability predicate for$\pa$, and$T_{\Pi^0_1}$the set of all$\Pi^0_1$theorems of$T$. By a theorem of Lindström, there exists a$\Pi^0_1$sentence$\pi$such that$\pa+\pi$is a$\Sigma^0_1$-conservative extension of$\pa+T_{\Pi^0_1}$.$T$proves the reflection principle $\tag{*}\Box_\pa(\neg\pi)\to\neg\pi$ which can be written as a$\Sigma^0_2$sentence, hence assuming$T$is good,$(*)$is provable in$\pa+T_{\Pi^0_1}$, and a fortiori in$\pa+\pi$. But then$\pa+\pi$proves its own consistency, hence by Gödel’s theorem, it is inconsistent. By$\Sigma^0_1$-conservativity,$\pa+T_{\pi^0_1}$\pa+T_{\Pi^0_1}$ is also inconsistent, hence $T$ is inconsistent, contradicting its goodness.

1

$\def\zfc{\mathrm{ZFC}}\def\pa{\mathrm{PA}}$ First, there is no recursively axiomatizable theory extending Robinson’s arithmetic which has the property of having existential witnesses as described by Sridhar Ramesh. Let $\pi=\forall x\,\theta(x)$ be a true but $T$-unprovable $\Pi^0_1$ sentence with $\theta$ bounded, which exists by Gödel’s theorem. Then $\exists y\,(\theta(y)\to\forall x\,\theta(x))$ is a tautology, but there is no $n\in\omega$ such that $T\vdash\theta(n)\to\forall x\,\theta(x)$: since $\pi$ is true, $\theta(n)$ is provable in Robinson’s arithmetic, hence $T$ would prove $\pi$.

In fact, an iteration of the same idea shows that the only consistent theory with the property of having existential witnesses is the true arithmetic $\mathrm{Th}(\mathbb N)$.

The situation with goodness is more complicated: there are good theories, such as any consistent theory axiomatizable over $\pa$ by a set of $\Pi^0_1$ sentences. Nevertheless, neither $\zfc$ nor any its extension is good.

Let $T=\zfc$, or more generally, let $T$ be any recursively axiomatizable extension of $\pa$ which proves the local $\Sigma^0_1$-reflection principle for $\pa$. Let $\Box_\pa$ denote the provability predicate for $\pa$, and $T_{\Pi^0_1}$ the set of all $\Pi^0_1$ theorems of $T$. By a theorem of Lindström, there exists a $\Pi^0_1$ sentence $\pi$ such that $\pa+\pi$ is a $\Sigma^0_1$-conservative extension of $\pa+T_{\Pi^0_1}$. $T$ proves the reflection principle $\tag{*}\Box_\pa(\neg\pi)\to\neg\pi$ which can be written as a $\Sigma^0_2$ sentence, hence assuming $T$ is good, $(*)$ is provable in $\pa+T_{\Pi^0_1}$, and a fortiori in $\pa+\pi$. But then $\pa+\pi$ proves its own consistency, hence by Gödel’s theorem, it is inconsistent. By $\Sigma^0_1$-conservativity, $\pa+T_{\pi^0_1}$ is also inconsistent, hence $T$ is inconsistent, contradicting its goodness.