[FOM] Gödel's functional interpretation

William Tait williamtait at mac.com
Mon May 30 11:40:08 EDT 2011


On May 29, 2011, at 3:27 PM, Añon Barfod wrote:

> It would be interesting to hear what's Voevodsy's take on Gödel's
> functional interpretation.
> 
> There's a proof theoretic discussion of the method in:
> 
> Feferman: "Gödel's functional dialectica interpretation", Handbook of
> proof theory.
> 
> On May 21, 2011, at 3:26 PM, Vladimir Voevodsky wrote:
>> It is very typical, that the consistency issues are related to the
>> termination for different algorithms and in this case it is a very
>> explicit combinatorial algorithm but there is no mathematical proof
>> that it terminates.

The reference should be to Avigad and Feferman. 

The algorithm in this case is the one which, applied to a closed numerical term of Gödel's theory T, computes it---i.e. carries out a certain sequence of reductions via the explicit and primitive recursive definitions. The statement that this algorithm terminates with a numeral in each case implies (in PRA) consistency of T and so of PA.

I do wish that Voevodsky would stop writing "there is no mathematical proof that it terminates", since that statement is, as numerous postings attest, literally ambiguous.  There are arguments for Con_{PA} or Con_{T} which most of is would accept as mathematical proofs; but we don't accept them as establishing the consistency of PA or T, resp.

Bill Tait


More information about the FOM mailing list