One point though: Godel-numbering is in the meta-theory, but we want to know why we need multiplication in the object theory. But, if I'm not mistaken, we need that it is representable in the object theory; I'd have to study the proof again. — TonesInDeepFreeze

Yes, I understand that it's a part you need in Gödel-numbering, to make the number that holds the logical sentence. Once you have both addition and multiplication, you can do what Gödel did. With Presburger Arithmetic the completeness is lost if you take into account also multiplication:

adding, for example, the multiplication function x: Z^2 -> Z(or even simply the ‘squaring’ function, from which multiplication is easily recovered) to Presburger arithmetic immediately results in undecidability, thanks to Gödel’s incompleteness theorem

(see On the Decidability ofPresburger Arithmetic Expanded with Powers)

But then I also found an interesting answer on StackExchange, which seems very interesting, an answer to the question "Why does multiplication lead to incompleteness where addition does not?":

The issue is not about multiplication per se, or even about the combination of addition and multiplication. The theory of Real Closed Fields has both, and is consistent and complete. The issue is about the strength of induction.

The induction axioms in Presburger arithmetic are the first order approximation of the Peano axiom, and basically do not allow for establishing facts about other facts that have, themselves, to be established inductively.

You cannot get real recursion off the ground unless you have a second order theory of counting, that allows you to represent the sets of integers for with the results are already established.

So to get a first order theory to start doing Gödel's proof, you have to bring in either infinitely many facts about addition, which are needed to establish the relevant results about multiplication, or a few facts about multiplication, itself, as additional axioms.

(See here)

I find this interesting. With real recursion I assume means recursion of real numbers. Well, if you have real numbers, then you're hopelessly mired in the notion of infinity and infinite sequences and so on. With mathematical induction, we get to questions about infinity.

Don't understand that quote. But comments that might be on target:

(1) "given complete induction. Unfortunately Peano's axiom of induction is not fully reducible to a collection of first-order statements."

I guess by 'complete induction' he means induction over all properties (i.e. a second order theory). And, yes, the PA induction schema is over only formulas. But the induction schema does define a set of first order sentences.

But I guess 'Peano's axiom of induction' refers to a second order axiom, not the first order PA axiom schema.

(2) The theory of real closed fields doesn't define the predicate 'is a natural number' (I hope I've stated that correctly).

(3) What do you mean by 'recursion of the reals'? Recursion requires well ordering.

What do you mean by 'recursion of the reals'? Recursion requires well ordering. — TonesInDeepFreeze

From the quote, the only difference between recursion and real recursion, that I can think of, is using recursion for reals, in other words recursive real numbers: "A recursive real number may be described intuitively as one for which we can effectively generate as long a decimal expansion as we wish, or equivalently, to which we can effectively find as close a rational approximation as we wish."

Because I don't think there's real recursion and "phony" unreal recursion.

Thanks for the comments!

real recursion — ssu

He might have meant something parallel to the distinction between first order induction and second order induction that he seemed to be mentioning, so that 'real induction' is second order and so too for 'real recursion'. But that would only be a guess.

recursive real numbers — ssu

That is not recursion over the reals. A recursive real r is such that there is a recursive function f on the naturals such that for each n, f(n) is the nth digit in the decimal expansion of r. That's still recursion over the naturals. I highly doubt that 'recursive real' is what he meant in this context. I think you're hearing hoofbeats in wild horse country and thinking zebras rather than horses.

Better deep in knowledge and shallow in misunderstanding. Better deep in love and shallow in hate. — TonesInDeepFreeze

Choke me in the shallow water before I get too deep. -- Edie Brickell.

Then you're discussing with the wrong person. — TonesInDeepFreeze

I have some darned fine conversations with myself.

You may prefer whatever you want; there's no need for forgiveness for preferring whatever you like; meanwhile, I prefer to show how you are wrong in saying that 'true' is not defined entirely with the notion of interpretations and not the notion of axioms. — TonesInDeepFreeze

You are free to do so, of course.

I have some darned fine conversations with myself. — fishfry

So did Bill Evans.

So did Bill Evans. — TonesInDeepFreeze

Help me out. The jazz player?

The albums 'Conversations With Myself' and 'Further Conversations With Myself'.

Second order recursion sounds indeed more logical.

It's only my guess as to what he might mean. I've never heard of second order recursion or what it might be, though it seems like something that might exist.

The albums 'Conversations With Myself' and 'Further Conversations With Myself'. — TonesInDeepFreeze

Thank you. "Today I learned."

Anytime you want jazz album recommendations, just ring.

Jazz is one thing I know a lot about, unlike logic.

Anytime you want jazz album recommendations, just ring. — TonesInDeepFreeze

Ok!

Jazz is one thing I know a lot about, unlike logic. — TonesInDeepFreeze

Haha very humble of you.

unlike logic. — TonesInDeepFreeze

Confession is the road to redemption. Nice start!

Theologician, redeem thyself.

very humble of you. — fishfry

Half is humble, since my knowledge of modern logic is not extensive relative to people who study it a lot more intensely (though vastly greater than cranks and jokers - such as in this forum - who know don't know jack about it). And I've forgotten a lot of what I knew and am rusty on many details and more advanced topics. Also, in the last couple of weeks, very atypically, I made not just one or two reasoning errors but a series of them, though I exercised intellectual honesty to correct them. The other half is not humble since I do have a well developed perspective on jazz - technically, historically, discographically - and a well developed taste in it and an intense emotional and spiritual connection with it, though there are people who know a tremendous amount more than me.