Search

Publisher Summary This chapter discusses the witness function method and provably recursive functions of Peano arithmetic. The witness function method is used with great success to characterize some classes of the provably total functions of various fragments of bounded arithmetic. It is shown that the witness function method can be applied to the fragments I∑n of Peano arithmetic to characterize the functions that are provably recursive in these fragments. This characterization of provably recursive functions are performed by a variety of methods; including Gentzen's assignment of ordinals to proofs with the Godel Dialectica interpretation and by model-theoretic methods. They provide a simple, elegant, and purely proof-theoretic method of characterizing the provably total functions of I∑n, and secondly, they unify the proof methods used for fragments of Peano arithmetic and for bounded arithmetic. The witness function method is related to the classical proof-theoretic methods of Kleene's recursive realizability, Godel's Dialectica interpretation, and the Kreisel no-counterexample interpretation. The witness function method provides an advantage over the other methods in that it leads to a more direct and intuitive understanding of many formal systems.

Publisher Summary 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.

We study properties of the natural order and the order of divisibility in arithmetic. After a brief survey of some classical results on end-extensions and cofinality for non-standard models of Peano arithmetic, we look at the incompleteness of arithmetic and present the undecidability of Th(IN, S, ) and several related theories. Next we discuss saturation: in particular a model is saturated if and only if one of its order structures is saturated. Then, we give a survey, new proofs and new results of the definability of arithmetic as a theory of two orders and answer two questions of J. ROBINSON. Resume Nous etudions des proprietes de l'ordre naturel et de l'ordre de divisibilite en arithmetique. Apres un bref survol de resultats classiques sur les extensions finales et cofinales des modeles non-standards de l'arithmetique de Peano, nous passons a l'incompletude de celle-ci et a l'indecidabilite de Th (IN, S, ) et de plusieurs autres theories. Ensuite nous parlons de saturation: en particulier un modele est sature si et seulement si l'une de ces deux structures d'ordre l'est. Nous terminons par une synthese, avec de nouvelles preuves et de nouveaux resultats, sur la definissabilite de l'arithmetique comme theorie de deux ordres et repondons a deux questions de J. ROBINSON.

Publisher Summary This chapter discusses the core structures of Peano arithmetic. If T is a theory in a first-order language L, it is said that an L-structure M is a core structure for T if M is uniquely embeddable in every model of T. Let L = {0, l, +, } be the usual language for arithmetic and P be the Peano axioms formulated in L. The standard model N of arithmetic is a core structure for P and is the only such structure. If T is a complete extension of P and M ≅ P, then the substructure M' of M with domain those elements of M that are point wise definable by an existential formula is easily seen to be a core structure for T, and M' may be non-standard. The chapter discusses the viability of finite consistent extension of P with a non-standard core structure.

A system ALPO of set theory is presented and proved to form a conservative extension of Peano arithmetic. The system has sufficient strength to allow a very substantial amount of analysis to be directly formalized, including Lebesgue integration theory, without resorting to wholesale padding of objects with extra information.

Publisher Summary This chapter introduces notion of definability in an arbitrary formalized theory T; more specifically, it explains under what condition a function on and to the natural numbers, or a set of natural numbers, is said to be definable in T. It shows that there is no consistent theory T in which a certain function D (the diagonal function) and a certain set V (the set of numbers correlated with valid sentences of T) are both definable. Hence, under some additional, though still very general assumptions, every consistent theory in which all recursive functions are definable is essentially undecidable. These results can serve as a general theoretical basis for the direct method in proofs of undecidability. The chapter also describes the formalized arithmetic N of natural numbers and some of its axiomatic subtheories—P, Q, and R. P is Peano's arithmetic; Q is a subtheory of P based upon a system of seven simple axioms; Ris a subtheory of Q with a very weak, though infinite, axiom system.

This chapter describes the natural number. It presents an economical collection of axioms. The chapter initiates the construction of a system of real numbers, with a consideration of a set. These axioms were developed by the Italian mathematician Peano, and are consequently called “Peano's postulates.” It could be shown that every set might be well-ordered (Zermelo's theorem); this result requires the addition of another axiom to those of set theory. Zermelo's theorem is equivalent to the axiom of choice.

Publisher Summary This chapter discusses how the properties of local functions can be used to get results concerning models of Peano's arithmetic. The concept of a local relation (or function) is defined. The basic property of these functions is that the recursive definition, which defines their iteration, can be formalized in Peano's arithmetic, a property that does not hold for arithmetical functions whose arguments and values are sets of natural numbers. This property is proved in the chapter. It is shown how the results of the property can be employed to get certain types of elements with respect to the theory of Peano's arithmetic. The concept was used to get results concerning measurable cardinals, the proof of which involved iterating a function whose arguments and values were proper classes. The chapter outlines some of the results concerning models and types of Peano's arithmetic, which are made possible through the use of local functions.

Publisher Summary The chapter discusses Peano's axioms and models of arithmetic and presents, how models of a similar kind can be set up in a perfectly constructive way when some very restricted arithmetical theories are considered. The chapter also presents remarks on the setting up of models of certain fragments of number theory—in particular, fragments of recursive arithmetic. In these simple cases the definition of nonstandard models are established in a perfectly constructive way.