Re: how were you taught Godel's completeness theorem?
From: Chris Menzel (cmenzel_at_remove-this.tamu.edu)
Date: 11/19/04
- Next message: Kenneth Doyle: "Aristotle's horse in De Morgan's harness."
- Previous message: Sam Hill: "Re: Curry's paradox - (Google=Google?)"
- In reply to: shane: "Re: how were you taught Godel's completeness theorem?"
- Messages sorted by: [ date ] [ thread ]
Date: 19 Nov 2004 12:20:04 GMT
On 18 Nov 2004 19:38:29 -0800, shane <clearthink@cavtel.net> said:
> ...I just wish that the standard write up on L. Henkin's completeness
> procedure would include a footnote that says: "NB: The complete
> consistent extension theorem implicitly relies on a decision method
> that may not be decideable.
Better, something like: "The complete consistent extension theorem uses
a construction that may not be decidable."
> And this is the reason it does not contradict incompleteness. For
> completeness decidability is not an issue."
"...it does not contradict Gödel's first Incompleteness Theorem. For
the completeness of first-order logic, decidability is not an issue."
"complete" is ambiguous between two senses and you want to make sure you
don't confuse them. FOL is "semantically" complete: all the logical
validities are provable. A theory T is "negation" complete if, for any
sentence A of its language, either T |- A or T |- ~A. Gödel's
Incompleteness theorem is about completeness in the latter sense.
> Students are already alerted to the fact that it is not a finite,
> calculable construction because, for one thing, there could be an
> infinite number of sentences to consider.
The decidability of a set, infinite or not, only requires that we have a
method that enables us to tell whether or not something is a member of
the set. There are lots of infinite decidable sets of sentences --
e.g., the set of sentences itself; the set of propositional tautologies,
the set of axioms of Peano Arithmetic (assuming a language with the
usual nonlogical symbols for arithmetic), etc.
Chris Menzel
- Next message: Kenneth Doyle: "Aristotle's horse in De Morgan's harness."
- Previous message: Sam Hill: "Re: Curry's paradox - (Google=Google?)"
- In reply to: shane: "Re: how were you taught Godel's completeness theorem?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
|
