Re: A question on GIT.

From: Tim Peters (tim.one_at_comcast.net)
Date: 09/07/04 

Date: Tue, 7 Sep 2004 16:38:31 -0400

[andrevh@sci.kun.nl]
> There is something I don't understand here. According to me, the
> following statement (G) is FALSE:
>
> G: G is undecidable
>
> G is not undecidable, G is decidable: G is false. So "I know G is false".
> Where am I going wrong?

I don't what what you're trying to say. The argument above seems to be:

    G is false.
    G is decidable.
    G is false.
    So "I know G is false".

Maybe you're confusing truth with provability -- or something like that.
Note that knowing a thing is false doesn't imply it's decidable.
Decidability is a question of what you can prove in a system, not a question
of truth.

It's easy to see that your G (suitably formalized) isn't provable in the
system. You haven't shown whether "not G" is or is not provable, though, so
I don't know on what basis you've concluded that G is decidable (other than
just repeating that it is).

Godel's reasoning was much different wrt his G:

    Assume G is provable.
        That leads to a contradiction.
        Therefore G is not provable.
        [And therefore also G is true, since at the meta level we
         can see that G asserts its own unprovability; *within* the
         system, it's just a statement about whether an integer exists
         satisfying a mountain of obscure constraints.]
    Assume -G is provable.
        That leads to a condtradiction.
        Therefore -G is not provable.
    Since neither G nor -G is provable, G is undecidable (by the
        defn of decidability).

The truth or falsity of G is irrelevant to his conclusion. It's interesting
that G is true in the standard model, but no use is made of that in the
proof of its undecidability.

Relevant Pages

  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... >> provability to have to be decidable. ... > Decidability is a separate issue. ... If the logics we're talking about ... without any reference to Goedel theorems. ...
    (comp.lang.prolog)
  • Re: Godels Incompleteness and Nonmonotonic Logic
    ... >> provability to have to be decidable. ... > Decidability is a separate issue. ... If the logics we're talking about ... without any reference to Goedel theorems. ...
    (sci.logic)
  • Re: .EXE -> .ASM -> .EXE
    ... Since the language of the two examples of the "liar's paradox" which I ... propositional logic *does* map exactly to the concept of undecidability ... in Computer Science. ... you're confusing computability with decidability. ...
    (alt.lang.asm)
  • Re: Proposal: 6NF
    ... Note that Liskov and Wong themselves defined the principle ... Rice's theorem says something about decidability, not provability. ... subtyping algorithms do, which in many cases are quite simple. ...
    (comp.databases.theory)