37 views

Skip to first unread message

Jun 27, 2008, 1:28:58 PM6/27/08

to

Can somebody provide me some good explanation on Godel's

incompleteness theorem in a simple way.

incompleteness theorem in a simple way.

Jun 27, 2008, 1:41:36 PM6/27/08

to

On Jun 27, 1:28 pm, moorthy <cmkmoor...@gmail.com> wrote:

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

You cannot have a mathematical system which is both consistent and

complete. Complete means that any truthful statement can be derived

from the axioms of the system. You may want it to be both consistent

and complete, but you can't have it both ways.

I'm paraphrasing to be generally understandable, but watch as I and my

explanation are ripped apart. If someone else can explain it better

YET simple, go right ahead.

Moorthy, read or skim Godel Escher Bach by Douglas Hofstadter. It is

excellent - entertaining and informative, and it deserved the Pulitzer

Prize.

Jun 27, 2008, 1:52:32 PM6/27/08

to

On Fri, 27 Jun 2008 10:41:36 -0700 (PDT), Neilist wrote:

> On Jun 27, 1:28 pm, moorthy <cmkmoor...@gmail.com> wrote:

>> Can somebody provide me some good explanation on Godel's

>> incompleteness theorem in a simple way.

> On Jun 27, 1:28 pm, moorthy <cmkmoor...@gmail.com> wrote:

>> Can somebody provide me some good explanation on Godel's

>> incompleteness theorem in a simple way.

> You cannot have a mathematical system which is both consistent and

> complete. Complete means that any truthful statement can be derived

> from the axioms of the system. You may want it to be both consistent

> and complete, but you can't have it both ways.

Actually, "complete" means that for any proposition P, either P or ~P can be

derived from the axioms of the system. "Consistent" means that not both P and

~P can be derived from the axioms.

> I'm paraphrasing to be generally understandable, but watch as I and my

> explanation are ripped apart. If someone else can explain it better

> YET simple, go right ahead.

> Moorthy, read or skim Godel Escher Bach by Douglas Hofstadter. It is

> excellent - entertaining and informative, and it deserved the Pulitzer

> Prize.

--

Dave Seaman

Third Circuit ignores precedent in Mumia Abu-Jamal ruling.

<http://www.indybay.org/newsitems/2008/03/29/18489281.php>

Jun 27, 2008, 2:36:41 PM6/27/08

to

In article <bc58dc82-b8ac-4ae7...@x35g2000hsb.googlegroups.com>,

Neilist <Neil...@gmail.com> wrote:

>On Jun 27, 1:28=A0pm, moorthy <cmkmoor...@gmail.com> wrote:

>> Can somebody provide me some good explanation on Godel's

>> incompleteness theorem in a simple way.

>

>You cannot have a mathematical system which is both consistent and

>complete. Complete means that any truthful statement can be derived

>from the axioms of the system. You may want it to be both consistent

>and complete, but you can't have it both ways.

>

>I'm paraphrasing to be generally understandable, but watch as I and my

>explanation are ripped apart.

Neilist <Neil...@gmail.com> wrote:

>On Jun 27, 1:28=A0pm, moorthy <cmkmoor...@gmail.com> wrote:

>> Can somebody provide me some good explanation on Godel's

>> incompleteness theorem in a simple way.

>

>You cannot have a mathematical system which is both consistent and

>complete. Complete means that any truthful statement can be derived

>from the axioms of the system. You may want it to be both consistent

>and complete, but you can't have it both ways.

>

>I'm paraphrasing to be generally understandable, but watch as I and my

>explanation are ripped apart.

It's a reasonably good explanation, though it would be better to add

that for the result to apply to a given "mathematical system", it must

be on the one hand sufficiently complex (so as to allow certain

arithmetical propositions to be 'coded'), and on the other hand, not

too complex (e.g., one must be able to recognize whether a given

sentence is an axiom of not); that is, there are some mild (and some

not-so-mild) technical restrictions on the systems to which the

theorem applies.

>Moorthy, read or skim Godel Escher Bach by Douglas Hofstadter. It is

>excellent - entertaining and informative, and it deserved the Pulitzer

>Prize.

Actually, as an intro to the theorem itself I think I might direct him

to Nagel and Newman's little booklet, "Goedel's Proof". Certainly a

quicker read than Hofstadter's otherwise very good book.

--

======================================================================

"It's not denial. I'm just very selective about

what I accept as reality."

--- Calvin ("Calvin and Hobbes" by Bill Watterson)

======================================================================

Arturo Magidin

magidin-at-member-ams-org

Jun 27, 2008, 2:51:18 PM6/27/08

to

On Jun 27, 1:52 pm, Dave Seaman <dsea...@no.such.host> wrote:

<snip>

> Actually, "complete" means that for any proposition P, either P or ~P can be

> derived from the axioms of the system.

Isn't that the same as "any truthful statement", like I said, since

either P or ~P is true but not both, by the Law of Excluded Middle?

Or is there a nuance which is unclear in "any truthful statement"

which has to be spelled out, such as to avoid esoteric logics where

both P and ~P are true and permissible? Or to not require invoking

the Law of Excluded Middle?

Jun 27, 2008, 2:58:55 PM6/27/08

to

On Fri, 27 Jun 2008 11:51:18 -0700 (PDT), Neilist wrote:

> On Jun 27, 1:52 pm, Dave Seaman <dsea...@no.such.host> wrote:

> On Jun 27, 1:52 pm, Dave Seaman <dsea...@no.such.host> wrote:

><snip>

>> Actually, "complete" means that for any proposition P, either P or ~P can be

>> derived from the axioms of the system.

> Isn't that the same as "any truthful statement", like I said, since

> either P or ~P is true but not both, by the Law of Excluded Middle?

How do you know which of P or ~P is the true one, especially if neither has a

proof?

> Or is there a nuance which is unclear in "any truthful statement"

> which has to be spelled out, such as to avoid esoteric logics where

> both P and ~P are true and permissible? Or to not require invoking

> the Law of Excluded Middle?

Jun 27, 2008, 3:25:40 PM6/27/08

to

On Jun 27, 10:41 am, Neilist <Neilis...@gmail.com> wrote:

> You cannot have a mathematical system which is both consistent and

> complete.

No, you can't have a recursively axiomatized system that also is

strong enough for a certain amount of arithmetic that is both

consistent and complete.

MoeBlee

Jun 27, 2008, 3:56:55 PM6/27/08

to

moorthy wrote:

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

This assertion is false.

Cheers.

Jun 27, 2008, 5:05:08 PM6/27/08

to

In article <g43gm7$l3q$4...@registered.motzarella.org>,

"This assertion is unprovable" would be a bit closer, I think.

Jun 27, 2008, 5:20:17 PM6/27/08

to

On Jun 27, 10:56 pm, "Kyle T. Jones" <pleaseemail...@realdomain.net>

wrote:

wrote:

******************************************************

What assertion? I only see a question...

Regards

Tonio

Jun 27, 2008, 5:47:25 PM6/27/08

to

Find out in the recent (June/July 2008) issue of

Notices of the American Mathematical Society, page 692:

Notices of the American Mathematical Society, page 692:

Thomas Jech: What is... Forcing?

The explanation, not claiming completeness, is simple enough

to give you (and me) the idea.

Forcing: tool for "proving unprovability".

Cheers, ZVK(Slavek).

Message has been deleted

Jun 27, 2008, 5:55:48 PM6/27/08

to

In article

<31062d6a-7015-47d4...@r66g2000hsg.googlegroups.com>,

Tonico <Toni...@yahoo.com> wrote:

<31062d6a-7015-47d4...@r66g2000hsg.googlegroups.com>,

Tonico <Toni...@yahoo.com> wrote:

I think Jones is saying that the answer to the question is: "This

assertion is false."

Jun 27, 2008, 6:01:19 PM6/27/08

to

moorthy wrote:

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

It states that any simple explanation will fail somewhere.

Cheers,

RR

Jun 28, 2008, 12:45:25 PM6/28/08

to

In what sense is that a "good explanation on Gödel's incompleteness

theorem in a simple way"?

--

Aatu Koskensilta (aatu.kos...@uta.fi)

"Wovon man nicht sprechen kann, daruber müss man schweigen"

- Ludwig Wittgenstein, Tractatus Logico-Philosophics

Jun 28, 2008, 12:46:32 PM6/28/08

to

Jun 28, 2008, 10:33:18 AM6/28/08

to

On 28 Jun 2008 19:46:32 +0300, Aatu Koskensilta

<aatu.kos...@uta.fi> wrote:

<aatu.kos...@uta.fi> wrote:

>Rainer Rosenthal <r.ros...@web.de> writes:

>> moorthy wrote:

>> > Can somebody provide me some good explanation on Godel's

>> > incompleteness theorem in a simple way.

>>

>> It states that any simple explanation will fail somewhere.

>

>How does Gödel's incompleteness theorem state that?

I think his simple explanation failed somewhere.

Jun 28, 2008, 12:55:41 PM6/28/08

to

moorthy <cmkmo...@gmail.com> writes:

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

An excellent and readable source on the incompleteness theorems is

Torkel Franzén's _Gödel's Theorem -- an Incomplete Guide to its Use

and Abuse_.

The first incompleteness theorem states that for any formal theory in

which elementary arithmetic can be carried out we can find a statement

G about the natural numbers with the property that if the theory is

consistent G is true but not formally derivable in the theory.

Here a formal theory consists of a mathematically specified language

together with rules for deriving formulas in the language from other

formulas, with certain formulas specified as axioms. A formal theory

is consistent if by means of the rules it is not possible to derive a

formula of the form "A and not-A" from the axioms. For any given

theory we might take the formula G furnished by the proof to be of the

form "the Diophantine equation D(x1, ..., xn) = 0 has no solutions",

and its being true if the theory is consistent means simply that if no

formula of the form "A and not-A" is derivable by the rules from the

axioms there are no solutions to the Diophantine equation D(x1, ...,

xn) = 0. (The equation depends on the theory in question).

Jun 28, 2008, 12:57:16 PM6/28/08

to

Neilist <Neil...@gmail.com> writes:

> Complete means that any truthful statement can be derived from the

> axioms of the system.

No, it doesn't.

> Moorthy, read or skim Godel Escher Bach by Douglas Hofstadter. It

> is excellent - entertaining and informative, and it deserved the

> Pulitzer Prize.

It also has the tendency to make people's head swim in confusion. For

a more sober approach I recommend Torkel Franzén's _Gödel's Theorem_,

Jun 28, 2008, 12:59:56 PM6/28/08

to

mag...@math.berkeley.edu (Arturo Magidin) writes:

> It's a reasonably good explanation, though it would be better to add

> that for the result to apply to a given "mathematical system", it must

> be on the one hand sufficiently complex (so as to allow certain

> arithmetical propositions to be 'coded'), and on the other hand, not

> too complex (e.g., one must be able to recognize whether a given

> sentence is an axiom of not); that is, there are some mild (and some

> not-so-mild) technical restrictions on the systems to which the

> theorem applies.

This is an odd use of "complex". In the ordinary sense there are

monstrously complex complete theories, and some theories which are

incomplete are not at all complex.

> Actually, as an intro to the theorem itself I think I might direct him

> to Nagel and Newman's little booklet, "Goedel's Proof". Certainly a

> quicker read than Hofstadter's otherwise very good book.

A quick read, to be sure, but also marred with all sorts of

misconceptios. There are much better sources these days.

Jun 28, 2008, 1:03:34 PM6/28/08

to

Neilist <Neil...@gmail.com> writes:

> On Jun 27, 1:52 pm, Dave Seaman <dsea...@no.such.host> wrote:

>

> > Actually, "complete" means that for any proposition P, either P or

> > ~P can be derived from the axioms of the system.

>

> Isn't that the same as "any truthful statement", like I said, since

> either P or ~P is true but not both, by the Law of Excluded Middle?

No. It is entirely possible for a theory to prove all sorts of stuff

and fail to be inconsistent. For example, consider the theory in the

language of arithmetic with "0=1" as its sole axiom.

Note here that in order to speak of truth or falsity of sentences we

must have some interpretation in mind, e.g. that the quantifiers range

over the naturals, '0' means 0, '+' means addition and so on, in case

of the language of arithmetic. If we do not have a fixed

interpretation in mind it makes no sense to speak of truth or falsity

of formal sentences, but it does make perfect sense to speak of

consistency of a theory even in that case, since the notion is defined

purely syntactically, in terms of formal derivations and the form of

formulas.

Jun 28, 2008, 1:19:04 PM6/28/08

to

Jun 28, 2008, 11:34:08 AM6/28/08

to

In article <82d4m1l...@A166.veli3.tontut.fi>,

Aatu Koskensilta <aatu.kos...@uta.fi> wrote:

>mag...@math.berkeley.edu (Arturo Magidin) writes:

>

>> It's a reasonably good explanation, though it would be better to add

>> that for the result to apply to a given "mathematical system", it must

>> be on the one hand sufficiently complex (so as to allow certain

>> arithmetical propositions to be 'coded'), and on the other hand, not

>> too complex (e.g., one must be able to recognize whether a given

>> sentence is an axiom of not); that is, there are some mild (and some

>> not-so-mild) technical restrictions on the systems to which the

>> theorem applies.

>

>This is an odd use of "complex".

Aatu Koskensilta <aatu.kos...@uta.fi> wrote:

>mag...@math.berkeley.edu (Arturo Magidin) writes:

>

>> It's a reasonably good explanation, though it would be better to add

>> that for the result to apply to a given "mathematical system", it must

>> be on the one hand sufficiently complex (so as to allow certain

>> arithmetical propositions to be 'coded'), and on the other hand, not

>> too complex (e.g., one must be able to recognize whether a given

>> sentence is an axiom of not); that is, there are some mild (and some

>> not-so-mild) technical restrictions on the systems to which the

>> theorem applies.

>

>This is an odd use of "complex".

For the first, I probably should have used "strong enough" rather than

"sufficiently complex".

>In the ordinary sense there are

>monstrously complex complete theories, and some theories which are

>incomplete are not at all complex.

Ehr... How does this contradict or undermine what I said? I realize

that there are "monstrously complex complete theories", even

consistent; why is this contrary to my saying that if the theory is

too complex the theorem need not apply? And while there are some

theories that are extremely simple and incomplete, they are not

incomplete by virtue of being able to apply Goedel's Theorem to

them. I did specify that "for the result to apply", not "for the

conclusion to hold".

Jun 28, 2008, 1:59:06 PM6/28/08

to

mag...@math.berkeley.edu (Arturo Magidin) writes:

> In article <82d4m1l...@A166.veli3.tontut.fi>,

> Aatu Koskensilta <aatu.kos...@uta.fi> wrote:

>

> >In the ordinary sense there are monstrously complex complete

> >theories, and some theories which are incomplete are not at all

> >complex.

>

> Ehr... How does this contradict or undermine what I said? I realize

> that there are "monstrously complex complete theories", even

> consistent; why is this contrary to my saying that if the theory is

> too complex the theorem need not apply?

There are monstrously complex complete axiomatisable theories. The

conditions a theory must satisfy for the incompleteness theorems to

apply are not very happily expressed in terms of complexity at all.

> And while there are some theories that are extremely simple and

> incomplete, they are not incomplete by virtue of being able to apply

> Goedel's Theorem to them. I did specify that "for the result to

> apply", not "for the conclusion to hold".

Robinson arithmetic, which can be shown incomplete by a Gödelian

argument, is not complex in any ordinary sense of the word.

--

Aatu Koskensilta (aatu.kos...@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"

Jun 28, 2008, 12:07:23 PM6/28/08

to

On Jun 28, 9:59 am, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

> magi...@math.berkeley.edu (Arturo Magidin) writes:

> > It's a reasonably good explanation, though it would be better to add

> > that for the result to apply to a given "mathematical system", it must

> > be on the one hand sufficiently complex (so as to allow certain

> > arithmetical propositions to be 'coded'), and on the other hand, not

> > too complex (e.g., one must be able to recognize whether a given

> > sentence is an axiom of not); that is, there are some mild (and some

> > not-so-mild) technical restrictions on the systems to which the

> > theorem applies.

>

> This is an odd use of "complex". In the ordinary sense there are

> monstrously complex complete theories, and some theories which are

> incomplete are not at all complex.

>

> > Actually, as an intro to the theorem itself I think I might direct him

> > to Nagel and Newman's little booklet, "Goedel's Proof". Certainly a

> > quicker read than Hofstadter's otherwise very good book.

>

> A quick read, to be sure, but also marred with all sorts of

> misconceptios. There are much better sources these days.

>

> --

> Aatu Koskensilta (aatu.koskensi...@uta.fi)

>

> "Wovon man nicht sprechen kann, daruber müss man schweigen"

> - Ludwig Wittgenstein, Tractatus Logico-Philosophics

> magi...@math.berkeley.edu (Arturo Magidin) writes:

> > It's a reasonably good explanation, though it would be better to add

> > that for the result to apply to a given "mathematical system", it must

> > be on the one hand sufficiently complex (so as to allow certain

> > arithmetical propositions to be 'coded'), and on the other hand, not

> > too complex (e.g., one must be able to recognize whether a given

> > sentence is an axiom of not); that is, there are some mild (and some

> > not-so-mild) technical restrictions on the systems to which the

> > theorem applies.

>

> This is an odd use of "complex". In the ordinary sense there are

> monstrously complex complete theories, and some theories which are

> incomplete are not at all complex.

>

> > Actually, as an intro to the theorem itself I think I might direct him

> > to Nagel and Newman's little booklet, "Goedel's Proof". Certainly a

> > quicker read than Hofstadter's otherwise very good book.

>

> A quick read, to be sure, but also marred with all sorts of

> misconceptios. There are much better sources these days.

>

> --

>

> "Wovon man nicht sprechen kann, daruber müss man schweigen"

> - Ludwig Wittgenstein, Tractatus Logico-Philosophics

Please cite some of the sources.

Jun 28, 2008, 2:34:20 PM6/28/08

to

amzoti <amz...@gmail.com> writes:

> Please cite some of the sources.

Torkel Franzén's _Gödel's Theorem -- an Incomplete Guide to Its Use

and Abuse_ is an excellent semi-popular account, giving the reader a

sober understanding of the incompleteness theorems and their

significance -- and also of their insignificance to all sorts of

things. For a more thorough treatment one could have a look at

Peter Smith: An Introduction to Gödel's Theorems

Torkel Franzén: Inexhaustibility -- a Non-Exhaustive Treatment

Raymond Smullyan: Gödel's Incompleteness Theorems

--

Aatu Koskensilta (aatu.kos...@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"

Jun 28, 2008, 12:14:59 PM6/28/08

to

On Jun 27, 8:36 pm, magi...@math.berkeley.edu (Arturo Magidin) wrote:

> It's a reasonably good explanation, though it would be better to add

> that for the result to apply to a given "mathematical system", it must

> be on the one hand sufficiently complex (so as to allow certain

> arithmetical propositions to be 'coded'), and on the other hand, not

> too complex (e.g., one must be able to recognize whether a given

> sentence is an axiom of not

Actually, the set of axioms need not be recursive but only recursively

enumerable.

Regards

Jun 28, 2008, 12:36:51 PM6/28/08

to

> In article

> <31062d6a-7015-47d4...@r66g2000hsg.goog

> <31062d6a-7015-47d4...@r66g2000hsg.goog

I think he is suggesting, as Arturo implied, that the

unprovable, self-referencing problem called, among other

names, Russell's Antinomy ("This assertion is false" is

true IFF the assertion is true)is a simple explanation of

Godel's theorem. Is it? Is it a simple explanation of

Godel's theorem if one substitutes, as Arturo suggested,

"This assertion is unprovable" (i.e., unprovable IFF the

assertion is provable)?

Tom

Jun 28, 2008, 2:32:52 PM6/28/08

to

In article <82r6ahj...@A166.veli3.tontut.fi>,

Aatu Koskensilta <aatu.kos...@uta.fi> wrote:

>mag...@math.berkeley.edu (Arturo Magidin) writes:

>

>> In article <82d4m1l...@A166.veli3.tontut.fi>,

>> Aatu Koskensilta <aatu.kos...@uta.fi> wrote:

>>

>> >In the ordinary sense there are monstrously complex complete

>> >theories, and some theories which are incomplete are not at all

>> >complex.

>>

>> Ehr... How does this contradict or undermine what I said? I realize

>> that there are "monstrously complex complete theories", even

>> consistent; why is this contrary to my saying that if the theory is

>> too complex the theorem need not apply?

>

>There are monstrously complex complete axiomatisable theories. The

>conditions a theory must satisfy for the incompleteness theorems to

>apply are not very happily expressed in terms of complexity at all.

Aatu Koskensilta <aatu.kos...@uta.fi> wrote:

>mag...@math.berkeley.edu (Arturo Magidin) writes:

>

>> In article <82d4m1l...@A166.veli3.tontut.fi>,

>> Aatu Koskensilta <aatu.kos...@uta.fi> wrote:

>>

>> >In the ordinary sense there are monstrously complex complete

>> >theories, and some theories which are incomplete are not at all

>> >complex.

>>

>> Ehr... How does this contradict or undermine what I said? I realize

>> that there are "monstrously complex complete theories", even

>> consistent; why is this contrary to my saying that if the theory is

>> too complex the theorem need not apply?

>

>There are monstrously complex complete axiomatisable theories. The

>conditions a theory must satisfy for the incompleteness theorems to

>apply are not very happily expressed in terms of complexity at all.

So, it's really about an unfelicitous choice of word?

>> And while there are some theories that are extremely simple and

>> incomplete, they are not incomplete by virtue of being able to apply

>> Goedel's Theorem to them. I did specify that "for the result to

>> apply", not "for the conclusion to hold".

>

>Robinson arithmetic, which can be shown incomplete by a Gödelian

>argument, is not complex in any ordinary sense of the word.

I would disagree, but then it would be two non-native speakers (I

believe; at least one, for sure) disagreeing about the 'ordinary

sense' of a word. The theory is, nonetheless, 'strong enough' to

sustain the argument.

The point, in any case, is that not any old mathematical theory will

do: there are technical requirements that need to be met, though I

perhaps failed to phrase them in a manner that was pleasing to your

ears and others.

Jun 28, 2008, 2:43:47 PM6/28/08

to

On Jun 28, 6:34 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

> amzoti <amz...@gmail.com> writes:

> > Please cite some of the sources.

>

> Torkel Franzén's _Gödel's Theorem -- an Incomplete Guide to Its Use

> and Abuse_ is an excellent semi-popular account, giving the reader a

> sober understanding of the incompleteness theorems and their

> significance -- and also of their insignificance to all sorts of

> things. For a more thorough treatment one could have a look at

>

> Peter Smith: An Introduction to Gödel's Theorems

> Torkel Franzén: Inexhaustibility -- a Non-Exhaustive Treatment

> Raymond Smullyan: Gödel's Incompleteness Theorems

>

> --

> Aatu Koskensilta (aatu.koskensi...@uta.fi)> amzoti <amz...@gmail.com> writes:

> > Please cite some of the sources.

>

> Torkel Franzén's _Gödel's Theorem -- an Incomplete Guide to Its Use

> and Abuse_ is an excellent semi-popular account, giving the reader a

> sober understanding of the incompleteness theorems and their

> significance -- and also of their insignificance to all sorts of

> things. For a more thorough treatment one could have a look at

>

> Peter Smith: An Introduction to Gödel's Theorems

> Torkel Franzén: Inexhaustibility -- a Non-Exhaustive Treatment

> Raymond Smullyan: Gödel's Incompleteness Theorems

>

> --

>

> "Wovon man nicht sprechen kann, darüber muss man schweigen"

> - Ludwig Wittgenstein, Tractatus Logico-Philosophics

thanks for your responses,,

It would be better, if you can indicate me some e-books of this

category..

CMKMoorthy

Jun 28, 2008, 5:17:09 PM6/28/08

to

What Godel did was to create a statement in number theory, S, that said

"S is not provable." If Godel had created a statement S that said "S is

not true", then Godel would have proved that mathematics is internally

self-contradictory, i.e., the famous liar paradox. But Godel was just

shy of the liar paradox. If you try to get the liar paradox out of this

statement, you instead get a statement that is clearly true, but clearly

not provable in number theory. (Of course, you would argue that since

we showed S was true, that we have in effect provided a proof. But you

will see that you had to use the extra axiom "number theory is

consistent" and hence all you have really proved is that it is not

possible to prove "number theory is consistent" within number theory.)

Actually you need to use an additional meta-assumption "provability

implies truth" to make this work. If you don't want to use this, use

instead an argument that works as follows:

S = "if S is true, then Santa-Claus exists"

except replace "S is true" by "S is provable", and "Santa Claus exists"

by "0=1".

A lot of Godel's proof was to demonstrate that provability was writable

in terms of number theory. He had to show that any computer program was

expressible in number theory.

Stephen

Jun 28, 2008, 5:59:45 PM6/28/08

to

On Jun 27, 6:28 pm, moorthy <cmkmoor...@gmail.com> wrote:

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

If you go to http://www.godelbook.net/ you can download the PDF of the

first chapter of my Gödel book, which ought to give you some clue as

to what it is about!

Jun 28, 2008, 6:16:09 PM6/28/08

to

On Jun 28, 1:59 pm, Peter_Smith <ps...@cam.ac.uk> wrote:

> On Jun 27, 6:28 pm, moorthy <cmkmoor...@gmail.com> wrote:

>

> > Can somebody provide me some good explanation on Godel's

> > incompleteness theorem in a simple way.

>

> If you go tohttp://www.godelbook.net/you can download the PDF of the> On Jun 27, 6:28 pm, moorthy <cmkmoor...@gmail.com> wrote:

>

> > Can somebody provide me some good explanation on Godel's

> > incompleteness theorem in a simple way.

>

> first chapter of my Gödel book, which ought to give you some clue as

> to what it is about!

In the future I think there will be many more axioms.

Mitch Raemsch

Jun 28, 2008, 6:59:42 PM6/28/08

to

Toni Lassila schrieb:

:-)

Jun 29, 2008, 8:32:12 AM6/29/08

to

moorthy wrote:

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

> Can somebody provide me some good explanation on Godel's

> incompleteness theorem in a simple way.

Here is my analysis; others may comment:

Goedel's undecidable statement circumvents syntactical self-reference by

substituting for it an endless reference to infinity. When expanded, it

appears like this:

"This is unprovable: This unprovable: This is unprovable: ..."

Goedel's actual theorem states that in any *omega-consistent*, *recursively

axiomatizable* theory (technical terms here) strong enough to support

arithmetic, there are statements neither provably true nor provably false.

Omega-consistency means that if a theorem is provable for all number-terms,

then there are no provable counterexamples -- sometimes informally

summarized by saying that if P(1), P(2), P(3), ... are provable, then

Ex~P(x) is not provable.

Jun 29, 2008, 11:36:09 AM6/29/08

to

"Scott H" <nospam> writes:

> Goedel's undecidable statement circumvents syntactical self-reference by

> substituting for it an endless reference to infinity. When expanded, it

> appears like this:

>

> "This is unprovable: This unprovable: This is unprovable: ..."

No such expansions or "endless references to infinity" can be found in

Gödel's proof or the Gödel sentence of a theory.

> Omega-consistency means that if a theorem is provable for all number-terms,

> then there are no provable counterexamples -- sometimes informally

> summarized by saying that if P(1), P(2), P(3), ... are provable, then

> Ex~P(x) is not provable.

This "informal summary" is in fact much clearer than the explanation

preceding it.

--

Aatu Koskensilta (aatu.kos...@uta.fi)

Jun 29, 2008, 9:56:37 AM6/29/08

to

On Jun 28, 9:59 pm, Peter_Smith <ps...@cam.ac.uk> wrote:

> On Jun 27, 6:28 pm, moorthy <cmkmoor...@gmail.com> wrote:

>

> > Can somebody provide me some good explanation on Godel's

> > incompleteness theorem in a simple way.

>

> If you go tohttp://www.godelbook.net/you can download the PDF of the> On Jun 27, 6:28 pm, moorthy <cmkmoor...@gmail.com> wrote:

>

> > Can somebody provide me some good explanation on Godel's

> > incompleteness theorem in a simple way.

>

> first chapter of my Gödel book, which ought to give you some clue as

> to what it is about!

i was able to read the first chapter of your book & was able to get

some understanding on the first incompleteness theorem of Godel..

But i need to spend some more time to get grasp on the second theorem

though...

i want to brief my understanding & would like to seek clarification

for my following doubt.

First theorem states that, for every theorem, there will exist a Godel

statement that will be unprovable using the theorem, but this

statement will be true...

You have provided a small theory on number system with basic addition

& multiplication. But i would like to know the Godel statement for

this theorem, which should be unprovable...

Please correct my understanding, if i am wrong somewhere..

CMKM

Jun 29, 2008, 2:45:04 PM6/29/08

to

Stephen Montgomery-Smith <ste...@math.missouri.edu> writes:

> What Godel did was to create a statement in number theory, S, that

> said "S is not provable."

To forestall possible misunderstanding here, let's be a bit more

explicit. Gödel showed how to create, for any formal theory T in which

elementary arithmetic can be carried through, a statement about

natural numbers G such that

(*) G is true if and only if G is not formally derivable in T

Now, G is a statement of the natural numbers of the form "for all

naturals n, P(n)" where P is a property of naturals such that given a

natural m it can be established using nothing but elementary

arithmetic, carrying out multiplications and sums, whether or not P

holds of m. By assumption, truths of the form "P holds of the natural

m" and "P does not hold of the natural m" can be established in T, and

we get the following

if G is false, then it is formally derivable in T that G is false

for if G is false, there is some natural k such that P does not hold

of k, and by the previous observation, it is then formally derivable

in T that P does not hold of k, and hence also that "for some n, not

P(n)".

Suppose now that G = "for all n, P(n)" were formally derivable in

T. By (*) we would have that G is false, that is, there is some k such

that not P(k). It would then be formally derivable in T that G is

false, i.e. not-G would be derivable. T would then be inconsistent:

both G and not-G would be derivable in T.

This argument establishes that if T is consistent, G is not formally

derivable in T. But by (*) G is then true, and thus there is an

arithmetical truth not provable in T, provided T is consistent.[1]

The tricky bit is of course showing that there is a sentence about the

naturals of the form "for all n, P(n)", with P of the appropriate

kind, such that (*) holds. This involves all sorts of trickery,

coding, ingenuity, and so on, the gory details of which are given in

any textbook on the subject.

Why be so technical here? I'll be frank and admit it's an exercise in

both pedagogy and futility. Pondering the incompleteness theorem in

terms of the Gödel sentence expressed as

This sentence is not provable.

and similar exercises easily lends a mystical air to the whole thing,

helping to obscure the purely mathematical content of the theorem, as

well as its general significance. In fact, as many have observed in

the past, it is perhaps best to forget all about the Gödel sentence,

and simply present the result in the form

For any consistent formal theory in which elementary arithmetic can

be carried through, there exists infinitely many true sentences of

the form "the Diophantine equation D(x1, ..., xn) = 0 has no

solutions" that are not formally derivable in the theory.

The Gödel sentence is really only of any importance in context of the

second incompleteness theorem, and lest the unprepared reader be led

astray and come off with the idea that incompleteness is all about

mind-boggling self-referential oddities and all that, it's not at all

a bad idea to downplay its role when, in fact, it plays no role apart

from suggesting metaphysical vistas of illumination.

Footnotes:

[1] Nothing has been said of *not-G* being formally derivable in

T. There is a reason for this: nothing in the argument prevents not-G

from being formally derivable in T even if T is consistent. For it

does not follow from (*) that G is false if not-G is derivable. The

theorem can be strengthened to yield, for a consistent T, a sentence R

such that neither R nor not-R is formally derivable, but this requires

some more elaborate technical machinery. Notice that if not-G is

formally derivable in T then, even if T is consistent, it proves

falsities since, by the argument above, if T is consistent, G is in

fact true.

Jun 29, 2008, 2:53:18 PM6/29/08

to

moorthy <cmkmo...@gmail.com> writes:

> First theorem states that, for every theorem, there will exist a Godel

> statement that will be unprovable using the theorem, but this

> statement will be true...

"Theory", not "theorem". Notice also that first incompleteness theorem

states only that for every formal theory (meeting certain criteria) we

can find a sentence G such that G is true but formally underivable in

the theory provided the theory is consistent.

> You have provided a small theory on number system with basic addition

> & multiplication. But i would like to know the Godel statement for

> this theorem, which should be unprovable...

The Gödel sentence of the theory is the arithmetical formulation,

through coding, of

There is not formal derivation of this sentence in the theory.

As to the second incompleteness theorem, recall that the first

incompleteness theorem establishes that the Gödel sentence G of a

theory T is true if T is consistent. Now, supposing T can formally

prove enough facts about formal derivability, it will be formally

derivable in T that

(*) if T is consistent, then G

Suppose T is consistent. Then G is not formally derivable in T. But if

"T is consistent" were formally derivable in T, we could, in T,

formally derive also G, by using (*). Thus if T is consistent, and

enough about formal derivability is formally provable in T to

establish (*), "T is consistent" is not formally derivable in T.

Jun 29, 2008, 12:33:44 PM6/29/08

to

On Jun 29, 2:32 pm, "Scott H" <nospam> wrote:

> moorthy wrote:

> > Can somebody provide me some good explanation on Godel's

> > incompleteness theorem in a simple way.

>

> Here is my analysis; others may comment:

>

> Goedel's undecidable statement circumvents syntactical self-reference by

> substituting for it an endless reference to infinity. When expanded, it

> appears like this:

>

> "This is unprovable: This unprovable: This is unprovable: ..."

> moorthy wrote:

> > Can somebody provide me some good explanation on Godel's

> > incompleteness theorem in a simple way.

>

> Here is my analysis; others may comment:

>

> Goedel's undecidable statement circumvents syntactical self-reference by

> substituting for it an endless reference to infinity. When expanded, it

> appears like this:

>

> "This is unprovable: This unprovable: This is unprovable: ..."

It appears that you consider Gödel's sentence 'ungrounded' in its meta-

theoretical interpretation.

But it is not so. The meta-theoretically interpreted G (which is a

proposition, a semantical object) does not speak of itself, it speaks

of the uninterpreted G (a syntactical object), which in turn speaks of

nothing at all since it has no semantical dimension; it is a chain of

symbols.

This stops the regress and makes Gödel's meta-theoretical proposition

perfectly grounded.

Regards

Jun 29, 2008, 12:38:03 PM6/29/08

to

On Jun 28, 7:19 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:> > <aatu.koskensi...@uta.fi> wrote:

>

> > >Rainer Rosenthal <r.rosent...@web.de> writes:

> > >> moorthy wrote:

>

> > >> > Can somebody provide me some good explanation on Godel's

> > >> > incompleteness theorem in a simple way.

>

> > >> It states that any simple explanation will fail somewhere.

>

> > >How does Gödel's incompleteness theorem state that?

>

> > I think his simple explanation failed somewhere.

>

> How did his simple explanation fail somewhere?

>

> > >Rainer Rosenthal <r.rosent...@web.de> writes:

> > >> moorthy wrote:

>

> > >> > Can somebody provide me some good explanation on Godel's

> > >> > incompleteness theorem in a simple way.

>

> > >> It states that any simple explanation will fail somewhere.

>

> > >How does Gödel's incompleteness theorem state that?

>

> > I think his simple explanation failed somewhere.

>

> How did his simple explanation fail somewhere?

In attempting self-reference?

Jun 29, 2008, 3:02:59 PM6/29/08

to

LauLuna <laurea...@yahoo.es> writes:

> In attempting self-reference?

Does my attempt at self-reference with this sentence also fail?

--

Aatu Koskensilta (aatu.kos...@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"

Jun 29, 2008, 4:50:53 PM6/29/08

to

Aatu Koskensilta wrote:

> Stephen Montgomery-Smith <ste...@math.missouri.edu> writes:

>

>> What Godel did was to create a statement in number theory, S, that

>> said "S is not provable."

>

> .............> Stephen Montgomery-Smith <ste...@math.missouri.edu> writes:

>

>> What Godel did was to create a statement in number theory, S, that

>> said "S is not provable."

>

>

> Why be so technical here? I'll be frank and admit it's an exercise in

> both pedagogy and futility. Pondering the incompleteness theorem in

> terms of the Gödel sentence expressed as

>

> This sentence is not provable.

>

> and similar exercises easily lends a mystical air to the whole thing,

> helping to obscure the purely mathematical content of the theorem, as

I think that to approach Goedel's Theorem your way (getting all the

technical details right) is very helpful, and exactly for the reasons

you state. But approaching it my way (trying to see the big picture) is

also helpful. The disadvantage of your way is that if the person

doesn't see the big picture, then they can get lost in the technical

details. This lends it a different mysticism, namely, this must be very

difficult to understand.

The best approach is to do it both ways.

I myself read a book that gave the technical details, but when I read

it, I skipped many of the details. It was useful to know that it could

be done, but I didn't want to read it myself.

Jun 30, 2008, 4:49:30 AM6/30/08

to

Aatu Koskensilta wrote:

> Pondering the incompleteness theorem in

> terms of the Gödel sentence expressed as

>

> This sentence is not provable.

>

> and similar exercises easily lends a mystical air to the whole thing,

> helping to obscure the purely mathematical content of the theorem, as

> well as its general significance. In fact, as many have observed in

> the past, it is perhaps best to forget all about the Gödel sentence,

> and simply present the result in the form

>

> For any consistent formal theory in which elementary arithmetic can

> be carried through, there exists infinitely many true sentences of

> the form "the Diophantine equation D(x1, ..., xn) = 0 has no

> solutions" that are not formally derivable in the theory.

> Pondering the incompleteness theorem in

> terms of the Gödel sentence expressed as

>

> This sentence is not provable.

>

> and similar exercises easily lends a mystical air to the whole thing,

> helping to obscure the purely mathematical content of the theorem, as

> well as its general significance. In fact, as many have observed in

> the past, it is perhaps best to forget all about the Gödel sentence,

> and simply present the result in the form

>

> For any consistent formal theory in which elementary arithmetic can

> be carried through, there exists infinitely many true sentences of

> the form "the Diophantine equation D(x1, ..., xn) = 0 has no

> solutions" that are not formally derivable in the theory.

What happened to the recursion theoretic formulation?

(You seemed to be so fond of that, recently.)

--

Cheers,

Herman Jurjus

Jun 30, 2008, 11:18:22 AM6/30/08

to

Herman Jurjus <hju...@hetnet.nl> writes:

> What happened to the recursion theoretic formulation?

Which formulation is the most appropriate depends on the context. If

we are concerned about the possibility that some mechanical form of

reasoning escapes incompleteness, perhaps by relying on some esoteric

logic, the recursion theoretic formulation, in terms of productivity

of the set of Pi-0-1 truths, is relevant.

It is entirely understandable writes of popular expositions like to

pontificate on the fact that the proof is inspired by the liar

paradox, involves a self-referential sentence, and so on. This is just

the sort of stuff people of certain bent find exciting, after

all. However, these aspects of the proof are almost entirely

irrelevant to actual mathematical and philosophical applications of

the incompleteness theorems -- for example, not a whit of pondering

about the liar is involved in the highly significant implication of

the second incompleteness theorem that very abstract assertions about

the higher reaches of the set theoretic hierarchy have consequences in

the realm of finite combinatorics. Thus, if one seeks a general

understanding of the incompleteness theorems and their significance,

as far as mathematics and philosophy go, it is probably advisable to

concentrate on just the statements of these theorems rather than their

proofs, or the Gödel sentence of this or that formal theory.

Jun 30, 2008, 11:09:18 AM6/30/08

to

Aatu Koskensilta wrote:

> Herman Jurjus <hju...@hetnet.nl> writes:

>

>> What happened to the recursion theoretic formulation?

>

> Which formulation is the most appropriate depends on the context. If

> we are concerned about the possibility that some mechanical form of

> reasoning escapes incompleteness, perhaps by relying on some esoteric

> logic, the recursion theoretic formulation, in terms of productivity

> of the set of Pi-0-1 truths, is relevant.

> Herman Jurjus <hju...@hetnet.nl> writes:

>

>> What happened to the recursion theoretic formulation?

>

> Which formulation is the most appropriate depends on the context. If

> we are concerned about the possibility that some mechanical form of

> reasoning escapes incompleteness, perhaps by relying on some esoteric

> logic, the recursion theoretic formulation, in terms of productivity

> of the set of Pi-0-1 truths, is relevant.

It also seems the 'right' formulation for those who are concerned with

the limits of the axiomatic method.

Ever since Euclid, reasoning from axioms seemed to be /the/ way to do

mathematics. And here's a result implying that the set of all sentences

true in the natural number sequence is not (r.e.) axiomatisable.

This way to look at Goedel's theorem may also serve to make it clear why

the result is so 'shocking'.

> It is entirely understandable writes of popular expositions like to

> pontificate on the fact that the proof is inspired by the liar

> paradox, involves a self-referential sentence, and so on. This is just

> the sort of stuff people of certain bent find exciting, after

> all. However, these aspects of the proof are almost entirely

> irrelevant to actual mathematical and philosophical applications of

> the incompleteness theorems -- for example, not a whit of pondering

> about the liar is involved in the highly significant implication of

> the second incompleteness theorem that very abstract assertions about

> the higher reaches of the set theoretic hierarchy have consequences in

> the realm of finite combinatorics. Thus, if one seeks a general

> understanding of the incompleteness theorems and their significance,

> as far as mathematics and philosophy go, it is probably advisable to

> concentrate on just the statements of these theorems rather than their

> proofs, or the Gödel sentence of this or that formal theory.

Couldn't agree more.

But it's too late now; Hofstadter's book has already done the damage.

--

Cheers,

Herman Jurjus

Jun 30, 2008, 12:09:30 PM6/30/08

to

> Can somebody provide me some good explanation on

> Godel's

> incompleteness theorem in a simple way.

> Godel's

> incompleteness theorem in a simple way.

A pretty clear sketch of what Godel did can be found here:

Jun 30, 2008, 5:03:59 PM6/30/08

to

On 28 kesä, 20:59, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

> magi...@math.berkeley.edu (Arturo Magidin) writes:

> > In article <82d4m1lckz....@A166.veli3.tontut.fi>,

> > Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

>

> > >In the ordinary sense there are monstrously complex complete

> > >theories, and some theories which are incomplete are not at all

> > >complex.

>

> > Ehr... How does this contradict or undermine what I said? I realize

> > that there are "monstrously complex complete theories", even

> > consistent; why is this contrary to my saying that if the theory is

> > too complex the theorem need not apply?

>

> There are monstrously complex complete axiomatisable theories. The

> conditions a theory must satisfy for the incompleteness theorems to

> apply are not very happily expressed in terms of complexity at all.

> magi...@math.berkeley.edu (Arturo Magidin) writes:

> > In article <82d4m1lckz....@A166.veli3.tontut.fi>,

> > Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

>

> > >In the ordinary sense there are monstrously complex complete

> > >theories, and some theories which are incomplete are not at all

> > >complex.

>

> > Ehr... How does this contradict or undermine what I said? I realize

> > that there are "monstrously complex complete theories", even

> > consistent; why is this contrary to my saying that if the theory is

> > too complex the theorem need not apply?

>

> There are monstrously complex complete axiomatisable theories. The

> conditions a theory must satisfy for the incompleteness theorems to

> apply are not very happily expressed in terms of complexity at all.

I don`t know. Every complete r.e FOL theory is recursive set, so in a

sense it is not as complex as any r.e but not recursive set.

> > And while there are some theories that are extremely simple and

> > incomplete, they are not incomplete by virtue of being able to apply

> > Goedel's Theorem to them. I did specify that "for the result to

> > apply", not "for the conclusion to hold".

>

> Robinson arithmetic, which can be shown incomplete by a Gödelian

> argument, is not complex in any ordinary sense of the word.

It is a recursively enumerable, but not recursive set, so I would call

it a complex set.

> Aatu Koskensilta (aatu.koskensi...@uta.fi)

Jul 1, 2008, 10:20:56 AM7/1/08

to

On Jun 28, 12:57 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

> Neilist <Neilis...@gmail.com> writes:

> > Complete means that any truthful statement can be derived from the

> > axioms of the system.

>

> No, it doesn't.

> Neilist <Neilis...@gmail.com> writes:

> > Complete means that any truthful statement can be derived from the

> > axioms of the system.

>

> No, it doesn't.

What a lousy response! "No, it doesn't". Childish. I'll just say

"yes it does".

Give the correct definition then, genius (sarcasm)!

> > Moorthy, read or skim Godel Escher Bach by DouglasHofstadter. It

> > is excellent - entertaining and informative, and it deserved the

> > Pulitzer Prize.

>

> It also has the tendency to make people's head swim in confusion.

Confusing for you, apparently. Godel Escher Bach is great fun, and it

eases the reader into Godel's work.

>For

> a more sober approach I recommend Torkel Franzén's _Gödel's Theorem_,

But is Franzen's work too sober = dry = boring? Or too advanced for

the original poster or to the average person?

Jul 1, 2008, 10:24:06 AM7/1/08

to

On Jun 30, 11:09 am, Herman Jurjus <hjur...@hetnet.nl> wrote:

<snip>

> But it's too late now; Hofstadter's book has already done the damage.

The damaage is in your head, buddy. Hofstadter's Godel Escher Bach is

a GREAT book! Fun, informative, diverse, touching on art, music,

math, science, and more!

Jul 1, 2008, 10:44:55 AM7/1/08

to

Neilist <Neil...@gmail.com> writes:

> On Jun 28, 12:57 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

>> Neilist <Neilis...@gmail.com> writes:

>> > Complete means that any truthful statement can be derived from the

>> > axioms of the system.

>>

>> No, it doesn't.

>

> What a lousy response! "No, it doesn't". Childish. I'll just say

> "yes it does".

>

> Give the correct definition then, genius (sarcasm)!

A theory T is complete if, for every formula P in the language of T,

either T |- P or T |- ~P.

--

"...you are around so that I have something else to do when I'm not

figuring something important out. I was especially intrigued on this

iteration by cursing, which I think I'll continue at some later date

as it's so amusing." --- James S. Harris

Jul 1, 2008, 10:56:49 AM7/1/08

to

It is far too long. I'm sure that the same material could be covered in

a book half the size.

--

He is not here; but far away

The noise of life begins again

And ghastly thro' the drizzling rain

On the bald street breaks the blank day.

Jul 1, 2008, 11:36:56 AM7/1/08

to

On Jul 1, 10:56 am, Frederick Williams <frederick.willia...@tesco.net>

wrote:

wrote:

<snip>

> It is far too long. I'm sure that the same material could be covered in

> a book half the size.

Then the publisher need only decrease the font size in half to please

YOU! (nyuk nyuk nyuk)

:-)

Jul 1, 2008, 11:59:55 AM7/1/08

to

On Jul 1, 5:20 pm, Neilist <Neilis...@gmail.com> wrote:

> On Jun 28, 12:57 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

>

> > Neilist <Neilis...@gmail.com> writes:

> > > Complete means that any truthful statement can be derived from the

> > > axioms of the system.

>

> > No, it doesn't.

>

> What a lousy response! "No, it doesn't". Childish. I'll just say

> "yes it does".

>

> Give the correct definition then, genius (sarcasm)!

>

********************************************************************> On Jun 28, 12:57 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

>

> > Neilist <Neilis...@gmail.com> writes:

> > > Complete means that any truthful statement can be derived from the

> > > axioms of the system.

>

> > No, it doesn't.

>

> What a lousy response! "No, it doesn't". Childish. I'll just say

> "yes it does".

>

> Give the correct definition then, genius (sarcasm)!

>

You shouldn't get pissed off: the definition of complete axiomatic

system is really NOT what you said: an axiomatic system is complete if

for any (well-formed) statement P, either P or ~P can be proved within

the axioms.

Put in another form, it could be said that the system is complete if

any well-defined valid formula is a (provable) theorem within the

system.

If you say "any truthful statement can be derived", you are messing

things up: how can you know whether a statement is truthful if you

haven't yet proved it? It sounds like a tautology: if the statement

can be derived (I understand this as meaning proved), then it is

truthful, and of course the other way around: if it is truthful then

it is so because it can be "derived" (= proved) in the system.

Regards

Tonio

Jul 1, 2008, 1:20:26 PM7/1/08

to

On Jul 1, 11:59 am, Tonico <Tonic...@yahoo.com> wrote:

<snip>

> You shouldn't get pissed off: the definition of complete axiomatic

> system is really NOT what you said: an axiomatic system is complete if

> for any (well-formed) statement P, either P or ~P can be proved within

> the axioms.

>

> Put in another form, it could be said that the system is complete if

> any well-defined valid formula is a (provable) theorem within the

> system.

>

> If you say "any truthful statement can be derived", you are messing

> things up: how can you know whether a statement is truthful if you

> haven't yet proved it? It sounds like a tautology: if the statement

> can be derived (I understand this as meaning proved), then it is

> truthful, and of course the other way around: if it is truthful then

> it is so because it can be "derived" (= proved) in the system.

>

> Regards

> Tonio

The original poster asked:

"Can somebody provide me some good explanation on Godel's

incompleteness theorem in a simple way."

I knew I'd get criticism for being inexact. Fine.

But when you or others start discussing P and ~P and talking axioms,

complexity of systems, etc., I think you're getting away from what the

original poster requested, which was a good yet simple explanation.

Of course, the original poster did not require 30 words or less, and

the original poster did not say "no math or logic symbols".

But how would you explain Godel's work, consistency, and completeness

without resorting to symbolic equations? I tried, since I did not

know the expertise of the original poster.

It must rankle mathematicians when a theorem or mathematical result is

paraphrased, and even without math or logic symbols, for it loses

exactness. Horror!

Jul 1, 2008, 2:54:16 PM7/1/08

to

On Tue, 1 Jul 2008 10:20:26 -0700 (PDT), Neilist wrote:

> But when you or others start discussing P and ~P and talking axioms,

> complexity of systems, etc., I think you're getting away from what the

> original poster requested, which was a good yet simple explanation.

> Of course, the original poster did not require 30 words or less, and

> the original poster did not say "no math or logic symbols".

> But how would you explain Godel's work, consistency, and completeness

> without resorting to symbolic equations? I tried, since I did not

> know the expertise of the original poster.

> It must rankle mathematicians when a theorem or mathematical result is

> paraphrased, and even without math or logic symbols, for it loses

> exactness. Horror!

A system is complete if every proposition expressible in the system is

decidable. That is, each proposition can be either proved or disproved.

No symbols. And no need to explain what it means for a statement to be

"true" if it can't be proved.

--

Dave Seaman

Third Circuit ignores precedent in Mumia Abu-Jamal ruling.

<http://www.indybay.org/newsitems/2008/03/29/18489281.php>

Jul 2, 2008, 6:07:47 AM7/2/08

to

Neilist <Neil...@gmail.com> writes:

> It must rankle mathematicians when a theorem or mathematical result is

> paraphrased, and even without math or logic symbols, for it loses

> exactness. Horror!

There is nothing wrong with informal explanations -- even if, as you

note, experts are sometimes overeager in their criticism --, except

when they're likely to mislead or confuse. Surely you're not

suggesting that giving an incorrect definition for completeness

somehow makes the explanation easier to follow?

--

Aatu Koskensilta (aatu.kos...@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"

- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

Jul 2, 2008, 6:13:19 AM7/2/08

to

Tonico <Toni...@yahoo.com> writes:

> If you say "any truthful statement can be derived", you are messing

> things up: how can you know whether a statement is truthful if you

> haven't yet proved it? It sounds like a tautology: if the statement

> can be derived (I understand this as meaning proved), then it is

> truthful, and of course the other way around: if it is truthful then

> it is so because it can be "derived" (= proved) in the system.

For the first-order language of arithmetic truth is a mathematically

defined property of formal sentences, and it's mathematically provable

that there are many (consistent) formal theories in which falsities

are derivable, and that being true is not equivalent to being formally

derivable in any formal theory.

Jul 2, 2008, 6:21:57 AM7/2/08

to

Neilist <Neil...@gmail.com> writes:

> Give the correct definition then, genius (sarcasm)!

The correct definition has already been given: a theory is complete if

for every sentence, either the sentence is formally derivable or its

negation is.

> Confusing for you, apparently.

What confusion do you have in mind?

> Godel Escher Bach is great fun, and it eases the reader into Godel's

> work.

_Gödel, Escher, Bach_ might well be great fun. As an exposition of the

incompleteness theorems it's not the best possible choice if one seeks

a clear general understanding of the incompleteness theorems and their

significance -- all sorts of pleasant reflections on self-reference

and so on, as inspired in many by Hofstadter's book, however valuable

in themselves, are in the end almost entirely irrelevant to any actual

mathematical and philosophical application of the incompleteness

theorems.

> But is Franzen's work too sober = dry = boring? Or too advanced for

> the original poster or to the average person?

Franzén's work is very readable and not at all dry.

Jul 2, 2008, 1:38:16 PM7/2/08

to

Aatu Koskensilta wrote:

> Neilist <Neil...@gmail.com> writes:

>

>> It must rankle mathematicians when a theorem or mathematical result is

>> paraphrased, and even without math or logic symbols, for it loses

>> exactness. Horror!

>

> There is nothing wrong with informal explanations -- even if, as you

> note, experts are sometimes overeager in their criticism --, except

> when they're likely to mislead or confuse. Surely you're not

> suggesting that giving an incorrect definition for completeness

> somehow makes the explanation easier to follow?

> Neilist <Neil...@gmail.com> writes:

>

>> It must rankle mathematicians when a theorem or mathematical result is

>> paraphrased, and even without math or logic symbols, for it loses

>> exactness. Horror!

>

> There is nothing wrong with informal explanations -- even if, as you

> note, experts are sometimes overeager in their criticism --, except

> when they're likely to mislead or confuse. Surely you're not

> suggesting that giving an incorrect definition for completeness

> somehow makes the explanation easier to follow?

Personally I appreciate a post-modern approach to mathematics. You

don't want to remove exactness in the final explanation, but

inexactnesses or oversimplifications can often be a major aid in

understanding, or even deriving, the proofs.

I find that most working mathematicians think very visually. (I even

knew a blind mathematician who, upon talking at length with him,

obviously thought about the subject visually.) Not so many

mathematicians think in terms of symbol manipulation, even though our

current understanding of mathematics is that it really is just

manipulation of "well formulated formulae."

The visual thinking often leads to powerful intuition - intuition that

can be at times misleading, but more often is helpful or even essential.

Jul 2, 2008, 2:15:19 PM7/2/08

to

On 2 heinä, 20:38, Stephen Montgomery-Smith

<step...@math.missouri.edu> wrote:

> Aatu Koskensilta wrote:

> > Neilist <Neilis...@gmail.com> writes:

>

> >> It must rankle mathematicians when a theorem or mathematical result is

> >> paraphrased, and even without math or logic symbols, for it loses

> >> exactness. Horror!

>

> > There is nothing wrong with informal explanations -- even if, as you

> > note, experts are sometimes overeager in their criticism --, except

> > when they're likely to mislead or confuse. Surely you're not

> > suggesting that giving an incorrect definition for completeness

> > somehow makes the explanation easier to follow?

>

> Personally I appreciate a post-modern approach to mathematics. You

> don't want to remove exactness in the final explanation, but

> inexactnesses or oversimplifications can often be a major aid in

> understanding, or even deriving, the proofs.

>

> I find that most working mathematicians think very visually. (I even

> knew a blind mathematician who, upon talking at length with him,

> obviously thought about the subject visually.) Not so many

> mathematicians think in terms of symbol manipulation,

<step...@math.missouri.edu> wrote:

> Aatu Koskensilta wrote:

> > Neilist <Neilis...@gmail.com> writes:

>

> >> It must rankle mathematicians when a theorem or mathematical result is

> >> paraphrased, and even without math or logic symbols, for it loses

> >> exactness. Horror!

>

> > There is nothing wrong with informal explanations -- even if, as you

> > note, experts are sometimes overeager in their criticism --, except

> > when they're likely to mislead or confuse. Surely you're not

> > suggesting that giving an incorrect definition for completeness

> > somehow makes the explanation easier to follow?

>

> Personally I appreciate a post-modern approach to mathematics. You

> don't want to remove exactness in the final explanation, but

> inexactnesses or oversimplifications can often be a major aid in

> understanding, or even deriving, the proofs.

>

> I find that most working mathematicians think very visually. (I even

> knew a blind mathematician who, upon talking at length with him,

> obviously thought about the subject visually.) Not so many

> mathematicians think in terms of symbol manipulation,

I`m not a mathematician, but I know that human brain is very poor at

symbol manipulation because of our low work memory. No one can exactly

tell how a true creative mathematics is made, but no one is of course

claiming it`s symbol manipulation in a sense that the symbol are

thought in a same way that we write them in a piece of paper. A

classic in this subject is Hadamard`s book and he also thinks it very

visual. In my own ramblings in mathematics everything is also visual

and curiously the visual objects which in some pervert way represent

mathematical objects often seem to have colours of the covers of then

textbooks where I first learned to know type of mathematical objects i

´m thinking.

Jul 2, 2008, 3:01:27 PM7/2/08

to

On Wed, 02 Jul 2008 12:38:16 -0500, Stephen Montgomery-Smith

<ste...@math.missouri.edu> wrote:

>Aatu Koskensilta wrote:

>> Neilist <Neil...@gmail.com> writes:

>>> It must rankle mathematicians when a theorem or mathematical result is

>>> paraphrased, and even without math or logic symbols, for it loses

>>> exactness. Horror!

>>

>> There is nothing wrong with informal explanations -- even if, as you

>> note, experts are sometimes overeager in their criticism --, except

>> when they're likely to mislead or confuse. Surely you're not

>> suggesting that giving an incorrect definition for completeness

>> somehow makes the explan

<ste...@math.missouri.edu> wrote:

>Aatu Koskensilta wrote:

>> Neilist <Neil...@gmail.com> writes:

>>> It must rankle mathematicians when a theorem or mathematical result is

>>> paraphrased, and even without math or logic symbols, for it loses

>>> exactness. Horror!

>>

>> There is nothing wrong with informal explanations -- even if, as you

>> note, experts are sometimes overeager in their criticism --, except

>> when they're likely to mislead or confuse. Surely you're not

>> suggesting that giving an incorrect definition for completeness

>> somehow makes the explan