4

I've worked through Henkin's proof of completeness, but now that I look back over it, I'm a little confused about what the actual statement of the completeness theorem is. Some of my sources state the theorem as:

Let $\Phi$ be a set of sentences, and $\phi$ a sentence. If $\Phi \vDash \phi$, then $\Phi \vdash \phi$.

While others state it as:

For any set of wff's $\Phi$ and for any wff $\phi$, if $\Phi \vDash \phi$, then $\Phi \vdash \phi$.

So do the well-formed-formulas have to be sentences, meaning they contain no free variables, in order for the completeness theorem to apply? Or is this true for any well-formed-formulas?

The sources that don't include the no free variables requirement do mention things like "treating all free variables appearing in any wff as names for particular elements in a structure", or "inserting corresponding universal quantifiers at the beginning of the formula if there are any free variables", which I imagine is probably in some way related to them being able to apply the completeness theorem to all wffs, but they don't provide any additional information, so I don't really understand what these actions actually mean, why we can do them, or what effects they are supposed to have.

I can't find any simple statement of the completeness theorem online that is in like actual mathematical notation to compare with. They all just vaguely explain in words what the theorem implies. So I'm having trouble deciding which of my sources to trust.

bones_mccoy
  • 573
  • I will find you a reference. The short answer is yes, the "assumptions" $\Phi$ can be wffs containing free variables, and the consquence $\phi$ can also be a wff containing one or more free variables. Variables which are free in the assumptions can be interpreted semantically as having an existential nature, that they refer to specific items, not to items in general. Variables that appear in the consquence as free variables can be understood as universal references unless they appeared as free in the assumptions. – hardmath Mar 09 '17 at 16:46

2 Answers2

3

The issue is simply to be consistent with the definition of logical consequence.

In :

Definition. Let $\Gamma$ be a set of wffs, $\varphi$ a wff. Then $\Gamma$ logically implies $\varphi$, written $\Gamma \vDash \varphi$, iff for every structure $\mathfrak A$ for the language and every function $s : \text {Var} \to |\mathfrak A|$ such that $\mathfrak A$ satisfies every member of $\Gamma$ with $s, \mathfrak A$ also satisfies $\varphi$ with $s$.

In this case, the Completeness Th (see page 135 ):

If $\Gamma \vDash \varphi$, then $\Gamma \vdash \varphi$,

is expressed for formulas.

If instead, like in:

  • Dirk van Dalen, Logic and Structure, Springer (5th ed, 2013), page 67, the relation of logical cosequence is defined for sentences:

Definition 3.4.4

(i) $\mathfrak A \vDash \varphi$ iff $\mathfrak A \vDash \text {Cl}(\varphi)$, ( where: let $\text {FV}(\varphi) = \{ z_1,\ldots, z_k \}$, then $\text {Cl}(\varphi) := ∀z_1 \ldots z_k \varphi$ is the universal closure of $\varphi$ )

[...]

(iv) $\Gamma \vDash \varphi$ iff ($\mathfrak A \vDash \Gamma \Rightarrow \mathfrak A \vDash \varphi$), where $\Gamma \cup \{ \varphi \}$ consists of sentences,

then the Completeness Th (see page 97 ) holds for sentences:

Theorem 4.1.3 (Completeness Theorem) $\Gamma \vdash \varphi ⇔ \Gamma \vDash \varphi$.

Your quote about "inserting corresponding universal quantifiers at the beginning of the formula if there are any free variables", matches with van Dalen's approach (see above).

Community
  • 1
Mauro ALLEGRANZA
  • 94,169
0

I think the sources which don't include the no free variables requirement are glossing over some points. First, an open formula cannot be either valid or invalid, because it is not a complete assertion [e.g I cannot say 'x is even' is either true or false without specifying what x is]. Second, the core tautologies from which all formulae are to be derived are themselves sentences, so in fact only sentences can be derived. So in a sense, it is OK to say 'wff' instead of 'sentence' because formulae that are not sentences cannot appear on either side of the equivalence between 'derivable' and 'valid'. This is a 'vacuously true' kind of situation.

Also, these sources are kind of 'cheating' in order to handle open formulae - when they say 'treat all free variables as particular elements' or 'insert universal quantifiers', they are in effect coercing open formulae into sentences.

PMar
  • 1
  • 2
    If you define logical consequence by "$\Gamma \vDash \varphi$ if and only if for every structure $\mathfrak A$ and every assignment $s : V \to |\mathfrak A|$, $\mathfrak A,s \vDash \Gamma$ implies $\mathfrak A,s \vDash \varphi$" (see the book by Enderton mentioned in Mauro ALLEGRANZA's answer), then it works even with free variables. – Uwe Mar 09 '17 at 17:24