Let \(𝑃(𝑥)\) be an arbitrary predicate over the domain of natural numbers.…

Correct statement: (P(0) ∧ (∀x [P(x) ⇒ P(x + 1)])) ⇒ (∀x P(x))

Reason (proof sketch):

• Base case: P(0) is given.

• Induction step: for an arbitrary k, if P(k) holds then by the given implication P(k+1) holds.

• Conclusion: starting from P(0) and applying the induction step repeatedly yields P(1), P(2), P(3), …, so P(n) holds for every natural number n.

Why the other three formulas are false (brief explanations and counterexamples):

• Statement with base P(0) and the step P(x) ⇒ P(x−1): The implication transfers truth downward, so knowing P(0) does not give P(1). Counterexample: take P(n) that is true only at n = 0; then the premises can hold while P(1) is false, so ∀x P(x) fails.

• Statement with base P(1000) and the step P(x) ⇒ P(x−1): From P(1000) you can deduce P(999), P(998), …, P(0), but you cannot deduce P(1001) or any larger n. Counterexample: let P(n) be true exactly for n ≤ 1000; premises hold but P(1001) is false.

• Statement with base P(1000) and the step P(x) ⇒ P(x+1): From P(1000) you can deduce P(1001), P(1002), …, but you cannot deduce P(0),…,P(999). Counterexample: let P(n) be true exactly for n ≥ 1000; premises hold but P(0) is false.

Summary: only the standard induction schema with base at 0 and step P(x)⇒P(x+1) guarantees P(n) for all natural numbers n.