Kreisel’s No-Counterexample Interpretation: How can we turn proofs in elementary number theory into programs?

For every true number-theoretic statement of the form “For all n there is an m such that P(n, m)” there is a witnessing function f such that for all n, P(n, f(n)) is true.

For example, a witnessing function for the statement “For all n there is an m such that m > n and m is prime” is any function which takes a number and returns a prime higher than that number, which certainly exists.

In general, if the statement “For all n0 there is an m0 such that for all n1 there is an m1 such that … for all nr there is an mr such that P(n0, m0, …, nr, mr)” is true then there are witnessing functions f0(n0), …, fr(n0, …, nr) such that for all n0, …, nr, P(n0, f0(n0), …, nr, fr(n0, …, nr)) is true.

Because it’s the case that if a number-theoretic statement is true, then its witnessing functions exist, we might hope that it woud be the case that if a number-theoretic statement is provable, then its witnessing functions are computable, that is, that we could extract a computer program for the witnessing functions from the proof.

For example, a computable witnessing function for the statement “For all n there is an m such that m > n and m is prime” can be easily extracted from Euclid’s proof that there are infinitely any primes.

Can this always be done? Unfortunately the answer is no, but Georg Kreisel’s No-Counterexample Interpretation gives an elegant piece of computational data that can be extracted from any provable number-theoretic statement.

For an example of a provable number-theoretic statement whose witnessing functions are not computable, consider the following: Let Halts(e, s) be the predicate which asserts that the eth Turing machine halts in s steps. (Note that Halts(e,s) is decidable—even primitive recursive.)

Clearly every Turing machine either halts or it doesn’t. It follows that “For all e there is an s such that for all r, (Halts(e,s) or ~Halts(e,r))” is provable (without any number-theoretic axioms even!) However, there can be no computable witnessing function f(e) for s, since if there were, we could solve the Halting problem: any e halts iff it halts in f(e) steps, which we can check computably.

Meditating on this example a bit may lead you to believe that there is no hope of extracting any computable information from this proof, which is one of the reasons why I think the no-counterexample interpretation is neat. It essentially says that although there may not be a sequence of computable witnessing functions for a provable statement, we may computably simulate a sequence of witnessing functions to someone who will only use them once, and who tells us in advance how he plans to use them.

Formally: Suppose that a statement of the form “For all n0 there is an m0 such that for all n1 there is an m1 such that … for all nr there is an mr such that P(n0, m0, …, nr, mr)” is provable in Peano Arithmetic (a first-order formal system for proving number-theoretic statements) where P is quantifier-free and involves only primitive recursive predicates and function symbols.

Then there are computable functionals f0, …, fr each taking r arguments, the ith of which is a function from \mathbb{N}^i to \mathbb{N} satisfying the following: For any functions g0, …, gr such that gi is from \mathbb{N}^i to \mathbb{N},

P(g0, f0(g0, …, gr), g1(f0(g0, …, gr)), f1(g0, …, gr), …, gr(f0(g0, …, gr), …,fr – 1(g0, …, gr)),fr(g0, …, gr))

is true.

Here the functions gi represent the way in which the witnessing functions were to be used, and the content of the claim is that we can write computer programs which, given these functions in advance can simulate the witnessing functions to the “satisfaction” of the functions gi.

Let’s see how this works in our example above: Our statement is “For all e there is an s such that for all r, either Halts(e,s) or ~Halts(e,r).” We can’t write a program which determines if the eth Turing machine halts or not, but suppose we know that given e and s, our customer will only check that “Halts(e,s) or ~Halts(e,r)” is true for some specific r = r(e, s). Then we can satisfy him or her as follows: given e, check if Halts(e, r(e, 0)) holds. If so, return s = r(e, 0)), and the customer will be satisfied since Halts(e, s) will hold. If not, return, s = 0 and the customer will be satisfied since Halts(e, r) will not hold.

For more information, check out Jeremy Avigad and Solomon Feferman’s excellent article on Gödel’s functional interpretation in the Handbook of Proof Theory (also available here online).

About these ads

2 Comments

Filed under Proof Theory

2 responses to “Kreisel’s No-Counterexample Interpretation: How can we turn proofs in elementary number theory into programs?

  1. I always liked the game-theoretic interpretation of Kreisel’s No-Counterexample Interpretation (and its big brother, Gödel’s Dialectica). This is related to the semantics game described in my post on Fraïssé’s Theorem.

    The witnessing functions form (the main part of) a winning strategy for True in the semantics game. While True’s winning strategy in that game is not computable in general, Kreisel’s No-Counterexample Interpretation says that there is a computable functional that witnesses that False does not have winning strategy in the semantics game associated to a true statement. Consequently, the existence of witnessing functions is equivalent to some form of determinacy (which depends on the base axioms).

  2. Pingback: Sequential compactness theorem @ unwanted capture

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s