How can I evaluate $(\forall x)(\phi \rightarrow (\exists x) \psi )$?

Question

In the book Logic and Structure written by Dirk van Dalen, something like $(\forall x)(\phi \rightarrow (\exists x) \psi ) $ (where x is the only free variable in $\psi$ and $\phi$) is a sentence.

But I just don't know how to evaluate this, the book doesn't explain this or show any example like this, but it does appear in the some of the exercices.

I tried to treat it as if it was equivalent to $((\forall x)\phi \rightarrow (\exists x)\psi)$ but sadly, it's not.

If anyone is familiar with these concepts, I'd appreciate any kind of help :)

Answer 1

What do you mean by "evaluate"? Determine its truth value in a structure? It goes just like any other formula, according to the definitions of interpretation:

$\begin{align} & \mathfrak{A} \vDash \forall x (\phi \to \exists x \psi)\\ \Leftrightarrow\ & \text{for all } a \in A, \mathfrak{A} \vDash (\phi \to \exists x \psi)[\overline{a}/x]\\ \Leftrightarrow\ & \text{for all } a \in A, \mathfrak{A} \vDash \phi[\overline{a}/x] \to \exists x \psi\\ \Leftrightarrow\ & \text{for all } a \in A, [\mathfrak{A} \nvDash \phi[\overline{a}/x] \text{ or } \mathfrak{A} \vDash \exists x \psi]\\ \Leftrightarrow\ & \text{for all } a \in A, [\mathfrak{A} \nvDash \phi[\overline{a}/x] \text{ or for some } b \in A, \mathfrak{A} \vDash \psi[\overline{b}/x] ] \end{align}$

So for all objects, either $\phi$ has to be false of that object, or for that object there has to be another object of which $\psi$ is true.

Note that the $\exists x$ "overwrites" the binding of $x$ by $\forall$; the $x$'es that occur in $\psi$ are existentially quantified and not effectively affected by the universal quantifier although it techically has scope over the entire formula.

---

In general we have the following logical equivalences (in van Dalen they appear as exercise 2 in chapter 2.5):

• provided that $x$ does not occur free in $\psi$:
  $\begin{align} & \forall x (\phi \to \psi)\\ ⟚ \ & \exists x \phi \to \psi \end{align}$
  and
  $\begin{align} & \exists x (\phi \to \psi)\\ ⟚ \ & \forall x \phi \to \psi \end{align}$
• provided that $x$ does not occur free in $\phi$:
  $\begin{align} & \forall x (\phi \to \psi)\\ ⟚ \ & \phi \to \forall x \psi \end{align}$
  and
  $\begin{align} & \exists x (\phi \to \psi)\\ ⟚ \ & \phi \to \exists x \psi \end{align}$

That is, quantifiers switch to their dual when moving them between outside the formula and the left-hand side of an implication, and remain the same when moving them between outside the formula the right-hand side of an implication.
Thus, since $x$ only occurs bound on the RHS of the implication, $\forall x (\phi \to \exists x \psi)$ is logically equivalent to

$$(\exists x \phi \to \exists x \psi)$$

So the above can more easily be rephrased as

Either there is no object of which $\phi$ is true, or there is at least one object of which $\psi$ is true.

Answer 2

$(\forall x)(\phi_x\rightarrow (\exists x)\psi_x)\tag{0}$

The definition of the implication symbol via truth table is $(1)$.

$$A\rightarrow B\tag{1}$$

\begin{array}{c|cc} &\lnot A&A\\\hline \lnot B&\color{orange}{1}&0\\ B&\color{orange}{1}&\color{blue}{1} \end{array}

$$\color{orange}{\lnot A}\lor \color{blue}{B}\tag{2}$$ Looking at this truth table, it is clear that an equivalent definition is $(2)$. As such, your attempt $(3)$ is equal to $(4)$, which is clearly different to the original formula $(0)$.

$(\forall x)\phi_x\rightarrow (\exists x)\psi_x\tag{3}$ $(\exists x)\lnot\phi_x\lor (\exists x)\psi_x\tag{4}$

---

The best way to interpret $(0)$ is to relabel the variables $(5)$, so $x$ does not appear twice in the sentence meaning different things each time.

$(\forall x)(\phi_x\rightarrow (\exists \color{red}{y})\psi_\color{red}{y})\tag{5}$

After relabelling the variables, you can expand the implication in the centre using $(2)$, and bring the universal quantifier from the front inside the brackets, noting that it only applies to the first formula $\phi$ $(6)$.

$(\forall x)\lnot\phi_x\lor (\exists y)\psi_y\tag{6}$

Finally, you can apply the definition of equality $(2)$ again to arrive at $(7)$, which is of a similar form to your attempt $(3)$.

$(\exists x)\phi_x\rightarrow (\exists y)\psi_y\tag{7}$