Anscombe holds that a proper account of intentional action must exhibit “a ‘form’ of description of events.” But what does that mean? To answer this question, I compare the method of Anscombe’s Intention with that of Frege’s Foundations of Arithmetic—another classic work of analytic philosophy that consciously opposes itself to psychological explanations. On the one hand, positively, I aim to identify and elucidate the kind of account of intentional action that Anscombe attempts to provide. On the other hand, negatively, (...) I hope to dispel the canard that Anscombe’s opposition to the causal theory of action is a product of “behaviorism.”. (shrink)

The first complete English translation of a groundbreaking work. An ambitious account of the relation of mathematics to logic. Includes a foreword by Crispin Wright, translators' Introduction, and an appendix on Frege's logic by Roy T. Cook. The German philosopher and mathematician Gottlob Frege (1848-1925) was the father of analytic philosophy and to all intents and purposes the inventor of modern logic. Basic Laws of Arithmetic, originally published in German in two volumes (1893, 1903), is Freges magnum opus. It (...) was to be the pinnacle of Freges lifes work. It represents the final stage of his logicist project the idea that arithmetic and analysis are reducible to logic and contains his mature philosophy of mathematics and logic. The aim of Basic Laws of Arithmetic is to demonstrate the logical nature of mathematical theorems by providing gapless proofs in Frege's formal system using only basic laws of logic, logical inference, and explicit definitions. The work contains a philosophical foreword, an introduction to Frege's logic, a derivation of arithmetic from this logic, a critique of contemporary approaches to the real numbers, and the beginnings of a logicist treatment of real analysis. As is well-known, a letter received from Bertrand Russell shortly before the publication of the second volume made Frege realise that his basic law V, governing the identity of value-ranges, leads into inconsistency. Frege discusses a revision to basic law V written in response to Russells letter in an afterword to volume II. The continuing importance of Basic Laws of Arithmetic lies not only in its bearing on issues in the foundations of mathematics and logic but in its model of philosophical inquiry. Frege's ability to locate the essential questions, his integration of logical and philosophical analysis, and his rigorous approach to criticism and argument in general are vividly in evidence in this, his most ambitious work. Philip Ebert and Marcus Rossberg present the first full English translation of both volumes of Freges major work preserving the original formalism and pagination. The edition contains a foreword by Crispin Wright and an extensive appendix providing an introduction to Frege's formal system by Roy T. Cook. Readership: Scholars and advanced students in philosophy of logic, philosophy of mathematics, and early analytic philosophy. (shrink)

This book develops arithmetic without the induction principle, working in theories that are interpretable in Raphael Robinson's theory Q. Certain inductive formulas, the bounded ones, are interpretable in Q. A mathematically strong, but logically very weak, predicative arithmetic is constructed. Originally published in 1986. The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These paperback editions preserve the original texts of these important books (...) while presenting them in durable paperback editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905. (shrink)

With the arrival of the nineteenth century, a process of change guided the treatment of three basic elements in the development of mathematics: rigour, the arithmetization and the clarification of the concept of function, categorised as the most important tool in the development of the mathematical analysis. In this paper we will show how several prominent mathematicians contributed greatly to the development of these basic elements that allowed the solid underpinning of mathematics and the consideration of mathematics as an axiomatic (...) way of thinking in which anyone can deduce valid conclusions from certain types of premises. This nineteenth century stage shares, possibly with the Heroic Age of Ancient Greece, the most revolutionary period in all history of mathematics. (shrink)

Symbolic arithmetic is fundamental to science, technology and economics, but its acquisition by children typically requires years of effort, instruction and drill1,2. When adults perform mental arithmetic, they activate nonsymbolic, approximate number representations3,4, and their performance suffers if this nonsymbolic system is impaired5. Nonsymbolic number representations also allow adults, children, and even infants to add or subtract pairs of dot arrays and to compare the resulting sum or difference to a third array, provided that only approximate accuracy is (...) required6–10. Here we report that young children, who have mastered verbal counting and are on the threshold of arithmetic instruction, can build on their nonsymbolic number system to perform symbolic addition and subtraction11–15. Children across a broad socio-economic spectrum solved symbolic problems involving approximate addition or subtraction of large numbers, both in a laboratory test and in a school setting. Aspects of symbolic arithmetic therefore lie within the reach of children who have learned no algorithms for manipulating numerical symbols. Our findings help to delimit the sources of children’s difficulties learning symbolic arithmetic, and they suggest ways to enhance children’s engagement with formal mathematics. We presented children with approximate symbolic arithmetic problems in a format that parallels previous tests of non-symbolic arithmetic in preschool children8,9. In the first experiment, five- to six-year-old children were given problems such as ‘‘If you had twenty-four stickers and I gave you twenty-seven more, would you have more or less than thirty-five stickers?’’. Children performed well above chance (65.0%, t1952.77, P 5 0.012) without resorting to guessing or comparison strategies that could serve as alternatives to arithmetic. Children who have been taught no symbolic arithmetic therefore have some ability to perform symbolic addition problems. The children’s performance nevertheless fell short of performance on non-symbolic arithmetic tasks using equivalent addition problems with numbers presented as arrays of dots and with the addition operation conveyed by successive motions of the dots into a box (71.3% correct, F1,345 4.26, P 5 0.047)8.. (shrink)

Philosophers of science since Nagel have been interested in the links between intertheoretic reduction and explanation, understanding and other forms of epistemic progress. Although intertheoretic reduction is widely agreed to occur in pure mathematics as well as empirical science, the relationship between reduction and explanation in the mathematical setting has rarely been investigated in a similarly serious way. This paper examines an important particular case: the reduction of arithmetic to set theory. I claim that the reduction is unexplanatory. In (...) defense of this claim, I offer evidence from mathematical practice, and I respond to contrary suggestions due to Steinhart, Maddy, Kitcher and Quine. I then show how, even if set-theoretic reductions are generally not explanatory, set theory can nevertheless serve as a legitimate foundation for mathematics. Finally, some implications of my thesis for philosophy of mathematics and philosophy of science are discussed. In particular, I suggest that some reductions in mathematics are probably explanatory, and I propose that differing standards of theory acceptance might account for the apparent lack of unexplanatory reductions in the empirical sciences. (shrink)

We argue that, under the usual assumptions for sufficiently strong arithmetical theories that are subject to Gödel’s First Incompleteness Theorem, one cannot, without impropriety, talk about *the* Gödel sentence of the theory. The reason is that, without violating the requirements of Gödel’s theorem, there could be a true sentence and a false one each of which is provably equivalent to its own unprovability in the theory if the theory is unsound.

We will introduce a partial ordering $\preceq_1$ on the class of ordinals which will serve as a foundation for an approach to ordinal notations for formal systems of set theory and second-order arithmetic. In this paper we use $\preceq_1$ to provide a new characterization of the ubiquitous ordinal $\epsilon _{0}$.

Orthodoxy holds that there is a determinate fact of the matter about every arithmetical claim. Little argument has been supplied in favour of orthodoxy, and work of Field, Warren and Waxman, and others suggests that the presumption in its favour is unjustified. This paper supports orthodoxy by establishing the determinacy of arithmetic in a well-motivated modal plural logic. Recasting this result in higher-order logic reveals that even the nominalist who thinks that there are only finitely many things should think (...) that there is some sense in which arithmetic is true and determinate. (shrink)

In arithmetic, if only because many of its methods and concepts originated in India, it has been the tradition to reason less strictly than in geometry, ...

In this paper we study the interpretations of a weak arithmetic, like Buss’s theory $\mathsf{S}^{1}_{2}$, in a given theory $U$. We call these interpretations the arithmetics of $U$. We develop the basics of the structure of the arithmetics of $U$. We study the provability logic of $U$ from the standpoint of the framework of the arithmetics of $U$. Finally, we provide a deeper study of the arithmetics of a finitely axiomatized sequential theory.

The paper explores the idea that some singular judgements about the natural numbers are immune to error through misidentification by pursuing a comparison between arithmetic judgements and first-person judgements. By doing so, the first part of the paper offers a conciliatory resolution of the Coliva-Pryor dispute about so-called “de re” and “which-object” misidentification. The second part of the paper draws some lessons about what it takes to explain immunity to error through misidentification. The lessons are: First, the so-called Simple (...) Account of which-object immunity to error through misidentification to the effect that a judgement is immune to this kind of error just in case its grounds do not feature any identification component fails. Secondly, wh-immunity can be explained by a Reference-Fixing Account to the effect that a judgement is immune to this kind of error just in case its grounds are constituted by the facts whereby the reference of the concept of the object which the judgement concerns is fixed. Thirdly, a suitable revision of the Simple Account explains the de re immunity of those arithmetic judgements which are not wh-immune. These three lessons point towards the general conclusion that there is no unifying explanation of de re and wh-immunity. (shrink)

Showing that the arithmetic mean number of offspring for a trait type often fails to be a predictive measure of fitness was a welcome correction to the philosophical literature on fitness. While the higher mathematical moments of a probability-weighted offspring distribution can influence fitness measurement in distinct ways, the geometric mean number of offspring is commonly singled out as the most appropriate measure. For it is well-suited to a compounding process and is sensitive to variance in offspring number. The (...) geometric mean thus proves to be a predictively efficacious measure of fitness in examples featuring discrete generations and within- or between-generation variance in offspring output. Unfortunately, this advance has subsequently led some to conclude that the arithmetic mean is never a good measure of fitness and that the geometric mean should accordingly be the default measure of fitness. We show not only that the arithmetic mean is a perfectly reasonable measure of fitness so long as one is clear about what it refers to, but also that it functions as a more general measure when properly interpreted. It must suffice as a measure of fitness in any case where the geometric mean has been effectively deployed as a measure. We conclude with a discussion about why the mathematical equivalence we highlight cannot be dismissed as merely of mathematical interest. (shrink)

We prove that for any recursively axiomatized consistent extension T of Peano Arithmetic, there exists a \ provability predicate of T whose provability logic is precisely the modal logic \. For this purpose, we introduce a new bimodal logic \, and prove the Kripke completeness theorem and the uniform arithmetical completeness theorem for \.

Proof-theoretic reflection principles are schemas which attempt to express the soundness of arithmetical theories within their own language, e.g., ${\mathtt{{Prov}_{\mathsf {PA}} \rightarrow \varphi }}$ can be understood to assert that any statement provable in Peano arithmetic is true. It has been repeatedly suggested that justification for such principles follows directly from acceptance of an arithmetical theory $\mathsf {T}$ or indirectly in virtue of their derivability in certain truth-theoretic extensions thereof. This paper challenges this consensus by exploring relationships between reflection (...) principles and principles of mathematical and transfinite induction as well as the status of the latter with respect to various foundational characterizations of number theory. (shrink)

An arithmetic theory of oppositions is devised by comparing expressions, Boolean bitstrings, and integers. This leads to a set of correspondences between three domains of investigation, namely: logic, geometry, and arithmetic. The structural properties of each area are investigated in turn, before justifying the procedure as a whole. Io finish, I show how this helps to improve the logical calculus of oppositions, through the consideration of corresponding operations between integers.

Many philosophers believe that a deflationist theory of truth must conservatively extend any base theory to which it is added. But when applied to arithmetic, it's argued, the imposition of a conservativeness requirement leads to a serious objection to deflationism: for the Gödel sentence for Peano Arithmetic is not a theorem of PA, but becomes one when PA is extended by adding plausible principles governing truth. This paper argues that no such objection succeeds. The issue turns on how (...) we understand the notion of logical consequence implicit in any conservativeness requirement, and whether we possess a categorical conception of the natural numbers. I offer a disjunctive response: if we possess a categorical conception of arithmetic, then deflationists have principled reason to accept a rich notion of logical consequence according to which the Gödel sentence follows from PA. But if we do not, then the reasons for requiring the derivation of the Gödel sentence lapse, and deflationists are free to accept a conservativeness requirement stated proof-theoretically. Either way, deflationism is in the clear. (shrink)

We prove that for each recursively axiomatized consistent extension T of Peano Arithmetic and \, there exists a \ numeration \\) of T such that the provability logic of the provability predicate \\) naturally constructed from \\) is exactly \ \rightarrow \Box p\). This settles Sacchetti’s problem affirmatively.

§ i. After deserting for a time the old Euclidean standards of rigour, mathematics is now returning to them, and even making efforts to go beyond them. ...

In this paper some of the history of the development of arithmetic in set theory is traced, particularly with reference to the problem of avoiding the assumption of an infinite set. Although the standard method of singling out a sequence of sets to be the natural numbers goes back to Zermelo, its development was more tortuous than is generally believed. We consider the development in the light of three desiderata for a solution and argue that they can probably not (...) all be satisfied simultaneously. (shrink)

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 to FO = (...) FO, answering a question raised by Barrington et al. about the Crane Beach Conjecture. Together with previous results on the Crane Beach Conjecture, our results imply that FO is strictly less expressive than FO = FO = FO. In more colorful language, one could say that, for parallel computation, multiplication is harder than addition. (shrink)

The purpose of this paper is to formulate first-order Peano arithmetic within the resources of relevant logic, and to demonstrate certain properties of the system thus formulated. Striking among these properties are the facts that it is trivial that relevant arithmetic is absolutely consistent, but classical first-order Peano arithmetic is straightforwardly contained in relevant arithmetic. Under, I shall show in particular that 0 = 1 is a non-theorem of relevant arithmetic; this, of course, is exactly (...) the formula whose unprovability was sought in the Hilbert program for proving arithmetic consistent. Under, I shall exhibit the requisite translation, drawing some Goedelian conclusions therefrom. Left open, however, is the critical problem whether Ackermann’s rule γ is admissible for theories of relevant arithmetic. The particular system of relevant Peano arithmetic featured in this paper shall be called R♯. Its logical base shall be the system R of relevant implication, taken in its first-order form RQ. Among other Peano arithmetics we shall consider here in particular the systems C♯, J♯, and RM3♯; these are based respectively on the classical logic C, the intuitionistic logic J, and the Sobocinski-Dunn semi-relevant logic RM3. And another feature of the paper will be the presentation of a system of natural deduction for R♯, along lines valid for first-order relevant theories in general. This formulation of R♯ makes it possible to construct relevantly valid arithmetical deductions in an easy and natural way; it is based on, but is in some respects more convenient than, the natural deduction formulations for relevant logics developed by Anderson and Belnap in Entailment. (shrink)

Is calculation possible without language? Or is the human ability for arithmetic dependent on the language faculty? To clarify the relation between language and arithmetic, we studied numerical cognition in speakers of Mundurukú, an Amazonian language with a very small lexicon of number words. Although the Mundurukú lack words for numbers beyond 5, they are able to compare and add large approximate numbers that are far beyond their naming range. However, they fail in exact arithmetic with numbers (...) larger than 4 or 5. Our results imply a distinction between a nonverbal system of number approximation and a language-based counting system for exact number and arithmetic. (shrink)

Published in honor of Sergio Galvan, this collection concentrates on the application of logical and mathematical methods for the study of central issues in formal philosophy. The volume is subdivided into four sections, dedicated to logic and philosophy of logic, philosophy of mathematics, philosophy of science, metaphysics and philosophy of religion. The contributions adress, from a logical point of view, some of the main topics in these areas. The first two sections include formal treatments of: truth and paradoxes; definitions by (...) abstraction; the status of abstract objects, such as mathematical objects and universal concepts; and the structure of explicit knowledge. The last two sections include papers on classical problems in philosophy of science, such as the status of subjective probability, the notion of verisimilitude, the notion of approximation, and the theory of mind and mental causation, and specific issues in metaphysics and philosophy of religion, such as the ontology of species, actions, and intelligible worlds, and the logic of religious belonging. (shrink)

The revival of the philosophy of mathematics in the 60s following its post-1931 slump left us with two conflicting positions on arithmetic’s ontological relationship to set theory. W.V. Quine’s view, presented in 'Word and Object' (1960), was that numbers are sets. The opposing view was advanced in another milestone of twentieth-century philosophy of mathematics, Paul Benacerraf’s 'What Numbers Could Not Be' (1965): one of the things numbers could not be, it explained, was sets; the other thing numbers could not (...) be, even more dramatically, was objects. Curiously, although Benacerraf’s article appeared in the heyday of Quine’s influence, it declined to engage the Quinean position squarely, even seemed to think it was not its business to do so. Despite that, in my experience, most philosophers believe that Benacerraf’s article put paid to the reductionist view that numbers are sets (though perhaps not the view that numbers are objects). My chapter will attempt to overturn this orthodoxy. (shrink)

In this paper we show how to interpret Robinson’s arithmetic Q and the theory R of Tarski, Mostowski, and Robinson as theories of cardinals in very weak theories of relations over a domain.

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. (...) Lastly, in the spirit of Buss, we show that any function which is definable by a ∑b1-formula in our theory is a function which is in Uniform NC. (shrink)

A real number x is computable iff it is the limit of an effectively converging computable sequence of rational numbers, and x is left computable iff it is the supremum of a computable sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to computable sequences of rational numbers we introduce a non-collapsing hierarchy {Σn, Πn, Δn : n ∈ ℕ} of real numbers. We characterize the classes Σ2, Π2 and Δ2 in various ways and give (...) several interesting examples. (shrink)

We show how second order logic incompleteness follows from incompleteness of arithmetic, as proved by Gödel.

We show that each of the five basic theories of second order arithmetic that play a central role in reverse mathematics has a natural counterpart in the language of nonstandard arithmetic. In the earlier paper [3] we introduced saturation principles in nonstandard arithmetic which are equivalent in strength to strong choice axioms in second order arithmetic. This paper studies principles which are equivalent in strength to weaker theories in second order arithmetic.

SEMANTIC ARITHMETIC: A PREFACE John Corcoran Abstract Number theory, or pure arithmetic, concerns the natural numbers themselves, not the notation used, and in particular not the numerals. String theory, or pure syntax, concems the numerals as strings of «uninterpreted» characters without regard to the numbe~s they may be used to denote. Number theory is purely arithmetic; string theory is purely syntactical... in so far as the universe of discourse alone is considered. Semantic arithmetic is a broad (...) subject which begins when numerals are mentioned (not just used) and mentioned as names of numbers (not just as syntactic objects). Semantic arithmetic leads to many fascinating and surprising algorithms and decision procedures; it reveals in a vivid way the experiential import of mathematical propositions and the predictive power of mathematical knowledge; it provides an interesting perspective for philosophical, historical, and pedagogical studies of the growth of scientific knowledge and of the role metalinguistic discourse in scientific thought. (shrink)

This paper is part of a larger project about the relation between mathematics and transcendental philosophy that I think is the most interesting feature of Kant’s philosophy of mathematics. This general view is that in the course of arguing independently of mathematical considerations for conditions of experience, Kant also establishes conditions of the possibility of mathematics. My broad aim in this paper is to clarify the sense in which this is an accurate description of Kant’s view of the relation between (...) mathematics and transcendental philosophy. (shrink)

Number theory abounds with conjectures asserting that every natural number has some arithmetic property. An example is Goldbach’s Conjecture, which states that every even number greater than 2 is the sum of two primes. Enumerative inductive evidence for such conjectures usually consists of small cases. In the absence of supporting reasons, mathematicians mistrust such evidence for arithmetical generalisations, more so than most other forms of non-deductive evidence. Some philosophers have also expressed scepticism about the value of enumerative inductive evidence (...) in arithmetic. But why? Perhaps the best argument is that known instances of an arithmetical conjecture are almost always small: they appear at the start of the natural number sequence. Evidence of this kind consequently suffers from size bias. My essay shows that this sort of scepticism comes in many different flavours, raises some challenges for them all, and explores their respective responses. (shrink)

This is the only work to provide a histori­cal account of Kant’s theory of arith­metic, examining in detail the theories of both his predecessors and his successors.

The incompleteness of formal systems for arithmetic has been a recognized fact of mathematics. The term “incompleteness” suggests that the formal system in question fails to offer a deduction which it ought to. This chapter focuses on the status of a formal system, Peano Arithmetic, and explores a viewpoint on which Peano Arithmetic occupies an intrinsic, conceptually well-defined region of arithmetical truth. The idea is that it consists of those truths which can be perceived directly from the (...) purely arithmetical content of a categorical conceptual analysis of the notion of natural number. The chapter explores its conceptual stability in light of the apparently destabilizing effect, through extensibility, of the phenomenon of incompleteness. It also offers heuristic and conceptual support for the viewpoint that Peano Arithmetic is the strongest natural first-order system for arithmetic, and that there is a sense in which it is complete with respect to purely arithmetical truth. (shrink)

This is a republication of R.K. Meyer's "Relevant Arithmetic", which originally appeared in the Bulletin of the Section of Logic 5. It sets out the problems that Meyer was to work on for the next decade concerning his system, R#.

Solovay proved the arithmetical completeness theorem for the system GL of propositional modal logic of provability. Montagna proved that this completeness does not hold for a natural extension QGL of GL to the predicate modal logic. Let Th(QGL) be the set of all theorems of QGL, Fr(QGL) be the set of all formulas valid in all transitive and conversely well-founded Kripke frames, and let PL(T) be the set of all predicate modal formulas provable in Tfor any arithmetical interpretation. Montagna’s results (...) are described as Th(QGL) ⊊ (Fr(QGL), PL(PA) ⊈ Fr(QGL), and Th(QGL) ⊊ PL(PA). In this paper, we prove the following three theorems: (1) Fr(QGL) ⊈ PL(T) for any Σ1-sound recursively enumerable extension T of I Σ1, (2) PL(T) ⊈ Fr(QGL) for any recursively enumerable S1755020312000275_inline1 A -theory T extending I Σ1, and (3) Th(QGL) ⊊ Fr(QGL) ∩ PL(T) for any recursively enumerable S1755020312000275_inline2 A -theory T extending I Σ2. To prove these theorems, we use iterated consistency assertions and nonstandard models of arithmetic, and we improve Artemov’s lemma which is used to prove Vardanyan’s theorem on the Π0 2-completeness of PL(T). (shrink)

There are two well‐known ways of doing arithmetic with ordinal numbers: the “ordinary” addition, multiplication, and exponentiation, which are defined by transfinite iteration; and the “natural” (or “Hessenberg”) addition and multiplication (denoted ⊕ and ⊗), each satisfying its own set of algebraic laws. In 1909, Jacobsthal considered a third, intermediate way of multiplying ordinals (denoted × ), defined by transfinite iteration of natural addition, as well as the notion of exponentiation defined by transfinite iteration of his multiplication, which we (...) denote. (Jacobsthal's multiplication was later rediscovered by Conway.) Jacobsthal showed these operations too obeyed algebraic laws. In this paper, we pick up where Jacobsthal left off by considering the notion of exponentiation obtained by transfinitely iterating natural multiplication instead; we shall denote this. We show that and that ; note the use of Jacobsthal's multiplication in the latter. We also demonstrate the impossibility of defining a “natural exponentiation” satisfying reasonable algebraic laws. (shrink)

We prove that the finite-model version of arithmetic with the divisibility relation is undecidable . Additionally we prove FM-representability theorem for this class of finite models. This means that a relation R on natural numbers can be described correctly on each input on almost all finite divisibility models if and only if R is of degree ≤0′. We obtain these results by interpreting addition and multiplication on initial segments of finite models with divisibility only.

ABSTRACT Two models of the Aristotelian syllogistic in arithmetic of natural numbers are built as realizations of an old Leibniz idea. In the interpretation, called Scholastic, terms are replaced by integers greater than 1, and s.Ap is translated as “s is a divisor of p”, sIp as “g.c.d. > 1”. In the interpretation, called Leibnizian, terms are replaced by proper divisors of a special “Universe number” u < 1, and sAp is translated as “s is divisible by p”, sIp (...) as ‘l.c.m. < u”. Both interpretations are proved to be adequate to the Aristotelian syllogistic. They are extended to syllogistic including term negation and term conjunction as well. (shrink)

Presented here is a new result concerning the computational power of so-called SADn computers, a class of Turing-machine-based computers that can perform some non-Turing computable feats by utilising the geometry of a particular kind of general relativistic spacetime. It is shown that SADn can decide n-quantifier arithmetic but not (n+1)-quantifier arithmetic, a result that reveals how neatly the SADn family maps into the Kleene arithmetical hierarchy. Introduction Axiomatising computers The power of SAD computers Remarks regarding the concept of (...) computability. (shrink)

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 (...) parallel time with a polynomial number of processors.0 We then define three theories of weak second-order arithmetic which respectively characterize relations in the classes of alternating logarithmic time, logspace and nondeterministic logspace. (shrink)

Øystein Linnebo has recently shown that the existence of successors cannot be proven in predicative Frege arithmetic, using Frege's definitions of arithmetical notions. By contrast, it is shown here that the existence of successor can be proven in ramified predicative Frege arithmetic.

The paper presents an outline of the general theory of countable arithmetically saturated models of PA and some of its applications. We consider questions concerning the automorphism group of a countable recursively saturated model of PA. We prove new results concerning fixed point sets, open subgroups, and the cofinality of the automorphism group. We also prove that the standard system of a countable arithmetically saturated model of PA is determined by the lattice of its elementary substructures.