GATE 2023 CS Q.26: solution and answer

GATE 2023 · CSQ.26 · 1 mark · MSQ

Geetha has a conjecture about integers, which is of the form

\forall x (P (x) \Rightarrow \exists y Q (x, y)),

where $P$ is a statement about integers, and $Q$ is a statement about pairs of integers. Which of the following (one or more) option(s) would imply Geetha's conjecture?

(A)
$\exists x (P (x) \land \forall y Q (x, y))$
(B)
$\forall x \forall y Q (x, y)$
(C)
$\exists y \forall x (P (x) \Rightarrow Q (x, y))$
(D)
$\exists x (P (x) \land \exists y Q (x, y))$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The options that imply the conjecture are (B) and (C).

Official answer: B, CSource: Official answer key, GATE 2023 CS (IIT Kanpur)

The conjecture is $\forall x (P (x) \Rightarrow \exists y Q (x, y))$ . A statement implies it only if, whenever it is true, every $x$ with $P (x)$ has some $y$ with $Q (x, y)$ .
(A) $\exists x (P (x) \land \forall y Q (x, y))$ talks about one $x$ only. Counter-model: take integers, $P (x)$ true for all $x$ , and $Q (x, y)$ true exactly when $x = 0$ . Then (A) holds with $x = 0$ , but for $x = 1$ there is no $y$ with $Q (1, y)$ , so the conjecture fails. (A) does not imply it.
(B) $\forall x \forall y Q (x, y)$ : fix any $x$ . Since the integers are non-empty, take $y = 0$ . Then $Q (x, 0)$ holds, so $\exists y Q (x, y)$ holds for every $x$ . Hence $P (x) \Rightarrow \exists y Q (x, y)$ is true for every $x$ . (B) implies the conjecture.
(C) $\exists y \forall x (P (x) \Rightarrow Q (x, y))$ : fix a witness $y_{0}$ with $P (x) \Rightarrow Q (x, y_{0})$ for all $x$ . Take any $x$ with $P (x)$ . Then $Q (x, y_{0})$ holds, so $\exists y Q (x, y)$ . Hence $\forall x (P (x) \Rightarrow \exists y Q (x, y))$ . This is the valid rule that $\exists y \forall x$ implies $\forall x \exists y$ . (C) implies the conjecture.
(D) $\exists x (P (x) \land \exists y Q (x, y))$ again names only one $x$ . Counter-model: $P (x)$ true for all $x$ , $Q (x, y)$ true exactly when $x = 0$ . (D) holds with $x = 0$ , but $x = 1$ has no $y$ with $Q (1, y)$ , so the conjecture fails. (D) does not imply it.
Correct options: (B) and (C).

KEY IDEA

To imply a statement of the form $\forall x (P \Rightarrow \exists y Q)$ , a premise must give a witness $y$ for every $x$ with $P (x)$ . $\forall x \forall y$ and $\exists y \forall x$ both do. A premise about only one $x$ (an $\exists x$ statement) cannot.

WATCH OUT FOR

Choosing (A) or (D) because they look like the conjecture, when an $\exists x$ premise says nothing about the other $x$ . Also doubting (C) because its quantifier order differs: $\exists y \forall x$ is stronger than $\forall x \exists y$ , so it implies it.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 7 Mathematical logic questions, with notes

GATE 2023 CS Q.26: solution and answer

Answer and solution

More Mathematical logic questions