What's So Special about Kruskal's Theorem and the Ordinal Gammo sub 0? A Survey of Some Results In Proof Theory.

This paper consists primarily of a survey of results of Harvey Friedman about some proof theoretic aspects of various forms of Krusals tree theorem, and in particular the connection with the ordinal Gamma 0. We also include a fairly extensive treatment of normal functions on the countable ordinals, and we give a glimpse of Veblen Hierarchies, some subsystems of second-order logic, slow-growing and fast-growing hierarchies including Girards result, and Goodstein sequences. The central theme of this paper is a powerful theorem due Kruskal, the tree theorem, as well as a finite miniaturization of Kruskals theorem due to Harvey Friedman. These versions of Kruskals theorem are remarkable from a proof-theoretic point of view because they are not provable in relatively strong logical systems. They are examples of so called natural independence phenomena, which are considered by more logicians as more natural than the mathematical incompleteness results first discovered by Godel. Kruskals tree theorem also plays a fundamental role in computer science because it is one of the main tools for showing that certain orderings on trees are well founded. These orderings play a crucial role in proving the termination of systems of rewrite rules and the correctness of Knuth-Bandix completion procedures. There is also a close connection between a certain infinite countable ordinal called Gamma sub 0 and Kruskals theorem. Previous definitions of the function involved in this connection are known to be incorrect, in that, the function is not monotonic. We offer a repaired definition of this function. and explore briefly the consequences of its existence. MM