CHAT: Goedel (was: Re: Láadan and woman's speak)

Peter Clark <pclark@...> wrote:
>         One parting comment: would someone mind explaining me what
> Goedel's theorem is?
    Goedel proved several theorems.  The most famous were his Completeness
Theorem and his two Incompleteness Theorems.  These all apply to first order
logic, i.e. logical systems in which quantification over objects, but not
sets of objects, is allowed.  I spent several semesters studying these
theorems in graduate school.  That was a while ago, but hopefully I can
describe them without mangling them too badly.

    The Completeness Theorem states that a statement is true in a given
theory if and only if it is provable in that theory.  "True" meaning true in
all models of the theory.

    One Incompleteness Theorem (I forget which is the First and which is the
Second) states that a consistent theory cannot prove its own consistency.

    The other Incompleteness Theorem states that any consistent theory which
is able to express arithmetic has undecidable statements.  "Undecidable"
means neither provable nor refutable, and therefore, by the Completeness
Theorem, neither true nor false.  (Although the statement he exhibits in the
proof is intuitively a true statement, and provably so in a stronger theory,
so you may hear the theorem described as "Any strong enough theory has true
statements which cannot be proven.". (The statement he exhibits is a
formalization of a variation of the Liar's Paradox, "This statement is not
provable.".))

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

             Dennis Paul Himes    <>    dennis@himes.connix.com
                  http://www.connix.com/~dennis/dennis.htm

Disclaimer: "True, I talk of dreams; which are the children of an idle
brain, begot of nothing but vain fantasy; which is as thin of substance as
the air."                      - Romeo & Juliet, Act I Scene iv Verse 96-99