Re: Godel's Incompleteness theorem

moorthy <cmkmoorthy@xxxxxxxxx> 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).

--
Aatu Koskensilta (aatu.koskensilta@xxxxxx)

"Wovon man nicht sprechen kann, daruber müss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophics
.

Relevant Pages

  • =?ISO-8859-1?Q?Re=3A_Not_understanding_G=F6del?=
    ... Godel incompleteness theorem w.r.t. proof of consitancy ... drawer principle) cannot be both consistent and complete. ... sufficiently complex to include the axioms of natural numbers isn't able ... applies to all functions from finite sets to finite sets, ...
    (comp.compression)
  • Re: Not understanding =?ISO-8859-1?Q?G=F6del?=
    ... Godel incompleteness theorem w.r.t. proof of consitancy ... sufficiently complex to include the axioms of natural numbers isn't able to be both consistent and complete. ... In fact, the axiom system that contains no axioms is surely consistent and complete: It cannot formulate any theorem, and thus there is not a single theorem that cannot be proven. ... It applies to all functions from finite sets to finite sets, ...
    (comp.compression)
  • Re: SR and GR without math
    ... You are thinking of Godel's First Incompleteness Theorem: ... In any consistent axiomatizable theory ... > proved internally consistent: Build a model for the Peano axioms. ...
    (sci.physics.relativity)
  • Re: Goedel - interesting problem?
    ... Gödel's 1st incompleteness theorem says that for any consistent formal ... formal theory containing elementary arithmetic and certain simple facts ... about formal provability are provable in T, ...
    (sci.logic)
  • Re: FOL & completeness
    ... The incompleteness theorem is that for any consistent, recursive set of ... axioms, there is a sentence that is true in the standard model (but NOT ...
    (sci.logic)