Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
3  
Could you explain why if ZFC is not "good" then it proves a false arithmetic statement? –  Trevor Wilson Aug 1 '12 at 18:26
1  
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
6  
@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
1  
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
add comment

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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