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