GATE Overflow Test Series | Mixed Subjects | Test 1 | Question: 13

Question

Which of the following statements is VALID?

• A. $\neg \forall x\exists y[(x\leq y)\rightarrow(x+y)<0]\Longleftrightarrow \exists x\forall y[(x>y)\wedge(x+y)\leq 0]$
• B. $\forall x\exists y[(x\leq y)\rightarrow(x+y)<0]\Longleftrightarrow \exists x\forall y[(x>y)\vee(x+y)\leq 0]$
• C. $\neg \forall x\exists y[(x\geq y)\rightarrow(x+y)>0]\Longleftrightarrow \exists x\forall y[(x>y)\wedge(x+y)\leq 0]$
• D. $\neg \exists x \forall y[(x<y)\rightarrow\forall z(x<z<y)]\Longleftrightarrow \forall x \exists y  \exists z [(z\leq x<y)\vee (x<y\leq z)]$ 

Answer 1

Option A:

Consider the set of Integers.

RHS of A is always FALSE as when $x > y$ and $x + y \leq 0, y $must be negative. Now consider the largest element in the set - let it be $p.$ Now, RHS of option A says that there exists $x > p$ which is not possible for the set of integers (possible if we consider the set of real numbers).

LHS of A is true for the set of integers. This is because if we take $x = 1,$ LHS returns TRUE as for no $y \geq x, (x+y) < 0.$  Since, we have LHS TRUE and RHS FALSE, option A is not valid.

Option B:

Consider the set of positive integers.

RHS is then always TRUE as the first term of the OR clause is TRUE $(\exists x\forall y[(x>y))$ as for every positive integer we have another positive integer greater than it. Now, the LHS is FALSE as if we take any two positive integers $x,y$ we'll never get $x + y < 0.$ So, the biconditional statement is FALSE.

Option C:
Similar to option A, if we consider the set of integers, RHS is FALSE. LHS becomes TRUE as if we take $x = -1$ there is no $y \leq x$ such that $x + y > 0.$ So, the biconditional statement is FALSE.

Option D:

$\neg \exists x \forall y[(x<y)\rightarrow\forall z(x<z<y)]$

$\Longleftrightarrow \forall x \neg\forall y[(x<y)\rightarrow\forall z(x<z<y)]$

$\Longleftrightarrow \forall x \exists y\neg [(x<y)\rightarrow\forall z(x<z<y)]$

$\Longleftrightarrow \forall x \exists y\neg [\neg (x<y)\vee \forall z(x<z<y)]$

$\Longleftrightarrow \forall x \exists y [(x<y)\wedge \neg \forall z(x<z<y)]$

$\Longleftrightarrow \forall x \exists y [(x<y)\wedge \exists z \neg(x<z<y)]$

$\Longleftrightarrow \forall x \exists y [(x<y)\wedge \exists z ((z\leq x)\vee (y\leq z))]$

$\Longleftrightarrow \forall x \exists y  \exists z [(x<y)\wedge ((z\leq x)\vee (y\leq z))]$

$\Longleftrightarrow \forall x \exists y  \exists z [((x<y)\wedge (z\leq x)) \vee ((x<y)\wedge (y\leq z))]$

$\Longleftrightarrow \forall x \exists y  \exists z [(z\leq x<y)\vee (x<y\leq z)]$

LHS $\Longleftrightarrow$ RHS

So, the correct answer is $(D)$.

Comments

@Deepak Poonia @gatecse Sir,

RHS is then always TRUE as the first term of the OR clause is TRUE $(∃x∀y (x>y))$ as for every positive integer we have another positive integer greater than it.

How is $(∃x∀y (x>y))$ always true? Doesn’t this mean there exists a $x$ which is greater than all $y$?

Shouldn’t $(∀y∃x[(x>y))$ be always true?