Phase transition thresholds for some Friedman-style independence results

Mathematical Logic Quarterly 53 (1):4-18 (2007)
  Copy   BIBTEX

Abstract

We classify the phase transition thresholds from provability to unprovability for certain Friedman-style miniaturizations of Kruskal's Theorem and Higman's Lemma. In addition we prove a new and unexpected phase transition result for ε0. Motivated by renormalization and universality issues from statistical physics we finally state a universality hypothesis

Categories

Keywords

Reprint years

DOI

10.1002/malq.200610022

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,069

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Phase Transition Results for Three Ramsey-Like Theorems.Florian Pelupessy - 2016 - Notre Dame Journal of Formal Logic 57 (2):195-207.
Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results.Andreas Weiermann - 2005 - Annals of Pure and Applied Logic 136 (1):189-218.
Phase transitions for Gödel incompleteness.Andreas Weiermann - 2009 - Annals of Pure and Applied Logic 157 (2-3):281-296.
Monomial ideals and independence of.Florian Pelupessy - 2017 - Mathematical Logic Quarterly 63 (1-2):59-65.
Exact unprovability results for compound well-quasi-ordered combinatorial classes.Andrey Bovykin - 2009 - Annals of Pure and Applied Logic 157 (2-3):77-84.
Which set existence axioms are needed to prove the cauchy/peano theorem for ordinary differential equations?Stephen G. Simpson - 1984 - Journal of Symbolic Logic 49 (3):783-802.
An application of graphical enumeration to PA.Andreas Weiermann - 2003 - Journal of Symbolic Logic 68 (1):5-16.
What's so special about Kruskal's theorem and the ordinal Γo? A survey of some results in proof theory.Jean Gallier - 1991 - Annals of Pure and Applied Logic 53 (3):199-260.
What's so special about Kruskal's theorem and the ordinal Γo? A survey of some results in proof theory.Jean H. Gallier - 1991 - Annals of Pure and Applied Logic 53 (3):199-260.
A Mathematical Commitment Without Computational Strength.Anton Freund - 2022 - Review of Symbolic Logic 15 (4):880-906.

Analytics

Added to PP
2014-01-16

Downloads
20 (#792,293)

6 months
7 (#491,733)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Current Research on Gödel’s Incompleteness Theorems.Yong Cheng - 2021 - Bulletin of Symbolic Logic 27 (2):113-167.
Phase transitions for Gödel incompleteness.Andreas Weiermann - 2009 - Annals of Pure and Applied Logic 157 (2-3):281-296.

View all 6 citations / Add more citations

References found in this work

Proof-theoretic investigations on Kruskal's theorem.Michael Rathjen & Andreas Weiermann - 1993 - Annals of Pure and Applied Logic 60 (1):49-88.
On the interpretation of non-finitist proofs–Part II.G. Kreisel - 1952 - Journal of Symbolic Logic 17 (1):43-58.

Add more references