New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems

DOI10.1016/0304-3975(91)90272-4zbMATH Open0728.03031OpenAlexW2004178012MaRDI QIDQ804570FDOQ804570

Authors: Horst Luckhardt 

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90272-4

Recommendations

• Gödel's third incompleteness theorem
• A direct proof of Gödel's incompleteness theorems
• On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
• scientific article; zbMATH DE number 2222023
• Gödel's second incompleteness theorem: how it is derived and what it delivers

zbMATH Keywords

consistency[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=G%EF%BF%BD%EF%BF%BDdel%27s+second+incompleteness+theorem&go=Go G��del's second incompleteness theorem]formally undecidable propositions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Finite Partially‐Ordered Quantifiers
• On Goedel speed-up and succinctness of language representations
• Some applications of Henkin quantifiers
• Herbrand-Analysen zweier Beweise des Satzes von Roth: Polynomiale Anzahlschranken
• Gödel's Second incompleteness theorem for Q
• Title not available (Why is that?)
• A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
• The computational complexity of logical theories
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Redundancies in the Hilbert-Bernays derivability conditions for Gödel's second incompleteness theorem
• The varieties of arboreal experience
• Finite approach to the problem of optimizing theorem-proving algorithms
• A Gödel Theorem on Network Complexity Lower Bounds
• Title not available (Why is that?)
• Title not available (Why is that?)
• A theorem on shortening the length of proof in formal systems of arithmetic
• Abbreviating proofs by adding new axioms

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems

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