Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
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
|
|
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
|
|
|
|
