A mathematical commitment without computational strength

DOI10.1017/S1755020321000265MaRDI QIDQ5046601zbMATH OpenFDO

Authors Anton Freund

Publication date 8 November 2022

Published in The Review of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.06915

zbMATH Keywords

computational strengthGödel's second incompleteness theoremHilbert's programindependenceKruskal's theorempolynomial-time algorithm

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) First-order arithmetic and fragments (03F30) Gödel numberings and issues of incompleteness (03F40) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Gödel's second incompleteness theorem for _n-definable theories
• scientific article; zbMATH DE number 2222027
• On Godel's Second Incompleteness Theorem
• On a Relationship between Gödel's Second Incompleteness Theorem and Hilbert's Program
• Automated Reasoning with Analytic Tableaux and Related Methods

Cites work

• A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
• Applied Proof Theory: Proof Interpretations and Their Use in Mathematics
• Beweisbarkeit und Unbeweisbarkeit von Anfangsfällen der transfiniten Induktion in der reinen Zahlentheorie
• Bounds for the closure ordinals of replete monotonic increasing functions
• David Hilbert's Lectures on the Foundations of Arithmetic and Logic 1917-1933
• Elementary descent recursion and proof theory
• Graph minors. XX: Wagner's conjecture
• Harvey Friedman's research on the foundations of mathematics
• scientific article; zbMATH DE number 3898883 (Why is no real title available?)
• scientific article; zbMATH DE number 4033742 (Why is no real title available?)
• scientific article; zbMATH DE number 4033746 (Why is no real title available?)
• scientific article; zbMATH DE number 3677903 (Why is no real title available?)
• scientific article; zbMATH DE number 3786775 (Why is no real title available?)
• scientific article; zbMATH DE number 1062120 (Why is no real title available?)
• scientific article; zbMATH DE number 1870429 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• scientific article; zbMATH DE number 3225350 (Why is no real title available?)
• scientific article; zbMATH DE number 3291106 (Why is no real title available?)
• Logic, language and computation. Festschrift in Honor of Satoru Takasu
• Nonconstructive tools for proving polynomial-time decidability
• Notation systems for infinitary derivations
• On Partially Conservative Sentences and Interpretability
• On the limit existence principles in elementary arithmetic and \(\varSigma_{n}^{0}\)-consequences of theories
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Ordinal numbers and the Hilbert basis theorem
• Proof theory. 2nd ed
• Proof theory. The first step into impredicativity
• Proof-theoretic investigations on Kruskal's theorem
• Provability algebras and proof-theoretic ordinals. I
• Reflection principles and provability algebras in formal arithmetic
• Reflection Principles and their Use for Establishing the Complexity of Axiomatic Systems
• Short proofs for slow consistency
• Subsystems of second order arithmetic
• The consistency of arithmetics
• Transfinite induction within Peano arithmetic
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture

Cited in

(8)

• Analysis of a double Kruskal theorem
• The inevitability of logical strength: strict reverse mathematics
• Nichtbeweisbarkeit von gewissen kombinatorischen Eigenschaften endlicher Bäume;Unprovability of certain combinatorial properties of finite trees
• Reflections on concrete incompleteness
• Incompleteness and jump hierarchies
• Friedman-Weiermann style independence results beyond Peano arithmetic
• Generalizations of the one-dimensional version of the Kruskal-Friedman theorems
• A mathematical commitment without computational strength

This page was built for publication: A mathematical commitment without computational strength

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5046601)