Proof-theoretic investigations on Kruskal's theorem

DOI10.1016/0168-0072(93)90192-GzbMath0786.03042WikidataQ56687925 ScholiaQ56687925MaRDI QIDQ1210137

Publication date: 16 May 1993

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

well-quasi-ordering ordinal analysis Kruskal's theorem finite trees proof-theoretical strength Reverse Mathematics Ackermann ordinal predicative analysis

Mathematics Subject Classification ID

Second- and higher-order arithmetic and fragments (03F35) Recursive ordinals and ordinal notations (03F15) Complexity of proofs (03F20)

Related Items

How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study, Minimal bad sequences are necessary for a uniform Kruskal theorem, Equivalence between Fraïssé's conjecture and Jullien's theorem, A MATHEMATICAL COMMITMENT WITHOUT COMPUTATIONAL STRENGTH, A comparison of well-known ordinal notation systems for $\varepsilon _{0}$, Labelled well-quasi-order for permutation classes, Open Questions in Reverse Mathematics, Well-Ordering Principles in Proof Theory and Reverse Mathematics, Partial impredicativity in reverse mathematics, The Bachmann-Howard structure in terms of $\Sigma_1$-elementarity, Theorems as Constructive Visions, Ordinal arithmetic based on Skolem hulling, Ordinal notation systems corresponding to Friedman's linearized well-partial-orders with gap-condition, Constructive Zermelo-Fraenkel set theory and the limited principle of omniscience, Generalized fusible numbers and their ordinals, Analysis of a Double Kruskal Theorem, Well ordering principles for iterated $\Pi^1_1$-comprehension, PREDICATIVE COLLAPSING PRINCIPLES, Bachmann-Howard derivatives, The length of an intersection, Fraïssé’s conjecture in Π11-comprehension, Computable aspects of the Bachmann–Howard principle, Unnamed Item, Derivatives of normal functions in reverse mathematics, Unnamed Item, On Ordinal Invariants in Well Quasi Orders and Finite Antichain Orders, Strong WQO Tree Theorems, The Reverse Mathematics of wqos and bqos, Ordinal arithmetic with simultaneously defined theta-functions, A Survey on Ordinal Notations Around the Bachmann-Howard Ordinal, Higman’s Lemma and Its Computational Content, On Relating Theories: Proof-Theoretical Reduction, An order-theoretic characterization of the Howard-Bachmann-hierarchy, A Computation of the Maximal Order Type of the Term Ordering on Finite Multisets, Well-partial-orderings and the big Veblen number, On the Equimorphism Types of Linear Orderings, $\Pi_1^1$-comprehension as a well-ordering principle, PROOF-THEORETIC STRENGTHS OF WEAK THEORIES FOR POSITIVE INDUCTIVE DEFINITIONS, Unnamed Item, A categorical construction of Bachmann–Howard fixed points, Pure $\Sigma_2$-elementarity beyond the core, A Survey on Ordinal Notations Around the Bachmann–Howard Ordinal, An application of graphical enumeration to PA *, A flexible type system for the small Veblen ordinal, Patterns of resemblance and Bachmann-Howard fixed points, On Fraïssé's conjecture for linear orders of finite Hausdorff rank, From Kruskal’s theorem to Friedman’s gap condition, Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results, Constructive Zermelo-Fraenkel Set Theory, Power Set, and the Calculus of Constructions, Well-ordering Principles, ω-models and $$ \varPi_{1}^{1} $$-comprehension, A Glimpse of $$ \sum_{3} $$-elementarity, Beziehungen des Ordinalzahlensystems OT(ϑ) zur Veblen-Hierarchie

Cites Work