Author |
Topic: Peano's axiom (Read 2237 times) |
|
Mickey1
Junior Member
Gender: 
Posts: 116
|
 |
Peano's axiom
« on: Nov 13th, 2010, 3:23pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Peano's axiom
« Reply #1 on: Nov 14th, 2010, 8:15am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 14th, 2010, 8:15am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Peano's axiom
« Reply #2 on: Nov 14th, 2010, 9:25am » |
Quote Modify
|
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) 0 ...... by (7)
2. SS(0)0 ...... by (7)
3. SS(0) S(0) ....... by (T)
4. S(0)0 ..... by (8 )
|
| « Last Edit: Nov 14th, 2010, 9:28am by 0.999... » |
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Peano's axiom
« Reply #3 on: Nov 17th, 2010, 8:06am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Peano's axiom
« Reply #4 on: Nov 17th, 2010, 10:06am » |
Quote Modify
|
on Nov 17th, 2010, 8:06am, 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.
|
| « Last Edit: Nov 17th, 2010, 1:03pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Peano's axiom
« Reply #5 on: Nov 17th, 2010, 12:52pm » |
Quote Modify
|
on Nov 17th, 2010, 10:06am, towr wrote:
He figured me out! 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Peano's axiom
« Reply #6 on: Nov 17th, 2010, 1:04pm » |
Quote Modify
|
Whoops. 
Well, they say great minds think alike, so it stands to reason I might confuse them sometimes..
|
| « Last Edit: Nov 17th, 2010, 1:05pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Peano's axiom
« Reply #7 on: Nov 17th, 2010, 1:16pm » |
Quote Modify
|
on Nov 17th, 2010, 1:04pm, 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
|
|
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Peano's axiom
« Reply #8 on: Nov 17th, 2010, 3:31pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Peano's axiom
« Reply #9 on: Nov 17th, 2010, 3:47pm » |
Quote Modify
|
I'll do the general case and add some notes (make same assumptions as in my previous post--implicitly adding (5) and (6) ):
1. Sn+1(0) 0
and
2. S(0) 0 by (7)
The test statement (and n+1 instances of (6)) imply that
3. Sn+1(0) S(0)
4. Sn(0) 0
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).
|
| « Last Edit: Nov 17th, 2010, 3:56pm by 0.999... » |
IP Logged |
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Peano's axiom
« Reply #10 on: Nov 17th, 2010, 4:57pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Peano's axiom
« Reply #11 on: Nov 18th, 2010, 12:43am » |
Quote Modify
|
on Nov 17th, 2010, 4:57pm, 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.
|
| « Last Edit: Nov 18th, 2010, 12:57am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Mickey1
Junior Member
Gender:
Posts: 116
|
|
Re: Peano's axiom
« Reply #12 on: Nov 18th, 2010, 2:23am » |
Quote Modify
|
Yes,
I see that now. Thanks for your comments.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print