# Is there difference between these formulas ?

I consider formulas for following fact $r\circ s\subseteq r\cap s$.
I know that correct is:
$\forall_{x,y}(\exists_z r(x,z)\wedge s(z,y)) \to r(x,y)\wedge s(x,y)$

However, I consider if also correct is:
$\forall_{x,y,z} r(x,z) \wedge s(z,y)) \to r(x,y)\wedge s(x,y)$

Hmm ? Where this second formula fail ?

• THe second formula has unbalanced parentheses Nov 17 '16 at 15:49
• And there aren’t enough parentheses in the first expression. It should be $$\forall_{x,y}\Big(\big(\exists_zr(x,z)\land s(z,y)\big)\to r(x,y)\land s(x,y)\Big)\;.$$ Nov 17 '16 at 15:53
• Ok, tell me please, is it possible to write this formula with only one $\forall$ ?
– user343207
Nov 17 '16 at 15:54
• To be even more annoyingly nitpicky, the first expression should be $\forall_{x,y}(\exists_z (r(x,z)\wedge s(z,y)) \to (r(x,y)\wedge s(x,y)))$. But yes, that is equivalent to $\forall_{x,y,z}((r(x,z)\wedge s(z,y)) \to (r(x,y)\wedge s(x,y)))$ Nov 17 '16 at 16:07

More generally, $$\tag1 \forall_x\Bigl(\bigl(\exists _y \phi(x,y)\bigr)\to \psi(x)\Bigr)$$ and $$\tag2 \forall_{x,y}\bigl(\phi(x,y)\to \psi(x)\bigr)$$ are equivalent. (Yours is a special case of this)
To see this, first assume $(1)$. Let $x,y$ be arbitrary. If $\phi(x,y)$ is false, then immediately $\phi(x,y)\to \psi(x)$. And if $\phi(x,y)$ is true, then in particular $\exists_y\phi(x,y)$ for this $x$, hence $\psi(x)$ an again $\phi(x,y)\to\psi(x)$ is true. We conclude $(2)$.
Now assume $(2)$ and let $x$ be arbitrary. If we assume $\exists_y\phi(x,y)$ then for such $y$ we conclude from $(2)$ that $\phi(x,y)\to\psi(x)$ and by modus ponens $\psi(x)$, hence we decudes $(\exists_y\phi(x,y))\to \psi(x)$ for our $x$, thus proving $(1)$.