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 02:30 RussellE <reasterly(a)gmail.com> writes: > If Peano arithmetic is consistent, it is also consistent > when we remove one axiom. Sure. But it does not follow from the fact that Peano arithmetic is essentially incomplete that Peano arithmetic with an axiom removed is essentially incomplete. It also does not follow from the fact that Peano arithmetic cannot be proven consistent using these and those principles that Peano arithmetic with an axiom removed cannot be proven consistent using these and those principles. These are elementary points I'm sure you'll appreciate on further reflection. > Then, why was it a big deal when Godel proved FOL is consistent and > complete? The consistency of first-order logic is a triviality, and has nothing to do with G�del. As for completeness, that first-order logic is complete was a moral certainty even before G�del's proof. The mathematical use we make of the completeness theorem today has little do with the reception of the result at the time. (Recall that essentially all formal theories at that time were higher-order. The predominant role of first-order logic in mathematical logic is a later development, due in no small part to the influence of G�del and Skolem.) > Can you give an example of an undecidable statement in FOL? You can give examples yourself if you pause to think for a moment. Recall that a formula is provable in pure first-order logic if and only if it is a logical validity. Just pick a formula that is not a logical validity and whose negation is not a logical validity. > I still find it hard to believe there are undecidable statements > about arithmetic for a finite set of natural numbers. It is indeed hard to believe obvious falsehoods. For any finite set of naturals there's a complete axiomatizable theory proving all sentences true in the set (throwing in successor, addition and multiplication for good measure). It's difficult to see why we should get very worked up over this on the face of it uninteresting fact. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: RussellE on 4 Mar 2010 03:10 On Mar 3, 11:30 pm, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > RussellE <reaste...(a)gmail.com> writes: > > If Peano arithmetic is consistent, it is also consistent > > when we remove one axiom. > > Sure. But it does not follow from the fact that Peano arithmetic is > essentially incomplete that Peano arithmetic with an axiom removed is > essentially incomplete. It also does not follow from the fact that Peano > arithmetic cannot be proven consistent using these and those principles > that Peano arithmetic with an axiom removed cannot be proven consistent > using these and those principles. These are elementary points I'm sure > you'll appreciate on further reflection. OK. It is not a big deal to remove an axiom and get a consistent thoery. > > Then, why was it a big deal when Godel proved FOL is consistent and > > complete? > > The consistency of first-order logic is a triviality, and has nothing to > do with Gödel. As for completeness, that first-order logic is complete > was a moral certainty even before Gödel's proof. The mathematical use we > make of the completeness theorem today has little do with the reception > of the result at the time. (Recall that essentially all formal theories > at that time were higher-order. The predominant role of first-order > logic in mathematical logic is a later development, due in no small part > to the influence of Gödel and Skolem.) > > > Can you give an example of an undecidable statement in FOL? > > You can give examples yourself if you pause to think for a > moment. Recall that a formula is provable in pure first-order logic if > and only if it is a logical validity. Just pick a formula that is not a > logical validity and whose negation is not a logical validity. I can come up with a statement that isn't a tautology or antimony. Are all such statements undeciable in FOL? > > I still find it hard to believe there are undecidable statements > > about arithmetic for a finite set of natural numbers. > > It is indeed hard to believe obvious falsehoods. For any finite set of > naturals there's a complete axiomatizable theory proving all sentences > true in the set (throwing in successor, addition and multiplication for > good measure). It's difficult to see why we should get very worked up > over this on the face of it uninteresting fact. I find it interesting. I would like such an axiomatic theory for all the natural number up to 2^500. I could come up with an FOL statement that is true only if a natural number is prime. I know such FOL statements exist. I just want the one with the fewest steps. Russell - 2 many 2 count
From: RussellE on 4 Mar 2010 03:29 On Mar 4, 12:10 am, RussellE <reaste...(a)gmail.com> wrote: > On Mar 3, 11:30 pm, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > > It is indeed hard to believe obvious falsehoods. For any finite set of > > naturals there's a complete axiomatizable theory proving all sentences > > true in the set (throwing in successor, addition and multiplication for > > good measure). It's difficult to see why we should get very worked up > > over this on the face of it uninteresting fact. > > I find it interesting. I would like such an axiomatic theory for > all the natural number up to 2^500. I could come up with > an FOL statement that is true only if a natural number is prime. > I know such FOL statements exist. I just want the one > with the fewest steps. Heck, I would be enough to know the FOL statement for primes with the smallest Gödel number. Russell - 2 many 2 count
From: Aatu Koskensilta on 4 Mar 2010 03:36 RussellE <reasterly(a)gmail.com> writes: > I can come up with a statement that isn't a tautology or antimony. > Are all such statements undeciable in FOL? Yes. Only logical truths are provable in pure first-order logic. > I would like such an axiomatic theory for all the natural number up to > 2^500. It is trivial to define such a theory. > I could come up with an FOL statement that is true only if a natural > number is prime. I know such FOL statements exist. I just want the > one with the fewest steps. (I take it you mean a formula that is true of a natural just in case the natural is a prime.) What's wrong with the obvious formula x > 1 and (y)(z)( y * z = x --> y = 1 or y = x) ? These are elementary questions, and you can profitably answer them for yourself by studying a good text on the subject. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: RussellE on 4 Mar 2010 04:54
On Mar 4, 12:36 am, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > RussellE <reaste...(a)gmail.com> writes: > > I can come up with a statement that isn't a tautology or antimony. > > Are all such statements undeciable in FOL? > > Yes. Only logical truths are provable in pure first-order logic. > > > I would like such an axiomatic theory for all the natural number up to > > 2^500. > > It is trivial to define such a theory. > > > I could come up with an FOL statement that is true only if a natural > > number is prime. I know such FOL statements exist. I just want the > > one with the fewest steps. > > (I take it you mean a formula that is true of a natural just in case the > natural is a prime.) What's wrong with the obvious formula > > x > 1 and (y)(z)( y * z = x --> y = 1 or y = x) OK. Requires looping through all y and all z. Would be nice to limit the quantifiers a bit. Something simpler than multiplication wouldn't hurt, either. Russell - 2 many 2 count |