[FOM] PA and recursive saturation: correction
Harvey Friedman
friedman at math.ohio-state.edu
Thu Mar 23 17:48:48 EST 2006
On 3/23/06 6:17 AM, "Jeremy Avigad" <avigad at cmu.edu> wrote:
> Responding to a posting of Arhat Virdi, on March 19 Harvey Friedman wrote:
>
>> Let T be any reasonable theory, finitely axiomatized like ISigma1, or
>> schematically like PA. We can form T(sat) as you indicate.
>
> ...
>
>> It also appears that for reasonable T, there is a superexponential blowup
>> here. Is this known?
>
> I responded that this is straightforwardly provable using techniques
> described by Pudlak in his article in the Handbook of Proof Theory.
>
> I was too glib. Harvey has pointed out to me that the argument I had in
> mind does not work when T is PA. In that case, I suspect the claim is
> false; with care, it should be possible to use reflection in PA and
> eliminate the sat predicate without significant blowup.
>
> I think my argument works in the finitely axiomatized case, though. That
> is, I think the following theorem and sketch of a proof are correct. ...
Avigad goes on to sketch an argument. What he sketches appears to be exactly
my proof for the finitely axiomatized case, except I just simply quote my
finite Godel's theorem rather than redo that self reference argument at the
end.
I thought I could probably also do this for (systems like) PA, but I will
think about this situation some more...
Harvey Friedman
More information about the FOM
mailing list