Re: Godel's Incompleteness and Nonmonotonic Logic

From: Aatu Koskensilta (aatu.koskensilta_at_xortec.fi)
Date: 08/26/04 

Date: Thu, 26 Aug 2004 13:02:07 +0300

Herman Jurjus wrote:

> Aatu Koskensilta wrote:
>
>> Gödel's incompleteness theorems do apply to second order theories as
>> well in the sense that for all theories containing a fragment
>> elementary arithemtic and (sound) deductive system there are
>> propositions which are neither refutable nor provable in the theory
>> according to the deductive system.
>
> With 'theory' you mean recursively enumerable theory, and for
> 'deductive system', a similar restriction is required, i think?

This is the customary restriction, yes. Generalisations of Gödel's
theorems do apply also to non-recursively enumerable theories and
deductive systems in which the derivability relation is not recursively
enumerable.

When talking about Gödel's theorems and higher order logics, it's often
  instructive to think of the deductive systems as translations of
higher order theories into multi-sorted first order theories with
suitable axioms, e.g. comprehension for the set sort. 

-- 
Aatu Koskensilta (aatu.koskensilta@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
  - Ludwig Wittgenstein, Tractatus Logico-Philosophicus

Relevant Pages

  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... >> Gödel's incompleteness theorems do apply to second order theories as ... deductive systems in which the derivability relation is not recursively ... When talking about Gödel's theorems and higher order logics, ...
    (sci.logic)
  • Re: Cantors circular "proof" that evens = integers
    ... axiomatizable complete but non-categorical second order ... Here completeness for higher order theories is understood ... but we can force the existence of such a theory. ...
    (sci.logic)