A Finite Model of Peano Arithmetic
in [Logic]
|
Prev: religion influenced a misguided infinity Re: Ad Infinitum really means Ad Negatorum #475 Correcting Math
Next: Another Hughes forgery, Remove this post from Usenet Re: An Ultrafinite Set Theory
From: Arturo Magidin on 5 Mar 2010 13:20 On Mar 5, 12:55 am, RussellE <reaste...(a)gmail.com> wrote: > On Mar 4, 9:11 am, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > > On Mar 3, 9:27 pm, RussellE <reaste...(a)gmail.com> wrote: > > > > On Mar 3, 7:19 pm, Arturo Magidin <magi...(a)member.ams.org> wrote: > > > > > On Mar 3, 6:10 pm, RussellE <reaste...(a)gmail.com> wrote: > > > > > > Start with Peano's axioms:http://en.wikipedia.org/wiki/Peano_axioms. > > > > > If an axiomatic theory is consistent, it will still be consistent if > > > > > we > > > > > remove an axiom. > > > > > > I will remove axiom 7: 0 is not the successor of any natural number. > > > > > I can now define the set {0,1} and show it is a model of PA. > > > > > > Define a successor function: > > > > > S(0) = 1 > > > > > S(1) = 0 > > > > > As near as I can tell, this set is a model of PA-Axiom 7. > > > > > So then, this is not a model for Peano Arithmetic, is it? > > > > This is a model of Peano arithmetic. It satisfies the 15 axioms > > > of Peano arithmetic given in the Wiki article. > > > No, it doesn't. As you point out, it does not satisfy Axiom 7, which > > says that "for every natural number n, S(n)=0 is false". In your > > model, S(1)=0, and 1 is a natural number, so S(1)=0 is TRUE, not > > false. > > > And if you look at the 15 axioms listed under "equivalent > > axiomatizations", you'll see that you fail lost of them. > > > Axiom 11 says: > > > For all x, y,z, if x<y then x+z < y+z. > > > Take x = 0, y = 1, and z= 1. Then x<y, but x+z = 1 and y+z=0, so you > > also have 1<0. So you either fail Axiom 11, or you fail Axiom 10 > > (trichotomy), or you fail Axiom 15, or you fail Axiom 14. > > Depends on how I define 1+1. > I was reading an article suggested by Aatu. > The author makes a clear distinction between addition > and the successor function. > > In most theories, addition is defined by successor. > While this is simpler, it is not neccessary. > I could say 1+1 is undefined. Or I can say > 1+1 is greater than any natural number. > > > So clearly, you were not looking at those 15 axioms, you were looking > > at the original list of 9 (since you said it satisfied PA-Axiom 7, but > > axiom 7 in this list is the existence of a multiplicative identity). > > I exclude axiom 7 of the original 9 axioms. Which means that, whatever it is you are doing, you aren't doing "Peano Arithmetic". > > > > > Nice try at a bait-n-switch, but I'm not falling for it. > > > > > Hell, if > > > > you want "Peano - "0 is not the successor anyone"", then you can take > > > > {0} and S:{0}-->{0} be the identity. So what? > > > > This isn't a model for Peano arithmetic because it doesn't > > > have an identity for multiplication. > > > It satisfies the same axioms from the original list as yours: Axioms > > 1-6, and axiom 8 and 9: > > > Axiom 1 says that for all x, x=x. This is true in {0}. > > Axiom 2 says for all x and y, if x=y, then y=x. Also true in {0}. > > Axiom 3 says that for all x, y, z, if x=y and y=z, then x=z. Also true > > in {0}. > > Axiom 4 says that if a=b and a is a natural number, then b is a > > natural number. Also true in {0}. > > Axiom 5 says that 0 is a natural number. True in my model. > > Axiom 6 says that if n is a natural number, then S(n) is a natural > > number. True in my model. > > Axiom 7 is of course not true, just like it is not true in your model. > > Axiom seven says that S(n)=0 is FALSE for every natural number n; in > > your model, S(1)=0 and 1 is a natural number; in my model, S(0)=0 and > > 0 is a natural number. > > Axiom 8 says that for all natural numbers m and n, if S(m)=S(n), then > > m=n. True in my model, since S is one-to-one. > > Axiom 9 says that if K is a subset such that 0 is in K, and if n is in > > K then s(n) is in K, then K is the set of all natural numbers. True in > > my model. > > > Now, if you want to look at the list under "Equivalent > > axiomatizations", > > I first need to define +, *, and < in some way (as do you). You > > clearly want to define + and * as in arithmetic modulo 2; but then you > > cannot define < in any meaningful way. You need 0<1 by Axiom 14, but > > then you run into the troubles mentioned above. > > Depends on how we define "+" and "*". There aren't that many possibilities, dear, and NONE of them will satisfy the 15 properties listed. Or even all but the condition "0<1". > In the article I read, the author uses the largest element for > "overflow" similar to how I defined NaN, not a number, > in another thread. And he does not get something that satisfies 1-13 and 15. > > Me, I'll define < as the empty relation, define 0+0 = 0, 0*0 = 0, > > 1=s(0)=0. This satisfies all fifteen listed axioms except for Axiom > > 14, so just as good as yours (all but one). > > OK. You have a model of PA- Axiom 7. > Axiom 14 is a problem only if you define addition using successor. If you define addition any other way, you run into other problems. There aren't that many possibilities, after all: there are only 8 ways to define addition if you want it to be commutative, depending only on what 0+0, 0+1, and 1+1 are. For your system, it doesn't matter which one is "neutral"; (Axiom 6). You will either have 0+0=0, 0+1=1; or you will have 1+1=1, 0+1=0; you cannot have both, obviously. And since S(0)=1 and S(1)=0, we can map one choice to the other (relative to the successor function), so we may as well take 0 to be the element that satisfies axiom 6. If you want it to be 1, take what I write below and change all the 1's into 0's and all the 0's into 1's, and you will get the same problem. Now, you have only one more decision to make: is 1+1=1, or is 1+1=0? If 1+1=0, then you are essentially doing arithmetic modulo 2; you cannot define an order in such a way that it satisfies both Axiom 10 (trichotomy) and Axiom 11 (addition respects order), even if you ignore axiom 14. For either you will have 0<1 or you will have 1<0. Either way, you get a contradiction by adding 1 to both. If you define 1+1=1, then you no longer have a problem with Axiom 11; but you still must have 0<1 if you are going to satisfy Axiom 10 and Axiom 13 (if x<y, then there exists z such that x+z<y). And you again run into problems with Axiom 11, since 0<1 but 0+1 is not less than 1+1. So it doesn't matter which way you define addition, and it doesn't matter if you ignore Axiom 14 or not, you simply do *not* get a model for the fifteen arithmetical axioms, or even for the fourteen you get by dropping Axiom 14. -- Arturo Magidin |