Proof of correctness¶
A mathematical demonstration that an algorithm satisfies a formal specification, separating partial correctness from the additional obligation to prove termination for total correctness.
Core Idea¶
A proof of correctness mathematically shows that an algorithm satisfies a formal specification for all admissible inputs. Partial correctness guarantees valid results when execution returns; total correctness additionally proves termination, usually through a well-founded progress argument. Partial correctness proves that if execution terminates, the returned result satisfies the postcondition. Partial correctness proves that if execution terminates, the returned result satisfies the postcondition.
Scope of Application¶
The method applies to formally specified algorithms and programs whose semantics support deductive, automated, or mechanically checked reasoning. Use it for formally modeled algorithms and implementations, with specification, semantics, proof obligations, termination status, and trusted assurance boundary explicit.
- Algorithm design. Proves input–output properties and termination.
- Hoare logic. Uses assertions and triples over imperative programs.
- Proof assistants. Mechanically check formal arguments.
- Compiler verification. Relates source and target semantics.
- Safety-critical software. Establishes selected properties beyond testing.
Clarity¶
Correctness proof separates four questions: what is required, what the algorithm means, whether results satisfy the requirement, and whether computation ends. It also exposes the assurance boundary between algorithm, implementation, platform, and specification. The closest near miss sets the boundary: Model checking is the closest near miss: it can provide formal proofs for finite-state models, but the technique and scope differ from a general deductive algorithm proof.
Manages Complexity¶
A program has many paths and states. Invariants and compositional proof rules summarize whole families of executions, replacing exhaustive enumeration with a finite chain of obligations whose assumptions and conclusions can be checked. The central mathematical completeness–trusted implementation stack tradeoff is this: An algorithm proof may leave compilers, hardware, and resources outside its model. A second strong specification–proof cost tension matters because Richer properties improve assurance while multiplying formalization and proof obligations.
Abstract Reasoning¶
Use three linked moves: formalize admissible inputs, required outputs, and operational or denotational semantics; decompose the algorithm into proof obligations using invariants and contracts; prove initialization, preservation, and postcondition consequences for every path. As a collapse test, the case exits when specification or semantics is informal, a path or input class is omitted, or total correctness is claimed without termination. A fourth check is to for total correctness, provide a well-founded decreasing measure or equivalent termination proof. A final check is to audit the trusted base and confirm that the specification expresses the intended requirement.
Knowledge Transfer¶
Proof methods transfer literally across algorithms when semantics and specifications are restated. A proof about an abstract routine does not automatically transfer to a compiled binary or resource-bounded environment; refinement links must be proved separately. No canonical parent prime is currently asserted; broader structural comparisons remain related-prime analogies until separately adjudicated in the DAG. A preserved property bridges local program steps to a global postcondition. Termination follows from progress in an order with no infinite descent.
Relationships to Other Abstractions¶
Current abstraction Proof of correctness Domain-specific
Parents (1) — more general patterns this builds on
-
Proof of correctness is a kind of Argument Prime
Proof of correctness is a domain-specific kind of argument under the frozen identity and differentia.
Hierarchy path (1) — routes to 1 parentless root
- Proof of correctness → Argument → Inference → Rationality → Normativity → Constraint
Neighborhood in Abstraction Space¶
Proof of correctness sits in a moderately populated region (40th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Formal Models & Logical Foundations (33 abstractions)
Nearest neighbors
- Modus ponens — 0.88
- Guard (computer science) — 0.87
- Second-Order Predicate — 0.87
- 3SUM — 0.87
- Proof calculus — 0.87
Computed from structural-signature embeddings · 2026-10-08