Not Understanding a Move in Henkin Completeness Proof

  • Thread starter MLP
  • Start date
  • Tags
    Proof
In summary, the sentence \exists y R(x,y) includes the Henkin constant c_1, so the constant c_2 is not in L1.
  • #1
MLP
32
0
Let L be a first order language. Let A be any set of sentences of L. We extend L0 (=L) to L1 by adding denumerably many constants c1, …,cn,… to L. We enumerate the existential formulas of L. We add Henkin axioms to L by taking each formula in the enumeration and making it the antecedant of a conditional whose consequent is an instantiation of the existential variable in the antecedent to the next earliest constant in the enumeration c1, …,cn,…

Up to here I think I get it. I have an extended system such that any existential claims entailed by the formulas in A, together with the appropriate Henkin axioms will yield instances of the existential claims via what I have seen called "witnessing constants". What I'm failing to see is why I need to go on? Once I have L1, why not just construct my model of L1? I am not understanding the move to add another set of constants and Henkin axioms, and then another, and so on to get L2,L3,etc.?

I'm sure I'm missing something obvious.
 
Physics news on Phys.org
  • #2
MLP said:
I'm sure I'm missing something obvious.
Yes, namely that quantifiers can be nested.

For example, take the sentence [itex]\exists x (P(x) \wedge \exists y R(x,y))[/itex]. [itex]\exists x (P(x) \wedge \exists y R(x,y)) \rightarrow (P(c_1) \wedge \exists y R(c_1,y))[/itex] is its Henkin axiom. To get rid of the quantifier binding the y variable, you have to add another Henkin axiom for the sentence [itex]\exists y R(c,y)[/itex]: [itex]\exists y R(c_1,y) \rightarrow R(c_1, c_2)[/itex]. But this sentence already includes the Henkin constant [itex]c_1[/itex], so the constant [itex]c_2[/itex] is not in L1. You need an infinite hierarchy of Henkin constants to deal with nested quantifiers of arbitrary depth. Only then can you reduce an arbitrary sentence to a propositional level.
 
  • #3
Thank you that was it!
 

Related to Not Understanding a Move in Henkin Completeness Proof

1. What is the Henkin completeness proof?

The Henkin completeness proof is a mathematical proof used in first-order logic to show that a consistent set of axioms has a model. It was developed by Leon Henkin in the 1940s and is an important result in logic and mathematics.

2. How does the Henkin completeness proof work?

The Henkin completeness proof works by showing that any consistent set of axioms can be extended to include a new constant symbol and a new axiom, without changing the consistency of the original set. This process can be repeated indefinitely, resulting in a set of axioms that has a model.

3. What is the significance of the Henkin completeness proof?

The Henkin completeness proof is significant because it provides a way to show that a set of axioms is consistent and has a model. This is important in mathematical logic, where consistency and completeness are fundamental concepts.

4. Can the Henkin completeness proof be applied to all logical systems?

The Henkin completeness proof is specifically designed for first-order logic, which is a powerful and widely used logical system. It may not be applicable to other logical systems, but the concepts and techniques used in the proof can be adapted to other systems.

5. What are some common challenges when trying to understand the Henkin completeness proof?

Some common challenges when trying to understand the Henkin completeness proof include the use of complex mathematical notation, the abstract nature of the proof, and the need for a strong foundation in mathematical logic. It may also be challenging for those who are not familiar with formal logic or mathematical proofs in general.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
17
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
3K
  • Introductory Physics Homework Help
Replies
2
Views
2K
  • Classical Physics
Replies
1
Views
1K
  • Differential Equations
Replies
1
Views
789
  • Precalculus Mathematics Homework Help
Replies
9
Views
2K
Back
Top