Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
Everand Logo

Welcome to Everand!

  • Discover millions of ebooks, audiobooks, and so much more with a free trial

    From $11.99/month after trial. Cancel anytime.

    Recursive Analysis
    Recursive Analysis
    Recursive Analysis
    Ebook211 pages1 hour

    Recursive Analysis

    By R. L. Goodstein

    ()

    Read preview

    About this ebook

    Recursive analysis develops natural number computations into a framework appropriate for real numbers. This text is based upon primary recursive arithmetic and presents a unique combination of classical analysis and intuitional analysis. Written by a master in the field, it is suitable for graduate students of mathematics and computer science and can be read without a detailed knowledge of recursive arithmetic.
    Introductory chapters on recursive convergence and recursive and relative continuity are succeeded by explorations of recursive and relative differentiability, the relative integral, and the elementary functions. A final chapter examines transfinite ordinals, and the text concludes with a helpful appendix of topics related to recursive irrationality and transcendence.
    LanguageEnglish
    PublisherDover Publications
    Release dateJan 23, 2013
    ISBN9780486158150
    Recursive Analysis

    Related to Recursive Analysis

    Titles in the series (100)

    View More
    View More

    Related ebooks

    Mathematics For You

    View More
    View More

    Related podcast episodes

    Related articles

    • UNLIMITED

      Why Mathematicians Should Stop Naming Things After Each Other

      Sep 2, 2020

      Any student of modern math must know what it feels like to drown in a well of telescoping terminology. For a high-profile example, let’s take the Calabi-Yau manifold, made famous by string theory. A Calabi-Yau manifold is a compact, complex Kähler ma

      6 min read

    • UNLIMITED

      Stellar Archaeology

      Jun 3, 2020

      Stellar Archaeology
      10 min read

    • UNLIMITED

      How Did We Get The Constellations?

      Oct 12, 2022

      How Did We Get The Constellations?
      3 min read

    • UNLIMITED

      How Dark Energy Behaves

      Sep 5, 2024

      How Dark Energy Behaves
      1 min read

    • UNLIMITED

      Euclid as Founding Father: We hold this mathematics to be self evident.

      Oct 13, 2016

      Despite the man’s awkward gestures, unkempt hair, and ill-fitting suit, it was one of the most extraordinary speeches that Reverend John Gulliver had ever heard. It was March 1860, and the venue was Norwich, Connecticut. The following morning Gullive

      8 min read

    • UNLIMITED

      This Philosopher Helped Ensure There Was No Nobel for Relativity: Henri Bergson’s debate with Albert Einstein reached and swayed the 1921 Nobel committee.

      Apr 21, 2016

      On April 6, 1922, Einstein met a man he would never forget. He was one of the most celebrated philosophers of the century, widely known for espousing a theory of time that explained what clocks did not: memories, premonitions, expectations, and antic

      12 min read

    • UNLIMITED

      Physicists Attack Math’s $1,000,000 Question

      Apr 4, 2017

      Physicists are attempting to map the distribution of the prime numbers to the energy levels of a particular quantum system.

      4 min read

    • UNLIMITED

      The Rhythm of Sculpture

      Jun 28, 2018

      This article is part of Nautilus’ month-long exploration of the science and art of time. Read the introduction here. In the studio, time does not pass—there is only an “eternal now.” The art coming from the studio is a crystallized form of the artist

      3 min read

    • UNLIMITED

      A Universe Made of Tiny, Random Chunks: The space-time that makes up our universe is inherently uncertain.

      Jun 6, 2013

      One of science’s most crucial yet underappreciated achievements is the description of the physical universe using mathematics—in particular, using continuous, smooth mathematical functions, like how a sine wave describes both light and sound. This is

      6 min read

    • UNLIMITED

      The Deepest Uncertainty

      May 16, 2019

      Georg Cantor died in 1918 in a sanatorium in Halle, Germany. A pre-eminent mathematician, he had laid the foundation for the theory of infinite numbers in the 1870s. At the time, his ideas received hostile opposition from prominent mathematicians in

      4 min read

    • UNLIMITED

      How to Build a Search Engine for Mathematics: The Surprising Power of Neil Sloane’s Encyclopedia of Integer Sequences.: The surprising power of Neil Sloane’s Encyclopedia of Integer Sequences.

      Oct 22, 2015

      On the average summer Saturday, the mathematician Neil Sloane woke up to a crisis. “There are always crises,” he said— albeit crises of the teapot tempest variety. One Saturday over breakfast, he faced an inbox message titled “edits from outer space.

      10 min read

    • UNLIMITED

      A Supermassive Lens On The Constants Of Nature

      Nov 25, 2020

      The 2020 Nobel Prize in Physics went to three researchers who confirmed that Einstein’s general relativity predicts black holes, and established that the center of our own galaxy houses a supermassive black hole with the equivalent of 4 million suns

      9 min read

    Related categories

    Reviews for Recursive Analysis

    0 ratings

    0 ratings0 reviews

    What did you think?

    Tap to rate

    Review must be at least 10 words

      Book preview

      Recursive Analysis - R. L. Goodstein

      INDEX

      CHAPTER I

      RECURSIVE CONVERGENCE

      Primitive and general recursive functions. Recursive arithmetic and its extensions. Recursive convergence and relative convergence.

      The reduced sequence. Recursive limits and tests for recursive convergence. Primitive and general recursive real numbers.

      1 Recursive analysis is a free variable theory of functions in a rational field, founded on recursive arithmetic. It involves no logical presuppositions and proceeds from definition to theorem by means of derivation schemata alone.

      The elementary formulae of recursive arithmetic are equations between terms, and the class of formulae is constructed from the elementary formulae by the operations of the propositional calculus. The terms are the free numeral variables, the sign 0 and the signs for functions. The function signs include the sign S(x) for the successor function (so that S(x) plays the part of x+ 1 in elementary algebra) and signs for functions introduced by recursion. The derivation rules are taken to be sufficient to establish the universally valid sentences of the propositional calculus, and include a schema permitting the substitution of terms for variables, the schema for equality

      a=b → {A (a) → A (b)},

      and the induction schema

      the schemata for explicit definition of functions for any number of arguments, and finally schemata for definition by recursion. The simplest definition schema for recursion, the schema of primitive recursion, is

      f(0, a) = α(a), f(S(n), a) = β(n, a, f(n, a)).

      Specifically this schema defines f(n, a) by primitive recursion from the functions α and β. We take as initial primitive recursive functions the successor function S(x), the identity function I(x), defined explicitly by the equation I(x) = x, and the zero function Z(x) defined by Z(x) = 0. A function is said to be primitive recursive if it is an initial function or is defined from primitive recursive functions by substitution or by primitive recursion.

      1,1 In this work we shall be principally concerned with primitive recursive functions. Without changing the character of the system we shall build, the class of functions could be enlarged to include for instance multiply recursive functions at the present state of knowledge). The system could not however be enlarged to admit the class of functions which has played so important a part in foundation researches, the class of quasi- (or general) recursive functions, without changing the character of the system entirely. A quasi-recursive function is defined by a system of equations (on the right hand sides of which we may suppose only numerals or primitive recursive functions appear) from which, by substitution, the value of the defined function may be derived for each assigned set of values of the arguments. The left-hand side of the equations may contain, however, in addition to the function being defined, auxiliary functions, about which we may have only incomplete information. Consider for instance the set of equations ¹

      where

      is a primitive recursive function for which (in some sense which remains to be considered) it is known that for each x there is a y for which x(x, y) = 0. Then these equations define f (x) as a quasi-recursive function. To show this we have to consider the way in which the values of f (x) may be derived from the equations. For the purpose of illustration let us suppose that for some given value of x, say x= 3, the first value of y for which x(x, y) vanishes is y = 7. Then, keeping x = 3, we see that

      π(3,0), π(3, 1), π(3, 2), ..., π(3, 7)

      are all greater than zero, but π(3, 8)=0. The auxiliary function τ(u, v, y) is defined only for values of u greater than zero and for v = 0 ; thus f (3) can be evaluated only when we find a y for which π(x, y) > 0 and π(x, Sy) = 0 and, as we have supposed, this occurs when y = 7 (and not for any other value of y), showing that f(3) = 7. This illustrates the fact that to determine the value of f(x), we must first find the value of y for which χ(x, y) = 0.

      In the definition of a quasi-recursive function no limitation is imposed upon the way in which we show that, for each x, there is a y for which χ(x, y)=0; we may for instance establish the existence of y by a proof in some formal system that the assumption that χ(x, y) > 0 for all y leads to a contradiction. Such a proof may provide us with no means of finding the y in question and therefore no means of finding f(x); we may go on calculating the values of χ(x, y) for greater and greater values of y for untold time without finding the y for which χ(x, y) = 0. By confining our considerations to primitive recursive functions we are assured that the values of all functions in the system may be determined in a preassignable number of steps.

      The most appropriate system for utilising quasi-recursive functions would be, not a free variable system, but one which contained an existential operator "∃ and a minimal operator μ" which selected the least of a given set of values. From an existential theorem

      (∃y) R(x, y)

      the minimal operator derives a function f(x) such that

      f(x) = (μy) R(x, y).

      If R(x, y) is a primitive recursive relation then f (x), defined by the minimal operator may be shown to be quasi-recursive; in fact the system of equations considered above is an instance of this. For future reference we list some further important properties of quasi-recursive functions and relations. ²

      There is a primitive recursive function T(z, x, y) such that for z = 0, 1, 2, ..., (∃y)T(z, x, y) is an enumeration of all predicates of the form (∃y)R(x, y) with recursive R. It follows that the class of predicates of the form (∃y)R(x, y) is the same whether R is quasi-recursive, or restricted to primitive recursive relations.

      For any given R let r be a value of z for which

      (∃y)R(x, y)↔(∃y)T(r, x, y)

      (where ↔denotes equivalence of relations) and therefore

      (∃y(R(r, y)↔(∃y)T(r, r, y)

      and therefore (∃y)R(r, y) is not equivalent to (y) ∼ T(r, r, y), and (taking ∼ S for R, and s for r)

      (y)S(s, y) ↔(y) ∼ T (s, s, y)

      so that

      (y)S(s, y) is not equivalent to (∃y)T(s, s ,y).

      Given any quasi-recursive predicate R(x) let R(x, y) denote the predicate R(x) & y= y so that R(x, y) is also quasi-recursive and

      R(x)↔ (∃y)R(x, y)↔ (y)R(x, y)

      whence it follows that there are numbers r, s for which

      R(r) differs from (y) ∼ T(r, r, y)

      and

      R(s) differs from (∃y)T(s, s, y)

      and therefore, neither(∃y)T(x, x, y) nor (y) ∼T(x, x, y) are recursive. In other words (∃y)T(x, x, y) is an example of a predicate of the form (∃y)R(x, y), with primitive recursive R, which is not quasi-recursive.

      Another important enumeration theorem runs as follows:

      For a certain primitive recursive function U(t) all quasi-recursive functions (of one variable) may be enumerated in the form

      U(µy T(n, x, y)), n = 0, 1, 2, ...

      and with the same U, and a corresponding T(n, x1, x2, ..., xk, y) all quasi-recursive functions of k variables may be enumerated in the form

      U(µy T(n, x1, x2, ..., xk, y)), n = 0, 1, 2, ...

      To return to primitive recursive functions we may remark that there are many definition schemata which though seemingly very different from that of primitive recursion are known to define only primitive recursive functions. We shall not enter into a consideration of these schemata here but we shall have occasion in the sequel to note instances of such schemata. For an account of the forms of recursive definition reference may be made to the author’s ‘Recursive Number Theory’ where it is shown that recursive arithmetic may be formalised in a system in which the axioms of the propositional calculus and the derivation schemata referred to above are all demonstrable.

      1, 2 The development of recursive analysis from recursive arithmetic involves the introduction of rational numbers and functions. A rational number may be defined to be an ordered triplet (p, q)/r, of natural numbers, with r > 0.

      We define

      where ‘↔’ is the sign for equivalence; thus for instance the equation (p, q)/r = (p′, q′)/r′ holds if, and only if, pr′ + q′r = p′r + qr′, and in particular (p, q)/r=(kp+n, kq+n)/kr, where k>O.

      A recursive function of one (or more) variables (p, q)/r is a triplet of recursive functions of natural numbers

      {P(p, q, r), Q(P q, r)}/R(p, q, r)

      with R(p, q, r) > 0, and such that (writing P for P(p, q, r), P′ for P( p′, q′, r′ ) and so on)

      (p′, q′)/r′= (p, q)/r → (P′, Q′)/R′= (P, Q)/R.

      For example the sum of two rational numbers is defined by

      (p1 q1)/r1 + (p2, q2)/r2 = (pir2 + P2r1,, q1r2 + q2r1)/r1r2;

      if

      (p1, q1)/r1

      Enjoying the preview?
      Page 1 of 1