3

Definition: Sentence - a first order logic formula with no free variables. Semantic deduction theorem claims that in case $\alpha$ is a sentence, and $\Sigma$ is a formula's set. Then $\Sigma , \alpha \models \beta \Rightarrow \Sigma \models \alpha \rightarrow \beta$

Proof: To demonstrate $M\models \alpha\rightarrow\beta$ it is enough to show that in case $M\models \alpha$ , $M\models\beta$ due to $\rightarrow$ definition. In case $M\models\alpha$ from the given condition, $M\models \Sigma,\alpha$ and $\Sigma,\alpha\models \beta \Rightarrow M\models \beta$.

My question is, where in the proof do we use the fact that $\alpha$ is a sentence. As I understand it, in case $\alpha$ is not a sentence , there might be a model $M$ such that , $M\not\models \alpha$ and $M\not\models \neg\alpha$ and therefore the stamtment "in case $M\models \alpha ...$" which is used in the proof is not valid in case $\alpha$ is not a sentence. Is it the right observation? Are there any other assumptions this prove makes which are based on the fact that $\alpha$ is a sentence and not a regular formula?

user5721565
  • 1,390
  • 11
  • 23

1 Answers1

2

Your argument is correct: the issue is with the $\vDash$ relation that, in some cases, is defined for sentences.

For open $\psi$ we have that $M \vDash \psi$ is defined as follows :

$M \vDash \psi \text { iff } M \vDash \text{Cl}(\psi)$

where $\text{Cl}(\psi)$ is the universal closure of $\psi$.

In this case, we have:

$\Sigma \vDash \varphi \text { iff } ( \text { if } M \vDash \Sigma \text { then } M \vDash \varphi)$, where $\Sigma \cup \{ \varphi \}$ consists of sentences.

If we want to adapt it to formulas, we have to consider the universal closure of the formulas in $\Sigma$ (call it $\Sigma'$) as well as the universal closure of $\varphi$.

Going now to your example (and simplifying it to a single variable $x$), we have that : $\Sigma, \alpha \vDash \beta$ is : $\Sigma', \forall x \alpha \vDash \forall x \beta$ while $\Sigma \vDash \alpha \to \beta$ is $\Sigma' \vDash \forall x ( \alpha \to \beta)$.

Now : $\forall x(\alpha \to \beta) \leftrightarrow (\alpha \to \forall x \beta)$ holds only if $x$ is not free in $\alpha$.

Example : for simplicity, we can forget about $\Sigma$.

Consider that $(x=0) \vDash \forall x (x=0)$ because, according to the convention above, it amounts to: $\text { if } M \vDash \forall x(x=0) \text { then } M \vDash \forall x (x=0)$.

But $\nvDash (x=0) \to \forall x (x=0)$ because $\forall x [(x=0) \to \forall x (x=0)]$ does not hold in $\mathbb N$.

Mauro ALLEGRANZA
  • 94,169