GATE CS 2017 Set 1 Q02 — Propositional and First Order Logic

We are given the first-order logic sentence:

$$F: \forall x (\exists y R(x, y))$$

This states that for every element $x$ in the domain, there exists at least one element $y$ such that $R(x, y)$ is true.

Let's analyze each statement assuming a non-empty domain:

1. $\exists y (\exists x R(x, y))$

   Since the domain is non-empty, there exists at least one element $a$ in the domain. Since $F$ is true, for $x = a$, there must exist some $b$ such that $R(a, b)$ is true. Therefore, there exists a pair $(a, b)$ satisfying $R(x, y)$, which means $\exists y (\exists x R(x, y))$ is true.
   Thus, $F \implies \text{I}$.

2. $\exists y (\forall x R(x, y))$

   This states that there is a single element $y$ that is related to all elements $x$. This is a stronger condition than $F$.
   Counterexample: Let the domain be $\{1, 2\}$ and $R = \{(1, 1), (2, 2)\}$. Here, $F$ is true, but statement II is false because no single $y$ works for both $x=1$ and $x=2$.
   Thus, $F \not\implies \text{II}$.

3. $\forall y (\exists x R(x, y))$

   This states that every element $y$ is related to by some $x$.
   Counterexample: Let the domain be $\{1, 2\}$ and $R = \{(1, 1), (2, 1)\}$. Here, $F$ is true (for $x=1, y=1$; for $x=2, y=1$). However, statement III is false because for $y = 2$, there is no $x$ such that $R(x, 2)$ is true.
   Thus, $F \not\implies \text{III}$.

4. $\neg \exists x (\forall y \neg R(x, y))$

   We can simplify this sentence using standard logical equivalences: $$\begin{aligned} \neg \exists x (\forall y \neg R(x, y)) &\equiv \forall x \neg (\forall y \neg R(x, y)) \\ &\equiv \forall x (\exists y \neg \neg R(x, y)) \\ &\equiv \forall x (\exists y R(x, y)) \end{aligned}$$ This is identical to $F$. Since it is equivalent to $F$, it is logically implied by $F$.
   Thus, $F \implies \text{IV}$.

Therefore, only statements I and IV are implied by $F$.