VARIANTS of KREISEL'S CONJECTURE on A NEW NOTION of PROVABILITY

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

Abstract

Kreisel's conjecture is the statement: if, for all n ∈ ℕ, PA ⊢ksteps φ(n), then PA ⊢ ∀x.φ(x). For a theory of arithmetic T, given a recursive function h, T ⊢≤h φ holds if there is a proof of φ in T whose code is at most h(#φ). This notion depends on the underlying coding. PhT(x) is a provability predicate for ⊢≤h in T. It is shown that there exists a sentence φ and a total recursive function h such that T ⊢≤h PrT(⌈PrT (⌈φ⌉) → φ⌉), but T ⊢/≤h φ, where PrTstands for the standard provability predicate in T. This statement is related to a conjecture by Montagna. Also variants and weakenings of Kreisel's conjecture are studied. By use of reexion principles, one can obtain a theory ThΓ that extends T such that a version of Kreisel's conjecture holds: given a recursive function h and φ(x) a Γ- formula (where Γ is an arbitrarily fixed class of formulas) such that, for all n ∈ N, T ⊢≤h φ(n), then ThΓ⊢ ∀x.φ(x). Derivability conditions are studied for a theory to statisfy the following implication: if T ⊢ ∀x.PhT(pφ(x)q), then T ⊢ ∀x.φ(x). This corresponds to an arithmetization of Kreisel's conjecture. It is shown that, for certain theories, there exists a function h such that ⊢k steps ⊆ ⊢≤h.

Original languageEnglish
JournalBulletin of Symbolic Logic
DOIs
Publication statusE-pub ahead of print - 2 Dec 2021

Fingerprint

Dive into the research topics of 'VARIANTS of KREISEL'S CONJECTURE on A NEW NOTION of PROVABILITY'. Together they form a unique fingerprint.

Cite this