What's So Special about Kruskal's Theorem and the Ordinal Gammo sub 0? A Survey of Some Results In Proof Theory.
Abstract
This paper consists primarily of a survey of results of Harvey Friedman about some proof theoretic aspects of various forms of Krusal's 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 Girard's 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 Kruskal's theorem due to Harvey Friedman. These versions of Kruskal's 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. Kruskal's 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 Kruskal's 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 30, 1993
- Accession Number
- ADA290387
Entities
People
- Jean H. Gallier
Organizations
- University of Pennsylvania