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)

Biró, B. and I. Sain, Peano arithmetic as axiomatization of the time frame in logics of programs and in dynamic logics, Annals of Pure and Applied Logic 63 201-225. We show that one can prove the partial correctness of more programs using Peano's axioms for the time frames of three-sorted time models than using only Presburger's axioms, that is it is useful to allow multiplication of time points at program verification and in dynamic and temporal logics. We (...) organized the paper as follows: 1. Preliminaries, 2. The main result, 3. Peano arithmetic with bounded multiplication, 4. Connections with temporal logics and dynamic logics, Acknowledgements, References. (shrink)

Gurevich and Shelah have shown that Peano Arithmetic cannot be interpreted in the monadic second-order theory of short chains (hence, in the monadic second-order theory of the real line). We will show here that it is consistent that the monadic second-order theory of no chain interprets Peano Arithmetic.

Jäger, G., Fixed points in Peano arithmetic with ordinals, Annals of Pure and Applied Logic 60 119-132. This paper deals with some proof-theoretic aspects of fixed point theories over Peano arithmetic with ordinals. It studies three such theories which differ in the principles which are available for induction on the natural numbers and ordinals. The main result states that there is a natural theory in this framework which is a conservative extension of Peano arithmeti.

We present an overview of the topics in the title and of some of the key results pertaining to them. These have historically been topics of interest in computability theory and continue to be a rich source of problems and ideas. In particular, we draw attention to the links and connections between these topics and explore their significance to modern research in the field.

PA is Peano arithmetic. The formula $\operatorname{Interp}_\mathrm{PA}(\alpha, \beta)$ is a formalization of the assertion that the theory PA + α interprets the theory PA + β (the variables α and β are intended to range over codes of sentences of PA). We extend Solovay's modal analysis of the formalized provability predicate of PA, Pr PA (x), to the case of the formalized interpretability relation $\operatorname{Interp}_\mathrm{PA}(x, y)$ . The relevant modal logic, in addition to the usual provability operator `□', (...) has a binary operator ` $\triangleright$ ' to be interpreted as the formalized interpretability relation. We give an axiomatization and a decision procedure for the class of those modal formulas that express valid interpretability principles (for every assignment of the atomic modal formulas to sentences of PA). Our results continue to hold if we replace the base theory PA with Zermelo-Fraenkel set theory, but not with Gödel-Bernays set theory. This sensitivity to the base theory shows that the language is quite expressive. Our proof uses in an essential way earlier work done by A. Visser, D. de Jongh, and F. Veltman on this problem. (shrink)

We employ the lens provided by formal truth theory to study axiomatizations of Peano Arithmetic ${\textsf {(PA)}}$. More specifically, let Elementary Arithmetic ${\textsf {(EA)}}$ be the fragment $\mathsf {I}\Delta _0 + \mathsf {Exp}$ of ${\textsf {PA}}$, and let ${\textsf {CT}}^-[{\textsf {EA}}]$ be the extension of ${\textsf {EA}}$ by the commonly studied axioms of compositional truth ${\textsf {CT}}^-$. We investigate both local and global properties of the family of first order theories of the form ${\textsf {CT}}^-[{\textsf {EA}}] +\alpha (...) $, where $\alpha $ is a particular way of expressing “ ${\textsf {PA}}$ is true” (using the truth predicate). Our focus is dominantly on two types of axiomatizations, namely: (1) schematic axiomatizations that are deductively equivalent to ${\textsf {PA}}$ and (2) axiomatizations that are proof-theoretically equivalent to the canonical axiomatization of ${\textsf {PA}}$. (shrink)

We construct a model of Peano arithmetic in an uncountable language which has no elementary end extension. This answers a question of Gaifman and contrasts with the well-known theorem of MacDowell and Specker which states that every model of Peano arithmetic in a countable language has an elementary end extension. The construction employs forcing in a nonstandard model.

The relative strengths of first-order theories axiomatized by transfinite induction, for ordinals less-than 0, and formulas restricted in quantifier complexity, is determined. This is done, in part, by describing the provably recursive functions of such theories. Upper bounds for the provably recursive functions are obtained using model-theoretic techniques. A variety of additional results that come as an application of such techniques are mentioned.

The system called F is essentially a sub-theory of Frege Arithmetic without the ad infinitum assumption that there is always a next number. In a series of papers (Systems for a Foundation of Arithmetic, True” Arithmetic Can Prove Its Own Consistency and Proving Quadratic Reciprocity) it was shown that F proves a large number of basic arithmetic truths, such as the Euclidean Algorithm, Unique Prime Factorization (i.e. the Fundamental Law of Arithmetic), and Quadratic Reciprocity, indeed (...) a sizable amount of arithmetic. In particular, F proves some (but not all) of the Peano Axioms; that is, F proves the axioms of a sub-theory - call it FPA - of second-order Peano-Arithmetic. This short technical note will demonstrate that the converse also holds, in the following sense. F has the same language as second-order Peano Arithmetic except that, in addition, it has a two-place predicate symbol “Μ”. Then it is possible to provide a definition, indeed a reasonable definition, for “Μ” such that FPA proves all the axioms of F. So F and FPA effectively have the same proof-theoretic strength. In particular FPA, which lacks the Successor Axiom stating that every natural number has a successor, is able to prove the Euclidean Algorithm, Unique Prime Factorization, and Quadratic Reciprocity, indeed (again) a sizable amount of arithmetic. (shrink)

This paper develops the philosophy and technology needed for adding a supremum operator to the interpretability logic ILM\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {ILM}$$\end{document} of Peano Arithmetic. It is well-known that any theories extending PA\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {PA}$$\end{document} have a supremum in the interpretability ordering. While provable in PA\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {PA}$$\end{document}, this fact is not reflected in the theorems of (...) the modal system ILM\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {ILM}$$\end{document}, due to limited expressive power. Our goal is to enrich the language of ILM\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {ILM}$$\end{document} by adding to it a new modality for the interpretability supremum. We explore different options for specifying the exact meaning of the new modality. Our final proposal involves a unary operator, the dual of which can be seen as a provability predicate satisfying the axioms of the provability logic GL\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathsf {GL}$$\end{document}. (shrink)

A proof of normalization for a classical system of Peano Arithmetic formulated in natural deduction is given. The classical rule of the system is the rule for indirect proof restricted to atomic formulas. This rule does not, due to the restriction, interfere with the standard detour conversions. The convertible detours, numerical inductions and instances of indirect proof concluding falsity are reduced in a way that decreases a vector assigned to the derivation. By interpreting the expressions of the vectors (...) as ordinals each derivation is assigned an ordinal less than ɛ0. The vector assignment, which proves termination of the procedure, originates in a normalization proof for Gödel’s T by Howard. (shrink)

Russell held that the theory of natural numbers could be derived from three primitive concepts: number, successor and zero. This leaves out multiplication and addition. Russell introduces these concepts by recursive definition. It is argued that this does not render addition or multiplication any less primitive than the other three. To this it might be replied that any recursive definition can be transformed into a complete or explicit definition with the help of a little set theory. But that is a (...) point about set theory, not number theory. We have learned more about the distinction between logic and set theory than was known in Russell's day, especially as this affects logicist aspirations. (shrink)

We study reducts of Peano arithmetic for which conditions of saturation imply the corresponding conditions for the whole model. It is shown that very weak reducts (like pure order) have such a property for κ-saturation in every κ ≥ ω 1 . In contrast, other reducts do the job for ω and not for $\kappa > \omega_1$ . This solves negatively a conjecture of Chang.

We present a functional interpretation of Peano arithmetic that uses Gödel’s computable functionals and which systematically injects uniformities into the statements of finite-type arithmetic. As a consequence, some uniform boundedness principles are interpreted while maintaining unmoved the -sentences of arithmetic. We explain why this interpretation is tailored to yield conservation results.

A model $\mathscr{M} = (M,+,\times, 0,1,<)$ of Peano Arithmetic $({\sf PA})$ is boundedly saturated if and only if it has a saturated elementary end extension $\mathscr{N}$. The ordertypes of boundedly saturated models of $({\sf PA})$ are characterized and the number of models having these ordertypes is determined. Pairs $(\mathscr{N},M)$, where $\mathscr{M} \prec_{\sf end} \mathscr{N} \models({\sf PA})$ for saturated $\mathscr{N}$, and their theories are investigated. One result is: If $\mathscr{N}$ is a $\kappa$-saturated model of $({\sf PA})$ and $\mathscr{M}_0, \mathscr{M}_1 (...) \prec_{\sf end} \mathscr{N}$ are such that $\aleph_1 \leq \mathrm{min}(\mathrm{cf}(M_0),\mathrm{dcf}(M_0)) \leq \mathrm{min}(\mathrm{cf}(M_1), \mathrm{dcf}(M_1)) < \kappa$, then $(\mathscr{N},M_0) \equiv (\mathscr{N},M_1)$. (shrink)

The principal result of this paper answers a long-standing question in the model theory of arithmetic [R. Kossak, J. Schmerl, The Structure of Models of Peano Arithmetic, Oxford University Press, 2006, Question 7] by showing that there exists an uncountable arithmetically closed family of subsets of the set ω of natural numbers such that the expansion of the standard model of Peano arithmetic has no conservative elementary extension, i.e., for any elementary extension of , there (...) is a subset of ω* that is parametrically definable in but whose intersection with ω is not a member of . We also establish other results that highlight the role of countability in the model theory of arithmetic. Inspired by a recent question of Gitman and Hamkins, we furthermore show that the aforementioned family can be arranged to further satisfy the curious property that forcing with the quotient Boolean algebra collapses 1 when viewed as a notion of forcing. (shrink)

We investigate the modal logic of interpretability over Peano arithmetic. Our main result is a compactness theorem that extends the arithmetical completeness theorem for the interpretability logic ILM ω . This extension concerns recursively enumerable sets of formulas of interpretability logic (rather than single formulas). As corollaries we obtain a uniform arithmetical completeness theorem for the interpretability logic ILM and a partial answer to a question of Orey from 1961. After some simplifications, we also obtain Shavrukov's embedding theorem (...) for Magari algebras (a.k.a. diagonalizable algebras). (shrink)

Let $\mathscr{L} = \{0, 1, +, \cdot, <\}$ be the usual first-order language of arithmetic. We show that Peano arithmetic is the least first-order L-theory containing IΔ0 + exp such that every complete extension T of it has a countable model K satisfying. (i) K has no proper elementary substructures, and (ii) whenever $L \prec K$ is a countable elementary extension there is $\bar{L} \prec L$ and $\bar{K} \subseteq_\mathrm{e} \bar{L}$ such that $K \prec_{\mathrm{cf}}\bar{K}$ . Other model-theoretic conditions (...) similar to (i) and (ii) are also discussed and shown to characterize Peano arithmetic. (shrink)

Theorem 1. If T is a sound formalized theory whose language contains the language of basic arithmetic, then there will be a true sentence GT of basic arithmetic such that T ￿ GT and ￿ ¬GT, so T must be negation incomplete.

Let= {0,1, +,·,<} be the usual first-order language of arithmetic. We show that Peano arithmetic is the least first-order-theory containingIΔ0+ exp such that every complete extensionTof it has a countable modelKsatisfying(i)Khas no proper elementary substructures, and(ii) wheneverL≻Kis a countable elementary extension there isandsuch that.Other model-theoretic conditions similar to (i) and (ii) are also discussed and shown to characterize Peano arithmetic.

We give some information about the action of Aut on M, where M is a countable arithmetically saturated model of Peano Arithmetic. We concentrate on analogues of moving gaps and covering gaps inside M.

In the Handbook of Mathematical Logic, the Paris-Harrington variant of Ramsey's theorem is celebrated as the first result of a long ‘search’ for a purely mathematical incompleteness result in first-order Peano arithmetic. This paper questions the existence of any such search and the status of the Paris-Harrington result as the first mathematical incompleteness result. In fact, I argue that Gentzen gave the first such result, and that it was restated by Goodstein in a number-theoretic form.

The paper introduces and utilizes a few new concepts: “nonstandard Peano arithmetic”, “complementary Peano arithmetic”, “Hilbert arithmetic”. They identify the foundations of both mathematics and physics demonstrating the equivalence of the newly introduced Hilbert arithmetic and the separable complex Hilbert space of quantum mechanics in turn underlying physics and all the world. That new both mathematical and physical ground can be recognized as information complemented and generalized by quantum information. A few fundamental mathematical problems (...) of the present such as Fermat’s last theorem, four-color theorem as well as its new-formulated generalization as “four-letter theorem”, Poincaré’s conjecture, “P vs NP” are considered over again, from and within the new-founding conceptual reference frame of information, as illustrations. Simple or crucially simplifying solutions and proofs are demonstrated. The link between the consistent completeness of the system mathematics-physics on the ground of information and all the great mathematical problems of the present (rather than the enumerated ones) is suggested. (shrink)

In this paper we study the automorphism groups of models of Peano Arithmetic. Kossak, Kotlarski, and Schmerl [9] shows that the stabilizer of an unbounded element a of a countable recursively saturated model of Peano Arithmetic M is a maximal subgroup of Aut if and only if the type of a is selective. We extend this result by showing that if M is a countable arithmetically saturated model of Peano Arithmetic, Ω ⊂ M is (...) a very good interstice, and a ∈ Ω, then the stabilizer of a is a maximal subgroup of Aut if and only if the type of a is selective and rational. (shrink)

Solovay proved (Israel J Math 25(3–4):287–304, 1976) that the propositional provability logic of any ∑2-sound recursively enumerable extension of PA is characterized by the propositional modal logic GL. By contrast, Montagna proved in (Notre Dame J Form Log 25(2):179–189, 1984) that predicate provability logics of Peano arithmetic and Bernays–Gödel set theory are different. Moreover, Artemov proved in (Doklady Akademii Nauk SSSR 290(6):1289–1292, 1986) that the predicate provability logic of a theory essentially depends on the choice of a binumeration (...) of the theory which is used to construct the provability predicate. In this paper, we compare predicate provability logics of I∑ n ’s. For a binumeration α(x) of a recursive theory T, let PL α(T) be the predicate provability logic of T defined by α(x). We prove that for any natural numbers i, j such that 0 < i < j, there exists a ∑1 binumeration α(x) of some recursive axiomatization of I∑ i such that ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsupseteq \bigcap_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ and ${{\sf PL}_\alpha({\rm I \Sigma}_i) \nsubseteq \bigcup_{\beta(x)}{\sf PL}_\beta({\rm I \Sigma}_j)}$ , where β(x) ranges over all ∑1 binumerations of recursive axiomatizations of I∑ j. (shrink)

Bounded lattices (that is lattices that are both lower bounded and upper bounded) form a large class of lattices that include all distributive lattices, many nondistributive finite lattices such as the pentagon lattice N₅, and all lattices in any variety generated by a finite bounded lattice. Extending a theorem of Paris for distributive lattices, we prove that if L is an ℵ₀-algebraic bounded lattice, then every countable nonstandard model ������ of Peano Arithmetic has a cofinal elementary extension ������ (...) such that the interstructure lattice Lt(������ / ������) is isomorphic to L. (shrink)

Wilkie proved in 1977 that every countable model ${\mathcal M}$ of Peano Arithmetic has an elementary end extension ${\mathcal N}$ such that the interstructure lattice $\operatorname {\mathrm {Lt}}({\mathcal N} / {\mathcal M})$ is the pentagon lattice ${\mathbf N}_5$. This theorem implies that every countable nonstandard ${\mathcal M}$ has an elementary cofinal extension ${\mathcal N}$ such that $\operatorname {\mathrm {Lt}}({\mathcal N} / {\mathcal M}) \cong {\mathbf N}_5$. It is proved here that whenever ${\mathcal M} \prec {\mathcal N} \models \mathsf (...) {PA}$ and $\operatorname {\mathrm {Lt}}({\mathcal N} / {\mathcal M}) \cong {\mathbf N}_5$, then ${\mathcal N}$ must be either an end or a cofinal extension of ${\mathcal M}$. In contrast, there are ${\mathcal M}^* \prec {\mathcal N}^* \models \mathsf {PA}^*$ such that $\operatorname {\mathrm {Lt}}({\mathcal N}^* / {\mathcal M}^*) \cong {\mathbf N}_5$ and ${\mathcal N}^*$ is neither an end nor a cofinal extension of ${\mathcal M}^*$. (shrink)

Letκbe the cardinality of some saturated model of Peano Arithmetic. There is a set of${2^{{\aleph _0}}}$saturated models of PA, each having cardinalityκ, such that wheneverMandNare two distinct models from this set, then Aut(${\cal M}$) ≇ Aut ($${\cal N}$$).

This paper concerns intermediate structure lattices Lt, where [MATHEMATICAL SCRIPT CAPITAL N] is an almost minimal elementary end extension of the model ℳ of Peano Arithmetic. For the purposes of this abstract only, let us say that ℳ attains L if L ≅ Lt for some almost minimal elementary end extension of [MATHEMATICAL SCRIPT CAPITAL N]. If T is a completion of PA and L is a finite lattice, then: If some model of T attains L, then every (...) countable model of T does. If some rather classless, ℵ1-saturated model of T attains L, then every model of T does. (shrink)

One of the philosophical uses of Dedekind’s categoricity theorem for Peano Arithmetic is to provide support for semantic realism. To this end, the logical framework in which the proof of the theorem is conducted becomes highly significant. I examine different proposals regarding these logical frameworks and focus on the philosophical benefits of adopting open-ended schemas in contrast to second order logic as the logical medium of the proof. I investigate Pederson and Rossberg’s critique of the ontological advantages of (...) open-ended arithmetic when it comes to establishing the categoricity of Peano Arithmetic and show that the critique is highly problematic. I argue that Pederson and Rossberg’s ontological criterion deliver the bizarre result that certain first order subsystems of Peano Arithmetic have a second order ontology. As a consequence, the application of the ontological criterion proposed by Pederson and Rossberg assigns a certain type of ontology to a theory, and a different, richer, ontology to one of its subtheories. (shrink)

The shortest definition of a number by a first order formula with one free variable, where the notion of a formula defining a number extends a notion used by Boolos in a proof of the Incompleteness Theorem, is shown to be non computable. This is followed by an examination of the complexity of sets associated with this function.

In this paper, we investigate definable models of Peano Arithmetic PA in a model of PA. For any definable model N without parameters in a model M, we show that N is isomorphic to M if M is elementary extension of the standard model and N is elementarily equivalent to M. On the other hand, we show that there is a model M and a definable model N with parameters in M such that N is elementarily equivalent to (...) M but N is not isomorphic to M. We also show that there is a model M and a definable model N with parameters in M such that N is elementarily equivalent to M, and N is isomorphic to M, but N is not definably isomorphic to M. And also, we give a generalization of Tennenbaum's theorem. At the end, we give a new method to construct a definable model by a refinement of Kotlarski's method. (shrink)

If${\cal M},{\cal N}$are countable, arithmetically saturated models of Peano Arithmetic and${\rm{Aut}}\left( {\cal M} \right) \cong {\rm{Aut}}\left( {\cal N} \right)$, then the Turing-jumps of${\rm{Th}}\left( {\cal M} \right)$and${\rm{Th}}\left( {\cal N} \right)$are recursively equivalent.

Let M be a model of first order Peano arithmetic and I an initial segment of M that is closed under multiplication. LetM0 be the {0, 1,+}-reduct ofM. We show that there is another model N of PA that is also an expansion of M0 such that a · Ma = a · Na if and only if a ∈ I for all a ∈ M.

Aimed at graduate students, research logicians and mathematicians, this much-awaited text covers over 40 years of work on relative classification theory for nonstandard models of arithmetic. The book covers basic isomorphism invariants: families of type realized in a model, lattices of elementary substructures and automorphism groups.

In response to Bhupinder Singh Anand''s article CAN WE REALLY FALSIFY TRUTH BY DICTAT? in THE REASONER II, 1, January 2008,that denies the existence of nonstandard models of Peano Arithmetic, we prove from Compactness the existence of such models.

Let \ be a class of formulas. We say that a theory T in classical logic has the \-disjunction property if for any \ sentences \ and \, either \ or \ whenever \. First, we characterize the \-disjunction property in terms of the notion of partial conservativity. Secondly, we prove a model theoretic characterization result for \-disjunction property. Thirdly, we investigate relationships between partial disjunction properties and several other properties of theories containing Peano arithmetic. Finally, we investigate (...) unprovability of formalized partial disjunction properties. (shrink)

If $M \models PA (= Peano Arithmetic)$ , we set $A^M = \{N \subset_e M: N \models PA\}$ and study this family.

The complete characterisation of order types of non-standard models of Peano arithmetic and its extensions is a famous open problem. In this paper, we consider subtheories of Peano arithmetic (both with and without induction), in particular, theories formulated in proper fragments of the full language of arithmetic. We study the order types of their non-standard models and separate all considered theories via their possible order types. We compare the theories with and without induction and observe (...) that the theories without induction tend to have an algebraic character that allows model constructions by closing a model under the relevant algebraic operations. (shrink)

There is an infinite set T of Turing-equivalent completions of Peano Arithmetic such that whenever M and N are nonisomorphic countable, arithmetically saturated models of PA and Th, Th∈T, then Aut≇Aut.

The complete characterisation of order types of non-standard models of Peano arithmetic and its extensions is a famous open problem. In this paper, we consider subtheories of Peano arithmetic (both with and without induction), in particular, theories formulated in proper fragments of the full language of arithmetic. We study the order types of their non-standard models and separate all considered theories via their possible order types. We compare the theories with and without induction and observe (...) that the theories without induction tend to have an algebraic character that allows model constructions by closing a model under the relevant algebraic operations. (shrink)

We consider expansions of models of Peano arithmetic to models ofA 2 s -¦Δ 1 1 +Σ 1 1 −AC which consist of families of sets definable by nonstandard formulas.