Let $x \in X, \ y \in Y, \ z \in Z$ and $w \in W$. Let $P_1(x,y), \ P_2(y,z), \ P_3(z,w)$ be some properties or sentences(for example, if $R \subseteq X \times Y$, then $P_1(x,y)$ may be $xRy$).
I can't get my head around the following fact: Say, $x$ and $w$ are fixed. The sentence "$\exists z \in Z: \ (\exists y \in Y: P_1(x,y) \wedge P_2(y,z)) \wedge P_3(z,w)$" is true if and only if "$\exists y \in Y: P_1(x,y) \wedge (\exists z \in Z: P_2(y,z) \wedge P_3(z,w))$" is. So, they are the same.
Why is that? Sure, one recommendation would pick up a book on mathematical logic and study it. But the problem is that I'm not studying logic at all, I've just encountered the need for such a proof in a book on set theory (namely, Halmos-"Naive Set Theory"). This is not my first math book, I've studied (pure and rigorous) mathematics before, but there were no need for such "logically sophisticated" proofs. How do I understand that?
There are two fundamental equivalences behind this:
$\exists x \exists y \varphi(x,y) \Leftrightarrow \exists y \exists x \varphi(x,y)$
This is because both sentences say the exact same thing: there are two objects standing in some relationship as expressed by $\varphi(x,y)$. So, if you have two quantifiers of the same type (it also works for two universals) right next to each other, then you can swap them. But they have to be the same type (you can't change $\forall x \exists y$ to $\exists y \forall x$) and they have to be right next to each other (e.g you can't change $\exists x \neg \exists y$ to $\exists y \neg \exists x$)
$\psi \land \exists x \varphi(x) \Leftrightarrow \exists x (\psi \land \varphi(x))$
To understand this, note that an existential can be seen as kind of disjunction, that is, if $a,b,c,...$ denote the objects in your domain, then you can think of an existential like this:
$\exists x \varphi(x) \approx \varphi(a) \lor \varphi(b) \lor \varphi(c) \lor ...$
Now, this is certainly not an official equivalence, as I am really mixing semantics and syntax here, but again, it serves to at least conceptuall understand why we can bring out an existential over a conjunct if that conjunct does not contain the relevant free variable, because we now get:
$\psi \land \exists x \varphi(x) \approx \psi \land (\varphi(a) \lor \varphi(b) \lor \varphi(c) \lor ....) \Leftrightarrow (\psi \land \varphi(a)) \lor (\psi \land \varphi(b)) \lor (\psi \land \varphi(c)) \lor ... \approx \exists x (\psi \land \varphi(x))$
Applying these two principles to your statement, we get:
$\exists z \in Z \exists y \in Y (P_1(x,y) \land P_2(y,z) \land P_3(z,w)) \Leftrightarrow$ (use principle 1)
$\exists y \in Y \exists z \in Z (P_1(x,y) \land P_2(y,z) \land P_3(z,w)) \Leftrightarrow$ (use principle 2)
$\exists y\in Y (P_1(x,y) \land \exists z (P_2(y,z) \land P_3(z,w)))$
Addendum
In response to a comment below by EE18: Yes, you can use the 'expansion method' used in 2) above to show a number of other equivalences. To do that, we'll use:
$\forall x \ \varphi(x) \approx \varphi(a) \land \varphi(b) \land \varphi(c) \land ...$
Now we can do:
3A) $\exists x \ \psi \Leftrightarrow \psi$
'Proof': $\exists x \ \psi \approx \psi \lor \psi \lor \psi ...\Leftrightarrow \psi$ (we get one entry of $\psi$ for each object in the domain, and because in classical logic we assume there is always at least one object in any domain, we get one or more $\psi$ terms that by Idempotence collapse into exactly one)
3B) $\forall x \ \psi \Leftrightarrow \psi$
'Proof': $\forall x \ \psi \approx \psi \land \psi \land \psi ...\Leftrightarrow \psi$ (we get one entry of $\psi$ for each object in the domain, and because in classical logic we assume there is always at least one object in any domain, we get one or more $\psi$ terms that by Idempotence collapse into exactly one)
4A) Distribution of $\exists$ over $\lor$:
$\exists x (\psi(x) \lor \varphi(x)) \Leftrightarrow \exists x \psi(x) \lor \exists \varphi(x) $
(where $\psi(x)$ is any formula (so that may or may not contain a free variable $x$)
'Proof':
$\exists x (\psi(x) \lor \varphi(x)) \approx (\psi(a) \lor \varphi(a)) \lor (\psi(b) \lor \varphi(b)) \lor (\psi(c) \lor \varphi(c)) ... \Leftrightarrow (\psi(a) \lor \psi(b) \lor \psi(c)...) \lor (\varphi(a) \lor \varphi(b) \lor \varphi(c) ...| \approx \exists x \ \psi(x) \lor \exists x \ \varphi(x) $
4B) Distribution of $\forall$ over $\land$:
$\forall x (\psi(x) \land \varphi(x)) \Leftrightarrow \forall x \ \psi(x) \land \forall x \ \varphi(x)$ (where $\psi(x)$ is any formula (so that may or may not contain a free variable $x$)
'Proof':
$\forall x (\psi(x) \land \varphi(x)) \approx (\psi(a) \land \varphi(a)) \land (\psi(b) \land \varphi(b)) \land (\psi(c) \land \varphi(c)) ... \Leftrightarrow (\psi(a) \land \psi(b) \land \psi(c)...) \land (\varphi(a) \land \varphi(b) \land \varphi(c) ...| \approx \forall x \ \psi(x) \land \forall x \ \varphi(x) $
With these, we can show some other things:
5A) Prenex Law $\exists$ over $\lor$:
$ \exists x (\psi \lor \varphi(x)) \Leftrightarrow \psi \lor \exists x \varphi(x)$
Proof:
$ \exists x (\psi \lor \varphi(x)) \Leftrightarrow \exists x \psi \lor \exists x \varphi(x) \Leftrightarrow \psi \lor \exists x \varphi(x)$
5B) Prenex Law $\forall$ over $\land$:
$ \forall x (\psi \land \varphi(x)) \Leftrightarrow \psi \land \forall x \varphi(x)$
Proof:
$ \forall x (\psi \land \varphi(x)) \Leftrightarrow \forall x \psi \land \forall x \varphi(x) \Leftrightarrow \psi \land \forall x \varphi(x)$
Of course, we could have shown 5A) and 5B) using the expansion method as well. (left as exercise to reader)
OK, couple more:
5C) Prenex Law $\exists$ over $\land$:
$ \exists x (\psi \land \varphi(x)) \Leftrightarrow \psi \land \exists x \varphi(x)$
'Proof':
$ \exists x (\psi \land \varphi(x)) \approx (\psi \land \varphi(a)) \lor (\psi \land \varphi(b)) \lor ... \Leftrightarrow \psi \land (\varphi(a) \lor \varphi(b) \lor ...) \approx \psi \land \exists x \ \varphi(x)$
(note, this is the same as 2) above .. but in reverse)
5D) Prenex Law $\forall$ over $\lor$:
$\forall x (\psi \lor \varphi(x)) \Leftrightarrow \psi \lor \forall x \ \varphi(x) $
'Proof':
$ \forall x (\psi \lor \varphi(x)) \approx (\psi \lor \varphi(a)) \land (\psi \lor \varphi(b)) \land ... \Leftrightarrow \psi \lor (\varphi(a) \land \varphi(b) \land ...) \approx \psi \lor \forall x \ \varphi(x)$
And finally, with these principles, we can now also show that while we are not allowed to swap neighboring $\forall$ and $\exists$ in sentences, we can if the quantified variables do not 'interact'. For example:
$\forall x \exists y (\psi(x) \lor \varphi(y)) \Leftrightarrow \forall x (\psi(x) \lor \exists y \ \varphi(y)) \Leftrightarrow \forall x \ \psi(x) \lor \exists y \ \varphi(y) \Leftrightarrow \exists y (\forall x \ \psi(x) \lor \varphi(y)) \Leftrightarrow \exists y \forall x ( \psi(x) \lor \varphi(y))$