Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Help reading a rigorous proof of Godel's incompleteness theorem
Replies: 4   Last Post: Aug 29, 2012 11:40 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
hagman

Posts: 1,923
Registered: 1/29/05
Re: Help reading a rigorous proof of Godel's incompleteness theorem
Posted: Aug 22, 2012 5:18 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Am Mittwoch, 22. August 2012 11:08:49 UTC+2 schrieb (unbekannt):
> On Wednesday, August 22, 2012 7:47:10 AM UTC+1, William Elliot wrote:
>

> > > I've been enjoying following this rigorous account of Godel's
>
> >
>
> > > incompleteness: http://web.yonsei.ac.kr/bkim/goedel.pdf
>
> >
>
> > >
>
> >
>
> > > However, I get somewhat lost around P11 on page 7 where functions don't
>
> >
>
> > > seem to be clearly well-defined.
>
> >
>
> > >
>
> >
>
> > > If anyone can possibly help me understand P11 a bit better, I would be
>
> >
>
> > > very grateful.
>
> >
>
> >
>
> >
>
> > How does P11 read? Does it include definitions of the functions?
>
>
>
> Thank you for your response.
>
> Section copy-pasted below from the pdf included in the original posting.
>
> Unfortunately, I do not have time to correct the symbols that were not correctly translated.
>
> BEGIN QUOTE
>
> Properties of Recursive Functions and Relations (continued):
>
> P11. For G : ! £! £!n ! ! a recursive function, the function F : ! £!n ! !,
>
> given by
>
> F(a; b) = G(F(a; b); a; b);
>
> is recursive.
>
> Proof. Note that
>
> F(a; b) = G(H(a; b); a; b)
>
> where
>
> H(a; b) = ¹x(Seq(x) ^ lh(x) = a ^ 8i < a((x)i+1 = G(Init(x; i); i; b)):
>
> According to this de¯nition, F(0; b) = G( <>; 0; b) = G(0; 0; b),
>
> F(1; b) = G( <G(0; 0; b)>; 1; b);
>
> and
>
> F(2; b) = G( <G(0; 0; b);G( <G(0; 0; b)>; 1; b)>; 2; b);
>
> showing that computation is cumbersome, but possible, for any particular value a.
>
> END QUOTE
>
>
>
> The functions seem much more complex than anything seen in the earlier parts of the paper. The functions are defined by recursion/induction and one must check that the definitions are legitimate.
>
> I struggle a bit with unravelling the logic at this point in the paper, althouh I had no obstacles before then. However, I have a demanding full-time job which doesn't involve mathematical logic so I'm unable to spend more than 1 or 2 hours untangling this. I'm hoping that some readers here might have some insights which will make the process easier for me.
>
>
>
> Thank You,
>
>
>
> Paul Epstein


This is a crucial step of the Gödel proof so should be digested thoroughly.
Note that \bar{F}(a,b) "uses" only F(0,b), ..., F(a-1,b) and thus the
definition of F is a valid recursive one - as a function.

But we need to see that F is a *recursive* function (and not just a
recursively defined function; of course, the terminolgy sonds confusing
at this point, then again this property is the very reason why recursive
are called so).

By unwrapping one level of complexity, i.e. spelling out the definition
of \bar{F} as H, you should see that ther is no vicious circle, i.e.
F does not really appear on the right hand side of its definition
because H does not appear on the right side of its definition.

I hope this helps you read on.

hagman



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.