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: Frederick Williams on 4 Mar 2010 10:51 Aatu Koskensilta wrote: > > Frederick Williams <frederick.williams2(a)tesco.net> writes: > > > Aatu Koskensilta wrote: > > > >> Boolos's _The Unprovability of Consistency, An Essay in Modal Logic_ is > >> a standard reference. > > > > I've told you before, my little darling, that's out of date. > > You've told me alright! I went out of my way and checked at amazon.com > to make sure I had the more up-to-date version, but, alas, my > inexcusable ineptitude proved my ultimate undoing in this instance. > > > You(*) want Boolos's The Logic of Provability, CUP. > > With utter disregard for your starry footnotes, yes, I want that book. If only I had known, I'd have sent you one for Christmas.
From: Aatu Koskensilta on 4 Mar 2010 11:56 Frederick Williams <frederick.williams2(a)tesco.net> writes: > Just suppose we had what might be called an "applied" FOL with names > a0, a1, a2, ... for which the intended interpretations are the > formulae phi0, phi1, phi2, ... taken in some order. There may be > other names besides. FAFOL(*) also has a one-place predicate P(x) for > which the intended interpretation is "the formulae named x is > provable". There may be other predicates besides. Axioms are added: > P(x) for each provable x and not-P(x) for each non-provable x. Then > one could consider the statements P(an) where an is the name of P(an). > (Fixed points, so to speak.) But then what, I don't know. I'm vigorously supposing that but I'm also at a loss as to what we should conclude, or what's the point to all this. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Jesse F. Hughes on 4 Mar 2010 12:07 Frederick Williams <frederick.williams2(a)tesco.net> writes: > RussellE 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. > > Look again, little looney lad, look again. > > No. 7 is For every natural number n, S(n) = 0 is False. > > but in your model S(S(0)) = 0. I thought exactly the same thing at first, but since he mentioned 15 axioms, I looked again. He apparently is referring to the axioms under "Equivalent axiomatizations." Of course, his model is not a model of those axioms either, as someone else pointed out. -- "[I]f I could go back, [...] I would tell myself not to step into a position where the fate of the entire world could rest in my hands. I would [avoid this] path to a nightmarish and surreal world, a topsy-turvy world, where everything changes." -- James S. Harris cannot escape his destiny.
From: Arturo Magidin on 4 Mar 2010 12:11 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. 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). 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. 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). -- Arturo Magidin
From: RussellE on 5 Mar 2010 01:55
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. > 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 "*". 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. > 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. Russell - 2 many 2 count |