Re: Godel's Incompleteness and Nonmonotonic Logic

From: George Greene (greeneg_at_quartet.cs.unc.edu)
Date: 08/26/04 

Date: 25 Aug 2004 23:51:47 -0400

Aatu Koskensilta <aatu.koskensilta@xortec.fi> writes:
 : Gödel's completeness theorem does apply to
 : infinite sets of axioms and derivations from them.

Finite derivations, yes.

 : In particular,
 : the deductive closure of a set of axioms A is exactly the set D of
 : its logical consequences.

Right, but that sort of implicates compactness:
if it's a logical consequence of any axiom-set,
then it's a logical consequence of a finite subset
of that axiom-set, because it's being a logical consequence
of something entails its having a proof from that something,
and since that proof has to be finite, the subclass of
axioms-from-the-original-set that the proof can get around
to "using" ALSO has to be finite.

 : This doesn't imply that the deductive
 : closure of any consistent set of axiom is complete in the sense
 : that for every sentence A, either A is in the deductive closure or
 : the negation of A is. Some are and some are not, but this has
 : nothing to do with the completeness theorem.

Right, but is the frequency with which this confuses people
ever going to be enough to motivate anybody to change the term?
I mean, who does Godel think he is, to have BOTH completeness
AND (not just one but two!) incompleteness theorems, for the SAME
(first-order) logic?? Semantic incompleteness arguably needs to
be called something else. If the completeness theorem is going to
continue to be called the completeness theorem, then the incompleteness
theorems ought to be renamed the "undecidability" theorems (or SOMEthing,
ANYthing other than "incompleteness"), implying that sufficiently rich
axiom-sets must allow sentences that the axioms do not (deductively,
EVEN though the relevant deductive calculus IS "complete") decide. 

-- 
 --- The history of our nation has demonstrated that separate is seldom, if ever, equal.
 --- (Feb.3,2004) Supreme Judicial Court of Massachusetts (4-3), adv.Sen.#2175

Relevant Pages

  • Re: Godels proof assumes G is valid
    ... in the context of the axioms. ... therefore NECESSARILY false, in the context of the axioms. ... doctoral dissertation -- of his COMPLETENESS theorem. ...
    (sci.logic)
  • Re: Do we really nedd to have models for a theory?
    ... we would never have LEARNED this completeness theorem. ... >> One reason we care about models of a theory is that often it's ... >BEFORE we had axioms for Peano Arithmetic. ... People usually use ZFC but even that was obviously ...
    (sci.logic)
  • Re: FOL & completeness
    ... The completeness theorem is that if a formula is satisfied by ALL ... iff, ... said axioms. ... usually mentioned as itself a clause in the incompleteness theorem. ...
    (sci.logic)
  • Re: Are Hilberts Axioms independent?
    ... |One feature of Hilbert's book is that the axioms are not first order ... the completeness theorem for first order logic doesn't apply ... every structure satisfying all of the B_i also satisfies A. Trivially, ... |one is entitled to have a model of non-Euclidean geometry, ...
    (sci.math)