Primitive recursive function/Talk

Comments on previous changes:

1. the initial set of X: they are axioms, not functions or terms. they are statements.
2. successor: you had better not use + in the definition. we haven't defined addition.
3. projection: the s suffix on words makes things plural.
4. p.r. versus primitive recursive: I personally think it was nicer with the abbreviation, but it's not a strong opinion.

I spent a lot of time in crafting this page. Please do me the courtesty of investing a similar degree of effort in your changes. --Wmorgan

Regarding number 2: I was assuming knowledge of the natural numbers and their addition. If you want to assume only Peano's axioms and start everything from there, you should link to the Peano axioms and not to "natural number line". Or do you want to start from a primitive, "geometric" understanding of the natural number line? --AxelBoldt

I think you have a point that "natural number line" does presuppose some ideas which I shouldn't assume are defined at this point. But certainly as addition is defined later on in the page I think it would be safest not to use it explicitly quite yet. Actually I'm a bit unclear as to whether the Peano postulates should be assumed or not. The textbook that I have on this subject (Epstein & Carnelli) uses the phrase "that number which follows n in the natural number series". Thoughts?

(BTW in rereading my comments above I come off as fairly obnoxious. That wasn't my intention, so please accept my apologies.)

And one last comment... I think I will change the definition of the set of p.r. functions to an inductive one rather than using terms like "smallest" and "closed", as upon further study, the latter, taken in the set-theoretic sense, presupposes infinite classes of functions, whereas with the former we can stay safely away from the i- word. --Wmorgan

You need at least the Peano axioms; otherwise you cannot talk about natural numbers in any meaningful way. I would probably not even bother; just mention the natural numbers, link to them, and be done with it. Then later show that the "intuitive addition" of natural numbers can be defined as a p.r. function. Everybody knows the natural numbers (or they think they do).

Also, a nice example of a p.r. function would be f(x,y) = 1 if x < y and 0 if x ≥ y. And maybe a typical function that's recursive but not p.r. --AxelBoldt