What's so special about Kruskal's theorem and the ordinal Γo? A survey of some results in proof theory

1991/09/01 by Jean H. Gallier, Jean Gallier · 64 citations
Computer Science · Mathematics · #Advanced Algebra and Logic #Algorithm #Connection (principal bundle) #Correctness #Countable set #Discrete mathematics #Kruskal's algorithm #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Mathematical proof #Mathematics #Monotonic function #Proof theory #Spanning tree

paper · pdf · doi:10.1016/0168-0072(91)90022-e

published in Annals of Pure and Applied Logic 53(3), 199-260 (Elsevier BV)

crossref issued 1991/09/01 · crossref published 1991/09/01 · crossref published-print 1991/09/01 · openalex publication_date 1991/09/01 · crossref created 2002/07/26 · crossref deposited 2024/12/06 · openalex created_date 2025/10/10 · crossref indexed 2026/01/13 · openalex updated_date 2026/08/02

Citations

• Classically and intuitionistically provably recursive functions
• Π12-logic, Part 1: Dilators
• Konstruktiver Aufbau eines Abschnitts der zweiten Cantorschen Zahlenklasse
• Accessible Independence Results for Peano Arithmetic
• The slow-growing and the Graegorczyk hierarchies
• Finiteness of the Odd Perfect and Primitive Abundant Numbers with n Distinct Prime Factors
• Normal functions and constructive ordinal notations

Cited by

• Fast-growing hierarchy [wikipedia]
• Hardy hierarchy [wikipedia]