GATE CS 2025 Set 2 Q5 — Propositional and First Order Logic

The given statement in Option A is the formal representation of the Principle of Mathematical Induction (PMI) over the domain of natural numbers $\mathbb{N} = \{0, 1, 2, \dots\}$:

• Base Case: $P(0)$ is true.
• Inductive Step: For any natural number $x$, if $P(x)$ is true, then $P(x+1)$ is also true.

By the principle of induction, these two conditions guarantee that $P(x)$ holds for all natural numbers $x$. Hence, the implication is always TRUE.

Why other options are FALSE:

• Option B: $\big( P(0) \wedge \forall x [P(x) \Rightarrow P(x-1)] \big) \Rightarrow \forall x P(x)$
  Counterexample: Define $P(x)$ such that $P(0) = \text{True}$ and $P(x) = \text{False}$ for all $x \ge 1$. The antecedent is true because $P(0)$ holds, and for any $x \ge 1$, $P(x) \Rightarrow P(x-1)$ simplifies to $\text{False} \Rightarrow P(x-1)$, which is vacuously true. However, the consequent $\forall x P(x)$ is false.
• Option C: $\big( P(1000) \wedge \forall x [P(x) \Rightarrow P(x-1)] \big) \Rightarrow \forall x P(x)$
  Counterexample: Define $P(x)$ to be true for all $x \le 1000$ and false for all $x > 1000$. The antecedent holds, but the consequent $\forall x P(x)$ is false because $P(1001)$ is false.
• Option D: $\big( P(1000) \wedge \forall x [P(x) \Rightarrow P(x+1)] \big) \Rightarrow \forall x P(x)$
  Counterexample: Define $P(x)$ to be true for all $x \ge 1000$ and false for all $x < 1000$. The antecedent holds, but the consequent $\forall x P(x)$ is false because $P(0)$ is false.