Re: short proof to Gödel's incompleteness theorem?

On Mar 30, 1:35 pm, chris2718...@xxxxxxxxxxxxxx wrote:
I've been trying to find a short version of Gödel's theorem. What's
wrong with this proof?

1. The set of predicates A(n) with one variable n, is countable
because they are built with a finite alphabet. So they can be listed,
A1(n), A2(n), ...

2. Let R(n):= "An(n) is not provable". Since proofs are also finite
lists of words, they also form a countable set, Proof. So "p provable"
here means  "exists q in Proof, last sentence of q = p"

3. Then R is a predicate with one variable, and must be R(n)=Am(n).

4  Am(m) is not provable iff R(m) iff Am(m)

5. So either Am(m) is true but unprovable, or Am(m) is false but
provable.

This would be a proof of a semantic version of Gödel's theorem (P is
incomplete or incorrect) if you had proved that the predicate R(x) is
expressible in P's language.

To prove this,Gödel had to touch (at least) on Gödelization, the
theory of primitive recursive functions, and on the diagonal lemma.
This is perhaps the technical core of Gödel's proof that is absent
from your sketch.

There is a widely known easy proof of a related result that goes this
way.

We prove there are incomputable (=undecidable) sets of naturals.The
set of algorithms is enumerable. The set of all sets of naturals is
not. So there are sets of naturals which no algorithm computes.

Consider that P can compute all computable functions on naturals
(according to the Church-Turing thesis). Assuming this, the
incomputability result is very close to a P-incompleteness result; the
missing step is proving that there are incomputable sets that can be
defined by means of P-expressible predicates.

But the result keeps a strong Gödelian air!

Regards.
.

Relevant Pages

  • Re: Python from Wise Guys Viewpoint
    ... Upon digging a bit I am running into discussions of Löb's theorem and ... incomplete, i.e. any consistent axiomatisable extension is incomplete. ... references to the literature on partial truth predicates. ...
    (comp.lang.lisp)
  • =?ISO-8859-1?Q?Re=3A_short_proof_to_G=F6del=27s_incompleteness_theorem=3F?=
    ... incomplete or incorrect) if you had proved that the predicate Ris ... theory of primitive recursive functions, ... set of algorithms is enumerable. ... So there are sets of naturals which no algorithm computes. ...
    (sci.logic)
  • An instance of Russells paradox?
    ... I have been studying Prolog for a while, ... difficulties which I seem to be unable to overcome on my own. ... Can all algorithms be enumerated, ... Can all predicates be generalized as having infinite arity, ...
    (sci.logic)