[FOM] Interpretability in Q

[Harvey Friedman]

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