Proof Decomposition¶

Why It Matters¶

Monolithic verification scales poorly - a system with N components has potentially 2^N interactions. Decomposition achieves modularity: prove each component correct in isolation, then prove the composition preserves correctness. This is both more tractable and more maintainable - changes require re-proving only affected components.

The Key Move¶

To prove a large system correct, decompose it into modules with explicit interfaces. For each module, prove: (1) given its preconditions, it satisfies its postconditions (local correctness), and (2) its assumptions about other modules are met (interface compatibility). Then prove that correct modules composed via correct interfaces yield a correct system (composition theorem).

Classic Application¶

Modular verification. To verify a large software system, decompose into functions/classes/modules. Verify each module against its specification. Then verify that the composition - how modules call each other - preserves the specifications. This scales to million-line systems where monolithic verification would be impossible.

Surprising Application¶

Life planning verification. To verify your life plan is coherent, decompose into domains: career, relationships, health, growth, impact. For each, specify goals and verify they're achievable (local correctness). Then verify composition: do career goals conflict with relationship goals? Does health support other domains? Inconsistencies reveal planning failures.

Failure Modes¶

False decomposition - modules aren't actually independent; interactions matter. Interface mismatch - modules satisfy their specs but composition fails. Circular dependencies - module A's correctness depends on B, whose correctness depends on A. Composition overhead - the composition proof is harder than the original monolithic proof.

Go Deeper¶

Misra & Chandy, "Proofs of Networks of Processes" (1981); Abadi & Lamport, "Conjoining Specifications" (1995)