scientific article; zbMATH DE number 227056

Publication date: 6 July 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

consistency model theory provability bounded arithmetic interpretability incompleteness self-reference recursion theory conservativity indicators fragments of arithmetic definable cuts reflexive theories combinatorics in fragments foundations of arithmetic of natural numbers partial truth definitions witnessing functions

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)

Related Items

Fragments of Heyting arithmetic ⋮ Relative Truth Definability of Axiomatic Truth Theories ⋮ Reverse Mathematics: The Playground of Logic ⋮ Truth definitions without exponentiation and the Σ₁ collection scheme ⋮ A MATHEMATICAL COMMITMENT WITHOUT COMPUTATIONAL STRENGTH ⋮ Burgess’PVis Robinson’sQ ⋮ Reduction games, provability and compactness ⋮ A Fortuitous Year with Leon Henkin ⋮ Unnamed Item ⋮ Restricted polynomial induction versus parameter free ordinary induction ⋮ EXISTENTIALLY CLOSED MODELS IN THE FRAMEWORK OF ARITHMETIC ⋮ A finite model-theoretical proof of a property of bounded query classes within PH ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ CONSISTENCY AND THE THEORY OF TRUTH ⋮ Restricted polynomial induction versus ordinary induction ⋮ HOW MUCH PROPOSITIONAL LOGIC SUFFICES FOR ROSSER’S ESSENTIAL UNDECIDABILITY THEOREM? ⋮ Extension and interpretability ⋮ Hard provability logics ⋮ Local collection and end-extensions of models of compositional truth ⋮ The absorption law. Or: how to Kreisel a Hilbert-Bernays-Löb ⋮ Maximum Schemes in Arithmetic ⋮ A Note on Relative Efficiency of Axiom Systems ⋮ TRUTH AND SPEED-UP ⋮ An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle ⋮ A small reflection principle for bounded arithmetic ⋮ Petr Hájek: A Scientific Biography ⋮ NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Logical Closure Properties of Propositional Proof Systems ⋮ TWO NEW SERIES OF PRINCIPLES IN THE INTERPRETABILITY LOGIC OF ALL REASONABLE ARITHMETICAL THEORIES ⋮ TRUTH AND FEASIBLE REDUCIBILITY ⋮ ANOTHER LOOK AT THE SECOND INCOMPLETENESS THEOREM ⋮ Unnamed Item ⋮ Monomial ideals and independence of ⋮ Fermat's last theorem and Catalan's conjecture in weak exponential arithmetics ⋮ Relatively Recursively Enumerable Versus Relatively Σ₁ in Models of Peano Arithmetic ⋮ The small‐is‐very‐small principle ⋮ Pell Equations and Weak Regularity Principles ⋮ On the finite axiomatizability of ⋮ PREDICATIVITY THROUGH TRANSFINITE REFLECTION ⋮ ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM ⋮ INCOMPLETENESS VIA PARADOX AND COMPLETENESS ⋮ On End‐Extensions of Models of ¬exp ⋮ Undecidability in diagonalizable algebras ⋮ Lean induction principles for tableaux ⋮ On quasitautologies ⋮ A few more dissimilarities between second-order arithmetic and set theory ⋮ Provability logic: models within models in Peano arithmetic ⋮ END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS ⋮ Reflection calculus and conservativity spectra ⋮ On Overspill Principles and Axiom Schemes for Bounded Formulas ⋮ A NOTE ON PREDICATIVE ORDINAL ANALYSIS I: ITERATED COMPREHENSION AND TRANSFINITE INDUCTION ⋮ ON A QUESTION OF KRAJEWSKI’S ⋮ More on Systems of Truth and Predicative Comprehension ⋮ Weak Arithmetics and Kripke Models ⋮ Truth definition for $\Delta _ 0$ formulas and PSPACE computations ⋮ Proof Theoretic Analysis by Iterated Reflection ⋮ On the strength of Ramsey's theorem for pairs ⋮ MUTUAL INTERPRETABILITY OF ROBINSON ARITHMETIC AND ADJUNCTIVE SET THEORY WITH EXTENSIONALITY ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Where pigeonhole principles meet Koenig lemmas ⋮ A theory for Log-Space and NLIN versus co-NLIN ⋮ Parallel strategies ⋮ Weak forms of the Regularity Principle in the presence of \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\bf {\mathsf {I}{\mathrm{E}}_1}$\end{document} ⋮ On the strength of Ramsey's theorem without Σ₁‐induction ⋮ ARITHMETICAL INTERPRETATIONS AND KRIPKE FRAMES OF PREDICATE MODAL LOGIC OF PROVABILITY ⋮ SOME (NON)TAUTOLOGIES OF ŁUKASIEWICZ AND PRODUCT LOGIC ⋮ Extracting Algorithms from Intuitionistic Proofs ⋮ A Model-Theoretic Property of Sharply Bounded Formulae, with some Applications ⋮ SELF-REFERENCE IN ARITHMETIC II ⋮ Fragment of Nonstandard Analysis with a Finitary Consistency Proof ⋮ Transfinite Progressions: A Second Look at Completeness ⋮ Bounded Scott Set Saturation ⋮ PROVABILITY LOGICS RELATIVE TO A FIXED EXTENSION OF PEANO ARITHMETIC ⋮ Formalizing non-standard arguments in second-order arithmetic ⋮ Arithmetic on semigroups ⋮ Theories of arithmetics in finite models ⋮ REFERENCE IN ARITHMETIC ⋮ Envelopes, indicators and conservativeness ⋮ Concrete Mathematical Incompleteness: Basic Emulation Theory ⋮ The Interpretation Existence Lemma ⋮ Extensions of the Finitist Point of View ⋮ Interpreting Weak König’s Lemma using the Arithmetized Completeness Theorem ⋮ Unnamed Item ⋮ A note on parameter free Π₁ -induction and restricted exponentiation ⋮ Approximate counting by hashing in bounded arithmetic ⋮ Saturation and Σ₂-transfer for ERNA ⋮ FINDING THE LIMIT OF INCOMPLETENESS I ⋮ A Buchholz derivation system for the ordinal analysis of KP + Π₃-reflection ⋮ The weak pigeonhole principle for function classes inS12 ⋮ Reverse mathematics and infinite traceable graphs ⋮ Nonstandard models that are definable in models of Peano Arithmetic ⋮ Other Proofs of Old Results ⋮ Classifying the Provably Total Functions of PA ⋮ THE EXPRESSIVE POWER OF TRUTH ⋮ MÜNCHHAUSEN PROVABILITY ⋮ European Summer Meeting of the Association for Symbolic Logic, Uppsala 1991 ⋮ HIERARCHICAL INCOMPLETENESS RESULTS FOR ARITHMETICALLY DEFINABLE EXTENSIONS OF FRAGMENTS OF ARITHMETIC ⋮ Weihrauch Complexity in Computable Analysis ⋮ Linear extensions of partial orders and reverse mathematics ⋮ Groundwork for weak analysis ⋮ On Guaspari's problem about partially conservative sentences ⋮ Reflection algebras and conservation results for theories of iterated truth ⋮ Fundamental notions of analysis in subsystems of second-order arithmetic ⋮ Well-behaved principles alternative to bounded induction ⋮ Arithmetical definability and computational complexity ⋮ The equivalence of theories that characterize ALogTime ⋮ Modeling sorites reasoning with adaptive fuzzy logic ⋮ On efficiency of notations for natural numbers ⋮ Circuit principles and weak pigeonhole variants ⋮ $\Delta_ 0$-complexity of the relation $y= \prod_{i\leq n} F(i)$ ⋮ The proof-theoretic strength of Ramsey's theorem for pairs and two colors ⋮ Separations of first and second order theories in bounded arithmetic ⋮ On arithmetic in the Cantor-Łukasiewicz fuzzy set theory ⋮ Induction rules, reflection principles, and provably recursive functions ⋮ Iterated multiplication in $VTC^0$ ⋮ Friedman-reflexivity ⋮ Partial collapses of the $\Sigma _1$ complexity hierarchy in models for fragments of bounded arithmetic ⋮ Preservation theorems for bounded formulas ⋮ Effectively inseparable Boolean algebras in lattices of sentences ⋮ Unifying the model theory of first-order and second-order arithmetic via $\mathrm{WKL}_0^\ast$ ⋮ An algebraic treatment of quantifier-free systems of arithmetic ⋮ Graph properties checkable in linear time in the number of vertices ⋮ The incompleteness theorems after 70 years ⋮ End extensions of models of linearly bounded arithmetic ⋮ Transfinite induction within Peano arithmetic ⋮ Slow reflection ⋮ On predicate provability logics and binumerations of fragments of Peano arithmetic ⋮ On the strength of Ramsey's theorem for trees ⋮ Positive provability logic for uniform reflection principles ⋮ Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs ⋮ Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms ⋮ The omega-rule interpretation of transfinite provability logic ⋮ Transductions in arithmetic ⋮ On $\mathsf{Q}$ ⋮ The strength of sharply bounded induction requires MSP ⋮ Bootstrapping. I ⋮ The logical strength of compositional principles ⋮ On the jumps of the degrees below a recursively enumerable degree ⋮ End extensions of models of fragments of $\mathrm{PA}$ ⋮ Tanaka's theorem revisited ⋮ Weak theories of concatenation and arithmetic ⋮ Interpretability degrees of finitely axiomatized sequential theories ⋮ The strength of extensionality. II: Weak weak set theories without infinity ⋮ Fixed points of self-embeddings of models of arithmetic ⋮ Introduction to clarithmetic. I ⋮ Parameter free induction and provably total computable functions ⋮ Algebraic combinatorics in bounded induction ⋮ First-order concatenation theory with bounded quantifiers ⋮ Theories with self-application and computational complexity. ⋮ Skolem functions of arithmetical sentences. ⋮ On axiom schemes for $T$-provably $\Delta_1$ formulas ⋮ Local induction and provably total computable functions ⋮ Categorical characterizations of the natural numbers require primitive recursion ⋮ Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 5--11, 2017 ⋮ Dickson's lemma and weak Ramsey theory ⋮ Mirroring theorems in free logic ⋮ The self-embedding theorem of $\text{WKL}_ 0$ and a non-standard method ⋮ Construction of models of bounded arithmetic by restricted reduced powers ⋮ On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data ⋮ Deflationary truth and the ontology of expressions ⋮ Epistemic entrenchment and arithmetical hierarchy ⋮ Notes on the computational aspects of Kripke's theory of truth ⋮ Proof lengths for instances of the Paris-Harrington principle ⋮ On partial disjunction properties of theories containing Peano arithmetic ⋮ The scope of Gödel's first incompleteness theorem ⋮ Ekeland's variational principle in weak and strong systems of arithmetic ⋮ Theories of initial segments of standard models of arithmetics and their complete extensions ⋮ Faith \& falsity ⋮ Implicit definability of subfields ⋮ Consistency statements and iterations of computable functions in $\mathrm{I}\Sigma_1$ and PRA ⋮ Triangular norm based predicate fuzzy logics ⋮ The predicative Frege hierarchy ⋮ Algorithmic randomness, reverse mathematics, and the dominated convergence theorem ⋮ Independence results for variants of sharply bounded induction ⋮ R.e. Prime powers and total rigidity ⋮ On Brouwer's continuity principle ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ Interpreting the compositional truth predicate in models of arithmetic ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Deflationism beyond arithmetic ⋮ Induction rules in bounded arithmetic ⋮ Truth, disjunction, and induction ⋮ Infinitary action logic with exponentiation ⋮ Tarski on ``essentially richer metalanguages ⋮ Intrinsic reasoning about functional programs. II: Unipolar induction and primitive-recursion ⋮ The closed fragment of the interpretability logic of PRA with a constant for I$\Sigma^1$ ⋮ On the limit existence principles in elementary arithmetic and $\varSigma_{n}^{0}$-consequences of theories ⋮ Bounded arithmetic, proof complexity and two papers of Parikh ⋮ Unprovability results for clause set cycles ⋮ Some conservation results on weak König's lemma ⋮ A model-theoretic characterization of the weak pigeonhole principle ⋮ A new proof of Ajtai's completeness theorem for nonstandard finite structures ⋮ Rosser provability and the second incompleteness theorem ⋮ Notations for exponentiation. ⋮ Nonerasing, counting, and majority over the linear time hierarchy ⋮ Ordinal notations and well-orderings in bounded arithmetic ⋮ Saturated models of universal theories ⋮ On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology ⋮ On inclusions between quantified provability logics ⋮ A note on typed truth and consistency assertions ⋮ The two halves of disjunctive correctness ⋮ SELF-REFERENCE UPFRONT: A STUDY OF SELF-REFERENTIAL GÖDEL NUMBERINGS ⋮ NONCLASSICAL TRUTH WITH CLASSICAL STRENGTH. A PROOF-THEORETIC ANALYSIS OF COMPOSITIONAL TRUTH OVER HYPE ⋮ On feasible numbers ⋮ EXTENDED FRAMES AND SEPARATIONS OF LOGICAL PRINCIPLES ⋮ A CLASSICAL MODAL THEORY OF LAWLESS SEQUENCES ⋮ MODEL THEORY AND PROOF THEORY OF THE GLOBAL REFLECTION PRINCIPLE ⋮ Models of Bounded Arithmetic Theories and Some Related Complexity Questions ⋮ Semi-honest subrecursive degrees and the collection rule in arithmetic ⋮ Compositional truth with propositional tautologies and quantifier-free correctness ⋮ AXIOMATIZATIONS OF PEANO ARITHMETIC: A TRUTH-THEORETIC VIEW ⋮ AN ESCAPE FROM VARDANYAN’S THEOREM ⋮ TWO-SORTED FREGE ARITHMETIC IS NOT CONSERVATIVE ⋮ On the complexity of learning programs ⋮ Solutions to the knower paradox in the light of Haack's criteria ⋮ Revisiting the conservativity of fixpoints over intuitionistic arithmetic ⋮ Notes on polynomially bounded arithmetic ⋮ A new proof of the weak pigeonhole principle ⋮ AXIOMATIC TRUTH, SYNTAX AND METATHEORETIC REASONING ⋮ UNIVERSAL ROSSER PREDICATES ⋮ MARGINALIA ON A THEOREM OF WOODIN ⋮ Approximate counting in bounded arithmetic ⋮ A note on Σ₁-maximal models ⋮ Elementary patterns of resemblance ⋮ Predicative logic and formal arithmetic ⋮ A model of $\widehat{R}^2_3$ inside a subexponential time resource ⋮ Rules and arithmetics ⋮ On end extensions of models of subsystems of Peano arithmetic ⋮ The prime number theorem is PRA-provable ⋮ The canonical Ramsey theorem and computability theory ⋮ The Complexity of Propositional Proofs ⋮ Some variations of the Hardy hierarchy ⋮ On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories ⋮ Counting as integration in feasible analysis ⋮ MINIMAL TRUTH AND INTERPRETABILITY ⋮ A NOTE ON DERIVABILITY CONDITIONS