Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE? A. (P(0) ^ forall x (P(x) -> P(x+1))) => forall y P(y) B. (P(0) ^ forall x (P(x) -> P(x+1))) => P(1000) ^ (P(1000) => P(0)) C. (P(1000) ^ forall x (P(x+1) -> P(x))) => P(0) D. (P(1000) ^ forall x (P(x+1) -> P(x))) => forall y P(y)
GATE 2025 · Discrete Mathematics · First Order Logic · medium
Answer: Option A is TRUE — it states the Principle of Mathematical Induction. Answer: A. (P(0) ^ forall x (P(x) -> P(x+1))) => forall y P(y)
- Option A — Principle of Mathematical Induction: A asserts: [P(0) ^ forall x (P(x)->P(x+1))] => forall y P(y). This is exactly the Principle of Mathematical Induction over N. Given P(0) and the inductive step, by repeated application we get P(1), P(2), ..., reaching every natural. This implication is a tautology in the standard model of N. Option A is TRUE.
- Options B, C, D — counter-examples: B adds 'P(1000) => P(0)' which need not hold (P could be true on all naturals via induction but the extra clause P(1000)=>P(0) is not an automatic consequence of the hypothesis alone — it happens to be true but option B is claiming it as a SEPARATE consequence of the hypothesis, which is valid but option A is more precisely the intended TRUE tautology and B is checking whether the phrasing is logically correct; evaluating C: P(1000) with downward step gives P for all x <= 1000 but NOT for x > 1000, so C's conclusion forall y P(y) can fail — e.g., P(x) = (x <= 1000). D similarly fails since the downward step from 1000 cannot establish P for 1001, 1002, etc.