Search

We present a number of results on the structure of initial segments of models of Peano arithmetic with the arithmetic operations of addition, subtraction, multiplication, division, exponentiation and logarithm. Each of the binary operations introduced is defined in two dual ways, often with quite different results, and we attempt to systematise the issues and show how various calculations may be carried out. To understand the behaviour of addition and subtraction we introduce a notion of derivative on cuts, analogous to differentiation in the calculus. Multiplication, division and other operations are described by higher order versions of derivative. The work here is presented as important preliminary work related to a nonstandard measure theory of non-definable bounded subsets of a model of Peano arithmetic.

Wos proposed 33 basic research problems for automated reasoning field, one of them is the problem of automated theorem finding. The problem has not been solved until now. The problem implicitly requires some metrics to be used for measuring interestingness of found theorems. We have proposed some metrics to measure interestingness of theorems found by using forward reasoning approach. We have measured interestingness of the theorems of NBG set theory by using those metrics. To confirm the generality of the proposed metrics, we have to apply them in other mathematical fields. This paper presents a case study in Peano’s arithmetic to show the generality of proposed metrics. We evaluate the interestingness of theorems of Peano’s arithmetic obtained by using forward reasoning approach, and confirm the effectiveness of the metrics.

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.

Shepherdson [14] showed that for a discrete ordered ring I, I is a model of I Open iff I is an integer part of a real closed ordered field. In this paper, we consider integer parts satisfying PA. We show that if a real closed ordered field R has an integer part I that is a nonstandard model of PA (or even IΣ4), then R must be recursively saturated. In particular, the real closure of I, RC (I), is recursively saturated. We also show that if R is a countable recursively saturated real closed ordered field, then there is an integer part I such that R = RC(I) and I is a nonstandard model of PA.

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 N5. 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 ℵ0-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.

We present a functional interpretation of Peano arithmetic that uses Godel’s computable functionals and which systematically injects uniformities into the statements of finite-type arithmetic. As a consequence, some uniform boundedness principles (not necessarily set-theoretically true) are interpreted while maintaining unmoved the Π 2 0 -sentences of arithmetic. We explain why this interpretation is tailored to yield conservation results.

We give alternative proofs of results due to Paris and Wilkie concerning the existence of end extensions of countable models of $B\Sigma_{1}$ , that is, the theory of $\Sigma_{1}$ collection.

A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model , i.e., the elementary diagram De () has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a single CD theory T such that every homogeneous model of T has a PA degree.

We establish the following model theoretic characterization of the fragment I¢0+Exp+B§1 of Peano arithmetic in terms of fixed points of automorphisms of models of bounded arithmetic (the fragment I¢0 of Peano arithmetic with induction limited to ¢0-formulae).

We study the arithmetical schema asserting that every eventually decreasing elementary recursive function has a limit. Some other related principles are also formulated. We establish their relationship with restricted parameter-free induction schemata. We also prove that the same principle, formulated as an inference rule, provides an axiomatization of the Σ 2 -consequences of I Σ 1 . Using these results we show that ILM is the logic of Π 1 -conservativity of any reasonable extension of parameter-free Π 1 -induction schema. This result, however, cannot be much improved: by adapting a theorem of D. Zambella and G. Mints we show that the logic of Π 1 -conservativity of primitive recursive arithmetic properly extends ILM . In the third part of the paper we give an ordinal classification of Σ n 0 -consequences of the standard fragments of Peano arithmetic in terms of reflection principles. This is interesting in view of the general program of ordinal analysis of theories, which in the most standard cases classifies Π -classes of sentences (usually Π 1 1 or Π 2 0 ).

Girard’s maxim, that Peano Arithmetic is (best viewed as) a theory of one inductive definition, is re-examined in the light of a weak theory EA(I;O) formalising basic principles of Nelson’s predicative Arithmetic.

This paper is a study of reflection principles in fragments of formal Peano arithmetic and their applications to the comparison and classification of arithmetical theories.

Let M be a model of first order Peano arithmetic (PA) 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.

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.

Let T 0?T 1 denote that each computable function, which is provable total in the first order theory T 0, is also provable total in the first order theory T 1. Te relation ? induces a degree structure on the sound finite Π2 extensions of EA (Elementary Arithmetic). This paper is devoted to the study of this structure. However we do not study the structure directly. Rather we define an isomorphic subrecursive degree structure , and then we study by ubrecursive and computability-theoretic means. Furthermore, we introduce and investigate some operators on the degrees of . These operators corresponds to inferencerules in formal arithmetic. One operator corresponds to the Σ1 collection rule. Another operator corresponds to the Σ1 induction rule.

This chapter introduces Peano Arithmetic and discusses two respects in which it is incomplete.

Within a weak subsystem of second-order arithmetic WKL0, we develop basic part of non-standard analysis up to the Peano existence theorem.

Sentient Arithmetic is defined as an extension of Elementary Arithmetic with three more derivation rules and the Incompleteness Theorems are derived within it without using any metalanguage. It is shown that Consistency cannot be chosen as an axiom

We prove that a necessary and sufficient condition for a countable set of sets of integers to be equal to the algebra of all sets of integers definable in a nonstandard elementary extension of ω by a formula of the PA language which may include the standardness predicate but does not contain nonstandard parameters, is as follows: is closed under arithmetical definability and contains 0(ω) the set of all (Gödel numbers of) true arithmetical sentences.Some results related to definability of sets of integers in elementary extensions of ω are included.

In the last chapter, we considered the theory IΔ 0 built in the language L A , whose axioms are those of Q, plus (the universal closures of) all instances of the Induction Schema for Δ 0 predicates. Now we lift that restriction on induction, and allow any L A predicate to appear in instances of the Schema. The result is (first-order) Peano Arithmetic. Being generous with induction (a) Given what we said in Section 9.1(a) about the motivation for the induction principle, any instance of the Induction Schema will be intuitively acceptable as an axiom, so long as we replace φ in the Schema by a suitable open wff which expresses a genuine property/relation. We argued at the beginning of the last chapter that Δ 0 wffs are eminently suitable, and we considered the theory you get by adding to Q the instances of the Induction Schema involving such wffs. But why should we be so very restrictive? Take any open wff φ of L A at all. This will be built from no more than the constant term ‘0’, the familiar successor, addition and multiplication functions, plus identity and other logical apparatus. Therefore – you might very well suppose – it ought also to express a perfectly determinate arithmetical property or relation. So why not be generous and allow any open L A wff to be substituted for φ in the Induction Schema? The result of adding to Q (the universal closures of) every instance of the Schema is PA – First-order Peano Arithmetic . (b) …

We study elementary second order extensions of the theoryID1 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Π11 comprehension and bar induction without set parameters.

A new method of “minimal” readability is proposed and applied to show that the definable functions of Heyting arithmetic (HA)—functions f such that HA ⊢ ∀x∃!yA(x, y) ⇒ for all m, A(m, f(m)) is true, where A(x, y) may be an arbitrary formula of ℒ(HA) with only x,y free—are precisely the provably recursive functions of the classical Peano arithmetic (PA), i.e., the < ε0-recursive functions. It is proved that, for prenex sentences provable in HA, Skolem functions may always be chosen to be < ε0-recursive. The method is extended to intuitionistic finite-type arithmetic, , and elementary analysis. Generalized forms of Kreisel's characterization of the provably recursive functions of PA and of the no-counterexample-interpretation for PA are consequently derived.

In this paper we study applicative theories of operations and numbers with (and without) the non-constructive minimum operator in the context of a total application operation. We determine the proof-theoretic strength of such theories by relating them to well-known systems like Peano Arithmetic PA and the system (Π∞0-CA)

We prove that in IST, Nelson's internal set theory, the Uniqueness and Collection principles, hold for all (including external) formulas. A corollary of the Collection theorem shows that in IST there are no definable mappings of a set X onto a set Y of greater (not equal) cardinality unless both sets are finite and #(Y) ≤ n #(X) for some standard n. Proofs are based on a rather general technique which may be applied to other nonstandard structures. In particular we prove that in a nonstandard model of PA, Peano arithmetic, every hyperinteger uniquely definable by a formula of the PA language extended by the predicate of standardness, can be defined also by a pure PA formula.

A type of first-order analogues of ptykes, namely ‘ptykoids’, are introduced, and bounds are found for the ptykoids of level 1 and 2 which can be proved to be ptykoids in Peano arithmetic. This gives rise toΠ30 andΠ40 independence results.

We show that that every countable model of PA has a conservative extension M with a subset Y such that a certain Σ1(Y)-formula defines in M a subset which is not r. e. relative to Y.

In this paper the modal operator “x is provable in Peano Arithmetic” is incorporated into first-order theories. A provability extension of a theory is defined. Presburger Arithmetic of addition, Skolem Arithmetic of multiplication, and some first order theories of partial consistency statements are shown to remain decidable after natural provability extensions. It is also shown that natural provability extensions of a decidable theory may be undecidable.

The aim of this paper is to extend the Bass-Milnor-Serre theorem to the nonstandard rings associated with nonstandard models of Peano arithmetic, in brief to Peano rings.First, we recall the classical setting. Let k be an algebraïc number field, and let θ be its ring of integers. Let n be an integer ≥ 3, and let G be the group Sln(θ) of (n, n) matrices of determinant 1 with coefficients in θ.The profinite topology in G is the topology having as fundamental system of open subgroups the subgroups of finite index.Congruence subgroups of finite index of G are the kernels of the maps Sln(θ) → Sln(θ/I) for which all ideals I of θ are of finite index. By taking these subgroups as a fundamental system of open subgroups, one obtains the congruence topology on G. Every open set for this topology is open in the profinite topology.We denote by Ḡ (resp., Ĝ) the completion of G for the congruence (resp., profinite) topology.The Bass-Milnor-Serre theorem [1] consists of the two following statements:(A) If k admits a real embedding, then we have an exact sequenceThat is, Ĝ and Ḡ are isomorphic.(B) If k is totally imaginary, then one has an exact sequencewhere μ(k)is the group of the roots of unity of k.

Feferman, S. and G. Jäger, Systems of explicit mathematics with non-constructive μ-operator. Part I, Annals of Pure and Applied Logic 65 (1993) 243-263.This paper is mainly concerned with the proof-theoretic analysis of systems of explicit mathematics with a non-constructive minimum operator. We start off from a basic theory BON of operators and numbers and add some principles of set and formula induction on the natural numbers as well as axioms for μ. The principal results then state: (i) BON(μ) plus set induction is proof-theoretically equivalent to Peano arithmetic PA; (ii) BON(μ) plus formula induction is proof-theoretically equivalent to the system (Π0∞-CA)

Biro, 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 (1993) 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.

A common foundation of finite arithmetic, hereditarily finite sets and sequences, binary trees and graphs is described as a progressive refinement of Haskell type classes.We derive as instances symbolic implementations of arithmetic operations in terms of rooted ordered trees representing hereditarily finite sets and sequences. Conversely, arithmetic implementations of pairs, powersets, von Neumann ordinals shade new light on the bi-interpretability between Peano arithmetic and a theory of hereditarily finite sets.As another instance, rooted ordered binary trees representing a simplified form of the type language of Goedel's System T are shown as directly emulating arithmetic and finite set operations.The main contribution of the paper is a fully constructive unification of paradigms - a chain of type classes does it all: Peano arithmetic, sets, sequences, binary trees, bitstrings. Another contribution is that we do it "efficiently" (i.e. in time and space asymptotically comparable with standard binary representations).The Haskell code in the paper is available at http://logic.cse.unt.edu/tarau/research/2010/shared.hs.

Starting from an executable "shared axiomatization" of a number of bi-interpretable theories (Peano arithmetic, hereditarily finite sets and functions) we introduce generic algorithms that can be instantiated to implement the usual arithmetic operations in terms of (purely symbolic) hereditarily finite constructs, as well as the type language of Godel's System T. The Haskell code in the paper is available at http://logic.cse.unt.edu/tarau/research/2010/short_shared.hs.

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.

We consider iterations of satisfaction classes and apply them to construct expansions of models of Peano arithmetic to models of A|Δ+∑-AC. 1991 MSC: 03F35, 03C62.

In a recent paper, Kaye and Wong proved the following result, which they considered to belong to the folklore of mathematical logic. THEOREM: The first-order theories of Peano arithmetic and ZF with the axiom of infinity negated are bi-interpretable: that is, they are mutually interpretable with interpretations that are inverse to each other. In this note, I describe a theory of sets that stands in the same relation to the bounded arithmetic IDelta0 + exp. Because of the weakness of this theory of sets, I cannot straightforwardly adapt Kaye and Wong's interpretation of arithmetic in set theory. Instead, I am forced to produce a different interpretation., 12 pages; section on omega-models removed due to error; references added and typos corrected

The complexity class of ***-bounded local search problems with goals is introduced for well-orderings ***, and is used to give a characterisation of definable NP search problems in Peano Arithmetic.

Kruskal proved that finite trees are well-quasi-ordered by hom(e)omorphic embeddability. Friedman observed that this statement is not provable in predicative analysis. Friedman also proposed (see in [Simpson]) some stronger variants of the Kruskal theorem dealing with finite labeled trees under hom(e)omorphic embeddability with a certain gap-condition, where labels are arbitrary finite ordinals from a fixed initial segment of ω. The corresponding limit statement, expressing that for all initial segments of ω these labeled trees are well-quasi-ordered, is provable in -CA, but not in the analogous theory -CA0 with induction restricted to sets. Schütte and Simpson proved that the one-dimensional case of Friedman's limit statement dealing with finite labeled intervals is not provable in Peano arithmetic. However, Friedman's gap-condition fails for finite trees labeled with transfinite ordinals. In [Gordeev 1] I proposed another gap-condition and proved the resulting one-dimensional modified statements for all (countable) transfinite ordinal-labels. The corresponding universal modified one-dimensional statement UM1 is provable in (in fact, is equivalent to) the familiar theory ATR0 whose proof-theoretic ordinal is Γ0. In [Gordeev 1] I also announced that, in the general case of arbitrarily-branching finite trees labeled with transfinite ordinals, in the proof-theoretic sense the hierarchy of the limit modified statements M (which are denoted by LMλ in the present note) is as strong as the hierarchy of the familiar theories of iterated inductive definitions (more precisely, see [Gordeev 1, Concluding Remark 3]). In this note I present a “positive” proof of the full universal modified statement UM, together with a short proof of the crucial “reverse” results which is based on Okada's interpretation of the well-established ordinal notations of Buchholz corresponding to the theories of iterated inductive definitions. Formally the results are summarized in §5 below.

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

Transreal arithmetic is a total arithmetic that contains real arithmetic, but which has no arithmetical exceptions. It allows the specification of the Universal Perspex Machine which unifies geometry with the Turing Machine. Here we axiomatise the algebraic structure of transreal arithmetic so that it provides a total arithmetic on any appropriate set of numbers. This opens up the possibility of specifying a version of floating-point arithmetic that does not have any arithmetical exceptions and in which every number is a first-class citizen. We find that literal numbers in the axioms are distinct. In other words, the axiomatisation does not require special axioms to force non-triviality. It follows that transreal arithmetic must be defined on a set of numbers that contains{-∞,-1,0,1,∞,p} as a proper subset. We note that the axioms have been shown to be consistent by machine proof.

Frege Arithmetic (FA) is the second-order theory whose sole non-logical axiom is Hume's Principle, which says that the number of Fs is identical to the number of Gs if and only if the Fs and the Gs can be one-to-one correlated. According to Frege's Theorem, FA and some natural definitions imply all of second-order Peano Arithmetic. This paper distinguishes two dimensions of impredicativity involved in FA—one having to do with Hume's Principle, the other, with the underlying second-order logic—and investigates how much of Frege's Theorem goes through in various partially predicative fragments of FA. Theorem 1 shows that almost everything goes through, the most important exception being the axiom that every natural number has a successor. Theorem 2 shows that the Successor Axiom cannot be proved in the theories that are predicative in either dimension.

In this chapter, we answer two fundamental questions concerning the formalization of arithmetic and give a characterization of recursive functions in a logical framework. A possible axiomatization of arithmetical properties is given by Peano’s axioms. The first important question concerning this theory is its decidability: is there an algorithm to determine whether an arithmetical first-order property is provable in Peano arithmetic?