Existential instantiation in Hilbert-style deduction systems - MathOverflow

Existential instantiation in Hilbert-style deduction systems

2012-12-18T01:16:38Z

In some deduction systems there is a rule* that given $\exists x (\phi(x))$, we can infer $\phi(y)$, where $y$ is a fresh variable (i.e., one we haven't yet mentioned in this context). Call this rule "EI."

(Edit: in the opening sentence I originally said "in natural deduction systems there is typically a rule that..." Andrej Bauer has kindly informed me that natural deduction systems typically do not have this rule. In this post I am, I have learned, using a somewhat unusual set of conventions regarding the treatment of free variables.)

Let $M$ denote a model, $A,B$ variable assignments, and $T,U$ theories. Let $\text{fv}(T)$ denote the set of variables free in $T$. Let $A|_{\text{fv}(T)}$ denote $A$ restricted in its domain to $\text{fv}(T)$.

Call this the "simple definition" of semantic entailment: $T \models U$ iff, for all $M,A$, if $M,A \models T$ then $M,A \models U$. We can't use the simple definition in a system with EI, because $A$ might not contain an appropriate value in a fresh variable we instantiate into.

For contrast, call this the "complicated definition" of semantic entailment: $T \models U$ iff, for all $M,A$, if $M,A \models T$ then $M,B \models U$, for some $B \supseteq A|_{\text{fv}(T)}$. That is, we can change the values of unused variables across semantic entailments. This definition is compatible with EI.

My questions:

Does a typical Hilbert system (e.g., the one on Wiki) allow for anything like EI? Can we actually infer $\phi(y)$ (with $y$ fresh) from $\exists x (\phi(x))$? If not, how do we make up for the lack of this feature?
Can a typical Hilbert system be interpreted by the simple definition of semantic entailment?
The Henkin-style completeness proofs with which I am familiar (e.g., this one) make essential use of EI in the step of constructing a maximal, consistent superset with witnesses. If Hilbert systems don't have EI, how do we fulfill the function of this step? If Hilbert systems don't have EI, is it even possible to prove them complete using a Henkin-style proof, or do we need to use a completely different method?

I'm asking because I'm trying to write a completeness proof for a non-classical logic (a variant of LP), with a Hilbert-style deduction system.

Thank you for your help!

Answer by Emil Jeřábek for Existential instantiation in Hilbert-style deduction systems

2012-12-18T12:51:27Z

First, the standard definition of semantic entailment is neither the “simple” one nor the “complicated” one, but the following: $T\models U$ iff for every $M$, if $M,A\models T$ for every $A$, then $M,A\models U$ for every $A$.

First-order Hilbert-style usually employ some form of a generalization rule: the simplest one is $$\phi\vdash\forall x\,\phi,$$ other common variants include $$\begin{align} \psi\to\phi\vdash\psi\to\forall x\,\phi,\\ \phi\to\psi\vdash\exists x\,\phi\to\psi, \end{align}$$ where $x$ must not occur free in $\psi$. (The choice of the rules depends on other axioms of the system, and of course on the logic, if you are dealing with non-classical systems.) Notice that these rules are not sound with respect to either your “simple” or “complicated” definition, but they are sound with respect to the semantics I gave above. (Note also that the system on the Wikipedia page, with no generalization rules, is quite unconventional.)

The way to simulate existential instantiation in Hilbert systems is by means of a “meta-rule”, much like you’d use the deduction theorem to simulate the implication introduction rule. The most common formulation is:

Lemma 1: If $T\vdash\phi(c)$, where $c$ is a constant not appearing in $T$ or $\phi$, then $T\vdash\forall x\,\phi(x)$.

A version with explicit existential quantifiers may look like this:

Lemma 1’: If $T\vdash\psi(c)\to\phi$, where $c$ is a constant not appearing in $T$, $\phi$, or $\psi$, then $T\vdash\exists x\,\psi(x)\to\phi$.

Both lemmas follow easily by replacing the constant everywhere with a fresh variable, and applying an appropriate version of the generalization rule. In order to simulate the natural deduction existential elimination rule, you are in a situation where you have already derived (or assume) $\exists x\,\psi(x)$. You add $\psi(c)$ as an extra assumption, where $c$ is a fresh constant, and derive the desired result $\phi$. By deduction theorem (you have to make sure to satisfy its hypotheses, such as by not using generalization rules in the proof snippet, or by assuming $\psi(c)$ is a sentence), this implies the provability of $\psi(c)\to\phi$, and therefore of $\exists x\,\psi(x)\to\phi$ by Lemma 1’.

In particular, the construction of a Henkin completion of a theory basically needs that if $T+\exists x\,\psi(x)$ is consistent, where $\psi(x)$ has no other free variable, then $T+\psi(c)$ is consistent, where $c$ is a fresh constant. This follows from Lemma 1’ and the deduction theorem in the way I indicated.

Answer by Carl Mummert for Existential instantiation in Hilbert-style deduction systems

2012-12-21T20:51:42Z

For comparison, Enderton's textbook uses a Hilbert-style system. He derives EI in a form that is essentially what Emil Jeřábek calls Lemma 1', but as a metatheorem:

(EI) If $\Gamma, \phi(c) \vdash \psi$ where $c$ does not occur in $\Gamma$, $\phi(x)$, or $\psi$, then $$\Gamma, (\exists x)\phi(x) \vdash \psi,$$ and there is a deduction witnessing this fact that does not mention $c$.

Here we do not deduce $\phi(c)$ from $(\exists x) \phi(x)$, rather we assume $\phi(c)$ as a temporary hypothesis, for an appropriate $c$, knowing that we can later weaken that hypothesis to $(\exists x)\phi(x)$. But $\phi(c)$ does not appear on the right side of the turnstile in the metatheorem: it is never a conclusion, only a hypothesis.

Also, Enderton does define $\vDash$ via your "simple definition": $\phi \vDash \psi$ means that for every structure $M$ and variable assignment $a$, if $M$ satisfies $\phi$ with $a$ then $M$ satisfies $\psi$ with $a$. In particular, he points out the example that $Q(x) \not\vDash (\forall z) Q(z)$, where $Q$ is a unary relation symbol, and in this sense free variables are indeed not "implicitly universally quantified" in his definition. He is still able to prove that $\Gamma \vdash \phi$ if and only if $\Gamma \vDash \phi$, with no restrictions on free variables, by being careful with the logical axioms he assumes in his Hilbert-style system. He does get universal generalization as a metatheorem: if $\Gamma \vdash \phi(x)$ and $\Gamma$ does not mention $x$ then $\Gamma \vdash (\forall x)\phi(x)$.

This is quite different than the definition of $\vDash$ mentioned by Emil Jeřábek, in which $Q(x) \vDash (\forall z) Q(z)$. Let's call that "implicitly universally quantified". I have found in several cases that authors who are concerned with universal algebra or equational theories seem to prefer to use the definition in which free variables are implicitly universally quantified, while those who are concerned with model theory may not even define satisfaction or logical implication for formulas with free variables (instead they define what it means for a tuple of elements to satisfy a formula in a given structure, which is slightly different). All the definitions agree if we only consider sentences, of course.