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 ?

  • $\begingroup$ THe second formula has unbalanced parentheses $\endgroup$ Nov 17 '16 at 15:49
  • $\begingroup$ 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)\;.$$ $\endgroup$ Nov 17 '16 at 15:53
  • $\begingroup$ Ok, tell me please, is it possible to write this formula with only one $\forall$ ? $\endgroup$
    – user343207
    Nov 17 '16 at 15:54
  • $\begingroup$ 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)))$ $\endgroup$
    – Bram28
    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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy