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: Aatu Koskensilta on 4 Mar 2010 04:58 RussellE <reasterly(a)gmail.com> writes: > Would be nice to limit the quantifiers a bit. Limit away: x > 1 and (y <= x)(z <= x)(y * z = x --> y = 1 or y = x) > Something simpler than multiplication wouldn't hurt, either. There's no way to define primality without multiplication. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Frederick Williams on 4 Mar 2010 08:31 RussellE wrote: > > On Mar 3, 4:16 pm, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > > RussellE <reaste...(a)gmail.com> writes: > > > As near as I can tell, this set is a model of PA-Axiom 7. > > > > Great. An obvious question suggests itself: so what? > > I have Peano arithmetic and I can prove the system > is consistent. Doesn't this prove PA is inconsistent? In your OP you wrote If an axiomatic theory is consistent, it will still be consistent if we remove an axiom. You didn't write If an axiomatic theory is consistent, it will still be consistent if we add an axiom.
From: FredJeffries on 4 Mar 2010 09:00 On Mar 3, 7: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 satisfy #11: if x < y then x+z < y+z By #14 0 < 1 If #11 were satisfied then 0 + 1 = 1 < 1 + 1 = 0 so 1 < 0 which contradicts #15.
From: Frederick Williams on 4 Mar 2010 09:20 RussellE wrote: > > Can you give an example of an undecidable statement in FOL? Depending on the details of the language, something like exists x P(x) > > Can you express "this statement can't be proven" in FOL? No because provability, being applicable to formulae, isn't first order. You may be interested in a modal logic called G which, iirc, is K plus L(Lp -> p) -> p L may be read as "it is provable in PA that". Solovay did some work on translating 'twixt G and PA. I'll find the references if you wish.
From: Aatu Koskensilta on 4 Mar 2010 09:29
Frederick Williams <frederick.williams2(a)tesco.net> writes: > RussellE wrote: > >> Can you express "this statement can't be proven" in FOL? > > No because provability, being applicable to formulae, isn't first > order. What do you mean by "first-order" here? Provability is a first-order concept in a straightforward sense: we can formalize in the first-order language of arithmetic the notion of provability in any arithmetically axiomatizable theory. > Solovay did some work on translating 'twixt G and PA. I'll find the > references if you wish. Boolos's _The Unprovability of Consistency, An Essay in Modal Logic_ is a standard reference. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus |