On the scheme of induction for bounded arithmetic formulas
From MaRDI portal
Publication:1104318
DOI10.1016/0168-0072(87)90066-2zbMath0647.03046OpenAlexW2011612028MaRDI QIDQ1104318
A. J. Wilkie, Jeffrey Bruce Paris
Publication date: 1987
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0168-0072(87)90066-2
fragments of arithmeticrelative consistencymetamathematics of weak systems of arithmeticunprovability of consistency
Related Items
End extensions of models of weak arithmetic theories, How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson's arithmetic q, Cofinality spectrum theorems in model theory, set theory, and general topology, RSUV isomorphisms for TAC\(^ i\), TNC\(^ i\) and \(TLS\), Quadratic forms in models of \(I\Delta _{0}+\Omega _{1}\). I, On induction-free provability, \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\), Relating the bounded arithmetic and polynomial time hierarchies, Herbrand analyses, Vaught's Theorem on Axiomatizability by a Scheme, EXISTENTIALLY CLOSED MODELS IN THE FRAMEWORK OF ARITHMETIC, Induction rules, reflection principles, and provably recursive functions, Bounded arithmetic and truth definition, On constructivity and the Rosser property: a closer look at some Gödelean proofs, Friedman-reflexivity, Propositional proof systems, the consistency of first order theories and the complexity of computations, A time-space hierarchy between polynomial time and polynomial space, CONSISTENCY AND THE THEORY OF TRUTH, Unifying the model theory of first-order and second-order arithmetic via \(\mathrm{WKL}_0^\ast\), Local behaviour of the Chebyshev theorem in models of I⊿0, An inside view of EXP; or, The closed fragment of the provability logic of IΔ0 + Ω1 with a prepositional constant for EXP, Preservation theorems and restricted consistency statements in bounded arithmetic, Toward the limits of the Tennenbaum phenomenon, End extensions of models of linearly bounded arithmetic, Primes and their residue rings in models of open induction, Pell equations and exponentiation in fragments of arithmetic, The absorption law. Or: how to Kreisel a Hilbert-Bernays-Löb, Model-theoretic applications of cofinality spectrum problems, Passive induction and a solution to a Paris-Wilkie open question, Nondeterministic stack register machines, Polynomially and superexponentially shorter proofs in fragments of arithmetic, The small‐is‐very‐small principle, Taking the Pirahã seriously, The logical strength of compositional principles, End extensions of models of fragments of \(\mathrm{PA}\), Interpretability degrees of finitely axiomatized sequential theories, The second incompleteness theorem and bounded interpretations, Parameter free induction and provably total computable functions, Bimodal logics for extensions of arithmetical theories, Algebraic combinatorics in bounded induction, Exponentiation and second-order bounded arithmetic, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, The formalization of interpretability, Bounded arithmetic and the polynomial hierarchy, A note on the interpretability logic of finitely axiomatized theories, On two problems concerning end extensions, Combinatorial principles in elementary number theory, Proof Theoretic Analysis by Iterated Reflection, Peano Corto and Peano Basso: A Study of Local Induction in the Context of Weak Theories, Self-verifying axiom systems, the incompleteness theorem and related reflection principles, A contribution to the end-extension problem and the \(\Pi_ 1\) conservativeness problem, On the provability logic of bounded arithmetic, The unprovability of small inconsistency. A study of local and global interpretability, The Axiom System IΣ0 Manages to Simultaneously Obey and Evade the Herbrandized Version of the Second Incompleteness Theorem, Bounds for cut elimination in intuitionistic propositional logic, The scope of Gödel's first incompleteness theorem, A model of \(\widehat{R}^2_3\) inside a subexponential time resource, Rules and arithmetics, Faith \& falsity, Consistency statements and iterations of computable functions in \(\mathrm{I}\Sigma_1\) and PRA, The predicative Frege hierarchy, Forcing in Proof Theory, Fragments of Arithmetic and true sentences, A generalization of the second incompleteness theorem and some exceptions to it, CONSISTENCY PROOF OF A FRAGMENT OF PV WITH SUBSTITUTION IN BOUNDED ARITHMETIC, Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem, The Interpretation Existence Lemma, On some formalized conservation results in arithmetic, On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories, A note on parameter free Π1 -induction and restricted exponentiation, \(S^ i_ 3\) and \(\overset\circ V^ i_ 2(BD)\), An exploration of the partial respects in which an axiom system recognizing solely addition as a total function can verify its own consistency, Non-standard finite fields over \(I\Delta_0+\Omega_1\), On the available partial respects in which an axiomatization for real valued arithmetic can recognize its consistency, Bounded arithmetic, proof complexity and two papers of Parikh, ON THE INVARIANCE OF GÖDEL’S SECOND THEOREM WITH REGARD TO NUMBERINGS, Witnessing functions in bounded arithmetic and search problems, Hereditarily-finite sets, data bases and polynomial-time computability, The arithmetics of a theory, Unprovability of circuit upper bounds in Cook's theory PV, A note on typed truth and consistency assertions, Polynomially bounded recursive realizability
Cites Work
