Loop invariants and total correctness
An invariant establishes correctness only with its proof obligations.
Key knowledge
A loop proof establishes an invariant initially, preserves it through each guarded iteration, and uses it with the false guard to derive the postcondition. Total correctness also requires termination, for example a nonnegative integer variant that strictly decreases.
Conditions and scope
- The precondition must imply initialization and the body must satisfy preservation.
- Preservation alone proves neither the required output nor termination.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Initialization, preservation, exit postcondition and well-founded decreasing variant; binary-search example.
2026-10-10 · Four proof obligations; no certification of an unexamined program.
Entry details
Permanent link to this entry ↗- Record identity
- info-loop-invariants
- Revision
- university-reference.1
- Structured reference record
- University reference