# Are all the theorems true?

The title sounds a bit philosophical, but it is

Consider a first order theory $T$, which is an extension of Peano Arithmetic. Call this theory "good" if it is consistent and satisfies the following

Property: For any $\phi\in\Sigma^0_{n+1}$ such that $T\vdash \phi$ there exists $\psi\in\Pi^0_{n}$ such that $T\vdash\psi$ and $PA\vdash\psi\to\phi$.

Question 1. Is $ZFC$ "good"?

Question 2. The same for $ZFC+something$ (from the lot of proposed new axioms).

Motivation.

If $ZFC$ is not "good" then there (EDIT) may be theorems which can be proved in $ZFC$ despite they are false (in the standard model of PA). I believe that $ZFC$ is "good". However, I would like to know if there is a formal proof. (Admittedly, I don't have a slightest idea what a proof may be like). By the way, "goodness" implies consistency, hence a proper proof requires some new axioms (a large cardinal, perhaps).

(EDIT). As Andreas Blass pointed out correctly, even if a theory is not "good" in the above sense, it does not yet follow that some of the theorems are wrong (an obvious fact which I have missed somehow). Still, the question if ZFC is "good" may be of some interest, in my opinion.

Question 3. Is "goodness" equivalent to consistency? (I doubt this).

EDIT: (Clarification). In this question, the theory $T$ is supposed to be "good" and at least as strong as $ZFC$. (Thus, the answer to Question 1 must be yes). The question is, whether $T\vdash Con(T)\to Good(T)$, where $Good(T)$ is a formalization of "goodness"; note that $Good(T)\in \Pi^0_{2}$.

P.S. Is there a standard term for "good"?

• Could you explain why if ZFC is not "good" then it proves a false arithmetic statement? – Trevor Wilson Aug 1 '12 at 18:26
• Trevor, it's not good if ZFC proves $(\exists n \in \omega)\psi(n)$ but doesn't prove $\psi(0)$, nor $\psi(1)$, nor $\psi(2)$, etc. – François G. Dorais Aug 1 '12 at 19:36
• @Francois: Even if it doesn't prove any specific numerical instance of $\psi$, couldn't one of those instances be true? In that case, I don't see how to show that $T$ proved a false arithmetical statement. – Andreas Blass Aug 1 '12 at 21:34
• For example, if $\psi(n)$ says that $2^{\aleph_0} < \aleph_\omega \implies 2^{\aleph_0} = \aleph_n$ then ZFC proves $(\exists n \in \omega)\,\psi(n)$ but does not prove $\psi(n)$ for any any $n<\omega$. – Trevor Wilson Aug 2 '12 at 2:13
• @Trevor: your $\psi$ does not count, because it is not arithmetic. @Andreas: your are right. – Alex Gavrilov Aug 2 '12 at 10:06

$\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.

• I do not understand why $(*)$ is provable in $\pa+\pi$. However, I begin to think that you are right and $\zfc$ is not "good". – Alex Gavrilov Aug 2 '12 at 15:54
• @Alex: $\pa+\pi$ extends $\pa+T_{\Pi^0_1}$, so anything provable in the latter is provable in the former. – Emil Jeřábek Aug 2 '12 at 15:58
• I got it. It's Theorem 4, is it not? Thank you much. – Alex Gavrilov Aug 2 '12 at 16:00
• Yes, the Lindström’s theorem I’m referring to is Theorem 4 in his paper. – Emil Jeřábek Aug 2 '12 at 16:05

"goodness" appears to be your attempt to describe the property of having existential witnesses (that whenever $T$ proves there exists an $x$ such that $P(x)$, there is also a specific numeral n such that $T$ proves $P(n)$). There are also other related ideas such as $\omega$-consistency. But "goodness" doesn't quite match any of these exactly.

Re: question 3: No, "goodness" is not equivalent to consistency. After all, PA plays an unduly special role in the definition of "good", and not such a special role in the idea of "consistent". An example of a theory which is consistent (on the standard assumption that PA is) but not "good" is PA + "PA is inconsistent". This proves the $\Sigma_1$ statement "PA is inconsistent", but no $\Pi_0$ statement entailing this in PA.

• You are right, but you did not answer any of the questions. Sorry, I didn's make Question 3 clear enough: it is about theories which are: 1) at least as strong as ZFC and 2) "good". Your example is not "good"and is much weaker than ZFC. – Alex Gavrilov Aug 2 '12 at 3:21
• As you poited put, $\omega$-consistency is related to what I call "goodness" (though technically it is neither necessary, nor sufficient). If you can give a reference to a proof of $\omega$-consistency of $ZFC$ this would be, at least, a partial answer. I confess, I don't know about such a proof. – Alex Gavrilov Aug 2 '12 at 3:34
• If question 3 is restricted to theories which are "good", then of course they will be consistent as well... consistency is part of your definition of "goodness"! What could question 3 be asking about, if not the question of whether there is a consistent, non-"good" theory? – Sridhar Ramesh Aug 2 '12 at 4:57
• The example I gave is also not restricted to PA. It works in exactly the same way for any base theory capable of speaking of itself; e.g., if ZFC is consistent, then ZFC + "ZFC is inconsistent" is consistent but not "good". – Sridhar Ramesh Aug 2 '12 at 4:57
• (I suppose I should point out, in case you are not aware, that the reason ZFC + "ZFC is inconsistent" is equiconsistent with ZFC is because of Goedel's second incompleteness theorem) – Sridhar Ramesh Aug 2 '12 at 4:59