Let \(P(x)\) be an arbitrary predicate over the domain of natural numbers.
Which ONE of the following statements is TRUE?
GATE CS - 2025,
Answer: A
The true statement is \((P(0) \wedge (\forall x[P(x) \Rightarrow P(x+1)])) \Rightarrow (\forall x P(x))\).
This is the principle of mathematical induction over the natural numbers starting at 0: if P holds at 0, and truth at x always carries to x + 1, then P holds at 0, 1, 2, ... and so at every natural number.
The others can fail for some predicate. Starting from P(0) and stepping downwards (x to x - 1) reaches nothing above 0. Starting from P(1000) and stepping downwards covers only 0 to 1000; starting from P(1000) and stepping upwards covers only 1000 onwards. The predicate 'x = 0' makes the second statement false (its premises hold, since P(x) is false for every x above 0), 'x ≤ 1000' makes the third false, and 'x ≥ 1000' the fourth.
Please log in or register to report this question.