Not Understanding a Move in Henkin Completeness Proof

  • Thread starter MLP
  • Start date
  • #1
MLP
32
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
147
0
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
MLP
32
0
Thank you that was it!
 

Related Threads on Not Understanding a Move in Henkin Completeness Proof

  • Last Post
Replies
13
Views
8K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
680
Replies
7
Views
591
  • Last Post
Replies
3
Views
3K
Replies
70
Views
12K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
16
Views
7K
  • Last Post
Replies
4
Views
2K
Top