Re: A recursion axiom for N?

In article <0a6ef43d-a1e0-4b6a-92cb-6f7817546337@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Dan Christensen <Dan_Christensen@xxxxxxxxxxxx> wrote:
After having shelved the problem for a few years, I am back to the
problem of proving the existence of recursively defined functions on
N, e.g. the "definition" of addition that is usually given:

1. For all x e N, x+1=3Dx'
2. For all x, y e N, x+y'=3D(x+y)'

Herman Rubin (Perdue University) has commented here (November 1, 2006)
that the existence of these functions does not follow from PA: "One
needs a stronger version of induction to do so."

From "The Dedekind /Peano Axioms" by D. Joyce, we have:

Defining functions by induction, also called recursion. Dedekind and
Peano both accepted the principle of mathematical induction for
defining functions on the natural numbers N. Both gave arguments that
this method should work based on intuitive properties of functions on
sets. We'll assume that the recursive definition of functions is
valid. It is possible to show that it='s valid using some basic axioms
of set theory, or some basic assumptions of logic, but we won't go
into that here. Alternatively, this property could be stated as an
axiom for N.

To define a function f : N --> S from the natural numbers to a set S,
it is only necessary to (1) say what element a of S that f(1) should
be, and (2), say what f(n0) should be in terms of n and f(n). In other
words, if (1) a is a specified element of S, and (2) g : N : S --> S
is a function that is already defined that takes two arguments, a
number k and an element s of S, and yields an element g(k, s) of S,
then the new function f can be defined recursively by the two
equations

(1). f(1) = a, and
(2). f(n') = g(n, f(n)).

There are, as you can imagine, variants of recursive definition just
as there are variants of mathematical induction. The one just
mentioned isn't the simpest or the strongest, but it's good enough to
use for many definitions.

Source: http://aleph0.clarku.edu/~djoyce/numbers/peano.pdf

My question to readers here, can it really be shown that, as Joyce put
it, "It's valid using some basic axioms of set theory, or some basic
assumptions of logic," or must I introduce another axiom in addition
to PA for the natural numbers?

Dan

One can either add the axiom of recursive computation, or
more simply one can assume that there are addition and
multiplication functions satisfying the properties. With
those, the Chinese Remainder Theorem is enough to get the
rest of inductive evaluation.

Without this, one can prove that, for every x, y, x+y and
x*y are defined, but not that the functions + and * are
defined. This subtle point seems to have escaped the
early workers in the field.

Using the ZF axioms for set theory, it can be shown that
the integers defined as the intersection of all inductive
sets satisfies the Peano axioms, and furthermore, ordinal
recursion is defined in this system, which allows for the
definition of the addition and multiplication functions.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@xxxxxxxxxxxxxxx Phone: (765)494-6054 FAX: (765)494-0558
.

Relevant Pages

  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... to me as to the purpose of your question about set theory that I ... matter, the CBL axioms). ... Turing only uses one base, Turing Machines, while Logic uses at least ... theorem, recursion theorem, double recursion theorem and others. ...
    (sci.logic)
  • Re: infinitely many nns = infinite nns?
    ... What is wrong with Phil studying set theory? ... I'll agree but with one caveat: Phil wants to prove induction, ... or actual infinity would LEGITIMATELY arise. ... Since I presented those axioms 4 times and Phil ...
    (sci.logic)
  • Re: Well Ordering the Reals
    ... >>>Induction is stated axiomatically by Peano and used without regard to the ... then there must be some principle of set theory ... of the set of natural numbers and the axioms of set theory. ... > According to the inductive axiom, but the naturals are not *defined* to be ...
    (sci.math)
  • Re: A recursion axiom for N?
    ... Defining functions by induction, also called recursion. ... it, "It's valid using some basic axioms of set theory, or some basic ...
    (sci.math)
  • Re: Question about induction
    ... induction are equivalent. ... their logic - like their set theory - fairly naively. ... and the comprehension schema as axioms. ... the principle of mathematical induction are provably equivalent in T. ...
    (sci.math)