Author |
Topic: Peano's axiom (Read 2222 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 |
|
|
|
|