Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for either a proof of counterexample of this:

Lemma: Let $\pi$ be a faithful interpretation of $PA$ into $ZFC$, and let $PA'$ be the image of $PA$ under $\pi$. If there is a $T$ with $PA' \subset T$ and $T$ proves $\operatorname{Con}(ZFC)$, then $ZFC \subset T$.

This feels too good to be true. Alas I have no counterexamples or a proof.

Thanks!

share|improve this question
1  
What you ask is very different from what your title asks. The lemma is indeed false, by the way. –  Andres Caicedo Apr 29 '12 at 23:53
    
Sorry for the typo, and thanks for pointing it out. The Lemma should read $PA' \subset T$ and $T$ proves $\operatorname{Con}(ZFC)$, not $\operatorname{Con}(PA')$. –  student Apr 30 '12 at 0:19
    
@Chuck that is a nice example. –  student Apr 30 '12 at 0:31
    
@Chuck, yes by set theory I mean $ZFC$. But by "$A$ stronger than $B$", I am asking not whether Con$(A)$ proves Con$(B)$, but the different question whether $B \subset A$. (Assume the theories are all in the same language.) By Goedel we know $A$ proves Con($B$) means $A$ not a subset of $B$, but can we show that $B\subset A$? –  student Apr 30 '12 at 0:35

3 Answers 3

up vote 2 down vote accepted

Consistency is a $\Pi_1$ statement, and in fact a universal $\Pi_1$ statement: if we have a strong enough base theory (say $\mathsf{I}\Delta_0$) then adding the consistency of $\mathsf{ZFC}$ will allow us to obtain all $\Pi_1$ consequences of $\mathsf{ZFC}$ but nothing more, e.g. we cannot prove existence of any new object.

For the first one, we need to show that we can define the truth of $\Pi_1$-formulas, and that consistency of $\mathsf{ZFC}$ is equivalent to $\Pi_1$-soundness of $\mathsf{ZFC}$ (this follows from $\mathsf{ZFC}$ being $\Sigma_1$-complete). Then if $\pi$ is a proof of $\mathsf{ZFC} \vdash \varphi$, then it is a finite object and therefore we can show its existence in $T$, and by $\Pi_1$-soundness it would follow $Tr(\varphi)$. Then we have to show that we can derive $\varphi$ from $Tr(\varphi)$ (which is proven by induction over the structure of the formulas).

For the second one, note that adding $\Pi_1$ axioms doesn't imply existence of any new objects.

share|improve this answer
    
Nice, thanks Kaveh. I'll have to go through the details of this for myself, but this is definitely a good start. –  student May 12 '12 at 23:57
1  
@user30013, you are welcome. Let me know if you run into trouble in completing the proof and I will provide more details. –  Kaveh May 13 '12 at 0:07
    
Kaveh, will do! –  student May 13 '12 at 2:10

The answer to the question in your title is indeterminate unless you specify what you mean by 'set theory'. If by 'set theory' you mean ZFC then, assuming that ZFC is consistent, $T$ will necessarily have to be stronger than ZFC since any any theory stronger than arithmetic cannot prove its own consistency by Godel's second theorem. (cf. Gentzen's proof of Con(PA) for an analogous situation.)

The lemma, as pointed out by Andres, is false. For example, to use Gentzen again, $$\text{PA}+(\text{transfinite induction up to } \epsilon _0) \vdash \text{Con(PA)}$$ but in no way does that imply that PA+(transfinite induction up to $\epsilon _0$) is stronger than ZFC, no matter where you interpret PA.

share|improve this answer
    
Why not two non-comparable theories, one of which proves the consistency of the other? –  GEdgar Apr 30 '12 at 0:40

For most pairs of naturally occuring theories, at least one embeds in the other (there is a linear hierarchy of "consistency strength") so in effect the question is whether there is a weak set theory, or a strong theory of arithmetic, intermediate between PA and ZFC. Several such theories of second-order arithmetic, thought of as weak systems of analysis, are considered in proof theory and in so-called Reverse Mathematics that determines the logical strength of particular theorems.

http://en.wikipedia.org/wiki/Second-order_arithmetic#Subsystems_of_second-order_arithmetic

EDIT: the question was changed to require Con(ZFC) not Con(PA'), which is a completely different matter. It is now asking whether telling Con(ZFC) to a limited theory of arithmetic adds to it all the proof-theoretic power of set theory, such as the ability to prove all the theorems of arithmetic provable in set theory. The answer must be "no", but I do not know a proof.

share|improve this answer

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.