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!
Best Answer
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.