Some questions about Godel's Results

  • Thread starter Asmodeus
  • Start date
In summary, the conversation discusses the use of Henkin axioms to prove Godel's Completeness theorem in the logic text "A Friendly Introduction to Mathematical Logic" by C. Leary. The last part of the proof requires understanding of equivalence classes, which are necessary for proving completeness with equality. The self-reference lemma, also known as Godel's Fixed-Point lemma, is explained and its role in the first incompleteness theorem is mentioned. The difference between completeness and incompleteness is also discussed, with the author possibly treating the equality case after proving completeness without it.
  • #1
Asmodeus
3
0
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.
 
Physics news on Phys.org
  • #2
"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?
 
  • #3
JSuarez said:
"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.
 

Related to Some questions about Godel's Results

1. What are Godel's Results?

Godel's Results refer to the mathematical theorems and proofs developed by Kurt Godel in the 1930s. They are considered some of the most significant contributions to mathematical logic and have had a profound impact on the fields of mathematics, computer science, and philosophy.

2. What is the Incompleteness Theorem?

The Incompleteness Theorem is one of Godel's most famous results. It states that any consistent formal system of mathematics will contain statements that cannot be proven or disproven within that system. In other words, there are always true statements that cannot be proven in any given mathematical system.

3. How did Godel's Results impact the field of mathematics?

Godel's Results had a significant impact on mathematics by demonstrating that it is impossible to create a complete and consistent system of mathematics. This challenged the long-held belief that mathematics could be used to answer all questions and raised new questions about the nature of mathematics and its limitations.

4. How are Godel's Results relevant to computer science?

Godel's Results are relevant to computer science because they have been applied to the study of computation and algorithms. They have also inspired the development of new fields such as theoretical computer science and computational complexity theory.

5. How did Godel's Results impact the field of philosophy?

Godel's Results had a profound impact on the field of philosophy by raising questions about the limits of human knowledge and the nature of truth. They also challenged the concept of a complete and consistent system of knowledge and have been used to argue for the existence of fundamental limitations to human understanding.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Programming and Computer Science
Replies
29
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
986
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Programming and Computer Science
Replies
32
Views
3K
  • Science and Math Textbooks
Replies
3
Views
1K
Back
Top