What is the intuitive explanation of $\exists y \theta(x,y) \to \psi(x)$ is the same to $\forall y ( \theta(x,y) \to \psi(x) )$?

Question

I was studying first order predicate logic and discovered tha:

$$\Sigma \vdash (\exists y \theta(x,y)) \to \psi(x)$$

is NOT the same as:

$$\Sigma \vdash \exists y ( \theta(x,y) \to \psi(x) )$$

which came to me as very big surprise. I do blind symbol crunching by recalling $p \to q $ is a short hand for $\neg p \lor q$, the reason is pretty obvious. Since:

$$ \Sigma \vdash (\exists y \theta(x,y)) \to \psi(x) $$

equivalent to:

$$ \Sigma \vdash \neg (\exists y \theta(x,y)) \lor \psi(x)$$ $$ \Sigma \vdash \neg (\exists y \theta(x,y)) \lor \psi(x)$$ $$ \Sigma \vdash \forall y \neg \theta(x,y) \lor \psi(x)$$ $$ \Sigma \vdash \forall y ( \neg \theta(x,y) \lor \psi(x))$$

and finally the expression that surprised me most and was most troubling to me:

$$ \Sigma \vdash \forall y ( \theta(x,y) \to \psi(x))$$

I would have not guessed that was equal to the original $\Sigma \vdash (\exists y \theta(x,y)) \to \psi(x)$ while $\Sigma \vdash \exists y ( \theta(x,y) \to \psi(x))$ is not the same. So we can't just pull out the quantifier if it's on the antecedent (but you can in the consequent). I was told by my professor that this should be obvious and if it wasn't that there was some intuitive misunderstanding of what implication means. He wasn't helpful so here I am.

So what is the intuition for why this happens? What misunderstanding do I have of implications with quantifiers? What is the proper way to understand implications with quantifiers? Whats a good foundation for this?

---

My main concern is that:

$$\Sigma \vdash (\exists y \theta(x,y)) \to \psi(x) \iff \Sigma \vdash \forall ( y \theta(x,y)) \to \psi(x)$$

is true while I thought it was "obvious" that:

$$\Sigma \vdash (\exists y \theta(x,y)) \to \psi(x) \iff \Sigma \vdash \exists ( y \theta(x,y)) \to \psi(x)$$

is true. But this second one is false and concerns me because it should have been obvious.

---

Attempt to explain my current understanding:

I think there is plenty of explanations of implications online, which I understand. My favorite one is explaining implications as a promise and one explores if the promise holds or not. So if $A \to B$ is an implication, then if $A$ is False but $B$ was True or False, then there is no lie, so the implication is true. Something true to something true is obviously ok and if the antecedent is false but leads to a truth then the statement is a lie. It makes sense.

For me also Modus Ponens (MP) makes implications make a lot of sense. If we have the implication IS true and the antecedent is true, then we do have "causation". Which is how I think of implications in the context of "causation" (inference rules).

Beyond that I am not sure what else I missed...anyone has an insight they can share with me please? This has had me extremely concerned for days...

---

Ok now I tried thinking about the opposite because the first answer seemed helpful but noticed that I am even more confused. i.e. whats going on in the case:

$$ (\forall y \varphi(x,y) ) \to \psi(x) $$

why is it equivalent to:

$$ \exists y (\varphi(x,y) \to \psi(x) ) $$

Answer 1

The intuition you should have is just that a conditional means "the consequent is true if the antecedant is."

• $(\exists y~\phi(y))\to \psi$ means, "$\psi$ is true if there is a $y$ that satisfies $\phi(y)$."

• $\forall y~(\phi(y)\to \psi)$ means "for any $y$, $\psi$ is true if that $y$ satisfies $\phi(y)$"

Which make the same guarantee about $\psi$ being true.

Answer 2

To prove $$(∃ y. P_y) ⇒ Q$$

You must provide proofs $P_y ⇒ Q$ for each “case of possible $y$” --this is just proof-by-case-analysis.

However, providing proofs $P_y ⇒ Q$ for each $y$ is the same as proving $$∀ y. (P_y ⇒ Q)$$

Hope that helps! :-)

---

Edit:

\begin{align*} \quad & \text{Let's prove: $(∃y. P_y) ⇒ Q$} \\ = \quad& \text{So assume $∃y. P_y$ and let us show $Q$ } \\ = \quad& \text{That is, *assume* some $y$ exists with $P_y$ and let us show $Q$ } \\ = \quad& \text{That is, *given* some $y$ exists with $P_y$ and let us show $Q$ } \\ = \quad& \text{That is, given a $y$ with $P_y$, let us show $Q$ } \\ = \quad& \text{That is, for any $y$ with $P_y$, let us show $Q$ } \\ = \quad& \text{That is, for any $y$, we can show if $P_y$ then $Q$ } \\ = \quad& \text{That is, we are proving $∀y. (P_y ⇒ Q)$} \end{align*}

Answer 3

I think you're running into a little bit of the Paradox of the Material Implication here. Yes, the equivalence holds, but that is using the material implication ... which does not always match our intuitions regarding the way we use conditional statements in natural language.

Anyway, one way of thinking about the equivalence is: Since $\theta(x)$ makes no reference to $y$ (and indeed, since $x$ is a free variable in both expressions), we can, independently of any choice of $y$, think about the truth-value of $\theta(x)$ (given some $x$):

If $\theta(x)$ is true, then $\exists y \theta(x,y)) \to \theta(x)$ is true as well, no matter the value of $\exists y \theta(x,y))$ (in fact, this is not obvious, and instance of the paradoxical nature of the material implication). But for that very same reason, no matter what we pick for $y$: $\theta(x,y)) \to \theta(x)$, will be true as well, i.e. we have that for any $y$: $\theta(x,y)) \to \theta(x)$ is true, and hence $\forall y (\theta(x,y)) \to \theta(x))$ is true. So, both statements are true if $\theta(x)$ is true.

If $\theta(x)$ is false, then there are two further cases to consider : either there is some $y$ such that $\theta(x,y)$ is true, or not.

If there is, i.e. if $\theta(x,y)$ is true for some $y$, then $\exists y \theta(x,y)$ is true, and since $\theta(x)$ is false, we get that $\exists y \theta(x,y)) \to \theta(x)$ is false. But for this very $y$ for which $\theta(x,y)$ is true, then given that $\theta(x)$ is false, we have that $\theta(x,y) \to \theta(x)$ is false, and hence $\forall y (\theta(x,y)) \to \theta(x))$ is false as well.

If there is not, then $\theta(x,y)$ is false for any $y$, and hence (and here is another instance of the paradoxical nature of the material implication ...) $\theta(x,y) \to \theta(x)$ is true for any $y$, and hence $\forall y (\theta(x,y)) \to \theta(x))$ is true. And, since in this case $\exists y \theta(x,y)$ is false, $\exists y \theta(x,y)) \to \theta(x)$ is true as well.

Answer 4

I'm not super satisfied with this explanation but its the best thing I have right now. The reason I am not super satisfied with it is because its just a giant proof (not a clear intuition/succinct explanation). Perhaps I will be able to extract from this a compact intuition in the future

Theorem: "if $\exists x Px$ then $Q$ $" \iff $ "$\forall x$ if $Px$ then $Q$."

Proof ($\Longrightarrow$) We want to show "if $\exists x Px$" then $Q$ $ \Longrightarrow "$ $\forall x$ if $Px$ then $Q$". Assume the implication "if $\exists x Px$ then $Q$" is true. WTS (Want To Show) "$\forall x$ if $Px$ then $Q$" follows (under that assumption). To show that we must consider any $x$ and show that the implication " if $Px$ then $Q$" is true. To show the implication is true, similarly, we must have that $Q$ follows from $Px$. Thus, consider any $x$ and assume $Px$. Recall we assumed "if $\exists x Px$ then $Q$". Now the question is does $Px$ satisfy $\exists x Px$? The answer is yes. Since $Px$ is true some $x$ satisfy $P$, so there does exist an $x$ that makes $Px$ true (meaning we satisfy "$\exists x Px$"). Thus, we satisfy the antecedent of "if $\exists x Px$ then $Q$" and by Modus Ponens (MP) we get $Q$ follows. This happens for any $x$ we choose, so $\forall x (Px \to Q)$.

($\Longleftarrow$) Now we want to show "$\forall x$ if $Px$ then $Q$" $\implies$ "if $\exists x Px$ then $Q$". The proof is concluded once we have arrived at "if $\exists x Px$ then $Q$" is true when we assumed "$\forall x$ if $Px$ then $Q$" is true. Thus assume "$\forall x$ if $Px$ then $Q$". WTS "if $\exists x Px$ then $Q$". To show "if $\exists x Px$ then $Q$" we need to show if we assume $\exists x Px$ that we get $Q$. Thus assume $\exists x Px$ and let the $x$ such that $Px$ be $x_T$ (so we have assumed $Px_T$). Recall we have that for any $x$ the implication "if $Px$ then $Q$" is true. In particular "if $Px_T$ then $Q$" is true. Since we have assumed $Px_T$ is true (and trying to see if $Q$ follows) by Modus Ponens we have $Q$, as required.

QED

Comments: another way to see this implication equivalence would be via truth table comparison. If the two are the same, then they must have the same truth tables. The first step ($\Longrightarrow$) shows that when "if $\exists x Px$ then $Q$ " is true then "$\forall x$ if $Px$ then $Q$." is true. This shows they are true in the same places. However, to have the same truth table, they would need to be false in the same places true. That is done by the converse proof ($\Longleftarrow$). Which is $\neg p \implies \neg q$ which shows false implies false (in the meta language). Thus, we get they match in false simply by showing the contrapositive.