Logical foundations of mathematics and computational complexity. A gentle introduction

DOI10.1007/978-3-319-00119-7MaRDI QIDQ4913583zbMATH OpenOpenAlexWikidataFDO

Authors Pavel Pudlák

Publication date 8 April 2013

Published in Springer Monographs in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-00119-7

zbMATH Keywords

computationcomputational complexityconsistencyexistencefoundations of mathematicslanguagelogicproof complexityproofs of impossibilityset theorytruth

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Complexity of computation (including implicit computational complexity) (03D15) Axiomatics of classical set theory and its fragments (03E30) Consistency and independence results (03E35) Proof theory in general (including proof-theoretic semantics) (03F03) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Gödel numberings and issues of incompleteness (03F40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 3948222
• scientific article; zbMATH DE number 2232435
• The foundations of mathematics
• scientific article; zbMATH DE number 2150901
• There's something about Gödel. The complete guide to the incompleteness theorem. Transl. from the Italian

Cited in

(22)

• The foundational debate. Complexity and constructivity in mathematics and physics. Proceedings of the conference on the foundational debate: constructivity and complexity in logic, mathematics and physics, Vienna, Austria, September 1994
• Computation, logic, games, and quantum foundations. The many facets of Samson Abramsky. Essays dedicated to Samson Abramsky on the occasion of his 60th birthday
• Further oracles separating conjectures about incompleteness in the finite domain
• Polynomial time ultrapowers and the consistency of circuit lower bounds
• An oracle separating conjectures about incompleteness in the finite domain
• Typical forcings, NP search problems and an extension of a theorem of Riis
• The Gödel phenomenon in mathematics: a modern view
• Truth and speed-up
• scientific article; zbMATH DE number 2134000 (Why is no real title available?)
• scientific article; zbMATH DE number 5072506 (Why is no real title available?)
• scientific article; zbMATH DE number 4075014 (Why is no real title available?)
• scientific article; zbMATH DE number 1344905 (Why is no real title available?)
• Incompleteness in the finite domain
• Martin Davis on computability, computational logic, and mathematical foundations
• P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
• Gödel, Tarski and the lure of natural language. Logical entanglement, formalism freeness
• Complexity barriers as independence
• Bounded Henkin quantifiers and the exponential time hierarchy
• An oracle with no up-complete sets, but NP = PSPACE
• Generic properties of a computational task predict human effort and performance
• On the complexity of finding falsifying assignments for Herbrand disjunctions

This page was built for publication: Logical foundations of mathematics and computational complexity. A gentle introduction

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