Existence and feasibility in arithmetic

DOI10.2307/2269958zbMath0243.02037OpenAlexW2040404640MaRDI QIDQ5654035

Publication date: 1971

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2269958

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Computability and recursion theory (03D99) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

J-Calc: a typed lambda calculus for intuitionistic justification logic ⋮ On V.A. Yankov’s Contribution to the History of Foundations of Mathematics ⋮ Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings ⋮ Two General Results on Intuitionistic Bounded Theories ⋮ Dual weak pigeonhole principle, Boolean complexity, and derandomization ⋮ A Conservation Result Concerning Bounded Theories and the Collection Axiom ⋮ The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem ⋮ Approximate counting and NP search problems ⋮ FUZZY LOGIC, FUZZY SETS, AND NATURAL LANGUAGES ⋮ Quadratic forms in models of \(I\Delta _{0}+\Omega _{1}\). I ⋮ Unnamed Item ⋮ Some paradoxes of infinity revisited ⋮ Relating the bounded arithmetic and polynomial time hierarchies ⋮ On the scheme of induction for bounded arithmetic formulas ⋮ Elementary realizability ⋮ Bounded functional interpretation and feasible analysis ⋮ On the number of steps in proofs ⋮ Interpretability suprema in Peano arithmetic ⋮ Preservation theorems and restricted consistency statements in bounded arithmetic ⋮ On parallel hierarchies and \(R_k^i\) ⋮ Pell equations and exponentiation in fragments of arithmetic ⋮ The absorption law. Or: how to Kreisel a Hilbert-Bernays-Löb ⋮ STRICT FINITISM, FEASIBILITY, AND THE SORITES ⋮ The logic of justified belief, explicit knowledge, and conclusive evidence ⋮ \(\Delta\)-languages for sets and LOGSPACE computable graph transformers ⋮ Primitive recursive reverse mathematics ⋮ Strict finitism and feasibility ⋮ On feasible numbers ⋮ On parallel hierarchies and R ki ⋮ Some structural similarities between uncountable sets, powersets and the universe ⋮ Grzegorcyk's hierarchy and IepΣ₁ ⋮ On the finite axiomatizability of ⋮ ON SHAVRUKOV’S NON-ISOMORPHISM THEOREM FOR DIAGONALIZABLE ALGEBRAS ⋮ Purity and Explanation: Essentially Linked? ⋮ A theory of hyperfinite sets ⋮ Quadratic forms in models of \(I\Delta_0 + \Omega_1\). II: Local equivalence ⋮ Build your own clarithmetic I: Setup and completeness ⋮ Skolem functions of arithmetical sentences. ⋮ Feasible operations on proofs: the logic of proofs for bounded arithmetic ⋮ The formalization of interpretability ⋮ Arithmetizing uniform \(NC\) ⋮ Parikh and Wittgenstein ⋮ \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly ⋮ Combinatorial principles in elementary number theory ⋮ Proof Theoretic Analysis by Iterated Reflection ⋮ Provability logic and the completeness principle ⋮ P, NP, Co-NP and weak systems of arithmetic ⋮ On the concept of finitism ⋮ Abelian groups and quadratic residues in weak arithmetic ⋮ A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points ⋮ The unprovability of small inconsistency. A study of local and global interpretability ⋮ Intuitionistic elementary arithmetic ⋮ Provably recursive functions of constructive and relatively constructive theories ⋮ Homomorphisms and chains of Kripke models ⋮ POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Bounded functional interpretation ⋮ Upper and lower Ramsey bounds in bounded arithmetic ⋮ Inconsistency in mathematics and the mathematics of inconsistency ⋮ Logics for reasoning about cryptographic constructions ⋮ Radical anti-realism, Wittgenstein and the length of proofs ⋮ Consistency statements and iterations of computable functions in \(\mathrm{I}\Sigma_1\) and PRA ⋮ Triangular norm based predicate fuzzy logics ⋮ Asymptotic cyclic expansion and bridge groups of formal proofs ⋮ Some Results on the Length of Proofs ⋮ A generalization of the second incompleteness theorem and some exceptions to it ⋮ Cycling in proofs and feasibility ⋮ Diophantine induction ⋮ The Complexity of Propositional Proofs ⋮ The sorites paradox and fuzzy logic ⋮ Non-standard finite fields over \(I\Delta_0+\Omega_1\) ⋮ Multifunction algebras and the provability of \(PH\downarrow\) ⋮ Turning cycles into spirals ⋮ Bounded arithmetic, proof complexity and two papers of Parikh ⋮ Unnamed Item ⋮ Formal frameworks for approximate reasoning ⋮ Hereditarily-finite sets, data bases and polynomial-time computability ⋮ Implicit computation complexity in higher-order programming languages

Cites Work