GATE CS 2025 Set 2 | Question 15

MCQ · 1 mark · −0.33

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

Which ONE of the following statements is TRUE?

  1. Option A: \(\big(P(0) \land (\forall x\, [P(x) \Rightarrow P(x + 1)])\big) \Rightarrow \big(\forall x\, P(x)\big)\) (correct)
  2. Option B: \(\big(P(0) \land (\forall x\, [P(x) \Rightarrow P(x - 1)])\big) \Rightarrow \big(\forall x\, P(x)\big)\)
  3. Option C: \(\big(P(1000) \land (\forall x\, [P(x) \Rightarrow P(x - 1)])\big) \Rightarrow \big(\forall x\, P(x)\big)\)
  4. Option D: \(\big(P(1000) \land (\forall x\, [P(x) \Rightarrow P(x + 1)])\big) \Rightarrow \big(\forall x\, P(x)\big)\)

Answer

(A)

Explanation

Option A is the principle of mathematical induction: \(P(0)\) holds, and truth passes from each \(x\) to \(x + 1\), so it reaches 1, 2, 3, … and hence every natural number. It is true for every predicate \(P\).

Each other option fails for some predicate:

  • B: take \(P(x)\) to be “\(x \le 5\)”. Both premises hold, but \(P(6)\) is false.
  • C: take “\(x \le 1000\)”. Both premises hold, but \(P(1001)\) is false.
  • D: take “\(x \ge 1000\)”. Both premises hold, but \(P(0)\) is false.

Answer: A