Project ForgeDiscrete Mathematics
Predicate Logic
GATE 2025
Medium
Let P(x) be an arbitrary predicate over the domain of natural numbers. Which ONE of the following statements is TRUE?
- (P(0) ∧ (∀x [P(x) ⇒ P(x+1)])) ⇒ (∀x P(x))
- B(P(0) ∧ (∀x [P(x) ⇒ P(x−1)])) ⇒ (∀x P(x))
- C(P(1000) ∧ (∀x [P(x) ⇒ P(x−1)])) ⇒ (∀x P(x))
- D(P(1000) ∧ (∀x [P(x) ⇒ P(x+1)])) ⇒ (∀x P(x))
Explanation
Option A is exactly the principle of mathematical induction over the naturals: a base case at the domain's actual minimum (0) plus a forward inductive step proves the property for ALL naturals. C and D instead anchor the base case at 1000, so even a valid forward or backward step only proves P for x≥1000 or x≤1000 respectively — never for ALL naturals. B anchors correctly at 0 but steps backward, which doesn't build upward from the base case at all.
Source: GATE CS 2025 (Session 2 / CS2) (2025)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.