provable

Provable is an adjective describing statements for which a formal proof exists within a specified deductive system. In mathematics and formal logic, a statement is provable if there is a finite sequence of applications of the system’s axioms and inference rules that derives the statement as a consequence. A statement that is provable from the standard axioms of a theory is called a theorem of that theory; unprovable statements may be undecidable or independent of the theory.

Proofs operate within a formal framework, such as propositional calculus, first-order logic, or more powerful systems like Zermelo–Fraenkel set theory with the axiom of choice (ZFC) or arithmetic (PA). In these systems, truth is relative to the axioms; a statement can be true in all intended interpretations yet be unprovable within the system if it lies beyond its expressive strength, as highlighted by Gödel’s incompleteness theorems. Provability is not the same as truth in a model. Soundness guarantees that every provable statement is true in the interpretation of the theory; completeness would guarantee that every true statement is provable, which fails for sufficiently strong systems.

In practice, the notion of provability is studied in provability logic, which treats proofs as modal operators. Advances in computer science have led to proof assistants (such as Coq and Lean) that enable machine-checked proofs, contributing to formal verification efforts. In cryptography, “provable security” denotes security claims proven within a formal computational model, typically via reductions to hard problems.