Re: Godel's incompleteness theorem vs Church's/Turings work
- From: "Peter_Smith" <ps218@xxxxxxxxx>
- Date: 13 Apr 2006 15:25:16 -0700
george wrote:
Frederick Williams wrote:
Incompleteness and undecidable are different things.
No, they're not.
In order for any theory-of-the-kind we're talking
about to be incomplete, there must necessarily be
statements in its language that it does not decide.
Take a toy case: a theory whose language consists of the propositional
atoms P, Q, and R, plus the truth-functional connective, whose sole
axiom is (say) P & Q, and whose logic is a standard natural deduction
system for propositional logic.
This theory is (i) negation incomplete [it doesn't decide whether R or
not-R, for example]. But (ii) it is a decidable theory -- i.e. the
question is "X a theorem?" for any sentence X in its language is
algorithmically decidable e.g. by a truth-table test on "(P & Q) -->
X".
Moral: the fact that there are statements in a theory's language that
it doesn't decide does NOT entail that it is an undecidable theory.
This is illustrated by FOL:No, it isn't.
FOL is a logic.
PA and all the things Godel was talking about
are THEORIES not NOT logics.
Both off-message here! (i) You can think of FOL as the theory whose
logic is first-order and whose set of non-logical axioms is null. But
(ii) of course -- as was pointed out -- FOL (although complete in the
sense of being having a deductive system that is complete with respect
to the standard semantics) is not a negation-complete theory (it
doesn't settle every sentence X in its language!).
You earlier also characterized FOL as "undecidable".
That is inappropriate. "Undecidable" does not reasonably
DIRECTLY apply to anything as big as a theory, let alone
something even BIgger like all of FOL. "Undecidable" is
properly and directly applied to ONE INDIVIDUAL sentence.
Not so. It is entirely standard to talk of theories being undecidable.
And appropriately so -- the issue is whether there exists an algorithm
that applies *theory-wide* to detemine the theoremhood of arbitrary
sentences.
.
- References:
- Godel's incompleteness theorem vs Church's/Turings work
- From: falcon
- Re: Godel's incompleteness theorem vs Church's/Turings work
- From: Frederick Williams
- Re: Godel's incompleteness theorem vs Church's/Turings work
- From: george
- Godel's incompleteness theorem vs Church's/Turings work
- Prev by Date: Re: Godel's incompleteness theorem vs Church's/Turings work
- Next by Date: Re: interpolation theorem of propositional logic
- Previous by thread: Re: Godel's incompleteness theorem vs Church's/Turings work
- Next by thread: Re: Godel's incompleteness theorem vs Church's/Turings work
- Index(es):
Relevant Pages
|
