[FOM] Interpretability in Q
Harvey Friedman
friedman at math.ohio-state.edu
Wed Dec 22 18:39:31 EST 2004
On 12/20/04 6:05 AM, "Edward T. Dean" <edean at myway.com> wrote:
>
> I have been skimming through Edward Nelson's _Predicative Arithmetic_
> recently, and he writes (at the tail end of Ch. 15) that he does not know the
> answer to a certain compatibility problem regarding interpretability in
> Robinson arithmetic: for formulas A and B, if both Q[A] and Q[B] are
> interpretable in Q, then is Q[A,B] interpretable in Q? I'm just wondering if
> anyone on FOM does know the answer, as the book is decently aged.
>
The answer is no. In fact, I give an example where Q[A,B] is not only not
interpretable in Q, but ZFC is interpretable in Q[A,B].
THEOREM. Let T be finitely axiomatized systems in predicate calculus with
equality. The following are equivalent.
i) EFA = ISigma0(exp) proves "T is cut free consistent";
ii) T is interpretable in Q.
Now take C = the Rosser sentence for ZFC = "every proof of C from ZFC has a
proof of notC from ZFC with smaller Godel number", and D = "every proof of
notD from ZFC has a proof of D from ZFC with smaller Godel number".
Let K be a suitably large finite fragment of PFA = ISigma0.
Then EFA proves "if K is cut free consistent then K + C is cut free
consistent", and "if K is cut free consistent then K + D is cut free
consistent".
Hence EFA proves "K + C is cut free consistent" and "K + D is cut free
consistent".
So by the Theorem, K + C is interpretable in Q, and K + D is interpretable
in Q.
Now K + C + D = K + Con(ZFC). It can be shown that ZFC is interpretable in K
+ Con(ZFC).
Years ago, I had a series of theorems to the effect that "relative
consistency is the same as interpretability". This stuff has been published
and reworked by several authors.
I don't remember seeing this particular refinement:
THEOREM. Let S,T be finitely axiomatized systems in predicate calculus with
equality, where Q is interpretable in S. The following are equivalent.
i) EFA = ISigma0(exp) proves "if S is cut free consistent then T is cut free
consistent;
ii) T is interpretable in S.
Harvey Friedman
More information about the FOM
mailing list