NCB: Provability Thresholds

Welcome to the first Neo Conference Blogging (NCB) post! Today's post covers some things discussed by Andreas Weiermann, hailing from The University of Utrecht (and not just because he knows where I blog). That's Andreas on the left, standing next to Alan Woods of The University of Western Australia and Andrew Brook-Taylor of The University of Vienna. We'll see Alan again in a later NCB post.

Now, we all know that Peano Arithmetic (PA) is incomplete, thanks to that crazy hipster Goedel. Problem is, not all of us are particularly enamoured of sentences that say naughty things about themselves. Do there exist natural number theoretic statements which are true for the natural numbers but unprovable in PA? Wouldn't it be deliciously scandalous if Goldbach or Riemann were in on such a conspiracy? Wouldn't it indeed!

As a matter of fact, there do exist number theoretic statements that are "naturally independant". One example is the Goodstein Sequence. This gizmo converges, but to prove that we need to use transfinite induction up to epsilon zero. Thanks to Gentzen, we also know that this is precisely what is needed to prove the consistency of PA. So, the Goodstein Sequence cannot be proven to converge from within PA. Pretty neat, huh?

One salient feature of the Goodstein Sequence is that it converges slower than Eric Moussambani approaching the finish line in a 10,000 meter race. Perhaps it is this sort of slow convergence that is behind its unprovability? Andreas showed us that it is, as well as a whole lot more, such as how to pinpoint precisely how fast a certain function has to grow for the associated statement (say about goodstein sequences) to be provable in PA.

I won't go through the actual results, since they rely on some technical definitions and, anyway, are explained in the paper below. Here's a neat logical limit law that Andreas mentioned, though. let &phi be a sentence in the language of linear orders. For some ordinal &alpha, let us say that &alpha |= &phi if &phi holds on the set of predecessors of &alpha. Suppose that we pick some ordinal &beta at random. What is the probability that &beta |= &phi? One way is to some asymptotic trickery and define a norm functions on ordinals (I won't get into the details). Then, fix some ordinal &alpha that lies between &omega^&omega and epsilon zero. Consider the number of ordinals &beta of norm n less than &alpha such that &beta |= &phi divided by the total number of ordinals of norm n less than &alpha. Then, it turns out that the limit as n goes to infinity of this ratio is either zero or one! So, depending on your choice of &alpha, a random ordinal less than &alpha almost surely satisfies &phi or almost surely does not. I told you it was neat!

Andreas has a survey paper discussing some trickery with phase transitions and such:

Analytic combinatorics, proof theoretic ordinals and phase transitions for independence results. Andreas Weiermann.

For the phase transition characterisation of Goodstein Sequences, see:

Classifying the phase transition for Hydra games and Goodstein sequences. Andreas Weiermann

More NCB tomorrow!