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

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)

The paper discusses the similarity between geometry, arithmetic, and logic, specifically with respect to the question of whether applied theories of each may be revised. It argues that they can - even when the revised logic is a paraconsistent one, or the revised arithmetic is an inconsistent one. Indeed, in the case of logic, it argues that logic is not only revisable, but, during its history, it has been revised. The paper also discusses Quine's well known (...) argument against the possibility of logical deviancy. (shrink)

The extra propositions which Wittgenstein added to Ramsey's copy of\nthe 'Tractatus' during their discussions in 1923 provide evidence,\nWrigley argues, that Wittgenstein's view of mathematics was quite\ndifferent from logicism. Contrary to this, Frascolla tries to prove\nthat the label 'no-classes logicism' tallies with the 'Tractarian'\nview of arithmetic.

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 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 \.

This chapter contains sections titled: Logical Applications Empirical Applications Wittgenstein: A Social Constructivist?

(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)

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)

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.

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.

This paper investigates a first-order extension of GL called \. We outline briefly the history that led to \, its key properties and some of its toolbox: the \emph{conservation theorem}, its cut-free Gentzenisation, the ``formulators'' tool. Its semantic completeness is fully stated in the current paper and the proof is retold here. Applying the Solovay technique to those models the present paper establishes its main result, namely, that \ is arithmetically complete. As expanded below, \ is a first-order modal (...) class='Hi'>logic that along with its built-in ability to simulate general classical first-order provability―"\" simulating the the informal classical "\"―is also arithmetically complete in the Solovay sense. (shrink)

In this paper we study the status of the arithmetical completeness of dynamic logic. We prove that for finitistic proof systems for dynamic logic results beyond arithmetical completeness are very unlikely. The role of the set of natural numbers is carefully analyzed.

T i 2 = S i +1 2 implies ∑ p i +1 ⊆ Δ p i +1 ⧸poly. S 2 and IΔ 0 ƒ are not finitely axiomatizable. The main tool is a Herbrand-type witnessing theorem for ∃∀∃ П b i -formulas provable in T i 2 where the witnessing functions are □ p i +1.

The class of all ordinal numbers can be partitioned into two subclasses in such a way that neither subclass contains an arithmetic progression of order type ω, where an arithmetic progression of order type τ means an increasing sequence of ordinal numbers γ r, δ ≠ 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 this paper we deal with some new axiom schemes for Peano's Arithmetic that can substitute the classical induction, least-element, collection and strong collection schemes in the description of PA.

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.

It can be argued that only the equational theories of some sub-elementary function algebras are finitistic or intuitive according to a certain interpretation of Hilbert's conception of intuition. The purpose of this paper is to investigate the relation of those restricted forms of equational reasoning to classical quantifier logic in arithmetic. The conclusion reached is that Edward Nelson's ‘predicative arithmetic’ program, which makes essential use of classical quantifier logic, cannot be justified finitistically and thus requires a different philosophical (...) foundation, possibly as a restricted form of logicism. (shrink)

The bounded arithmetic theory S2 is finitely axiomatized if and only if the polynomial hierarchy provably collapses. If T2i equals S2i + 1 then T2i is equal to S2 and proves that the polynomial time hierarchy collapses to ∑i + 3p, and, in fact, to the Boolean hierarchy over ∑i + 2p and to ∑i + 1p/poly.

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)

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. Given a new definition of equality all the Peano-type axioms of Mendelson except one can be derived. A rather weak extra axiom allows the proof of the remaining Peano axiom. Note. The illative combinatory logic used in this paper is similar to the logic employed in computer languages such as ML. (shrink)

The paper considers a generalization of Peano arithmetic, Hilbert arithmetic as the basis of the world in a Pythagorean manner. Hilbert arithmetic unifies the foundations of mathematics (Peano arithmetic and set theory), foundations of physics (quantum mechanics and information), and philosophical transcendentalism (Husserl’s phenomenology) into a formal theory and mathematical structure literally following Husserl’s tracе of “philosophy as a rigorous science”. In the pathway to that objective, Hilbert arithmetic identifies by itself information related to finite sets and series and quantum (...) information referring to infinite one as both appearing in three “hypostases”: correspondingly, mathematical, physical and ontological, each of which is able to generate a relevant science and area of cognition. Scientific transcendentalism is a falsifiable counterpart of philosophical transcendentalism. The underlying concept of the totality can be interpreted accordingly also mathematically, as consistent completeness, and physically, as the universe defined not empirically or experimentally, but as that ultimate wholeness containing its externality into itself. (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)

Since there are non-sortal predicates Frege’s attempt to derive Arithmetic from Logic stumbles at its very first step. There are properties without a number, so the contingency of that condition shows Frege’s definition of zero is not obtainable from Logic. But Frege made a crucial mistake about concepts more generally which must be remedied, before we can be clear about those specific concepts which are numbers.

This article discusses the properties of a controllable, flexible, hybrid parallel computing architecture that potentially merges pattern recognition and arithmetic. Humans perform integer arithmetic in a fundamentally different way than logic-based computers. Even though the human approach to arithmetic is both slow and inaccurate it can have substantial advantages when useful approximations are more valuable than high precision. Such a computational strategy may be particularly useful when computers based on nanocomponents become feasible because it offers a way to make (...) use of the potential power of these massively parallel systems. Because the system architecture is inspired by neuroscience and is applied to cognitive problems, occasional mention is made of experimental data from both fields when appropriate. (shrink)

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)

Constructive ZF + full separation is shown to be equiconsistent with Second Order Arithmetic.

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)

In nonstandard mathematics, the predicate ‘x is standard’ is fundamental. Recently, ‘relative’ or ‘stratified’ nonstandard theories have been developed in which this predicate is replaced with ‘x is y -standard’. Thus, objects are not standard in an absolute sense, but standard relative to other objects and there is a whole stratified universe of ‘levels’ or ‘degrees’ of standardness. Here, we study stratified nonstandard arithmetic and the related transfer principle. Using the latter, we obtain the ‘reduction theorem’ which states that arithmetical (...) formulas can be reduced to equivalent bounded formulas. Surprisingly, the reduction theorem is also equivalent to the transfer principle. As applications, we obtain a truth definition for arithmetical sentences and we formalize Nelson's notion of impredicativity. (shrink)

The existence of non-standard models of first-order Peano-Arithmetic (PA) threatens to undermine the claim of the moderate mathematical realist that non-mysterious access to the natural number structure is possible on the basis of our best arithmetical theories. The move to logics stronger than FOL is denied to the moderate realist on the grounds that it merely shifts the indeterminacy “one level up” into the meta-theory by, illegitimately, assuming the determinacy of the notions needed to formulate such logics. This paper argues (...) that the challenge can be met. We show how the quantifier “there are infinitely many” can be uniquely determined in a naturalistically acceptable fashion and thus be used in the formulation of a theory of arithmetic. We compare the approach pursued here with Field’s justification of the same device and the popular strategy of invoking a second-order formalism, and argue that it is more robust than either of the alternative proposals. (shrink)

In Entailment, Anderson and Belnap motivated their modification E of Ackermann’s strenge Implikation Π Π’ as a logic of relevance and necessity. The kindred system R was seen as relevant but not as modal. Our systems of Peano arithmetic R# and omega arithmetic R## were based on R to avoid fallacies of relevance. But problems arose as to which arithmetic sentences were (relevantly) true. Here we base analogous systems on E to solve those problems. Central to motivating E is (...) the rejection of fallacies of modality. Our slogan here for this is, “No diamonds entail any boxes.” Form the strenge Peano arithmetic E# like R#, adding appropriate forms of the Peano axioms to Ackermann’s E.. (shrink)

This paper explores models for arithmetic in substructural logics. In the existing literature on substructural arithmetic, frame semantics for substructural logics are absent. We will start to fill in the picture in this paper by examining frame semantics for the substructural logics C (linear logic plus distribution), R (relevant logic) and CK (C plus weakening). The eventual goal is to find negation complete models for arithmetic in R.

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 develops a general language of event configurations to discuss and compare various modes of proposition formation. It is shown that any finite orthogonality space can be numerically encoded. This encoding is applied to show that the quasimanual of all orthogonal subsets of any finite point-determining orthogonality space may be decomposed into a union of manuals and that the logic of these quasimanuals may be regarded as a composite of interlocking associative orthoalgebras.