Results for 'arithmetical complexity'

961 found
Order:
  1.  32
    Arithmetical complexity of fuzzy predicate logics — A survey II.Petr Hájek - 2010 - Annals of Pure and Applied Logic 161 (2):212-219.
    Results on arithmetical complexity of important sets of formulas of several fuzzy predicate logics are surveyed and some new results are proven.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  2.  28
    (1 other version)Arithmetic complexity of the predicate logics of certain complete arithmetic theories.Valery Plisko - 2001 - Annals of Pure and Applied Logic 113 (1-3):243-259.
    It is proved in this paper that the predicate logic of each complete constructive arithmetic theory T having the existential property is Π1T-complete. In this connection, the techniques of a uniform partial truth definition for intuitionistic arithmetic theories is used. The main theorem is applied to the characterization of the predicate logic corresponding to certain variant of the notion of realizable predicate formula. Namely, it is shown that the set of irrefutable predicate formulas is recursively isomorphic to the complement of (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  3.  14
    Parametric Presburger arithmetic: complexity of counting and quantifier elimination.Tristram Bogart, John Goodrick, Danny Nguyen & Kevin Woods - 2019 - Mathematical Logic Quarterly 65 (2):237-250.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  4.  26
    Individual Differences in Math Ability Determine Neurocognitive Processing of Arithmetic Complexity: A Combined fNIRS-EEG Study.Christina Artemenko, Mojtaba Soltanlou, Silke M. Bieck, Ann-Christine Ehlis, Thomas Dresler & Hans-Christoph Nuerk - 2019 - Frontiers in Human Neuroscience 13.
  5. The complexity of classification problems for models of arithmetic.Samuel Coskey & Roman Kossak - 2010 - Bulletin of Symbolic Logic 16 (3):345-358.
    We observe that the classification problem for countable models of arithmetic is Borel complete. On the other hand, the classification problems for finitely generated models of arithmetic and for recursively saturated models of arithmetic are Borel; we investigate the precise complexity of each of these. Finally, we show that the classification problem for pairs of recursively saturated models and for automorphisms of a fixed recursively saturated model are Borel complete.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  38
    Bounded arithmetic, propositional logic, and complexity theory.Jan Krajicek - 1995 - New York, NY, USA: Cambridge University Press.
    This book presents an up-to-date, unified treatment of research in bounded arithmetic and complexity of propositional logic, with emphasis on independence proofs and lower bound proofs. The author discusses the deep connections between logic and complexity theory and lists a number of intriguing open problems. An introduction to the basics of logic and complexity theory is followed by discussion of important results in propositional proof systems and systems of bounded arithmetic. More advanced topics are then treated, including (...)
    Direct download  
     
    Export citation  
     
    Bookmark   22 citations  
  7. Kolmogorov complexity and characteristic constants of formal theories of arithmetic.Shingo Ibuka, Masato Kikuchi & Hirotaka Kikyo - 2011 - Mathematical Logic Quarterly 57 (5):470-473.
     
    Export citation  
     
    Bookmark  
  8.  48
    Complex analysis in subsystems of second order arithmetic.Keita Yokoyama - 2007 - Archive for Mathematical Logic 46 (1):15-35.
    This research is motivated by the program of Reverse Mathematics. We investigate basic part of complex analysis within some weak subsystems of second order arithmetic, in order to determine what kind of set existence axioms are needed to prove theorems of basic analysis. We are especially concerned with Cauchy’s integral theorem. We show that a weak version of Cauchy’s integral theorem is proved in RCAo. Using this, we can prove that holomorphic functions are analytic in RCAo. On the other hand, (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  9.  32
    S. N. Artemov. Arithmetically complete modal theories. Six papers in logic, American Mathematical Society translations, ser. 2 vol. 135, American Mathematical Society, Providence1987, pp. 39–54. , vol. 14 , pp. 115–133.) - S. N. Artemov. On modal logics axiomatizing provability. Mathematics of the USSR—Izvestiya, vol. 27 no. 3 , pp. 401–429. , pp. 1123–1154.) - S. N. Artemov. Nonarithmeticity of truth predicate logics of provability. Soviet mathematics—Doklady, vol. 32 , pp. 403–405. , pp. 270–271.) - V. A. Vardanyan. Arithmetic complexity of predicate logics of provability and their fragments. Soviet mathematics—Doklady, vol. 33 no. 3 , pp. 569–572. , pp. 11–14.) - S. N. Artemov. Numerically correct provability logics. Soviet mathematics—Doklady, vol. 34 , pp. 384–387. , pp. 1289–1292.). [REVIEW]Vann McGee - 1991 - Journal of Symbolic Logic 56 (1):329-332.
  10.  50
    Implicational complexity in intuitionistic arithmetic.Daniel Leivant - 1981 - Journal of Symbolic Logic 46 (2):240-248.
  11.  78
    Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem.Neil Thapen - 2011 - Archive for Mathematical Logic 50 (7):665-680.
    We give a new characterization of the strict Σjb\forall {\Sigma^b_j} sentences provable using Σkb{\Sigma^b_k} induction, for 1 ≤ j ≤ k. As a small application we show that, in a certain sense, Buss’s witnessing theorem for strict Σkb{\Sigma^b_k} formulas already holds over the relatively weak theory PV. We exhibit a combinatorial principle with the property that a lower bound for it in constant-depth Frege would imply that the narrow CNFs with short depth j Frege refutations form a strict hierarchy with (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  12.  29
    Kolmogorov complexity and characteristic constants of formal theories of arithmetic.Shingo Ibuka, Makoto Kikuchi & Hirotaka Kikyo - 2011 - Mathematical Logic Quarterly 57 (5):470-473.
    We investigate two constants cT and rT, introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that cT does not represent the complexity of T and found that for two theories S and T, one can always find a universal Turing machine such that equation image. We prove the following are equivalent: equation image for some universal Turing machine, equation image for some (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  13.  33
    Models of Bounded Arithmetic Theories and Some Related Complexity Questions.Abolfazl Alam & Morteza Moniri - 2022 - Bulletin of the Section of Logic 51 (2):163-176.
    In this paper, we study bounded versions of some model-theoretic notions and results. We apply these results to the context of models of bounded arithmetic theories as well as some related complexity questions. As an example, we show that if the theory S21(PV)\rm S_2 ^1(PV) has bounded model companion then NP=coNP\rm NP=coNP. We also study bounded versions of some other related notions such as Stone topology.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  85
    (1 other version)Bounded Arithmetic, Cryptography and Complexity.Samuel R. Buss - 1997 - Theoria 63 (3):147-167.
  15.  29
    Bounded arithmetic, proof complexity and two papers of Parikh.Samuel R. Buss - 1999 - Annals of Pure and Applied Logic 96 (1-3):43-55.
  16.  47
    Spatial complexity of character-based writing systems and arithmetic in primary school: a longitudinal study.Maja Rodic, Tatiana Tikhomirova, Tatiana Kolienko, Sergey Malykh, Olga Bogdanova, Dina Y. Zueva, Elena I. Gynku, Sirui Wan, Xinlin Zhou & Yulia Kovas - 2015 - Frontiers in Psychology 6.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  24
    Undecidable complexity statements in -arithmetic.Ron Sigal - 1989 - Journal of Symbolic Logic 54 (2):415-427.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  18.  23
    The Structural Complexity of Models of Arithmetic.Antonio Montalbán & Dino Rossegger - 2024 - Journal of Symbolic Logic 89 (4):1703-1719.
    We calculate the possible Scott ranks of countable models of Peano arithmetic. We show that no non-standard model can have Scott rank less than $\omega $ and that non-standard models of true arithmetic must have Scott rank greater than $\omega $. Other than that there are no restrictions. By giving a reduction via $\Delta ^{\mathrm {in}}_{1}$ bi-interpretability from the class of linear orderings to the canonical structural $\omega $ -jump of models of an arbitrary completion T of $\mathrm {PA}$ we (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19. On the complexity of models of arithmetic.Kenneth McAloon - 1982 - Journal of Symbolic Logic 47 (2):403-415.
    Let P 0 be the subsystem of Peano arithmetic obtained by restricting induction to bounded quantifier formulas. Let M be a countable, nonstandard model of P 0 whose domain we suppose to be the standard integers. Let T be a recursively enumerable extension of Peano arithmetic all of whose existential consequences are satisfied in the standard model. Then there is an initial segment M ' of M which is a model of T such that the complete diagram of M ' (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  20.  18
    (1 other version)Proof complexity and feasible arithmetics, DIMACS workshop, April 21–24, 1996, edited by Paul W. Beame and Samuel R. Buss, Series in discrete mathematics and theoretical computer science, vol. 39, American Mathematical Society, Providence1998, xii + 320 pp. [REVIEW]Alexander A. Razborov - 1999 - Journal of Symbolic Logic 64 (4):1823-1825.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  21.  47
    On the complexity of arithmetical interpretations of modal formulae.Lev D. Beklemishev - 1993 - Archive for Mathematical Logic 32 (3):229-238.
  22.  55
    Arithmetic, proof theory, and computational complexity, edited by Peter Clote and Krajíček Jan, Oxford logic guides, no. 23, Clarendon Press, Oxford University Press, Oxford and New York1993, xiii + 428 pp. [REVIEW]Fernando Ferreira - 1995 - Journal of Symbolic Logic 60 (3):1014-1017.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  23.  76
    Arithmetical definability over finite structures.Troy Lee - 2003 - Mathematical Logic Quarterly 49 (4):385.
    Arithmetical definability has been extensively studied over the natural numbers. In this paper, we take up the study of arithmetical definability over finite structures, motivated by the correspondence between uniform AC0 and FO. We prove finite analogs of three classic results in arithmetical definability, namely that < and TIMES can first-order define PLUS, that < and DIVIDES can first-order define TIMES, and that < and COPRIME can first-order define TIMES. The first result sharpens the equivalence FO =FO (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  24.  43
    Partial collapses of the complexity hierarchy in models for fragments of bounded arithmetic.Zofia Adamowicz & Leszek Aleksander Kołodziejczyk - 2007 - Annals of Pure and Applied Logic 145 (1):91-95.
    For any n, we construct a model of in which each formula is equivalent to an formula.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  25.  46
    Fragments of Arithmetic and true sentences.Andrés Cordón-Franco, Alejandro Fernández-Margarit & F. Félix Lara-Martín - 2005 - Mathematical Logic Quarterly 51 (3):313-328.
    By a theorem of R. Kaye, J. Paris and C. Dimitracopoulos, the class of the Πn+1-sentences true in the standard model is the only consistent Πn+1-theory which extends the scheme of induction for parameter free Πn+1-formulas. Motivated by this result, we present a systematic study of extensions of bounded quantifier complexity of fragments of first-order Peano Arithmetic. Here, we improve that result and show that this property describes a general phenomenon valid for parameter free schemes. As a consequence, we (...)
    Direct download  
     
    Export citation  
     
    Bookmark   6 citations  
  26.  83
    Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
    We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ₂—theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ₁—theory of multiplication and order is decidable in finite models as well (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  27.  45
    Bounded arithmetic for NC, ALogTIME, L and NL.P. Clote & G. Takeuti - 1992 - Annals of Pure and Applied Logic 56 (1-3):73-117.
    We define theories of bounded arithmetic, whose definable functions and relations are exactly those in certain complexity classes. Based on a recursion-theoretic characterization of NC in Clote , the first-order theory TNC, whose principal axiom scheme is a form of short induction on notation for nondeterministic polynomial-time computable relations, has the property that those functions having nondeterministic polynomial-time graph Θ such that TNC x y Θ are exactly the functions in NC, computable on a parallel random-access machine in polylogarithmic (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   14 citations  
  28.  29
    Presburger arithmetic, rational generating functions, and quasi-polynomials.Kevin Woods - 2015 - Journal of Symbolic Logic 80 (2):433-449.
    Presburger arithmetic is the first-order theory of the natural numbers with addition. We characterize sets that can be defined by a Presburger formula as exactly the sets whose characteristic functions can be represented by rational generating functions; a geometric characterization of such sets is also given. In addition, ifp= are a subset of the free variables in a Presburger formula, we can define a counting functiong to be the number of solutions to the formula, for a givenp. We show that (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  29.  77
    Fuzzy logic and arithmetical hierarchy III.Petr Hájek - 2001 - Studia Logica 68 (1):129-142.
    Fuzzy logic is understood as a logic with a comparative and truth-functional notion of truth. Arithmetical complexity of sets of tautologies and satisfiable sentences as well of sets of provable formulas of the most important systems of fuzzy predicate logic is determined or at least estimated.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  30.  63
    Fuzzy logic and arithmetical hierarchy, II.Petr Hájek - 1997 - Studia Logica 58 (1):129-141.
    A very simple many-valued predicate calculus is presented; a completeness theorem is proved and the arithmetical complexity of some notions concerning provability is determined.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  31.  23
    Ordinal arithmetic based on Skolem hulling.Gunnar Wilken - 2007 - Annals of Pure and Applied Logic 145 (2):130-161.
    Taking up ordinal notations derived from Skolem hull operators familiar in the field of infinitary proof theory we develop a toolkit of ordinal arithmetic that generally applies whenever ordinal structures are analyzed whose combinatorial complexity does not exceed the strength of the system of set theory. The original purpose of doing so was inspired by the analysis of ordinal structures based on elementarity invented by T.J. Carlson, see [T.J. Carlson, Elementary patterns of resemblance, Annals of Pure and Applied Logic (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  32.  38
    Arithmetizing Uniform NC.Bill Allen - 1991 - Annals of Pure and Applied Logic 53 (1):1-50.
    Allen, B., Arithmetizing Uniform NC, Annals of Pure and Applied Logic 53 1–50. We give a characterization of the complexity class Uniform NC as an algebra of functions on the natural numbers which is the closure of several basic functions under composition and a schema of recursion. We then define a fragment of bounded arithmetic, and, using our characterization of Uniform NC, show that this fragment is capable of proving the totality of all of the functions in Uniform NC. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  33. Purity in Arithmetic: some Formal and Informal Issues.Andrew Arana - 2014 - In Godehard Link, Formalism and Beyond: On the Nature of Mathematical Discourse. Boston: De Gruyter. pp. 315-336.
    Over the years many mathematicians have voiced a preference for proofs that stay “close” to the statements being proved, avoiding “foreign”, “extraneous”, or “remote” considerations. Such proofs have come to be known as “pure”. Purity issues have arisen repeatedly in the practice of arithmetic; a famous instance is the question of complex-analytic considerations in the proof of the prime number theorem. This article surveys several such issues, and discusses ways in which logical considerations shed light on these issues.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  34.  68
    Krajíček Jan. Bounded arithmetic, propositional logic, and complexity theory. Encyclopedia of mathematics and its applications, vol. 60. Cambridge University Press, Cambridge, New York, and Oakleigh, Victoria, 1995, xiv + 343 pp. [REVIEW]P. Clote - 1999 - Journal of Symbolic Logic 64 (3):1357-1362.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  35.  91
    Presburger arithmetic with unary predicates is Π11 complete.Joseph Y. Halpern - 1991 - Journal of Symbolic Logic 56 (2):637 - 642.
    We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is Π 1 1 complete. Adding one unary predicate is enough to get Π 1 1 hardness, while adding more predicates (of any arity) does not make the complexity any worse.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  36.  35
    Logic, Automata, and Computational Complexity: The Works Of Stephen A. Cook. Edited by Bruce M. Kapron, ACM Books, vol. 43. Association for Computing Machinery, New York, xxvi + 398 pp.—therein: - Michelle Waitzman. Stephen Cook: Complexity’s Humble Hero, pp. 3–28. - Bruce M. Kapron and Stephen A. Cook, ACM Interview of Stephen A. Cook by Bruce M. Kapron, pp. 29–44. - Stephen A. Cook, Overview of Computational Complexity, pp. 47–70. - Christos H. Papadimitriou, Cook’s NP-Completeness Paper and the Dawn of the New Theory, pp. 73–82. - Jan Krajíček, The Cook–Reckhow Definition, pp. 83–94. - Sam Buss, Polynomially Verifiable Arithmetic, pp. 95–106. - Paul Beame and Pierre McKenzie, Towards a Complexity Theory of Parallel Computation, pp. 107–126. - Nicholas Pippenger, Computation with Limited Space, pp. 127–140. - Stephen A. Cook, The Complexity of Theorem-Proving Procedures, pp. 143–152. - Stephen A. Cook, _Characterizations of Pushdown Machines in Terms of Time-Bound. [REVIEW]Pavel Pudlák - 2023 - Bulletin of Symbolic Logic 29 (4):657-660.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  37. The Relationship of Arithmetic As Two Twin Peano Arithmetic(s) and Set Theory: A New Glance From the Theory of Information.Vasil Penchev - 2020 - Metaphilosophy eJournal (Elseviers: SSRN) 12 (10):1-33.
    The paper introduces and utilizes a few new concepts: “nonstandard Peano arithmetic”, “complementary Peano arithmetic”, “Hilbert arithmetic”. They identify the foundations of both mathematics and physics demonstrating the equivalence of the newly introduced Hilbert arithmetic and the separable complex Hilbert space of quantum mechanics in turn underlying physics and all the world. That new both mathematical and physical ground can be recognized as information complemented and generalized by quantum information. A few fundamental mathematical problems of the present such as Fermat’s (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  38.  23
    Elementary arithmetic.Geoffrey E. Ostrin & Stanley S. Wainer - 2005 - Annals of Pure and Applied Logic 133 (1):275-292.
    There is a very simple way in which the safe/normal variable discipline of Bellantoni–Cook recursion [S. Bellantoni, S. Cook, A new recursion theoretic characterization of the polytime functions, Computational Complexity 2 97–110] can be imposed on arithmetical theories like PA: quantify over safes and induct on normals. This weakens the theory severely, so that the provably recursive functions become more realistically computable . Earlier results of D. Leivant [Intrinsic theories and computational complexity, in: D. Leivant , Logic (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  39.  87
    Arithmetic based on the church numerals in illative combinatory logic.M. W. Bunder - 1988 - Studia Logica 47 (2):129 - 143.
    In the early thirties, Church developed predicate calculus within a system based on lambda calculus. Rosser and Kleene developed Arithmetic within this system, but using a Godelization technique showed the system to be inconsistent.Alternative systems to that of Church have been developed, but so far more complex definitions of the natural numbers have had to be used. The present paper based on a system of illative combinatory logic developed previously by the author, does allow the use of the Church numerals. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  40.  31
    Proof complexity.Jan Krajíček - 2019 - New York, NY: Cambridge University Press.
    Proof complexity is a rich subject drawing on methods from logic, combinatorics, algebra and computer science. This self-contained book presents the basic concepts, classical results, current state of the art and possible future directions in the field. It stresses a view of proof complexity as a whole entity rather than a collection of various topics held together loosely by a few notions, and it favors more generalizable statements. Lower bounds for lengths of proofs, often regarded as the key (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  41. To see or not to see: The visual component of complex mental arithmetic.Wendy Ann Deslauriers, Gene P. Ouellette, Martin Barnes & Jo-Anne LeFevre - 2008 - In B. C. Love, K. McRae & V. M. Sloutsky, Proceedings of the 30th Annual Conference of the Cognitive Science Society. Cognitive Science Society.
     
    Export citation  
     
    Bookmark  
  42.  54
    Husserl's Psychology of Arithmetic.Carlo Ierna - 2012 - Bulletin d'Analyse Phénoménologique 8:97-120.
    In 1913, in a draft for a new Preface for the second edition of the Logical Investigations, Edmund Husserl reveals to his readers that "The source of all my studies and the first source of my epistemological difficul­ties lies in my first works on the philosophy of arithmetic and mathematics in general", i.e. his Habilitationsschrift and the Philosophy of Arithmetic: "I carefully studied the consciousness constituting the amount, first the collec­tive consciousness (consciousness of quantity, of multiplicity) in its simplest and (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  43. Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
    We develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM) in PV₁ + dWPHP(PV).
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  44. Gentzen’s “cut rule” and quantum measurement in terms of Hilbert arithmetic. Metaphor and understanding modeled formally.Vasil Penchev - 2022 - Logic and Philosophy of Mathematics eJournal 14 (14):1-37.
    Hilbert arithmetic in a wide sense, including Hilbert arithmetic in a narrow sense consisting by two dual and anti-isometric Peano arithmetics, on the one hand, and the qubit Hilbert space (originating for the standard separable complex Hilbert space of quantum mechanics), on the other hand, allows for an arithmetic version of Gentzen’s cut elimination and quantum measurement to be described uniformy as two processes occurring accordingly in those two branches. A philosophical reflection also justifying that unity by quantum neo-Pythagoreanism links (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  45.  26
    On the ability to inhibit complex thoughts: A stop-signal study of arithmetic.Gordon D. Logan & Carol Y. Barber - 1985 - Bulletin of the Psychonomic Society 23 (4):371-373.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  46.  74
    A Revision-Theoretic Analysis of the Arithmetical Hierarchy.Gian Aldo Antonelli - 1994 - Notre Dame Journal of Formal Logic 35 (2):204-218.
    In this paper we apply the idea of Revision Rules, originally developed within the framework of the theory of truth and later extended to a general mode of definition, to the analysis of the arithmetical hierarchy. This is also intended as an example of how ideas and tools from philosophical logic can provide a different perspective on mathematically more “respectable” entities. Revision Rules were first introduced by A. Gupta and N. Belnap as tools in the theory of truth, and (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  47. Numbers and Arithmetic: Neither Hardwired Nor Out There.Rafael Núñez - 2009 - Biological Theory 4 (1):68-83.
    What is the nature of number systems and arithmetic that we use in science for quantification, analysis, and modeling? I argue that number concepts and arithmetic are neither hardwired in the brain, nor do they exist out there in the universe. Innate subitizing and early cognitive preconditions for number— which we share with many other species—cannot provide the foundations for the precision, richness, and range of number concepts and simple arithmetic, let alone that of more complex mathematical concepts. Numbers and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  48.  51
    Complexity of the -query Tautologies in the Presence of a Generic Oracle.Toshio Suzuki - 2000 - Notre Dame Journal of Formal Logic 41 (2):142-151.
    Extending techniques of Dowd and those of Poizat, we study computational complexity of in the case when is a generic oracle, where is a positive integer, and denotes the collection of all -query tautologies with respect to an oracle . We introduce the notion of ceiling-generic oracles, as a generalization of Dowd's notion of -generic oracles to arbitrary finitely testable arithmetical predicates. We study how existence of ceiling-generic oracles affects behavior of a generic oracle, by which we show (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  49. Whither relevant arithmetic?Harvey Friedman & Robert K. Meyer - 1992 - Journal of Symbolic Logic 57 (3):824-831.
    Based on the relevant logic R, the system R# was proposed as a relevant Peano arithmetic. R# has many nice properties: the most conspicuous theorems of classical Peano arithmetic PA are readily provable therein; it is readily and effectively shown to be nontrivial; it incorporates both intuitionist and classical proof methods. But it is shown here that R# is properly weaker than PA, in the sense that there is a strictly positive theorem QRF of PA which is unprovable in R#. (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   20 citations  
  50. The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
    Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   7 citations  
1 — 50 / 961