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$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 2, 2012 at 2:13
  • $\begingroup$ @Trevor: your $\psi$ does not count, because it is not arithmetic. @Andreas: your are right. $\endgroup$ Commented 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$ Commented 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$ Commented Aug 2, 2012 at 15:58
  • $\begingroup$ I got it. It's Theorem 4, is it not? Thank you much. $\endgroup$ Commented Aug 2, 2012 at 16:00
  • $\begingroup$ Yes, the Lindström’s theorem I’m referring to is Theorem 4 in his paper. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Aug 2, 2012 at 4:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .