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

Can you please give some explanation/reference to study this method?

---

COULD YOU EXPLAIN THIS METHOD A BIT MORE

---

B, C are the correct answers, i used arrow diagram for the function x -> y, is it a correct way to solve the problem? i feel this method is super easy

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)}$

Comments

Wow, thanks for the amazing explanation!!

---

Fallen in love with 2nd approach.

 

Answer 2

Detailed Video Explanation:

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

Comments

Great

---

I did the silly mistake of assuming the Getha's conjecture should imply the given options

Answer 3

Let’s assume for simplicity: 

• $x$ and $y$ are from a set of names of students
• $P(x)$ reads “$x$ is a girl”
• $Q(x,y)$ reads “$y$ likes $x$”

Then the given logic:

S: $\forall x\bigl(P(x)\implies\exists y(x,y)\bigr)$ reads as:

“For all students ($x$), if $x$ is girl then there exists at least one student ($y$), such that $y$ likes $x$”

 

Option A: $\exists x\bigl(P(x) \land \forall y Q(x,y)\bigr)$ reads as:

“There exists at least one student ($x$) such that $x$ is a girl and for all students ($y$) $y$ likes $x$”

This can be true if all students like just one girl but S reads that for every girl there is a student who likes her.

So A doesn’t imply S

 

Option B: $\forall x \forall y Q(x,y)$ reads as:

“For all students ($x$) there are all students ($y$) such that $y$ likes $x$”

Everybody likes everybody. This implies S because then $Q(x,y)$ becomes always true or RHS of S becomes always true

If you have trouble understanding then think like this, try to impose statement B on S and check whether S is still true.

B can be reframed as: For all students ($x$) irrespective of whether $x$ is a girl or not, all students ($y$) like $x$

So B implies S

 

Option C: $\exists y \forall x \bigl( P(x) \implies Q (x,y) \bigr)$ reads as:

“There exists at least one student ($y$) for all students ($x$) such that if $x$ is a girl then $y$ likes $x$” 

For all students ($x$) if $x$ is a girl then there exists at least one student ($y$) who likes all girls

So C implies S

 

Option D: $\exists x\bigl(P(x) \land \exists y Q(x,y)\bigr)$ reads as:

“There exists at least one student ($x$) such that $x$ is a girl and there exists at least one student ($y$) such that $y$ likes $x$”

This can be true if for only one girl there is a student who likes her but S reads for all girls there is a student who likes them.

So D doesn’t imply S

Comments

lovely analogy

---

Quickest way to solve this question.

Answer 4

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.

---

killer explanation..

Answer 5

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

Answer 6

https://www.youtube.com/live/ezgLUjkNvec?t=189s