3
$\begingroup$

In the PDF textbook "A Friendly Introduction to Mathematical Logic 2nd Edition" by Christopher C. Leary and Lars Kristiansen, page 53, the first quantifier inference rule (QR) is defined by the ordered pair $(\Gamma,\theta)$ such that $\Gamma=\{\psi\to\phi\}$ and $\theta=\psi\to(\forall x\phi)$ where $x$ is not free in the formula $\psi$ (note this is important). The book provides a proof of $\Gamma\vDash\theta$ on page 56, but I decided to give my own, very similar proof.

My proof goes as follows:

$$\Gamma\vDash\theta\iff(\psi\to\phi)\vDash[\psi\to(\forall x\phi)]$$

Let $\mathfrak{U}$ be some fixed, arbitrary interpretation. Thus, continuing forth,

$$(\psi\to\phi)\vDash[\psi\to(\forall x\phi)]\iff\mathfrak{U}\vDash(\psi\to\phi)\Rightarrow\mathfrak{U}\vDash[\psi\to(\forall x\phi)]$$

If $\mathfrak{U}\not\vDash(\psi\to\phi),$ then we're done, so let's assume $\mathfrak{U}\vDash(\psi\to\phi)$ which we'll donote (Assumption 1). This leaves us to prove $\mathfrak{U}\vDash[\psi\to(\forall x\phi)]$ under (Assumption 1).

$$\mathfrak{U}\vDash[\psi\to(\forall x\phi)]\iff\mathfrak{U}\vDash\psi\Rightarrow\mathfrak{U}\vDash(\forall x\phi)$$

Like previously, if $\mathfrak{U}\not\vDash\psi$, then we're done, so let's assume $\mathfrak{U}\vDash\psi$ which we'll denote (Assumption 2). This leaves us to prove $\mathfrak{U}\vDash(\forall x\phi)$ under (Assumption 2).

\begin{align} \mathfrak{U}\vDash(\forall x\phi)&\iff(\forall s)(\mathfrak{U}\vDash(\forall x\phi)[s]) \\ &\iff(\forall s)(\forall a)(\mathfrak{U}\vDash\phi[s[x|a]]) \\ \text{Let $s=t$ be some fixed, arbitrary} \\ \text{variable assignment function into $\mathfrak{U}$.} \\ &\iff(\forall a)(\mathfrak{U}\vDash\phi[t[x|a]]) &&(1) \end{align}

From (Assumption 1),

\begin{align} \mathfrak{U}\vDash(\psi\to\phi)&\iff\mathfrak{U}\vDash\psi\Rightarrow\mathfrak{U}\vDash\phi \\ &\iff(\forall s)(\mathfrak{U}\vDash\psi[s])\Rightarrow(\forall s)(\mathfrak{U}\vDash\phi[s]) \\ \text{Let $s=t[x|a]$ be the same x-modified} \\ \text{assignment function seen in (1).} \\ &\iff\mathfrak{U}\vDash\psi[t[x|a]]\Rightarrow\mathfrak{U}\vDash\phi[t[x|a]]) \\ &\iff(\forall a)(\mathfrak{U}\vDash\psi[t[x|a]])\Rightarrow(\forall a)(\mathfrak{U}\vDash\phi[t[x|a]]) && (2) \end{align}

From (Assumption 2),

\begin{align} \mathfrak{U}\vDash\psi&\iff(\forall s)(\mathfrak{U}\vDash\psi[s]) \\ \text{Let $s=t[x|a]$ be the same x-modified} \\ \text{assignment function seen in (1).} \\ &\iff\mathfrak{U}\vDash\psi[t[x|a]] \\ &\iff(\forall a)(\mathfrak{U}\vDash\psi[t[x|a]])&&(3) \end{align}

Frome (2) and (3), we can deduce (1) and thus we have proven $\mathfrak{U}\vDash(\forall x\phi)$ and we are done. (I have left out some of the final steps, but the remaining steps should be trivial to complete from here hopefully.) $\square$

I'm pretty sure this proof is correct, but the only thing I'm unsure about is the necessity that $x$ be not free in $\psi$. The proof shown in the book uses this fact to help prove $\Gamma\vDash\theta$, so it makes me uneasy about the validity of my proof. From my proof, it seems unnecessary that $x$ be not free in the $\psi$, but I'm might be missing something. Can someone show me where I'm mistaken within my proof and explain why $x$ must not be free in $\psi$.

$\endgroup$
  • $\begingroup$ The reason that we need $x$ to not be free is that $x$ could be mentioned in $\psi$ and $\phi$, but we are only adding a quantifier to $\phi$. For example $x = y \to x =y$ but $x = y \not \to (\forall x)[x = y]$. $\endgroup$ – Carl Mummert Jun 19 '18 at 14:01
  • 1
    $\begingroup$ The error is in the equivalence following : "This leaves us to prove $\mathfrak U \vDash [ψ→(∀xϕ)]$ under (Assumption 1)." See page 38, Ex.1.9.1.4 : $\vDash (\phi \to \psi)$ and $\phi \vDash \psi$ are not equivalent. $\endgroup$ – Mauro ALLEGRANZA Jun 20 '18 at 7:15
2
$\begingroup$

Why must $x$ be not free in $ψ$ in order for $(ψ→ϕ) ⊨ [ψ→(∀xϕ)]$ ?

Because with $x$ free the inference is not valid.

In order to see why the condition is necessary, we can consider the following counter-example : $\psi,\phi := (x=0)$ and consider the stucture $\mathbb N$.

We want to show that :

$(x=0) \to (x=0) \vDash (x=0) \to \forall x (x=0).$

This means [see page 36] :

if $\mathbb N \vDash ((x=0) \to (x=0))$, then $\mathbb N \vDash (x=0) \to \forall x (x=0))$.

See page 37 :

This definition is a little bit tricky. It says that if $\Delta$ is true in $\mathfrak A$, then $\Delta$ is true in $\mathfrak A$. Remember, for $\Delta$ to be true in $\mathfrak A$, it must be the case that $\mathfrak A \vDash \Delta[s]$ for every assignment function $s$.

Now we cam follow your proof considering $\mathbb N$ as $\mathfrak U$.

let's assume (1) : $\mathbb N \vDash ((x=0) → (x=0))$;

this assumption is clearly correct.

And we have to show that $(x=0) \to \forall x (x=0)$ is true in $\mathbb N$, i.e. that :

$\mathbb N \vDash (x=0) \to \forall x (x=0))[s]$, for every assignment function $s$.

If $s(x) \ne 0$, we are done (the antecedent is False).

The issue is when $s(x)=0$, because we want that : $\mathbb N \vDash (\forall x(x=0))[s]$.

In order to have this, we need that :

$\mathbb N \vDash (x=0)[t[x|n]]$, for every $n \in \mathbb N$,

where $t[x|n]$ is an "$x$-variant" of $s$, i.e. is as $s$ except for $s(x)=n$.

And here we are stuck....

Clearly :

$\mathbb N \nvDash (x=0)[t[x|1]]$.

$\endgroup$
  • $\begingroup$ I still need help finding at which step my proof fails and why it failed. I understand your counter-example, but I'm having a hard time using it to backtrack through my proof and locate the exact error I made. $\endgroup$ – Kainoa B Jun 20 '18 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.