Fast growing functions and ordinals

Add to your list(s) Download to your calendar using vCal

• Richard Kaye, School of Maths, University of Birmingham
• Tuesday 01 November 2016, 16:00-18:00
• Watson Building (Mathematics, R15 on map) Room 310.

If you have a question about this talk, please contact Richard.

Week 6 is reading week in Birmingham, so it seems a good idea to take a gentle look at this topic, which is of central importance to much of proof theory and the theory of models of arithmetic. The session is particularly aimed at students who are new to the topic.

The subject under discussion can be presented as a nice game. The two (or more) players are both given a piece of paper the size of a postage stamp, or possibly filespace the size of an SMS text, and must define a (finite) natural number. The person who defines the largest natural number wins. The usual trick is to write down something like f(1000) for a very fast growing function f. A sensible variation on the game requires the function f to be computable (recursive).

Obviously, exponentiation will allow some astronomical numbers to be defined. But this might not win. Numbers from Ramsey theory tend to be big, but this kind of strategy needs care. You may have heard of the Knuth up-arrow notation, or Conway’s chained arrow notation. This is better, but will still lose against clever opponents.

To study Peano Arithmetic (PA) all of these and more are needed. It turns out that PA is closely related to Goodstein sequences, and to a game called Hercules and the Hydra. To analyse all these functions and say some thing about their growth rates, ordinals are required. Families of recursive functions defined using ordinals, such as the “fast growing hierarchy” and the “Hardy hierarchy” are useful tools for this study. I will explain all this, at least up to the ordinal epsilon-0 (which is what you need for first order PA).

This talk is part of the Midlands Logic Seminar series.

This talk is included in these lists:

• Midlands Logic Seminar
• Watson Building (Mathematics, R15 on map) Room 310

Note that ex-directory lists are not shown.