wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        general >> truth >> Peano & Godel
        
(Message started by: Mickey1 on Dec 28^th, 2010, 7:08am)

Title: Peano & Godel
Post by Mickey1 on Dec 28^th, 2010, 7:08am

Let's look at the Axioms (copied from Wikipedia) once more:

1. 0 is a natural number.
2. For every natural number x, x = x.
3. For all natural numbers x and y, if x = y, then y = x.
4. For all natural numbers x, y and z, if x = y and y = z, then x = z.
5. For all a and b, if a is a natural number and a = b, then b is also a natural number.
6. For every natural number n, S(n) is a natural number.
7. For every natural number n, S(n) = 0 is False. That is, there is no natural number whose successor is 0.
8. For all natural numbers m and n, if S(m) = S(n), then m = n.
9. If K is a set such that:
- 0 is in K, and
- for every natural number n, if n is in K, then S(n) is in K, then K contains every natural number.

Are these axioms actually axioms or are they a definition of the natural numbers?

Alternative 1
Let us assume they define the natural numbers. In that case they can easily be proved by a simple reference to the definitions.

Alternative 2
We intuitively understand the natural numbers, and now include the axioms as axioms, or we allow the axioms 1-5 to be definitions - they seem to lie close to an intuitive understanding of the numbers - and let 6-9 be axioms. We assume these axioms (6-9) to hold, i.e. to be true, in our system we call the natural numbers, or our work with natural numbers.

Do we not now have some statements (i.e. 6-9) which are true but not provable in Godels sense?
They obviously don't follow from 1-5.
Peanos axioms are the basis for the natural numbers, and therefore a natural point of departure for our discussion since they are the minimum requirement for the phenomenon (true but unprovable) to appear.

Am I making it too easy?

Title: Re: Peano & Godel
Post by towr on Dec 28^th, 2010, 9:32am

on 12/28/10 at 07:08:22, Mickey1 wrote:

Are these axioms actually axioms or are they a definition of the natural numbers?

I'd say they are both; these are not mutually exclusive things. The Peano axioms define the natural numbers and some properties of them, so you can meaningfulyl talk about it within the logic.
The "real" natural numbers form a model for this logic. (And ideally in such cases, you would have that everything which is true in/off the model is provable in the logic, and vice versa that everything provable in the logic is true in the model.)

Quote:

We intuitively understand the natural numbers, and now include the axioms as axioms, or we allow the axioms 1-5 to be definitions - they seem to lie close to an intuitive understanding of the numbers - and let 6-9 be axioms.

Err, are you really satisfied with 0 being the only natural number that's defined?
Personally, I'd want at least axioms 1 and 6.
But without the other axioms you're simply talking about something very different from natural numbers. For example, without 8, a "natural number" might have two different successors.

Quote:

Do we not now have some statements (i.e. 6-9) which are true but not provable in Godels sense?

Those statements aren't in any way "true but unprovable" in the logic, because without them you're not talking about natural numbers. For example, 1-5 are true for trees as well as natural numbers, but 8 isn't true for (all) trees, because children of the same node needn't be equal. And if you take the model of whole numbers, then 7 and 9 aren't true.
The logic is incomplete in the sense that it lacks the specificity to speak of what you want to talk about, not in a Godelian sense.

Title: Re: Peano & Godel
Post by 0.999... on Dec 29^th, 2010, 9:45am

on 12/28/10 at 07:08:22, Mickey1 wrote:

Alternative 2
We intuitively understand the natural numbers, and now include the axioms as axioms, or we allow the axioms 1-5 to be definitions - they seem to lie close to an intuitive understanding of the numbers - and let 6-9 be axioms. We assume these axioms (6-9) to hold, i.e. to be true, in our system we call the natural numbers, or our work with natural numbers.

Do we not now have some statements (i.e. 6-9) which are true but not provable in Godels sense?

Your sense of truth comes from intuition, which when formalized will yield axioms 6-9 or an equivalent form (by the uniqueness of the natural numbers).

As I now realize towr was getting at. :)

Title: Re: Peano & Godel
Post by Mickey1 on Jan 20^th, 2011, 8:13pm

I asked Prof Piodnik in Latvia the same question and this is his answer:

For Goedel’s proof, only the following “property” of Peano axioms is essential: by using these axioms, one can describe completely how do Turing machines work. See Representation Theorem in Section 3.3. /He is referring here to his presentation of Godel's proof on his home page-Mickey1/ So, any axioms having this property, could be used instead.

But, of course, if one is proving incompleteness of particular axioms, the construction of Goedel’s formula G will involve these axioms “in Goedel’s numbered list”.

“a simple version with the axiom and only one operator, “+” (the so-called Presburger arithmetic, see Section 3.1) “would actually be consistent”, indeed, but in this system, one cannot define multiplication of natural numbers and cannot “describe completely how do Turing machines work”.

My best wishes,
Karlis Podnieks
Professor
University of Latvia
www.ltn.lv/~podnieks

******

However I still can't free myself from the formal similarity between the axioms, being true by definition and unprovable since they are "slimmed". I asked if the axioms themselves appear in Godel's numbered list; hence his answer that they might if they were under examination.

If it hadn't been for the Presburger thing I would have thought disrespectfully that Godel pointed back to the axioms and that the scam had gone undetected for 80 years.

I still think the proof should say "there is at least one statement ... , apart from the axioms".

Otherwise I fully agree with the historical view of towr.

Title: Re: Peano & Godel
Post by towr on Jan 20^th, 2011, 10:48pm

on 01/20/11 at 20:13:26, Mickey1 wrote:

I still think the proof should say "there is at least one statement ... , apart from the axioms".

Axioms are provable within a system by themselves; after all, A implies A. What's at issue are theorems that cannot be proved within the system, but which can be shown to be true in the system by looking at it from outside.

The tricky part is that you can use Godel numbering to mix the two views; you can take a theorem known to be true but unprovable and translate it into a theorem about number properties. Because one is true if and only if the other is true, the translated theorem cannot be provable in any number theory in which they can be expressed.

Title: Re: Peano & Godel
Post by Mickey1 on Jan 27^th, 2011, 7:32am

I thought initially that defining natural numbers through the Peano axioms would lead to a different set of natural numbers than if one started with the intuitive natural numbers and “strengthened” or “reformed” them by introducing the axioms, and I accepted only proof in the first version, that is “A is A” by definition, but I realize that also axiom A must imply A in any case.

My two processes are probably one and the same process.

Title: Re: Peano & Godel
Post by rmsgrey on Jan 27^th, 2011, 8:56am

The only difference in results between starting with the axioms, and starting with intuition and adding the axioms is if intuition includes something that the axioms don't cover - in which case, talking about it gets tricky...