Re: how were you taught Godel's completeness theorem?

From: shane (clearthink_at_cavtel.net)
Date: 11/19/04 

Date: 18 Nov 2004 19:38:29 -0800

> Your observation rephrased: Even if we start with a decidable
> set Gamma of sentences, the consistent complete extension Phi
> might not be decidable. Right. But that does not affect the
> completeness proof. The completeness proof needs only the fact
> that a consistent complete extension Phi *exists*. Not that
> you can compute it.
>
> --Herb Enderton

Dr. Enderton,

I have your mathematical logic book and use it in conjunction
with Shoenfield. Thank you for your helpful comments.

What you write is, of course, absolutely right. I just wish
that the standard write up on L. Henkin's completeness procedure
would include a footnote that says: "NB: The complete consistent
extension theorem implicitly relies on a decision method that
may not be decideable. And this is reason it does not contra-
dict incompleteness. For completeness decidability is not
an issue." Students are already alerted to the fact
that it is not a finite, calculable construction because, for
one thing, there could be an infinite number of sentences to
consider. But I failed to be critical and detect the second
level of non-computability through the decision issue.

In the big picture my complaint is (very) small!

> But there is more here. Given an oracle for 0' (the degree of
> the halting problem), you *can* compute Phi. So the model of
> Gamma given by Henkin's proof might have an undecidable theory,
> but it's not wildly undecidable, just of degree 0'.
I hope to make time for recursion theory next semester so that
I can make full use of this tip.

Regards,
Shane