Question

Consider the first-order logic sentence $F:\forall x\left(\exists yR(x,y)\right)$. Assuming non-empty logical domains, which of the sentences below are impied by F ?
I $\exists y\left(\exists xR(x,y)\right)$
II $\exists y\left(\forall xR(x,y)\right)$
III $\forall y\left(\exists xR(x,y)\right)$
IV $\rightharpoondown \exists x(\forall y\rightharpoondown R(x,y))$

• A. IV only
• B. I and IV only
• C. II only
• D. II and III only

Answer 1

The correct option is B

I and IV only

I. $\forall x\exists yR(x,y)\to \exists y\left(\exists xR\right(x,y\left)\right)$ is true, since $\exists y\left(\exists xR\right(x,y\left)\right)\equiv \exists x\left(\exists yR\right(x,y\left)\right)$

II. $\forall x\exists yR(x,y)\to \exists y\left(\forall xR\right(x,y\left)\right)$ is false Since $\exists y$ when it is outside is stronger then when it is inside.

III. $\forall x\exists yR(x,y)\to \forall y\exists xR(x,y)$ is false Since R(x,y) may not be symmetric in x and y.

IV. $\forall x\exists yR(x,y)\to \rightharpoondown (\exists x\forall y\rightharpoondown R(x,y\left)\right)$ is true Since $\rightharpoondown (\exists x\forall y\rightharpoondown R(x,y\left)\right)\equiv \forall x\exists yR(x,y)$

So, IV will reduce to $\forall x\exists yR(x,y)\to \forall x\exists yR(x,y)$ which is trivially true.

So correct answer is I and IV only which is option (b).