Formal Theorem Proving

A formal theorem-proving system verifies a proof by translating mathematical statements and reasoning steps into a formal language that a computer can process. It accepts a theorem only when every step follows from declared axioms, definitions or previously proved results through permitted rules of inference.

Representing the theorem formally

The user first specifies the objects, assumptions and desired conclusion using a formal logic, such as propositional, first-order or higher-order logic. Definitions and earlier theorems are drawn from a formal library, while syntax and typing rules ensure that expressions are well formed.

• Formalisation removes reliance on unstated assumptions and ambiguous natural-language reasoning.
• The conclusion is verified relative to the selected axioms and logical system, not independently of them.

Constructing and checking the proof

An automated theorem prover searches for a derivation, whereas a proof assistant usually combines human guidance with automation. The resulting proof is represented as a sequence of justified steps or as a proof object.

• A small proof-checking kernel checks each inference against the logic's rules and verifies references to definitions and earlier results.
• If any step is ill typed, unsupported or applies a rule incorrectly, the proof is rejected.
• Proof checking is mechanical, but discovering a proof may require extensive search and may not terminate in sufficiently expressive systems.

What acceptance establishes

If the underlying calculus is sound, a kernel-accepted conclusion follows logically from its recorded premises. This provides stronger assurance than testing examples because the argument covers all cases represented by the specification.

• The guarantee still depends on the correctness of the formal specification, chosen axioms, libraries and trusted kernel.
• A formally verified proof can establish the wrong intended claim if the real problem was translated incorrectly.
• By Gödel's incompleteness theorems, sufficiently expressive consistent formal systems cannot prove every mathematical truth expressible within them.

How UPSC asks this