[FOM] Gentzen's consistency proof
Timothy Y. Chow
tchow at alum.mit.edu
Thu May 10 23:14:32 EDT 2018
I'm trying to understand Gentzen's consistency proof of PA. There is
something that I think follows as a corollary of the proof but I'm
wondering if I'm missing something.
Suppose I write down explicitly a Turing machine M that represents
epsilon_0. That is, M takes a pair of natural numbers (a,b) as input and
outputs either 0 or 1, and I can prove (using ZF or whatever) that if I
interpret an output of 1 as "a < b" then I get a total ordering on the
natural numbers that is order isomorphic to epsilon_0.
Does Gentzen's proof give an effective procedure for taking a PA-proof of
0=1 and producing a Turing machine M' that outputs an infinite sequence of
natural numbers a_1, a_2, a_3, ... such that a_i > a_{i+1} for all i,
where ">" denotes the aforementioned epsilon_0 ordering computed by M?
I think that the answer is yes but I'm a little concerned that
ineffectivity might creep in somewhere.
Tim
More information about the FOM
mailing list