GATE CSE 2023 | Question: 16

Question

Geetha has a conjecture about integers, which is of the form
\[
\forall x(P(x) \Longrightarrow \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) \wedge \forall y Q(x, y))$
• B. $\forall x \forall y Q(x, y)$
• C. $\exists y \forall x(P(x) \Longrightarrow Q(x, y))$
• D. $\exists x(P(x) \wedge \exists y Q(x, y))$

Comments

ans is b,c or c,d.??     some are telling c,d is the answer??

Answer 1

Here, domain is the set of integers, So, elements $x,y \in   \{...,-3,-2,-1,0,1,2,3,...\}$ and assuming a tautology is defined as a formula or assertion that is true in every possible interpretation.

Since, statement $\forall x P(x)$ is same as $P(1) \wedge P(2) \wedge ...$ and statement $\exists x P(x)$ is same as $P(1) \vee P(2) \vee ...$

(Here, “...” contains all the elements from the domain, not only positive integers) and $A$ implies $B$ is true means $A \Rightarrow B$ is a tautology. Some points can be noted as:

1. Symbols  $\forall$(universal quantifier) is used for conjunction and $\exists$(existential quantifier) is used for disjunction.

2. $\neg \forall x \neg \equiv \exists x$ and $\neg \exists x \neg \equiv \forall x$ 
3. Using Null Quantification, we can write $\forall x (P(x) \Rightarrow \exists y Q(x,y))$ as $\forall x \exists y (P(x) \Rightarrow Q(x,y)).$ Both are equivalent expressions. 

 

Method 1:

 

B.  $\forall x \forall y Q(x,y) \Rightarrow  [\forall x (P(x) \Rightarrow \exists y Q(x,y))]$

$ \equiv \forall x \forall y Q(x,y) \Rightarrow  [\forall x \exists y (P(x) \Rightarrow Q(x,y))]$

$ \equiv \forall x \forall y Q(x,y) \Rightarrow  [\forall x \exists y (\neg P(x) \vee Q(x,y))]$

$ \equiv \forall x \forall y Q(x,y) \Rightarrow  [\forall x (\neg \forall y (P(x) \wedge \neg Q(x,y))]$

Now, both sides of $\Rightarrow$ there are $\forall$ (universal) quantifier and which is used for conjunction. If we try to make left side true then right side should also be true to become this formula as tautology.

So, left side is true when $Q(x,y)$ is true for each $x,y$ from the domain and so in right side, $ \neg Q(x,y)$ becomes false and so, $P(x) \wedge \neg Q(x,y)$ becomes false and so, $\neg \forall y (P(x) \wedge \neg Q(x,y)$ becomes true and so, $\forall x (\neg \forall y (P(x) \wedge \neg Q(x,y))$ becomes true. 

Hence, when left side is true then right sides is also true and so, it is a tautology and so, B is correct.

C.  $\exists y \forall x (P(x) \Rightarrow Q(x,y))  \Rightarrow  [\forall x (P(x) \Rightarrow \exists y Q(x,y))]$

$\equiv \exists y \forall x (P(x) \Rightarrow Q(x,y))  \Rightarrow  [\forall x \exists y (P(x) \Rightarrow Q(x,y))]$

$\equiv \exists y \forall x R(x,y)  \Rightarrow  \forall x \exists y R(x,y)$

Now, Consider the interpretation of $R(x,y)$ as $x+y=0.$ Now, $\exists y \forall x R(x,y)$ means that “There exist an integer y such that for every ineger x, R(x, y)” which is false because if we choose any y then there will be “only one” x. In the same way, $\forall x \exists y R(x,y)$ is true because for every x there exist a y such that $x+y=0.$

$\exists y \forall x R(x,y)$ is true if and only if there exist a y which makes $R(x,y)$ true for every x. So, y does not depend on x.

$\forall x \exists y R(x,y)$ is true if and only if for every x, there exist a y which makes $R(x,y)$ true. So, here y can depend on x.

So, $\exists y \forall x R(x,y)$ is stronger than $\forall x \exists y R(x,y)$.

Hence, if $\exists y \forall x R(x,y)$ is true then $\forall x \exists y R(x,y)$ must also be true but if $\forall x \exists y R(x,y)$ is true then $\exists y \forall x R(x,y)$ need not be true as can be seen from above interpretation of $x+y=0.$

A.  $\exists x (P(x) \wedge \forall y Q(x,y))  \Rightarrow  [\forall x (P(x) \Rightarrow \exists y Q(x,y))]$

$\equiv \neg \forall x [P(x) \Rightarrow \exists y \neg Q(x,y)] \Rightarrow [\forall x (P(x) \Rightarrow \exists y Q(x,y))]$

$\equiv \neg [P(1) \Rightarrow \exists y \neg Q(1,y) \wedge P(2) \Rightarrow \exists y \neg Q(2,y) \wedge ...]$

$\Rightarrow  [P(1) \Rightarrow \exists y Q(1,y) \wedge P(2) \Rightarrow \exists y Q(2,y) \wedge ...]$

Now, assign $P(1)$ and $P(2)$ as True and $Q(1,y)$ is False for every y and $Q(2,y)$ is True for every y which makes right side of $\Rightarrow$ as False and left side as True. Hence, it is not a tautology.

D.  $\exists x (P(x) \wedge \exists y Q(x,y))  \Rightarrow  [\forall x (P(x) \Rightarrow \exists y Q(x,y))]$

$\equiv \neg \forall x [P(x) \Rightarrow \forall y \neg Q(x,y)] \Rightarrow [\forall x (P(x) \Rightarrow \exists y Q(x,y))]$

$\equiv \neg [P(1) \Rightarrow \forall y \neg Q(1,y) \wedge P(2) \Rightarrow \forall y \neg Q(2,y) \wedge ...]$

$\Rightarrow [P(1) \Rightarrow \exists y Q(1,y) \wedge P(2) \Rightarrow \exists y Q(2,y) \wedge ...]$

Now, assign $P(1)$ and $P(2)$ as True and $Q(1,y)$ is False for every y and $Q(2,y)$ is True for every y which makes right side of $\Rightarrow$ as False and left side as True. Hence, it is not a tautology.

Hence, B and C are correct options.

 

Method 2 :

We can write the given conjecture as:

$S: \ \ [P(1) \Rightarrow  (Q(1,1) \vee Q(1,2) \vee...)] \wedge [P(2) \Rightarrow (Q(2,1) \vee Q(2,2) \vee...)] \wedge ...$

Now, $A$ implies $B$ is true means $A \Rightarrow B$ is a tautology.

So, here, we will try to make above statement $S$ as False and try to make each given option as True and if we are able to do it, then it will not be a tautology and hence, that option does not imply $S.$

Now, if we try to make $S$ as False, it means at least one $[P(x) \Rightarrow \exists y Q(x,y)]$ is False which means:

$\textbf{The conditions are:}$

$(1)$ $P(a)$ is True for at least one $a$ and

$(2)$ $Q(a,b)$ is False for all $y$ with the corresponding $a$ from $(1).$

Where $a$ and $b$ come from the domain.

Now, comes to each option one by one.

$(A)$ We can write it as:

$[P(1) \wedge \forall y Q(1,y)] \vee [P(2) \wedge \forall y Q(2,y)] \vee ...$

We can make it as true by making $P(1)$ as true and $\forall y Q(1,y)$ as false to satisfy the above conditions and for other $P(c)$ as true and $\forall y Q(c,y)$ as True where $c \neq 1$. In this way, above condition is also satisfied and also, we are able to make whole statement true.

Hence, $(A)$ is wrong.

$(B)$ We can write it as:

$\forall y Q(1,y) \wedge \forall y Q(2,y) \wedge ... $

Now, we can't make it as true because according to the above condition $(2),$ $Q(a,b)$ is False for all $b$ with at least one $a$ which makes whole statement false.

Hence, $(B)$ is correct.

$(C)$ We can write it as:

$\exists y [(P(1) \Rightarrow Q(1,y)) \wedge (P(2) \Rightarrow Q(2,y)) \wedge...]$

Again, we can't make it True because we can set $P(1)$ as True and $Q(1,y)$ as False for all $y$. In this way above condition is satisfied and also the whole statement becomes False.

Hence, $(C)$ is correct.

$(D)$ We can write it as:

$[P(1) \wedge \exists y Q(1,y)] \vee [P(2) \wedge \exists y Q(2,y)] \vee ...]$

We can make this statement as true by making $P(1)$ as true and $\exists y Q(1,y)$ as False which satisfies the given condition but we can make $P(2)$ as true and $\exists y Q(2,y)$ as True and in this way, whole statement becomes true.

Hence, $(D)$ is wrong.

$\textbf{Therefore, (B),(C)}$

Answer 2

Detailed Video Explanation:

GATE CSE 2023 - First Order Logic question, Geetha Conjecture P(x), Q(x,y)

Answer 3

I don't know if this approach is right. But I post this to give a idea so that someone can enhance this with formal procedure if this approach seems right.

First let us get rid of quantifiers (blindly applying universal instantiation and existential instantiation) and reduce the well formed formula (wff) to propositional logic.

NOTE:

Since $P$ is free from variable $y$ the following holds

$\forall x(P(x) \rightarrow \exists y Q(x, y)) \Leftrightarrow \forall x\:\exists y (P(x) \rightarrow Q(x, y))$ 

 

OPTION A:

$\left (P\wedge Q \right ) \implies \left ( P\rightarrow Q \right )$

This is a Tautology. But $\exists x \: \forall y \Rightarrow \forall x \: \exists y$ is not a valid implication.

So as a whole $\exists x(P(x) \wedge \forall y Q(x, y))\implies \forall x(P(x) \rightarrow \exists y Q(x, y))$ is not a valid implication.

OPTION B:

$ Q \implies \left ( P\rightarrow Q \right )$

This is a Tautology. Here $\forall x \: \forall y \Rightarrow \forall x \: \exists y$ is also a valid implication.

So as a whole $\forall x \forall y \: Q(x, y))\implies \forall x(P(x) \rightarrow \exists y Q(x, y))$ is a valid implication.

OPTION C:

$\left ( P\rightarrow Q \right ) \implies \left ( P\rightarrow Q \right )$

This is a Tautology. Here $\exists y \: \forall x \Rightarrow \forall x \: \exists y$ is also a valid implication.

So as a whole $\exists y \forall x(P(x) \rightarrow Q(x, y))\implies \forall x(P(x) \rightarrow \exists y Q(x, y))$ is a valid implication.

OPTION D:

$\left (P\wedge Q \right ) \implies \left ( P\rightarrow Q \right )$

This is a Tautology. Here $\exists x \: \exists y \Rightarrow \forall x \: \exists y$ is not a valid implication.

So as a whole $\exists x(P(x) \wedge \exists y Q(x, y))\implies \forall x(P(x) \rightarrow \exists y Q(x, y))$ is not a valid implication.

SOME VALID IMPLICATIONS

Comments

@Deepak Poonia Is this the correct way to do this question?

---

I don't know. I leave this as an open question. Let someone analyze this and say if this approach is right or wrong. I accept either. According to me we can use this for solving real time exams. Because some implications in first order logic are always valid.

Answer 4

Detailed Video Solution:  First Order Logic question, P(x) --> Q(x,y)

$\color{\red}{\text{ALL Discrete Mathematics Questions:}}$

Question 1:  Permutation question, Separating Permutations of A,B

Question 2: Greedy Graph Coloring Algorithm

Question 3: Group Theory Question

Question 4: Equivalence Classes, Surjective Function Question