A speculative investigation of how Frege's logical views change between Begriffsschrift and Grundgesetze and how this might have affected the formal development of logicism.

In a famous paper of 1931, Gödel proved that any formalization of elementary Arithmetic is incomplete, in the sense that it contains statements which are neither provable nor disprovable. Some two years before this, Presburger proved that a mutilated system of Arithmetic, employing only addition but not multiplication, is complete. This essay is partly an exposition of a system such as Presburger's, and partly an attempt to gain insight into the source of the incompleteness of Arithmetic, by (...) linking Presburger's result with Gödel's. Chapter 1, p. 1. (shrink)

The famous theory of undecidable sentences created by Kurt Godel in 1931 is presented as clearly and as rigorously as possible. Introductory explanations beginning with the necessary facts of arithmetic of integers and progressing to the theory of representability of arithmetical functions and relations in the system (S) prepare the reader for the systematic exposition of the theory of Godel which is taken up in the final chapter and the appendix.

After a summary of earlier work it is shown that elementary or Kalmar arithmetic can be interpreted within the system of Russell's Principia Mathematica with the axiom of infinity but without the axiom of reducibility.

This books states, as clearly and concisely as possible, the most fundamental principles of set-theory and mathematical logic. Included is an original proof of the incompleteness of formal logic. Also included are clear and rigorous definitions of the primary arithmetical operations, as well as clear expositions of the arithmetic of transfinite cardinals.

We show that certain model-theoretic forcing arguments involving subsystems of second-order arithmetic can be formalized in the base theory, thereby converting them to effective proof-theoretic arguments. We use this method to sharpen the conservation theorems of Harrington and Brown-Simpson, giving an effective proof that WKL+0 is conservative over RCA0 with no significant increase in the lengths of proofs.

In this paper, we introduce the systems ns-ACA₀ and ns-WKL₀ of non-standard second-order arithmetic in which we can formalize non-standard arguments in ACA₀ and WKL₀, respectively. Then, we give direct transformations from non-standard proofs in ns-ACA₀ or ns-WKL₀ into proofs in ACA₀ or WKL₀.

I make an attempt at the description of the delicate role of the standard model of arithmetic for the syntax of formal systems. I try to assess whether the possible instability in the notion of finiteness deriving from the nonstandard interpretability of arithmetic affects the very notions of syntactic metatheory and of formal system. I maintain that the crucial point of the whole question lies in the evaluation of the phenomenon of formalization. The ideas of Skolem, (...) Zermelo, Beth and Carnap (among others) on the problem are discussed. ‘A tries to explain to B the meaning of negation. Finally A gives up, saying: “You don’t understand what I mean, and I am not going to explain any longer,” to which B replies: “Yes, I see what you mean, and I am glad you are willing to continue your explanations”’. G. Mannoury, reported by E. W. Beth (Beth, 1963, 489). (shrink)

Many philosophers have considered logical reasoning as an inborn ability of mankind and as a distinctive feature in the human mind; but we all know that the distribution of this capacity, or at any rate its development, is very unequal. Few people are able to set up a cogent argument; others are at least able to follow a logical argument and even to detect logical fallacies. Nevertheless, even among educated persons there are many who do not even attain this relatively (...) modest level of development. According to my personal observations, lack of logical ability may be due to various circumstances. In the first place, I mention lack of general intelligence, insufficient power of concentration, and absence of formal education. Secondly, however, I have noticed that many people are unable, or sometimes rather unwilling, to argue ex hypothesi; such persons cannot, or will not, start from premisses which they know or believe to be false or even from premisses whose truth is not, in their opinion, sufficient ly warranted. Or, if they agree to start from such premisses, they sooner or later stray away from the argument into attempts first to settle the truth or falsehood of the premisses. Presumably this attitude results either from lack of imagination or from undue moral rectitude. On the other hand, proficiency in logical reasoning is not in itself a guarantee for a clear theoretic insight into the principles and foundations of logic. (shrink)

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.

We present a theory VF of partial truth over Peano arithmetic and we prove that VF and ID 1 have the same arithmetical content. The semantics of VF is inspired by van Fraassen's notion of supervaluation.

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)

We present a theory VF of partial truth over Peano arithmetic and we prove that VF and ID 1 have the same arithmetical content. The semantics of VF is inspired by van Fraassen's notion of supervaluation.

What seem to be Kurt Gödel’s first notes on logic, an exercise notebook of 84 pages, contains formal proofs in higher-order arithmetic and set theory. The choice of these topics is clearly suggested by their inclusion in Hilbert and Ackermann’s logic book of 1928, the Grundzüge der theoretischen Logik. Such proofs are notoriously hard to construct within axiomatic logic. Gödel takes without further ado into use a linear system of natural deduction for the full language of higher-order logic, (...) with formal derivations closer to one hundred steps in length and up to four nested temporary assumptions with their scope indicated by vertical intermittent lines. (shrink)

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 it to the opposition of propositional logic, to which Gentzen’s cut rule refers immediately, on the one hand, and the linguistic and mathematical theory of metaphor therefore sharing the same structure borrowed from Hilbert arithmetic in a wide sense. An example by hermeneutical circle modeled as a dual pair of a syllogism (accomplishable also by a Turing machine) and a relevant metaphor (being a formal and logical mistake and thus fundamentally inaccessible to any Turing machine) visualizes human understanding corresponding also to Gentzen’s cut elimination and the Gödel dichotomy about the relation of arithmetic to set theory: either incompleteness or contradiction. The metaphor as the complementing “half” of any understanding of hermeneutical circle is what allows for that Gödel-like incompleteness to be overcome in human thought. (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)

Let ℸ be the set of Gödel numbers Gn of function symbols f such that PRA ⊢ and let γ be the function such that equation imageWe prove: The r. e. set ℸ is m-complete; the function γ is not primitive recursive in any class of functions {f1, f2, ⃛} so long as each fi has a recursive upper bound. This implies that γ is not primitive recursive in ℸ although it is recursive in ℸ.

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}$.

This paper provides examples in arithmetic of the account of rational intuition and evidence developed in my book After Gödel: Platonism and Rationalism in Mathematics and Logic . The paper supplements the book but can be read independently of it. It starts with some simple examples of problem-solving in arithmetic practice and proceeds to general phenomenological conditions that make such problem-solving possible. In proceeding from elementary ‘authentic’ parts of arithmetic to axiomatic formal arithmetic, the paper (...) exhibits some elements of the genetic analysis of arithmetic knowledge that is called for in Husserl’s philosophy. This issues in an elaboration on a number of Gödel’s remarks about the meaning of his incompleteness theorems for the notion of evidence in mathematics. (shrink)

We give a new characterization of the strict $$\forall {\Sigma^b_j}$$ sentences provable using $${\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 $${\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 (...) j, and hence that the relativized bounded arithmetic hierarchy can be separated by a family of $$\forall {\Sigma^b_1}$$ sentences. (shrink)

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)