Construction of a Henkin Theory

Question

I'm trying to understand Henkin's proof of Gödel's completeness theorem, specifically the construction of a Henkin theory T' with language L' from an arbitrary theory T over a language L. My problem with the proof is that I don't understand why does it suffice to consider the subset of all the L'-formulas with at most one free variable when extending the theory T. Isn't the Henkin property a property of all L'-formulas, even those with more than one free variable?

Thank you very much for your help.

score 1 · Accepted Answer · answered Oct 17 '16 at 19:31

1

The definition of a Henkin Theory $T$ requires that for each sentence $\exists x \phi$ in the language of $T$ there is a constant $c_{\phi}$ such that $T \vdash (\exists x \phi) \Rightarrow \phi[c/x]$. I.e., $\phi$ is expected to have only the variable $x$ free. It wouldn't work to extend this to formulas $\phi$ with other free variables. E.g., consider the following formula in the language of arithmetic:

$$\phi(x, y) \mathrel{:=} \exists x [(y = 0 \Rightarrow x = 0) \land (y > 0 \Rightarrow x = 1)]$$

It would be inconsistent with the theory of arithmetic to introduce a constant $c$ such that $\phi(c, y)$ holds for all $y$.

answered Oct 17 '16 at 19:31

Rob Arthan

48,577

I think that's not quite what the OP's asking - I think they're asking why we don't add constants $c, d$ and a sentence saying $\phi(c, d)$. (And the answer is we already did, essentially.) – Noah Schweber Oct 17 '16 at 19:43
@NoahSchweber: possibly. Over to the OP to clarify. – Rob Arthan Oct 17 '16 at 20:02
I had a basic confusion with the definition, your answer clarified it. Thank you very much – Santiago Estupiñán Oct 17 '16 at 21:59

score 0 · Answer 2 · answered Oct 17 '16 at 19:43

Let's take a formula $\phi(x, y)$ such that the sentence $\exists x, y\phi(x, y)$ is in $T'$. Then:

Consider the sentence "$\exists x(\exists y\phi(x, y))$". Our expanded language $L'$ contains a new constant $c$ for this sentence, and our expanded theory contains the sentence "$\exists y(\phi(c, y)$."
But now that's itself a sentence of the form "$\exists z[stuff]$." So we add a constant $d$ for it, too, and the sentence "$\phi(c, d)$."

So two-variable formulas are handled in this "two step" process; similarly for $n$-variable formulas.

Thank you for your answer, I had a more basic confusion, but thanks anyway — Santiago Estupiñán, Oct 17 '16 at 22:01

Construction of a Henkin Theory

2 Answers2