Godel's Incompleteness theorem
moorthy
incompleteness theorem in a simple way.
Neilist
> 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.
Dave Seaman
> 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>
Arturo Magidin
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
Neilist
<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?
Dave Seaman
> 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?
MoeBlee
> 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
Kyle T. Jones
> Can somebody provide me some good explanation on Godel's
> incompleteness theorem in a simple way.
This assertion is false.
Cheers.
Arturo Magidin
"This assertion is unprovable" would be a bit closer, I think.
Tonico
wrote:
******************************************************
What assertion? I only see a question...
Regards
Tonio
Zdislav V. Kovarik
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).
A N Niel
<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."
Rainer Rosenthal
> 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
Aatu Koskensilta
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
Aatu Koskensilta
Toni Lassila
<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.
Aatu Koskensilta
> 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).
Aatu Koskensilta
> 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_,
Aatu Koskensilta
> 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
> 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.
Aatu Koskensilta
Arturo Magidin
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".
Aatu Koskensilta
> 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"
amzoti
> 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.
Aatu Koskensilta
> 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"
LauLuna
> 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
T.H. Ray
> <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
Arturo Magidin
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.
moorthy
> 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
Stephen Montgomery-Smith
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
Peter_Smith
> 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!
BURT
> 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
Rainer Rosenthal
:-)
Scott H
> 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.
Aatu Koskensilta
> 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)
moorthy
> 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
Aatu Koskensilta
> 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.
Aatu Koskensilta
> 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.
LauLuna
> 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
LauLuna
>
> > >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?
Aatu Koskensilta
> 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"
Stephen Montgomery-Smith
> 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.
Herman Jurjus
> 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
Aatu Koskensilta
> 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.
Herman Jurjus
> 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
PiperAlpha167
> Godel's
> incompleteness theorem in a simple way.
A pretty clear sketch of what Godel did can be found here:
Gc
> 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)
Neilist
> 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?
Neilist
<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!
Jesse F. Hughes
> 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
Frederick Williams
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.
Neilist
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)
:-)
Tonico
> 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
Neilist
<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!
Dave Seaman
> 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>
Aatu Koskensilta
> 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
Aatu Koskensilta
> 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.
Aatu Koskensilta
> 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.
Stephen Montgomery-Smith
> 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.
Gc
<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.
Toni Lassila
<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 explanation easier to follow?
>
>Personally I appreciate a post-modern approach to mathematics.
Post-modern approach to mathematics?
"Let X be a separable Banach space. Giraffe. Two men on a roof. The
existential pain of nothingness. The claim follows."
>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."
I find mathematical logic about the last thing that one can approach
by thinking visually.
Stephen Montgomery-Smith
> 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 explanation easier to follow?
>> Personally I appreciate a post-modern approach to mathematics.
>
> Post-modern approach to mathematics?
>
> "Let X be a separable Banach space. Giraffe. Two men on a roof. The
> existential pain of nothingness. The claim follows."
Your chauvinist response shows that you "just don't get it!"
:-)
Gc
> On Wed, 02 Jul 2008 12:38:16 -0500, Stephen Montgomery-Smith
> >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."
>
> I find mathematical logic about the last thing that one can approach
> by thinking visually.
?In is elemantary form that`s true, but when you encouter
ultrafilters, models, boolean circuits and such, your own mental
models are hepfull. Visual mathematics need not to relate to geometry.
Herman Jurjus
> 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 explanation easier to follow?
>> Personally I appreciate a post-modern approach to mathematics.
>
> Post-modern approach to mathematics?
>
> "Let X be a separable Banach space. Giraffe. Two men on a roof. The
> existential pain of nothingness. The claim follows."
FYI that's not post-modernism. That's Dadaism.
--
Cheers,
Herman Jurjus
third...@hotmail.com
> Can somebody provide me some good explanation on Godel's
> incompleteness theorem in a simple way.
Yeah. Read James R Meyer's book The Shackles of Conviction. It is a
novel about Godel and his Incompleteness Theorem, but gives the best
expalanation of Godel's theorem I have come across. And it's a damn
good novel too. Meyer has website www.jamesrmeyer.com.
Brian Chandler
Ho hum. Here's a quote from the author's website:
"I [James Meyer] believe that it is reasonable to claim that I am the
first person ever to properly understand Gödel's proof of his
Incompleteness Theorem."
At http://www.jamesrmeyer.com/aboutme.html
Elsewhere we read that having (uniquely) understood it he has
consigned it to the dustbin. We observe that he is also unable to make
a reasonable stab at stating said consignand.
Brian Chandler
There are only three things that really matter: Truth, Beauty, and
Jokes
Gib Bogle
Nice sig