Some questions about Godel's Results

[Asmodeus]

I'm in Mathematical Logic course. I just wanted to tie a few loose ends.

In our logic text, ("A Friendly Introduction to Mathematical Logic" -C. Leary) he uses the Henkin axioms to prove Godel's Completeness theorem. I understand the whole proof, except the last part that requires equivalence classes. Can anyone spell this out for me.


Further, can someone explain the self-reference lemma to me? For instance, our text uses v=4. Why is this so? Is it because 4 = 2^2, which is not a godel number?

What is the precise difference between the completeness in the first sense, and (in)completeness in the second sense?

Any explanations or good links would be greatly appreciated.

 

[JSuarez]

"A friendly introduction to ML"? Oh God...

Well, I don't know this text, so I cannot comment on how its author does things, but Henkin-style completness proofs are the pretty much standard these days. But there is one thing: equivalence classes are necessary if you are proving completness for the calculus with equality, and they appear right at the beggining, in the definition of the domain (the canonical, or Herbrand, domain is defined out of the language's closed terms and, if you have equality, them you must group them in equivalence classes, so that equality really behaves like equality, not something weaker), not at the end: the last part is, usually, the proof that there is a maximal consistent set of a particular type.

Is it possible that the author proves completness for the calculus without equality (which doesn't require equivalence classes), and then treats the equality case? And, perhaps, says that the major change in the proofs is precisely in the domains' definition?

I'll take that the self-reference lemma is the (more usually called) Gödel's Fixed-Point lemma: if you have an arithmetizable (so that you may code any formula) and sufficiently powerful theory (capable of representing the partial recursive functions, for example), then this lemma states that, given a formula A(x), with x free, then tere is a sentence B, with code #B, such that B <->A(#B) is provable.

You need this lemma in the proof of the first incompletness theorem, where you apply it to the A(x) = Prov(x) (or Bew(x)) predicate.

Informally, the lemma states that the sentence B has the property A, iff B is the case.

Are you sure you are asking about the difference between completness and incompletness? This is almost obvious. Or are you asking about incompletness in the first and second senses?

 

[Asmodeus]

"A friendly introduction to ML"? Oh God...

Well, I don't know this text, so I cannot comment on how its author does things, but Henkin-style completness proofs are the pretty much standard these days. But there is one thing: equivalence classes are necessary if you are proving completness for the calculus with equality, and they appear right at the beggining, in the definition of the domain (the canonical, or Herbrand, domain is defined out of the language's closed terms and, if you have equality, them you must group them in equivalence classes, so that equality really behaves like equality, not something weaker), not at the end: the last part is, usually, the proof that there is a maximal consistent set of a particular type.

Is it possible that the author proves completness for the calculus without equality (which doesn't require equivalence classes), and then treats the equality case? And, perhaps, says that the major change in the proofs is precisely in the domains' definition?

I'll take that the self-reference lemma is the (more usually called) Gödel's Fixed-Point lemma: if you have an arithmetizable (so that you may code any formula) and sufficiently powerful theory (capable of representing the partial recursive functions, for example), then this lemma states that, given a formula A(x), with x free, then tere is a sentence B, with code #B, such that B <->A(#B) is provable.

You need this lemma in the proof of the first incompletness theorem, where you apply it to the A(x) = Prov(x) (or Bew(x)) predicate.

Informally, the lemma states that the sentence B has the property A, iff B is the case.

Are you sure you are asking about the difference between completness and incompletness? This is almost obvious. Or are you asking about incompletness in the first and second senses?

I had my mathematical logic exam last night, so I had to figure out all these things myself.

Yes, it was the difference between the two senses of completeness, notice the "in" was in parentheses.

"Is it possible that the author proves completness for the calculus without equality (which doesn't require equivalence classes), and then treats the equality case?"

Exactly the case.