Godel's incompleteness theorems
in [Math]
|
Prev: SIMPLIFIED FOR SOME MATHEMATICS -- PROOF THAT PRIME NUMBERS ARE IN SETS OF 36
Next: Complex Number - Real part of Sqrt(1+z)?
From: MoeBlee on 30 Mar 2010 14:40 On Mar 30, 12:42 pm, zuhair <zaljo...(a)gmail.com> wrote: > On Mar 30, 12:16 pm, MoeBlee <jazzm...(a)hotmail.com> wrote: > > > > > On Mar 30, 12:01 pm, zuhair <zaljo...(a)gmail.com> wrote: > > > > Suppose we have a set theory T, which cannot define > > > the notion of "natural number", would that make T > > > escape the incompleteness theorems of Godel's. > > > It's not a matter of defining 'natural number'. Rather, it's a matter > > of being able to do a certain amount of arithmetic in the theory. We > > don't have to define 'natural number' just to do arithmetic. First > > order PA doesn't define, in the theory, 'natural number', but first > > order PA is rich enough to do enough arithmetic so that it is > > incomplete. > > > So the fact that a theory doesn't define 'natural number' doesn't in > > itself entail that the theory is complete. > > > MoeBlee > > What is exactly meant by "enough" arithmetic? is there a definition of > that > "enough"? I don't know about a technical definition (I think there is one, but I don't recall). However, very roughly speaking, it's enough arithmetic to code enough of the syntax of the language to produce a "Godel sentence" (one that "says", for a specific natural number n, that the sentence with Godel number n is unprovable, while that sentence itself has Godel number n). MoeBlee
From: MoeBlee on 30 Mar 2010 14:42 On Mar 30, 1:23 pm, Frederick Williams <frederick.willia...(a)tesco.net> wrote: > Daryl McCullough wrote: > > > zuhair says... > > > >Suppose we have a set theory T, which cannot define > > >the notion of "natural number", would that make T > > >escape the incompleteness theorems of Godel's. > > > If T does not have a notion of natural number, then it is possible for T to be > > complete. For example, the theory of real closed fields is decidable and > > complete. > > What do you mean by having a notion of natural number? In any field one > has > > 0, 1, 1 + 1, 1 + 1 + 1, ... . But in the language of real closed fields, there is not a way to define the predicate of being one of those numbers you just mentioned. Sure, for any given natural number, you can define it, but there is not a way to define the general predicate 'is a natural number' where the predicate is satisfied by all and only the natural numbers. MoeBlee
From: Frederick Williams on 30 Mar 2010 16:50 zuhair wrote: > > Suppose we have a set theory T, which cannot define > the notion of "natural number", would that make T > escape the incompleteness theorems of Godel's. You may be interested R M Smullyan 'Languages in which self reference is possible' JSL, 22 pp 55-67, also in J Hintikka ed 'The philosophy of mathematics' OUP 1969. -- I can't go on, I'll go on.
From: zuhair on 30 Mar 2010 17:35 On Mar 30, 12:01 pm, zuhair <zaljo...(a)gmail.com> wrote: > Suppose we have a set theory T, which cannot define > the notion of "natural number", would that make T > escape the incompleteness theorems of Godel's. > > Zuhair Thanks to all who replied to this post. Zuhair
From: Daryl McCullough on 30 Mar 2010 22:17
Frederick Williams says... >Daryl McCullough wrote: >> >> zuhair says... >> > >> >Suppose we have a set theory T, which cannot define >> >the notion of "natural number", would that make T >> >escape the incompleteness theorems of Godel's. >> >>If T does not have a notion of natural number, then it is possible for T to be >> complete. For example, the theory of real closed fields is decidable and >> complete. > >What do you mean by having a notion of natural number? In any field one >has > > 0, 1, 1 + 1, 1 + 1 + 1, .... In the theory of reals, there are natural numbers, but there is no formula N(x) that is true of the natural numbers but false of reals that are not naturals. This makes a big difference when it comes to undecidability. It is undecidable which Diophantine equations have integral solutions. But it is perfectly decidable which Diophantine equations have real number solutions. -- Daryl McCullough Ithaca, NY |