Schur’s Lemma says that the endomorphism ring of a simple left R-module is a division ring. It plays a fundamental role to prove classical ring structure theorems like the Jacobson Density Theorem and the Wedderburn–Artin Theorem. We first define the endomorphism ring of simple left R-modules by their Π10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi ^{0}_{1}$$\end{document} subsets and show that Schur’s Lemma is provable in RCA0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm RCA_{0}$$\end{document}. A ring (...) R is left primitive if there is a faithful simple left R-module and left semisimple if the left regular module RR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_{R}R$$\end{document} is semisimple. The Jacobson Density Theorem and the Wedderburn-Artin Theorem characterize left primitive ring and left semisimple ring, respectively. We then study such theorems from the standpoint of reverse mathematics. (shrink)

The parameter-free part $$\textbf{PA}_2^*$$ of $$\textbf{PA}_2$$, second order Peano arithmetic, is considered. We make use of a product/iterated Sacks forcing to define an $$\omega $$ -model of $$\textbf{PA}_2^*+ \textbf{CA}(\Sigma ^1_2)$$, in which an example of the full Comprehension schema $$\textbf{CA}$$ fails. Using Cohen’s forcing, we also define an $$\omega $$ -model of $$\textbf{PA}_2^*$$, in which not every set has its complement, and hence the full $$\textbf{CA}$$ fails in a rather elementary way.

In this paper the numerical strength of fragments of arithmetical comprehension, choice and general uniform boundedness is studied systematically. These principles are investigated relative to base systems Tnω in all finite types which are suited to formalize substantial parts of analysis but nevertheless have provably recursive functions of low growth. We reduce the use of instances of these principles in Tnω-proofs of a large class of formulas to the use of instances of certain arithmetical principles thereby determining (...) faithfully the arithmetical content of the former. This is achieved using the method of elimination of Skolem functions for monotone formulas which was introduced by the author in a previous paper.As corollaries we obtain new conservation results for fragments of analysis over fragments of arithmetic which strengthen known purely first-order conservation results.We also characterize the provably recursive functions of type 2 of the extensions of Tnω based on these fragments of arithmetical comprehension, choice and uniform boundedness. (shrink)

First order reasoning about hyperintegers can prove things about sets of integers. In the author’s paper Nonstandard Arithmetic and Reverse Mathematics, Bulletin of Symbolic Logic 12 100–125, it was shown that each of the “big five” theories in reverse mathematics, including the base theory, has a natural nonstandard counterpart. But the counterpart of has a defect: it does not imply the Standard Part Principle that a set exists if and only if it is coded by a hyperinteger. In this paper (...) we find another nonstandard counterpart, *RCA0′, that does imply the Standard Part Principle. (shrink)

First order reasoning about hyperintegers can prove things about sets of integers. In the author’s paper Nonstandard Arithmetic and Reverse Mathematics, Bulletin of Symbolic Logic 12 100–125, it was shown that each of the “big five” theories in reverse mathematics, including the base theory , has a natural nonstandard counterpart. But the counterpart of has a defect: it does not imply the Standard Part Principle that a set exists if and only if it is coded by a hyperinteger. In this (...) paper we find another nonstandard counterpart, *RCA0′, that does imply the Standard Part Principle. (shrink)

Research on dyscalculia in neurodegenerative diseases is still scarce, despite high impact on patients’ independence and activities of daily living function. Most studies address Alzheimer’s Disease; however, patients with Parkinson’s Disease also have a higher risk for cognitive impairment while the relation to arithmetic deficits in financial contexts has rarely been studied. Therefore, the current exploratory study investigates deficits in two simple arithmetic tasks in financial contexts administered within the Clinical Dementia Rating in a sample of 100 PD patients. Patients (...) were classified as cognitively normal or mildly impaired according to Level I consensus criteria, and assessed using a comprehensive neuropsychological test battery, neurological motor examination, and sociodemographic and clinical questionnaires. In total, 18% showed arithmetic deficits: they were predominately female, had longer disease duration, more impaired global cognition, but minor signs of depression compared to PD patients without arithmetic deficits. When correcting for clinical and sociodemographic confounders, greater impairments in attention and visuo-spatial/constructional domains predicted occurrence of arithmetic deficits. The type of deficit did not seem to be arbitrary but seemed to involve impaired place × value processing frequently. Our results argue for the importance of further systematic investigations of arithmetic deficits in PD with sensitive tests to confirm the results of our exploratory study that a specific subgroup of PD patients present themselves with dyscalculia. (shrink)

Inferential expressivism makes a systematic distinction between inferences that are valid qua preserving commitment and inferences that are valid qua preserving evidence. I argue that the characteristic inferences licensed by the principle of comprehension, from "x is P" to "x is in the extension of P" and vice versa, fail to preserve evidence, but do preserve commitment. Taking this observation into account allows one to phrase inference rules for unrestricted comprehension without running into Russell’s paradox. In the resulting (...) logic, one can derive full second-order arithmetic. Thus, it is possible to derive classical arithmetic in a consistent logic with unrestricted comprehension. (shrink)

(Goodsell, Journal of Philosophical Logic, 51(1), 127-150 2022) establishes the noncontingency of sentences of first-order arithmetic, in a plausible higher-order modal logic. Here, the same result is derived using significantly weaker assumptions. Most notably, the assumption of rigid comprehension—that every property is coextensive with a modally rigid one—is weakened to the assumption that the Boolean algebra of properties under necessitation is countably complete. The results are generalized to extensions of the language of arithmetic, and are applied to answer a (...) question posed by Bacon and Dorr (2024). (shrink)

We give a new elementary proof of the comparison theorem relating $\sum^1_{n + 1}-\mathrm{AC}\uparrow$ and $\Pi^1_n -\mathrm{CA}\uparrow$ ; the proof does not use Skolem theories. By the same method we prove: a) $\sum^1_{n + 1}-\mathrm{DC} \uparrow \equiv (\Pi^1_n -CA)_{ , for suitable classes of sentences; b) $\sum^1_{n+1}-DC \uparrow$ proves the consistency of (Π 1 n -CA) ω k, for finite k, and hence is stronger than $\sum^1_{n+1}-AC \uparrow$ . a) and b) answer a question of Feferman and Sieg.

In this article, the relationship between second-order comprehension and unrestricted mereological fusion (over atoms) is clarified. An extension PAF of Peano arithmetic with a new binary mereological notion of “fusion”, and a scheme of unrestricted fusion, is introduced. It is shown that PAF interprets full second-order arithmetic, Z_2.

This paper presents new constructions of models of Hume's Principle and Basic Law V with restricted amounts of comprehension. The techniques used in these constructions are drawn from hyperarithmetic theory and the model theory of fields, and formalizing these techniques within various subsystems of second-order Peano arithmetic allows one to put upper and lower bounds on the interpretability strength of these theories and hence to compare these theories to the canonical subsystems of second-order arithmetic. The main results of this (...) paper are: (i) there is a consistent extension of the hyperarithmetic fragment of Basic Law V which interprets the hyperarithmetic fragment of second-order Peano arithmetic, and (ii) the hyperarithmetic fragment of Hume's Principle does not interpret the hyperarithmetic fragment of second-order Peano arithmetic, so that in this specific sense there is no predicative version of Frege's Theorem. (shrink)

Real-world information is imperfect and is usually described in natural language (NL). Moreover, this information is often partially reliable and a degree of reliability is also expressed in NL. In view of this, the concept of a Z-number is a more adequate concept for the description of real-world information. The main critical problem that naturally arises in processing Z-numbers-based information is the computation with Z-numbers. Nowadays, there is no arithmetic of Z-numbers suggested in existing literature. This book is the first (...) to present a comprehensive and self-contained theory of Z-arithmetic and its applications. Many of the concepts and techniques described in the book, with carefully worked-out examples, are original and appear in the literature for the first time. The book will be helpful for professionals, academics, managers and graduate students in fuzzy logic, decision sciences, artificial intelligence, mathematical economics, and computational economics. (shrink)

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 polynomial simulations and (...) conservativity results, various witnessing theorems, the translation of bounded formulas (and their proofs) into propositional ones, the method of random partial restrictions and its applications, direct independence proofs, complete systems of partial relations, lower bounds to the size of constant-depth propositional proofs, the method of Boolean valuations, the issue of hard tautologies and optimal proof systems, combinatorics and complexity theory within bounded arithmetic, and relations to complexity issues of predicate calculus. Students and researchers in mathematical logic and complexity theory will find this comprehensive treatment an excellent guide to this expanding interdisciplinary area. (shrink)

Axiomatic set theory with full comprehension is known to be consistent in Łukasiewicz fuzzy predicate logic. But we cannot assume the existence of natural numbers satisfying a simple schema of induction; this extension is shown to be inconsistent.

We show that the categoricity of second-order Peano axioms can be proved from the comprehension axioms. We also show that the categoricity of second-order Zermelo–Fraenkel axioms, given the order type of the ordinals, can be proved from the comprehension axioms. Thus these well-known categoricity results do not need the so-called “full” second-order logic, the Henkin second-order logic is enough. We also address the question of “consistency” of these axiom systems in the second-order sense, that is, the question of (...) existence of models for these systems. In both cases we give a consistency proof, but naturally we have to assume more than the mere comprehension axioms. (shrink)

Yu, X., Riesz representation theorem, Borel measures and subsystems of second-order arithmetic, Annals of Pure and Applied Logic 59 65-78. Formalized concept of finite Borel measures is developed in the language of second-order arithmetic. Formalization of the Riesz representation theorem is proved to be equivalent to arithmetical comprehension. Codes of Borel sets of complete separable metric spaces are defined and proved to be meaningful in the subsystem ATR0. Arithmetical transfinite recursion is enough to prove the measurability of (...) Borel sets for any finite Borel measure on a compact complete separable metric space. (shrink)

We introduce a notion of syntactical truth predicate (s.t.p.) for the second order arithmetic PA 2 . An s.t.p. is a set T of closed formulas such that: (i) T(t = u) if and only if the closed first order terms t and u are convertible, i.e., have the same value in the standard interpretation (ii) T(A → B) if and only if (T(A) $\Longrightarrow$ T(B)) (iii) T(∀ x A) if and only if (T(A[x ← t]) for any closed first (...) order term t) (iv) T(∀ X A) if and only if (T(A[X ←▵]) for any closed set definition $\triangle = \{x \mid D(x)\}$ ). S.t.p.'s can be seen as a counterpart to Tarski's notion of (model-theoretical) validity and have main model properties. In particular, their existence is equivalent to the existence of an ω-model of PA 2 , this fact being provable in PA 2 with arithmetical comprehension only. (shrink)

The basic human ability to treat quantitative information can be divided into two parts. With proto-arithmetical ability, based on the core cognitive abilities for subitizing and estimation, numerosities can be treated in a limited and/or approximate manner. With arithmetical ability, numerosities are processed (counted, operated on) systematically in a discrete, linear, and unbounded manner. In this paper, I study the theory of enculturation as presented by Menary (2015) as a possible explanation of how we make the move from (...) the proto-arithmetical ability to arithmetic proper. I argue that enculturation based on neural reuse provides a theoretically sound and fruitful framework for explaining this development. However, I show that a comprehensive explanation must be based on valid theoretical distinctions and involve several stages in the development of arithmetical knowledge. I provide an account that meets these challenges and thus leads to a better understanding of the subject of enculturation. (shrink)

We study elementary second order extensions of the theoryID 1 of non-iterated inductive definitions and the theoryPA Ω of Peano arithmetic with ordinals. We determine the exact proof-theoretic strength of those extensions and their natural subsystems, and we relate them to subsystems of analysis with arithmetic comprehension plusΠ 1 1 comprehension and bar induction without set parameters.

We show that a theory of autonomous iterated Ramseyness based on second order arithmetic (SOA) is proof-theoretically equivalent to ${\Pi^1_2}$ -comprehension. The property of Ramsey is defined as follows. Let X be a set of real numbers, i.e. a set of infinite sets of natural numbers. We call a set H of natural numbers homogeneous for X if either all infinite subsets of H are in X or all infinite subsets of H are not in X. X has the (...) property of Ramsey if there exists a set which is homogeneous for X. The property of Ramsey is considered in reverse mathematics to compare the strength of subsystems of SOA. To characterize the system of ${\Pi^1_2}$ -comprehension in terms of Ramseyness we introduce a system of autonomous iterated Ramseyness, called R-calculus. We augment the language of SOA with additional set terms (called R-terms) ${R\vec{x}X\phi(\vec{x},X)}$ for each first order formula ${\phi(\vec{x},X)}$ (where φ may contain further R-terms). The R-calculus is a system which comprises comprehension for all first order formulas (which may contain R-terms or other set parameters) and defining axioms for the R-terms which claim that for each ${\vec{x}}$ , we can remove finitely many elements from the set ${R\vec{x}X\phi(\vec{x},X)}$ such that the remaining set is homogeneous for ${\{{X}{\phi(\vec{x},X)\}}}$ . We show that the R-calculus proves the same ${\Pi^1_1}$ -sentences as the system of ${\Pi^1_2}$ -comprehension. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:684 JOURNAL OF THE HISTORY OF PHILOSOPHY 33:4 OCTOBER 1995 "Private I.anguage" and the pivotal paper in the Stoic section, "The Conjunctive Model," bring out a third feature of Brunschwig's method. Many of his essays take their start from a small text or a relatively local problem, one which does not primafacie bear significantly on large philosophical issues. Yet in a rigorously conceived philosophical system, the whole is often (...) reflected in the details; where possible Brunschwig elicits the larger significance. He shows how Epicurean physics provides a normative model for Epicurean psychology without falling into the reductionist error; the Epicurean does extrapolate from physical theory to human experience, but in so doing he does not forget that human beings are not just atomic; they are atomic compounds. Reductionism does not follow from materialism, for Epicurus or for us. Similarly in "The Conjunctive Model" Brunschwig connects, in a manner which is speculative but nevertheless compelling, a important Stoic thesis in logic (that a conjunction is false if even one of its conjuncts is false) with a comprehensive understanding of Stoic ethics and physics, thereby giving definite content to the Stoic claims about the coherence of their system. The other Stoic papers focus on ontology and logic, showing how central these are to Stoicism. The titles speak for themselves: "Remarks on the Stoic Theory of the Proper Noun," "Remarks on the Classification of Simple Propositions in Hellenistic Logics," "The Stoic Theory of the Supreme Genus and Platonic Ontology," and "Did Diogenes of Babylon Invent the Ontological Argument?" (the answer is 'no'). One essay ("On a Stoic Way of Not Being") disguises by its title a crucial contribution to the philosophy of mind. The papers on Scepticism include "The 6oov ~t~ x~ ~.6"f.t 9 Formula in Sextus Empiricus," a definitive treatment of a verbal formula crucial to understanding the precise character of his sceptical stance, and "Sextus Empiricus on the xptxfl0tov," the only paper in the volume which has previously appeared in English. The papers "Once Again on Eusebius on Aristocles on Timon on Pyrrho" and "The Title of Timon's lndalmoi: From Odysseus to Pyrrho" deal with early Pyrrhonism, for which the evidence is so thin that no firm conclusions can be drawn. Yet even here Brunschwig's care and skill are exemplary, and his argument that we should look to Timon rather than Pyrrho as the creator of Pyrrhonism is as convincing as anything could be in this area. This is a collection which specialists must read and even nonspecialists will value for its elegant combination of rigor, intellectual honesty, and philosophical insight. BRAD INWOOD University of Toronto Michael J. B. Allen. Nuptial Arithmetic: Marsilio Ficino's Commentary on the Fatal Number in Book VIII of Plato's Republic. Berkeley: University of California Press, 1994. PP. x + 291. Cloth, $5o.oo. Marsilio Ficino was born in 1433 and died in 1499 at the age of 66. He would have been pleased if he could have known that. For three years before in 1496 (or slightly earlier) he declared in his Commentary on the Fatal Number that 6 was the perfect number and BOOK R~VIEWS 685 that contemplations of the sextile relations of the planets might lead to the return of the golden age of Saturn "some day," This is the fifth volume of Michael Allen's seminal studies of Ficino's Platonic commentaries; if his notable additional articles on further Ficino commentaries were assembled, as they sometime must be, it would be his sixth--not that he takes the same pleasure in numbers as his subject Ficino did. But 6 is the key to Ficino's unraveling of Plato's "fatal number" in Republic 546. To end the suspense, Ficino's solution, aided by Aristotle, Politics V. 1316, is (4 + 3 + 5)3or (6 x 2)3 or 1728. But 1728 what? There is no clue. The book is itself a valuable contribution to the history of philosophy. Allen reviews the history of this topos up to Brumbaugh and Rees. Although Ficino's entry was known and discussed in the sixteenth century, it has been lost from sight since, and Alien restores it importantly to... (shrink)

In the late XVII century in England has establishes the school of “political arithmetic”, which goal consisted in the analysis of social phenomena on the basis of quantitative indicators. Its main representatives became William Petty, John Graunt and Charles Davenant (1656-1714). The latter left a mark in the history of England as a philosopher, politician and publicist, who made a significant contribution to the development and implementation of the methods of “political arithmetic”. The object of this research is the views (...) of the English thinker, reflected in his pamphlets and treatises of the 1690’s. The subject is the Davenant’s views on the principles and tasks of “political arithmetic” in the context of his political theory. Special attention is given to correlation between Davenant’s views on the development of “political arithmetic’ and his concept of public administration. The scientific novelty lies in the comprehensive examination of the political and economic views of Charles Davenant within the framework of his attitude on the method of “political arithmetic”. The author delivers a thesis on the importance of the political and epistemological context, which formed Davenant’s views on the quantitative indicators. Grasp of quantitative data Davenant correlated directly with the practice of administration. According to the philosopher, a public official having the capacity for “evaluation” and proper interpretation of data could avoid many mistakes in decision-making and reliance on “bad” advices. The thinker suggested that possession of quantitative data and their competent interpretation could increase the efficiency of administration. (shrink)

Understanding arithmetic word problems involves a complex interaction of text comprehension and mathematical processes. This article presents a computer simulation designed to capture the working memory demands required in “bottomup” comprehension of arithmetic word problems. The simulation's sentence‐level parser and text integration component reflect the importance of processing the problem from its original natural language presentation. Children's probability of solution was analyzed in exploratory regression analyses as a function of the simulation's sentence‐level and text integration processes. Working memory (...) variables measuring the combined effects of concepts to remember and text integration inferences account for a significant proportion of variance in children's solution probabilities across the first four grade levels (K‐3). Consistent with previous results from others, which highlighted the significance of small changes in problem wording, the simulation offers a process‐oriented perspective as to why natural language presentation constrains the comprehension of mathematical relationships. (shrink)

We initiate the reverse mathematics of general topology. We show that a certain metrization theorem is equivalent to Π2 1 comprehension. An MF space is defined to be a topological space of the form MF(P) with the topology generated by $\lbrace N_p \mid p \in P \rbrace$ . Here P is a poset, MF(P) is the set of maximal filters on P, and $N_p = \lbrace F \in MF(P) \mid p \in F \rbrace$ . If the poset P is (...) countable, the space MF(P) is said to be countably based. The class of countably based MF spaces can be defined and discussed within the subsystem ACA0 of second order arithmetic. One can prove within ACA0 that every complete separable metric space is homeomorphic to a countably based MF space which is regular. We show that the converse statement, "every countably based MF space which is regular is homeomorphic to a complete separable metric space," is equivalent to Π2 1-CA0. The equivalence is proved in the weaker system Π1 1-CA0. This is the first example of a theorem of core mathematics which is provable in second order arithmetic and implies Π2 1 comprehension. (shrink)

Lyubetsky and Kanovei showed in [8] that there is a second-order arithmetic model of $\mathrm {Z}_2^{-p}$, (comprehension for all second-order formulas without parameters), in which $\Sigma ^1_2$ - $\mathrm {CA}$ (comprehension for all $\Sigma ^1_2$ -formulas with parameters) holds, but $\Sigma ^1_4$ - $\mathrm {CA}$ fails. They asked whether there is a model of $\mathrm {Z}_2^{-p}+\Sigma ^1_2$ - $\mathrm {CA}$ with the optimal failure of $\Sigma ^1_3$ - $\mathrm {CA}$. We answer the question positively by constructing such a (...) model in a forcing extension by a tree iteration of Jensen’s forcing. Let $\mathrm {Coll}^{-p}$ be the parameter-free collection scheme for second-order formulas and let $\mathrm {AC}^{-p}$ be the parameter-free choice scheme. We show that there is a model of $\mathrm {Z}_2^{-p}+\mathrm { AC}^{-p}+\Sigma ^1_2$ - $\mathrm {CA}$ with a failure of $\Sigma ^1_4$ - $\mathrm {CA}$. We also show that there is a model of $\mathrm {Z}_2^{-p}+\mathrm {Coll}^{-p}+\Sigma ^1_2$ - $\mathrm {CA}$ with a failure of $\Sigma ^1_4$ - $\mathrm {CA}$ and a failure of $\mathrm {AC}^{-p}$, so that, in particular, the schemes $\mathrm {Coll}^{-p}$ and $\mathrm {AC}^{-p}$ are not equivalent over $\mathrm {Z}_2^{-p}$. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:176 Reviews c:\users\ken\documents\type3402\rj 3402 050 red.docx 2015-02-04 9:19 PM THE GRUNDGESETZE Nicholas Griffin Russell Research Centre / McMaster U. Hamilton, on, Canada l8s 4l6 [email protected] Gottlob Frege. Basic Laws of Arithmetic. Derived Using Concept-script. Volumes i and ii. Translated and edited by Philip A. Ebert and Marcus Rossberg with Crispin Wright. Oxford: Oxford U. P., 2013. Pp. xxxix + xxxii + 253 + xv + 285 + A–42 + (...) i–11. isbn 978-0-19-928174-9. £60; us$110. iven the steadily rising interest in Frege’s work since the 1950s, it is surprising that his Grundgesetze der Arithmetik, the work he thought would be the crowning achievement of his career, has not previously been fully translated into English. Other Frege works have long been available in English. The earlier Grundlagen der Arithmetik was nicely, if not always entirely accurately, translated by J. L. Austin and published in 1950.1 Translations of Frege’s other philosophical writings began to appear in influential editions about the same time,2 initially a small corpus that has been gradually added to over the years to include works from his Nachlass and letters from his correspondence.3 Somewhat later, the Begriffsschrift, Frege’s momentous first 1 The Foundations of Arithmetic (Oxford: Blackwell, 1950; 2nd edn. 1953). The later translation under the same title by Dale Jacquette (London: Longman, 2007) is much less satisfactory. 2 The first importance source for these was Peter Geach and Max Black’s Translations from the Philosophical Writing of Gottlob Frege (1952; 2nd edn. 1960; 3rd edn. 1980), though it included reprints of some much earlier translations. 3 The two most comprehensive English sources for the shorter writings are now Brian d= Reviews 177 c:\users\ken\documents\type3402\rj 3402 050 red.docx 2015-02-04 9:19 PM contribution to modern logic, the work which Quine 4 said had made logic a great subject, was translated in full despite the difficulties of Fregean notation.5 But through all this the Grundgesetze remained largely (though not entirely ) untranslated. The view seems, for a long time, to have been that Frege’s contributions to logic were to be found in the Begriffsschrift and his contributions to philosophy in the Grundlagen and a small number of seminal articles. The Grundgesetze, on the other hand, was widely thought not to have added much to these magni ficent achievements, but to have employed them in a project that was doomed by the discovery of Russell’s paradox; namely, the attempt to show that arithmetic could be rigorously derived from purely logical principles. In the bleak aftermath of Russell’s paradox it came to seem as if whatever was of value in the Grundgesetze had already been published elsewhere, while what was new in it was mistaken.6 That assessment of the book’s value, combined with the huge difficulties of typesetting Frege’s idiosyncratic two-dimensional notation, and the sheer scale of the work (even without the anticipated third volume, which was abandoned in the face of Russell’s paradox, it was, by far, Frege’s largest work) made it seem as though a translation of the whole Grundgesetze was not only a prohibitively large undertaking, but also one which was not really necessary. And so, through much of the twentieth century, the Grundgesetze vied with Principia Mathematica as the world’s bestknown but least-read philosophical book. But this understanding of the Grundgesetze’s importance could not withstand the development of neo-logicism, brought to prominence by Crispin Wright’s Frege’s Conception of Numbers as Objects.7 The key insight of neoMcGuinness, ed., Frege, Collected Papers on Mathematics, Logic, and Philosophy (1984); and Michael Beaney, ed., The Frege Reader (1997). 4 At least in early editions of Mathematical Logic. The remark was removed in later ones in deference to Boole. 5 By Stefan Bauer-Mengelberg in Jean van Heijenoort, ed., From Frege to Gödel (1967), pp. 5–82. 6 Not surprisingly the one part of the Grundgesetze which has appeared most frequently in translation is the “Nachwort” responding to Russell’s paradox which Frege added as the book was in press. Geach... (shrink)

We show that the fact that the first player wins every instance of Galvin’s “racing pawns” game is equivalent to arithmetic transfinite recursion. Along the way we analyze the satisfaction relation for infinitary formulas, of “internal” hyperarithmetic comprehension, and of the law of excluded middle for such formulas.

Problem-solving software that is not-necessarily infallible is central to AI. Such software whose correctness and incorrectness properties are deducible by agents is an issue at the foundations of AI. The Comprehensibility Theorem, which appeared in a journal for specialists in formal mathematical logic, might provide a limitation concerning this issue and might be applicable to any agents, regardless of whether the agents are artificial or natural. The present article, aimed at researchers interested in the foundations of AI, addresses many questions (...) related to that theorem, including differences between it and results of Gödel and Turing that have sometimes played key roles in Minds and Machines articles. This study also suggests that—if one is willing to assume a thesis due to Donald Knuth—the Comprehensibility Theorem is the first mathematical theorem implying the impossibility of any AI agent or natural agent—including a not-necessarily infallible human agent—satisfying a rigorous and deductive interpretation of the self-comprehensibility challenge. Some have pointed out the difficulty of self-comprehensibility, even according to presumably a less rigorous interpretation. This includes Socrates, who considered it to be among the most important of intellectual tasks. Self-comprehensibility in some form might be essential for a kind of self-reflection useful for self-improvement that might enable some agents to increase their success. We use the methods of applied mathematics, rather than philosophy, although some topics considered could be of interest to philosophers. (shrink)

Concepts of L1 space, integrable functions and integrals are formalized in weak subsystems of second order arithmetic. They are discussed especially in relation with the combinatorial principle WWKL (weak-weak König's lemma and arithmetical comprehension. Lebesgue dominated convergence theorem is proved to be equivalent to arithmetical comprehension. A weak version of Lebesgue monotone convergence theorem is proved to be equivalent to weak-weak König's lemma.

We prove that a nonstandard extension of arithmetic is effectively conservative over Peano arithmetic by using an internal version of a definable ultrapower. By the same method we show that a certain extension of the nonstandard theory with a saturation principle has the same proof-theoretic strength as second order arithmetic, where comprehension is restricted to arithmetical formulas.

In this paper we study the logical strength of the determinacy of infinite binary games in terms of second order arithmetic. We define new determinacy schemata inspired by the Wadge classes of Polish spaces and show the following equivalences over the system RCA0*, which consists of the axioms of discrete ordered semi‐rings with exponentiation, Δ10 comprehension and Π00 induction, and which is known as a weaker system than the popularbase theory RCA0: 1. Bisep(Δ10, Σ10)‐Det* ↔ WKL0, 2. Bisep(Δ10, Σ20)‐Det* (...) ↔ ATR0 + Σ11 induction, 3. Bisep(Σ10, Σ20)‐Det* ↔ Sep(Σ10, Σ20)‐Det* ↔ Π11‐CA0, 4. Bisep(Δ20, Σ20)‐Det* ↔ Π11‐TR0, where Det* stands for the determinacy of infinite games in the Cantor space (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

The first comprehensive intellectual biography of William Petty, the inventor of 'political arithmetic' and a key figure in the English colonization of Ireland, the institutionalization of experimental science, and early social science.

We locate winning strategies for various ${\mathrm{\Sigma }}_{3}^{0}$ -games in the L-hierarchy in order to prove the following: Theorem 1. KP+Σ₂-Comprehension $\vdash \exists \alpha L_{\alpha}\ models"\Sigma _{2}-{\bf KP}+\Sigma _{3}^{0}-\text{Determinacy}."$ Alternatively: ${\mathrm{\Pi }}_{3}^{1}\text{\hspace{0.17em}}-{\mathrm{C}\mathrm{A}}_{0}\phantom{\rule{0ex}{0ex}}$ "there is a β-model of ${\mathrm{\Delta }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0}\text{\hspace{0.17em}}\text{\hspace{0.17em}}+\text{\hspace{0.17 em}}{\mathrm{\Sigma }}_{3}^{0}$ -Determinacy." The implication is not reversible. (The antecedent here may be replaced with ${\mathrm{\Pi }}_{3}^{1}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left({\mathrm{\Pi }}_{3}^{1}\right)-{\mathrm{C}\mathrm{A}}_{0}:\text{\hspace{0.17em}}{\mathrm{\Pi }}_{3}^{1}$ instances of Comprehension with only ${\mathrm{\Pi }}_{3}^{1}$ -lightface definable parameters—or even weaker theories.) Theorem 2. KP +Δ₂-Comprehension +Σ₂-Replacement + ${\mathrm{\Sigma }}_{3}^{0}\phantom{\rule{0ex}{0ex}}$ (...) -Determinacy. (Here AQI is the assertion that every arithmetical quasi-inductive definition converges.) Alternatively: $\Delta _{3}^{1}{\rm CA}_{0}+{\rm AQI}\nvdash \Sigma _{3}^{0}$ -Determinacy. Hence the theories: ${\mathrm{\Pi }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0},\text{\hspace{0.17em}}{\mathrm{\Delta }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0}+\text{\hspace{0.17em}}{\mathrm{\Sigma }}_{3}^{0}-\mathrm{D}\mathrm{e}\mathrm{t}\phantom{\rule{0ex}{0ex}}$ -Det, ${\mathrm{\Delta }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0}+\mathrm{A}\mathrm{Q}\mathrm{I}$ , and ${\mathrm{\Delta }}_{3}^{1}-{\mathrm{C}\mathrm{A}}_{0}\phantom{\rule{0ex}{0ex}}$ are in strictly descending order of strength. (shrink)

By RCA 0 , we denote a subsystem of second order arithmetic based on Δ0 1 comprehension and Δ0 1 induction. We show within this system that the real number system R satisfies all the theorems (possibly with non-standard length) of the theory of real closed fields under an appropriate truth definition. This enables us to develop linear algebra and polynomial ring theory over real and complex numbers, so that we particularly obtain Hilbert’s Nullstellensatz in RCA 0.

Abstract.This paper is the second in a series of three culminating in an ordinal analysis of Π12-comprehension. Its objective is to present an ordinal analysis for the subsystem of second order arithmetic with Δ12-comprehension, bar induction and Π12-comprehension for formulae without set parameters. Couched in terms of Kripke-Platek set theory, KP, the latter system corresponds to KPi augmented by the assertion that there exists a stable ordinal, where KPi is KP with an additional axiom stating that every (...) set is contained in an admissible set. (shrink)

This paper addresses the structures and ), whereMis a nonstandard model of PA andωis the standard cut. It is known that ) is interpretable in. Our main technical result is that there is an reverse interpretation of in ) which is ‘local’ in the sense of Visser [11]. We also relate the model theory of to the study of transplendent models of PA [2].This yields a number of model theoretic results concerning theω-models and their standard systems SSy, including the following.•$\left (...) \prec \left$if and only if$M \prec K$and$\left} \right) \prec \left} \right)$.•$\left} \right) \prec \left} \right)$if and only if$\left \prec \left$for someω-saturatedM*.•$M{ \prec _{\rm{e}}}K$implies SSy = SSy, but cofinal extensions do not necessarily preserve standard system in this sense.• SSy=SSy if and only if ) satisfies the full comprehension scheme.• If SSy is uniformly defined by a single formula, then ) satisfies the full comprehension scheme; and there are modelsMfor which SSy is not uniformly defined in this sense. (shrink)

IΣ n andBΣ n are well known fragments of first-order arithmetic with induction and collection forΣ n formulas respectively;IΣ n 0 andBΣ n 0 are their second-order counterparts. RCA0 is the well known fragment of second-order arithmetic with recursive comprehension;WKL 0 isRCA 0 plus weak König's lemma. We first strengthen Harrington's conservation result by showing thatWKL 0 +BΣ n 0 is Π 1 1 -conservative overRCA 0 +BΣ n 0 . Then we develop some model theory inWKL 0 and (...) illustrate the use of formalized model theory by giving a relatively simple proof of the fact thatIΣ 1 provesBΣ n+1 to be Π n+2-conservative overIΣ n . Finally, we present a proof-theoretic proof of the stronger fact that theΠ n+2 conservation result is provable already inIΔ 0 + superexp. ThusIΣ n+1 proves 1-Con (BΣ n+1) andIΔ 0 +superexp proves Con (IΣ n )↔Con(BΣ n+1). (shrink)

This is a text for a one or two semester course on axiomatic set theory; the goal is to introduce and develop one system of set theory in a complete and thorough way, presupposing only the elusive "mathematical maturity" of the reader. There are nine chapters which begin with a development of propositional and predicate logic oriented toward set theory and develop the Zermelo-Fraenkel system in exceptional detail. The book starts slowly, the first 120 pages being devoted to logical preliminaries (...) and the introduction of axioms; it gathers speed, however, and the remaining chapters include treatment of the algebra of classes, relations and functions, order of various sorts and Zorn's lemma, real numbers and equivalence classes, the equipollence of sets, similarity as a relation of sets, the ordinal numbers and their arithmetic, the cardinal numbers and their arithmetic. These later chapters are extremely detailed and comprehensive, presenting a wealth of material. There are numerous exercises, many quite difficult, at the end of each chapter, along with a summary of that chapter's content. Because of the single-mindedness of the book, there is little reference to other systems of set theory, but this is not a drawback at all. The presentation is orthodox, but not dull; careful, but not generally pedantic or repetitive. This makes it a good text for self-study.—P. J. M. (shrink)

Frege's theorem says that second-order Peano arithmetic is interpretable in Hume's Principle and full impredicative comprehension. Hume's Principle is one example of an abstraction principle, while another paradigmatic example is Basic Law V from Frege's Grundgesetze. In this paper we study the strength of abstraction principles in the presence of predicative restrictions on the comprehension schema, and in particular we study a predicative Fregean theory which contains all the abstraction principles whose underlying equivalence relations can be proven to (...) be equivalence relations in a weak background second-order logic. We show that this predicative Fregean theory interprets second-order Peano arithmetic. (shrink)

Presburger's essay on the completeness and decidability of arithmetic with integer addition but without multiplication is a milestone in the history of mathematical logic and formal metatheory. The proof is constructive, using Tarski-style quantifier elimination and a four-part recursive comprehension principle for axiomatic consequence characterization. Presburger's proof for the completeness of first order arithmetic with identity and addition but without multiplication, in light of the restrictive formal metatheorems of Gödel, Church, and Rosser, takes the foundations of arithmetic in mathematical (...) logic to the limits of completeness and decidability. (shrink)

A theory T is tight if different deductively closed extensions of T (in the same language) cannot be bi-interpretable. Many well-studied foundational theories are tight, including $\mathsf {PA}$ [39], $\mathsf {ZF}$, $\mathsf {Z}_2$, and $\mathsf {KM}$ [6]. In this article we extend Enayat’s investigations to subsystems of these latter two theories. We prove that restricting the Comprehension schema of $\mathsf {Z}_2$ and $\mathsf {KM}$ gives non-tight theories. Specifically, we show that $\mathsf {GB}$ and $\mathsf {ACA}_0$ each admit different bi-interpretable (...) extensions, and the same holds for their extensions by adding $\Sigma ^1_k$ -Comprehension, for $k \ge 1$. These results provide evidence that tightness characterizes $\mathsf {Z}_2$ and $\mathsf {KM}$ in a minimal way. (shrink)

We prove Fraïssé’s conjecture within the system of Π11-comprehension. Furthermore, we prove that Fraïssé’s conjecture follows from the Δ20-bqo-ness of 3 over the system of Arithmetic Transfinite Recursion, and that the Δ20-bqo-ness of 3 is a Π21-statement strictly weaker than Π11-comprehension.

In this paper, we consider, for a set \ of natural numbers, the following notions of finitenessFIN1:There are a natural number l and a bijection f between \\);FIN5:It is not the case that \\), and infinitenessINF1:There are not a natural number l and a bijection f between \\);INF5:\\). In this paper, we systematically compare them in the method of constructive reverse mathematics. We show that the equivalence among them can be characterized by various combinations of induction axioms and non-constructive principles, (...) including the axiom of bounded comprehension. (shrink)

Arithmetical comprehension is proved to be equivalent to the enumerability of singular points of any measure on the Cantor space. It is provable in ACA0 that any perfect closed subset of [0, 1] is the support of some continuous positive linear functional on C[0, 1].