My book and my teacher both said that these two statements are different:
1) $∀x∈A,∃y∈B, F(x, y)⇒G(x)$
2) $∀x∈A,(∃y∈B, F(x, y))⇒G(x)$
How can just adding an extra parenthesis make the statement different? I am not quite sure I understand. If they are different, how are there negation different? Would the negation be as follows:
1) $∀x∈A,∃y∈B, F(x, y) ∧ ¬ G(x)$
2) $∀x∈A,(∀y∈B, ¬ F(x, y)) ∧ ¬ G(x)$
SIDE NOTE: I tried taking contrapositives, but ended up with the same expression for both. So how and why are they diffrent? $¬ G(x) ⇒ ∃x∈A,∀y∈B, ¬ F(x, y) $
Thanks
Because adding parentheses changes the scope of quantifiers.
Thus, the two formulas are not equivalent, provided that we read 1) as: $∀x \ [∃y \ (F(x,y) \to G(x))]$.
See Prenex normal form:
Formula 2) is $∀x \ [(∃y \ F(x,y)) \to G(x)]$, where the scope of the existential quantifier is restricted to sub-formula $F(x,y)$.
Thus, according to the equivalence above, 2) is equivalent to: $∀x \ [∀y \ (F(x,y) \to G(x))]$.
An easy check: formula 2) is equivalent to: $∀x \ [\lnot (∃y \ F(x,y)) \lor G(x)]$, i.e. to: $∀x \ [(∀y \lnot F(x,y)) \lor G(x)]$.
In general, the universal quantifier does not "distribute" over $\lor$ but, due to the fact that $y$ does not occur in $G(x)$, we can move it to get: $∀x \ [∀y \ ( \lnot F(x,y) \lor G(x))]$.
Maybe your perplexities are due to the (not so good) practice of mixing commas and parentheses to identify the scope of quantifiers.
Formula 1): $∀x∈A,∃y∈B,F(x,y)⇒G(x)$ is $∀x∈A \ [∃y∈B \ (F(x,y)⇒G(x))]$ where the scope of the existential quantifier is the sub-formula $F(x,y)⇒G(x)$.
Formula 2): $∀x∈A,(∃y∈B,F(x,y))⇒G(x)$, instead, is $∀x∈A \ [∃y∈B \ (F(x,y)) ⇒G(x)]$ where the scope of the existential quantifier is only the sub-formula $F(x,y)$.