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

        general >> truth >> Peano's axiom 
        
(Message started by: Mickey1 on Nov 13th, 2010, 3:23pm)
Title: Peano's axiom
Post by Mickey1 on Nov 13th, 2010, 3:23pm
I have a problem in relation to Peano’s axioms. I use the first version of the axiom from Wikipedia’s formulation, including having the first number as 0 instead of 1. I am wondering if the definition of “=” allows too much. The additional axiom I want to test is
“for all natural numbers n and m different from 0, n=m, and furthermore 0=0” (test axiom to be added to the rest).
The first 5 axioms seems to be self evident with my new axiom inserted, since n=m and 0=0. If this is true, can axioms 6 to 9 save the day, falsifying my axiom?
Wikipedia mentions the axioms:
1. For every natural number x, x = x.
2. For all natural numbers x and y, if x = y, then y = x.
3. For all natural numbers x, y and z, if x = y and y = z, then x = z.
4. For all a and b, if a is a natural number and a = b, then b is also a natural number. ,
5. 0 is 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.
8. For all natural numbers m and n, if S(m) = S(n), then m = n.
9. If K is a set such that:
 o 0 is in K, and
 o for every natural number n, if n is in K, then S(n) is in K,
 o then K contains every natural number.

I assume that axioms 1-6 cannot fulfill this function (saving the day). 6 and 7 together seem powerful in that they rule out that n=m for all numbers, so that S(n) is a natural number (6) but not 0 (7). This rules out a simpler test axiom (n=m  for all numbers) but I can’t see how my test axiom is falsified. I can see that “and n=S(n) is also false” being added to (7) might remedy the situation. Other than that, how can we understand the set of axioms?
Are the axioms not intended to - uniquely - point to the natural numbers as we intuitively understand them?
Or is Wikipedia’s version wrong?
Grateful for any help.
Title: Re: Peano's axiom
Post by towr on Nov 14th, 2010, 8:15am
Just to be clear, you want to know whether the theorem "for all natural numbers n and m different from 0, n=m, and furthermore 0=0" can be disproved using the Peano axioms?

I think axiom 8) poses a big problem, because for any n > m, it brings you back to n-m = 0. Which you already had to make one exception for, but you'll have to make an exception for every number.
Title: Re: Peano's axiom
Post by 0.999... on Nov 14th, 2010, 9:25am
Formalizing a specific case of what towr said:
The combination of your test statement (call it T), (7) and (8 ) leads to a contradiction:
1. S(0)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif0   ...... by  (7)
2. SS(0)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif0 ...... by (7)
3. SS(0)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/eq.gifS(0) ....... by (T)
4. S(0)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/eq.gif0 ..... by (8 )
Title: Re: Peano's axiom
Post by Mickey1 on Nov 17th, 2010, 8:06am
I saw this posibility that towr points out, but I am speculating that my extra axiom might block the steps involving the definition of minus in n-m.

That is to say: the undecided or - in my suspicion - too open "=" operator allowing my extra axiom (whether I explicitly stated it or not) would perhaps make the minus definition possible, but it would not necessarily be the only consequence of the preceeding axioms regarding the use of a+b=c implying later that a=b-c (which is possible but does not necessarily follow from my sets of axiom).
So I guess that my question can be rephrased: are the first axioms enough  to arrive at a meaningful addiiton or subtraction definition before the introduction of S(n). Or: is + sufficiently limited in its environment of definitions, so that it resembles how we intuitivly understand it?

Somewhat unrelated, as I write this I, ask myself if axiom can be order-of-appearance sensitive (apart from the trivial case that the use of definitions  logically should appear after the definition itself).
Title: Re: Peano's axiom
Post by towr on Nov 17th, 2010, 10:06am

on 11/17/10 at 08:06:59, Mickey1 wrote:
I saw this posibility that towr points out, but I am speculating that my extra axiom might block the steps involving the definition of minus in n-m.
Axioms only add ways to derive theorems, they can't block derivations. If you can derive something from axiom A to Y, you can derive it from axioms A to Z; at worst adding Z makes the logic inconsistent (as happens in this case).


Quote:
So I guess that my question can be rephrased: are the first axioms enough  to arrive at a meaningful addiiton or subtraction definition before the introduction of S(n). Or: is + sufficiently limited in its environment of definitions, so that it resembles how we intuitivly understand it?
I'm not sure what you're asking. n+m is just shorthand for Sn(Sm(0))  (associativity and commutativity can be proved). And all you need for subtraction is axiom 8.
By applying axiom 8 n times, you get Sn(Sx(0)) = Sn(Sy(0))  implies Sx(0) = Sy(0)
So then if y = 0, we must have to x = 0 because of axiom 7.


And in any case, you only need one specific counter-example, which pex 0.999... has provided.
Title: Re: Peano's axiom
Post by 0.999... on Nov 17th, 2010, 12:52pm

on 11/17/10 at 10:06:34, towr wrote:
which pex has provided.

He figured me out!  :P
Title: Re: Peano's axiom
Post by towr on Nov 17th, 2010, 1:04pm
Whoops.  :-[
Well, they say great minds think alike, so it stands to reason I might confuse them sometimes..
Title: Re: Peano's axiom
Post by pex on Nov 17th, 2010, 1:16pm

on 11/17/10 at 13:04:29, towr wrote:
Whoops.  :-[
Well, they say great minds think alike, so it stands to reason I might confuse them sometimes..

Let me thank you from this account :P
Title: Re: Peano's axiom
Post by Mickey1 on Nov 17th, 2010, 3:31pm
I still dont see how one arrives at 0.999's last step.

S(...n times(0)=S(...times(0) only implies that n=m, as I stated in my extra axiom.

How does one arrive at the last step, the forbidden S(0)=0?
Title: Re: Peano's axiom
Post by 0.999... on Nov 17th, 2010, 3:47pm
I'll do the general case and add some notes (make same assumptions as in my previous post--implicitly adding (5) and (6) :P ):

1. Sn+1(0) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif0
and
2. S(0) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif0 by (7)
The test statement (and n+1 instances of (6)) imply that
3. Sn+1(0) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/eq.gifS(0)

4. Sn(0) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/eq.gif0
This comes from the fact that Sk denotes k iterations of the operation S; put in notation, Sk(0) denotes S(Sk-1(0)). So, applying (5) to see that 0 is a natural number, we may use (8 ), substituting m = Sn(0) and n = 0 to get our statement 4.


Edit: to show that this is all-inclusive, use (9).
Title: Re: Peano's axiom
Post by Mickey1 on Nov 17th, 2010, 4:57pm
Thank you but I am still concerned by your use of minus (or plus) which I don't think is backed by the axioms at this point.

Bear with me one more time while I rephrase:

Statement 1: The axioms do not contradict that n=m for all numbers different from 0.

Statement 2:
S(n) can be interpreted as a number different from 0.

I guess another way to describe my uneasyness is that you both use a tool to disprove me, consisting of the natural numbers (complete with plus and minus), but these are the very object of our discussion, they cannot be assumed to exist in a certain way at this point other than defined in the axioms. I am not sure you can refer to "k times" or "k-1 times". There is no  axiom saying that + exists or that x+a=x+b implies that a=b, so I don't think there is a way to go backwards (k-1) since k-1=k (T) if not 0, or using minus more generally.

Another way to rephrase the result: The Peano axioms leads to two elements, one called 0 and the other called "different from 0". An operation can therefore under this interpretation not be done k times, only 0 times or "different from 0" times.

I realize that in reality you must start somewhere, perhaps accepting going from an intuitive to a  semi-intuitive situation and later to a  more stringent situation. Perhaps one must accept that.
Title: Re: Peano's axiom
Post by towr on Nov 18th, 2010, 12:43am

on 11/17/10 at 16:57:46, Mickey1 wrote:
Bear with me one more time while I rephrase:

Statement 1: The axioms do not contradict that n=m for all numbers different from 0.
Yes, they do. It's contradicted by use of axiom 7 and 8.
It's contradicted by the fact that by axiom 8, S(S(0))=S(0) implies S(0)=0, which is contradicted by axiom 7.
It's contradicted by the fact that by axiom 8, S(S(S(0)))=S(0) implies S(S(0))=0, which is contradicted by axiom 7.
It's contradicted by the fact that by axiom 8, S(S(S(0)))=S(S(0)) implies S(S(0))=S(0), which is contradicted by our derivation two statements up.
It's contradicted by the fact that by axiom 8, S(S(S(S(0))))=S(S(0)) implies S(S(S(0)))=S(0), which is contradicted by our derivation two statements up.
And so on, and so on.

For any specific n and m, if they are not equal, you can construct a proof that leads to a contradiction. And we only need to do it for 1 specific counterexample to disproof the theorem.


Quote:
Statement 2:
S(n) can be interpreted as a number different from 0.
Stronger than that, by axiom 7 S(n) can only be interpreted as something different than 0.


Quote:
I guess another way to describe my uneasyness is that you both use a tool to disprove me, consisting of the natural numbers (complete with plus and minus)
No, we aren't. We're only using axioms 7 and 8. There rest is just shorthand, not additional assumptions or tools.

If n and m are natural numbers than either n=0 or m=0, or (by 9) n=S(a) and m=S(b), in which case by 8 we have a=b.  
For the specific case m=1 (i.e. S(0)), this gives an immediate contradiction with axiom 7 if n is different from m.
if m > 1, you can just repeat the same step to bring the number down further.


Quote:
I am not sure you can refer to "k times" or "k-1 times".
Sure you can, because it's what you do in the proof; it's not something within the logic system, it's a description about the proof.
If I apply axiom 8 three times to S(S(S(S(0)))) = S(S(S(0))) that simply means

given
S(S(S(S(0)))) = S(S(S(0)))
by applying axiom 8 we have
S(S(S(0))) = S(S(0))
by applying axiom 8 a second time we have
S(S(0)) = S(0)
by applying axiom 8 a third time we have
S(0) = 0
Now by applying axiom 7, we arrive at a contradiction. Therefore S(S(S(S(0)))) = S(S(S(0))) is inconsistent with axioms 1-9, and therefore the general statement that all natural numbers different from 0 are equal is also inconsistent with the peano axioms.


Quote:
There is no axiom saying that + exists or that x+a=x+b implies that a=b
+ is just shorthand. just as 4 is shorthand from S(S(S(S(0)))).
Also 0.999...'s counterexample makes no use of it in the first place. Nor does my counterexample in the previous paragraph.
Title: Re: Peano's axiom
Post by Mickey1 on Nov 18th, 2010, 2:23am
Yes,

I see that now. Thanks for your comments.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board