Re: Godel's Incompleteness and Nonmonotonic Logic

From: Student (jagasian_at_mailinator.com)
Date: 08/25/04 

Date: 25 Aug 2004 10:00:34 -0700

> > Godel's two famous theorems apply to first-order predicate logic.
>
> I'm not completely sure what two theorems you are referring to,
> but if the theorem generally known as `the' "incompleteness theorem"
> is among them then this statement is clearly false.

Ok, lets settle this once and for all. There is no ambiguity as the
original and its translations are readily available of Kurt Godel's
"On Formally Undecidable Propositions of Principia Mathematica and
Related Systems I". I am referring to the two incompleteness theorems
presented there, the frist implying the second. Godel's first theorem
shows that assuming consistency, there exists a formula in first-order
predicate logic that is neither provable nor is its negation provable.
 Godel's second incompleteness theorem refutes Hilbert's goal of
obtaining a satisfactory consistency proof for arithmetic. It states
that if first-order predicate logic is consistent then you cannot
prove said consistency within first-order predicate logic.

Furthermore, quick web searches for lose unwilling to consult the
original text also reaffirm my claim that Godel's theorems deal with
first-order predicate logic. Here is an English translation of
Godel's paper, but I am not sure of its accuracy:

http://home.ddc.net/ygg/etext/godel/godel3.htm

"Proposition VI" is Godel's first incompleteness theorem and
"Proposition XI" is Godel's second incompleteness theorem.

If you are unwilling to even read a free online translation of Godel's
paper, then at least skim through the admittedly unreliable (i.e. they
use Hofstadter's imfamous text as a reference) Wiki page and the
similarly unreliable Woflram math dictionary:

http://en.wikipedia.org/wiki/G%F6del's_incompleteness_theorem
http://mathworld.wolfram.com/GoedelsIncompletenessTheorem.html

"From Frege to Godel" by Heijenoort has a translation that was
approved by Godel himself. That is a reliable source that makes no
use of pseudo-mathematical texts - it only uses official English
translations of original works by real mathematicians. If you spend
the time to read that translation, then you should, without a doubt,
realize your error.

I see no reason why we need to cover this. Do logicians no longer
study Hilbert's metamathematical program? Maybe you are confused by
Godel numbering, which encodes predicates as numbers... thats still
first-order, but I guess I can see the possible confusion as long as
you completely ignore the entire concept of Godel numbering.

> > See
> > Kleene's "Introduction to Metamathematics", Kleene's "Mathematical
> > Logic", or Girard's "Proof Theory and Logical Complexity : Volume I",
> > if you cannot get your hands on the Godel's original work (or a
> > translation thereof).
>
> You are very generous with your references. I have none of them
> immediately available, but as they stem from respectable authors, I am
> sure you will find in them no claim that first-order predicate logic
> is in danger of being incomplete in the standard meaning of this
> concept.

Please at least read the original work before you make such claims.

> It is nice to cite things, but on usenet it is considered good form
> to define the things one is talking about.
>
> Maybe you could give a rigorous definition of "answer set style logics"?

Take classical logic, with one more rule: if "F" is not provable, then
"not F" is provable, where F is any well formed formula in first-order
predicate logic, i.e. negation commutes with provability, as is
seemingly the case in these "Answer Set" logics such as AnsProlog and
its varients.

Finally, with regards to your comments on the importance of
computability... my original question is not of computability, it is
about consistency. The undecidability (lack of computability) of
provability is not the same as provability, which is what is referred
to in the aforementioned extension to classical logic.

Relevant Pages

  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... I am referring to the two incompleteness theorems ... Godel's second incompleteness theorem refutes Hilbert's goal of ... If you are unwilling to even read a free online translation of Godel's ... provability is not the same as provability, ...
    (sci.logic)
  • Re: 5. How did language originate? In the creation of Ancient Genealogies
    ... (President Joseph Smith, Jr.) ... Translation from what? ... the nature or history of human language. ... "writings" you are referring to? ...
    (sci.lang)
  • Re: Inside or Outside ?
    ... A numerical relation Ris said to be expressible in S ... provability path of P, ... Give a translation of "2 is prime" into the first-order language of ... a bit interesting at the formal level. ...
    (sci.logic)
  • Re: Inside or Outside ?
    ... A numerical relation Ris said to be expressible in S iff there ... provability path of P, ... Give a translation of "2 is prime" into the first-order language of ...
    (sci.logic)
  • Re: Aerodynamic question for you engineers
    ... I'm unfamiliar with the term 'translation' as it refers to this issue. ... I presume you are referring to one of these definitions: ... Rotation is the ...
    (rec.aviation.piloting)