7
$\begingroup$

The title sounds a bit philosophical, but it is
about mathematics. Let me explain.

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"?

$\endgroup$
5
  • 3
    $\begingroup$ Could you explain why if ZFC is not "good" then it proves a false arithmetic statement? $\endgroup$ Aug 1, 2012 at 18:26
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 1, 2012 at 19:36
  • 6
    $\begingroup$ @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. $\endgroup$ Aug 1, 2012 at 21:34
  • 1
    $\begingroup$ 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$. $\endgroup$ Aug 2, 2012 at 2:13
  • $\begingroup$ @Trevor: your $\psi$ does not count, because it is not arithmetic. @Andreas: your are right. $\endgroup$ Aug 2, 2012 at 10:06

2 Answers 2

11
$\begingroup$

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

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

"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.

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Aug 2, 2012 at 3:21
  • $\begingroup$ 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. $\endgroup$ Aug 2, 2012 at 3:34
  • $\begingroup$ 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? $\endgroup$ Aug 2, 2012 at 4:57
  • $\begingroup$ 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". $\endgroup$ Aug 2, 2012 at 4:57
  • $\begingroup$ (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) $\endgroup$ Aug 2, 2012 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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