The GATE Grind

GATE 2025 CS (CS2) – Question 15

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 1 mark · Multiple choice

Let $P(x)$ be an arbitrary predicate over the domain of natural numbers.

Which ONE of the following statements is TRUE?

  1. $(P(0) \wedge (\forall x\,[P(x) \Rightarrow P(x+1)])) \Rightarrow (\forall x\,P(x))$
  2. $(P(0) \wedge (\forall x\,[P(x) \Rightarrow P(x-1)])) \Rightarrow (\forall x\,P(x))$
  3. $(P(1000) \wedge (\forall x\,[P(x) \Rightarrow P(x-1)])) \Rightarrow (\forall x\,P(x))$
  4. $(P(1000) \wedge (\forall x\,[P(x) \Rightarrow P(x+1)])) \Rightarrow (\forall x\,P(x))$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $(P(0) \wedge (\forall x\,[P(x) \Rightarrow P(x+1)])) \Rightarrow (\forall x\,P(x))$

Explanation

Option A is the principle of mathematical induction: a base case at 0 plus the step $P(x) \Rightarrow P(x+1)$ covers all naturals. The others fail to cover all naturals, for example D never covers values below 1000.