Re: A recursion axiom for N?

On Mar 29, 8:26 pm, hru...@xxxxxxxxxxxxxxxxxxxx (Herman Rubin) wrote:
In article <0a6ef43d-a1e0-4b6a-92cb-6f7817546...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Dan Christensen  <Dan_Christen...@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.

Thanks again, Herman!

From a pedagogical perspective, simple sounds good. As a fallback
position, I have been presenting addition and multiplication as
"definitions" apart from PA in my program. I see that Peano himself
originally included recursive "defintions" of addition and
multiplication (really axioms) in his seminal paper. Perhaps I should
consider doing the same.

Dan
Download my DC Proof software at http://www.dcproof.com




 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
hru...@xxxxxxxxxxxxxxx         Phone: (765)494-6054   FAX: (765)494-0558

.

Relevant Pages

  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... axiom replaces Peano's 5 axioms.) ... I prove theorems of Godel, Rosser, Turing, Smullyan and you say I ... that you trumpet it to be, not simply its application to recursion ... Every number has a successor number: For every N printed in line 2, ...
    (sci.logic)
  • 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: Godel proved maths inconsistent not incompleteness theorem
    ... Perhaps if you answered the following for CBL: ...   it is recursive. ... represented by the elements of the universal set and one of the axioms ... Recursion Theory doesn't use a set theory, ...
    (sci.logic)
  • Re: A recursion axiom for N?
    ... needs a stronger version of induction to do so." ... it, "It's valid using some basic axioms of set theory, or some basic ... recursion is defined in this system, ...
    (sci.math)
  • Re: incompleteness and inconsistency
    ... can one say in behalf of the idea induction on infinite ordinals as ... I don't understand how we can be finitistic using induction ... recursion are finitistically kosher. ... as having *infinitistic* set theory at our disposal. ...
    (sci.logic)