Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Not Understanding a Move in Henkin Completeness Proof

  1. Nov 13, 2011 #1


    User Avatar

    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.
  2. jcsd
  3. Nov 13, 2011 #2
    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.
  4. Nov 13, 2011 #3


    User Avatar

    Thank you that was it!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Not Understanding a Move in Henkin Completeness Proof
  1. Completeness theorem (Replies: 3)

  2. Proof that a=a (Replies: 3)