Quantifiers and paranthesis

Question

1. $\exists j (A(j) \land B(j)) \rightarrow \exists p F(p)$

2. $\exists j (A(j) \land B(j) \rightarrow \exists p F(p))$

Can someone please tell me the difference between these two ?

Answer 1

First, note that in 1. $\exists j$ belongs to the left part of the implication, while in 2. $\exists j$ binds the whole formula.

Remember that, for an implication if $A$ is False, then $A\to B$ is allways true no matter if $B$ is true. For your formula $2.$ to be true, there just has to be some element $j_0$ for which $(A(j_0)\wedge B(j_0))$ is false in order for $(A(j_0)\wedge B(j_0) \to \exists p F(p))$ to be true.

However in $1$ if we have some element j_1 such that $A(j_1)\wedge B(j_1)$ hold then we must have $\exists p F(p)$. We can even rewrite.

Lets create a structure $M$ using universe $\mathbb{N}$, let $A^M = B^M = Even $ (the interpretation of $A$ and $B$ in $M$) and let $F=\emptyset$. Note that $M \models \exists j (A(j)\wedge B(j) \to \exists p F(p))$, since if we choose $j=1$ then the left part of the implication is False and thus the implication is true. However $M\not\models \exists j (A(j)\wedge B(j)) \to \exists p F(p)$ since $\exists j (A(j)\wedge B(j))$ is true in $M$ (for $j=2$ for instance), and thus for the implication to be true $M\models\exists p F(p)$ would have to hold, but it does not.

Hence $M \models 1.$ but $M\not\models 2.$ and thus the formulas are clearly different.

Answer 2

Applying basic equivalence laws to the second statement:

$$\exists j (A(j) \land B(j) \rightarrow \exists p F(p)) \Leftrightarrow \text{ (Implication)}$$

$$\exists j (\neg(A(j) \land B(j)) \lor \exists p F(p)) \Leftrightarrow \text{ (Distribution } \exists \text{ over } \lor \text{)}$$

$$\exists j \neg(A(j) \land B(j)) \lor \exists j \exists p F(p) \Leftrightarrow \text{ (Null Quantification)}$$

$$\exists j \neg(A(j) \land B(j)) \lor \exists p F(p) \Leftrightarrow \text{ (Quantification Negation)}$$

$$\neg \forall j (A(j) \land B(j)) \lor \exists p F(p) \Leftrightarrow \text{ (Implication)}$$

$$\forall j (A(j) \land B(j)) \rightarrow \exists p F(p)$$

So now you clearly see the difference with the first statement.

Also, to give a very simple concrete example to see that the two are making different claims:

Take as the domain the natural numbers.

Let $A(x)$ be '$x$ is even', $B(x)$ be '$x$ is prime', and $F(x)$ be '$x$ is an elephant'

Then the first statement:

$$\exists j (A(j) \land B(j)) \rightarrow \exists p F(p)$$

is False, because there is an even prime number, but there is no number that is an elephant, and so the antecedent of the conditional is true, while the consequent is false, making the whole statement false.

But the second statement, which as we saw is equivalent to:

$$\forall j (A(j) \land B(j)) \rightarrow \exists p F(p)$$

is True, since it is not true that all natural numbers are even and prime, and so the antecedent of this conditional is false, making the whole statement true.