scientific article; zbMATH DE number 910749

MaRDI QIDQ4885911zbMATH OpenFDO

Authors Pavel Pudlák

Publication date 9 February 1997

zbMATH Keywords

finite consistencyHerbrand consistencyincompletenesslengths of proofsnon-standard models of arithmeticspeed-up of proofs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4004177
• Short proofs for slow consistency
• scientific article; zbMATH DE number 4033740
• Propositional proof systems, the consistency of first order theories and the complexity of computations

Cited in

(23)

• Short proofs for slow consistency
• Further oracles separating conjectures about incompleteness in the finite domain
• An oracle separating conjectures about incompleteness in the finite domain
• Montague's paradox, informal provability, and explicit modal logic
• Propositional proof systems and fast consistency provers
• A generalization of the second incompleteness theorem and some exceptions to it
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Much shorter proofs: A bimodal investigation
• Observations on truth, consistency and lengths of proofs
• On the consistency of consistent conjectures
• scientific article; zbMATH DE number 4004177 (Why is no real title available?)
• A note on proofs of falsehood
• scientific article; zbMATH DE number 4033740 (Why is no real title available?)
• The paradox of the knower revisited
• scientific article; zbMATH DE number 1215500 (Why is no real title available?)
• On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
• The axiom system \(\mathrm{I}\Sigma_{0}\) manages to simultaneously obey and evade the Herbrandized version of the second incompleteness theorem
• P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
• On the connection between narrowing and proof by consistency
• Long and short proofs
• Numeral completeness of weak theories of arithmetic
• Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem
• Passive induction and a solution to a Paris-Wilkie open question

This page was built for publication:

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