[FOM] Gentzen's consistency proof
tchow
tchow at alum.mit.edu
Mon May 14 19:04:56 EDT 2018
On 2018-05-14 10:28, WILLIAM TAIT wrote:
> Since there are no proofs of 0=1(I hope!), maybe you need to
> formulate your question.
Here is an attempt to be more precise.
I've been focusing on Gentzen's first proof, that uses game-theoretic
concepts and trees. As I understand it, to every true statement of
arithmetic one can associate a "reduction," which is an effective
strategy for winning a certain syntactic game. A skeptic who is queasy
about infinite sets and the concept of a "true statement of arithmetic"
can nevertheless accept that Gentzen has a way of explicitly
constructing reductions (which can be represented explicitly as Turing
machines that implementing the winning strategy) for the "base case"
and, for each deductive rule in PA, effectively producing a reduction
for the result of the deduction. (I'm being intentionally vague here
about the specific implementation of PA since I believe it doesn't
really matter for my question.)
The most obvious avenue for the skeptic that I can see is that the
skeptic might not believe that Gentzen's algorithm for producing new
reductions (Turing machines) always produces Turing machines that
*halt*, when we track through a PA-proof. The skeptic can therefore
imagine a PA-proof of 0=1, and imagine running Gentzen's algorithm to
produce a corresponding sequence of reductions. But it seems to me that
the skeptic is going to say that the alleged reduction of 0=1 doesn't
halt. To me as a non-skeptic, this would seem to be a claim that a
particular ordinal < epsilon_0 admits an infinite decreasing
subsequence.
So I guess what I'm wondering if this line of reasoning can be
formalized in, say, PRA, as a proof of an assertion that the procedure
I've described above does indeed effectively produce a non-halting
Turing machine (that is traversing a decreasing subsequence in some
ordinal < epsilon_0) from a PA-proof of 0=1.
Tim
More information about the FOM
mailing list