6
$\begingroup$

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!

  • 0
    @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$?2012-04-30

3 Answers 3

1

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.

  • 1
    Why not two non-compa$r$able theorie$s$, one of which proves $t$he consistency of the other?2012-04-30
2

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.

2

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.

  • 0
    Kaveh, will do!2012-05-13