Semantic Completeness for Correct Maintenance: A Strict Hierarchy of Typing and Inheritance

Abstract

Correct maintenance preserves required answers, excludes invalid states, and minimizes lifetime semantic edits. Banning semantic completeness makes it impossible. We prove necessary conditions for this optimum: a strict hierarchy with exact minima for identity names, contract memberships, and implementation-class pairs left to code or tooling. When meanings look alike but need different answers, graph coloring gives the fewest stable key values. Contract parents supply membership, not code: one suffices exactly for tree-shaped member groups; multiple parents derive any finite membership map. For distinct, independently changing providers, no unwanted inheritance, and one ancestry chain per class, the ancestry gap d_↓ counts the fewest required provider-class pairs any correct preserving repair leaves outside inheritance. It is zero exactly when provider groups fit a tree. Reparenting, infinite helpers, replication, arbitrary delegation, and generators cannot lower this minimum. Multiple parents derive every finite relation with no outside pairs. Batching can cut edits, not forced answers; prices do not change their minimum. In a constructed history, every snapshot fits a tree, yet each update forces a parent change or forwarding or blocking before or after it. Keeping the original one-parent map leaves exactly n(n + 1)/2 required connections outside ancestry after n updates. No algorithm recognizes all and only permanently tree-shaped generated streams. 18 of 20 pinned, preselected Python source-class maps have positive gaps. A SQLAlchemy component has gap 520 and no lookup conflict after excluding order-sensitive lookups. Its checked repair needs exactly 59 shared bundles. Lean 4 checks all numbered formal results, halting reductions, and certified lower bounds; independent replay checks attaining repairs. Complexity-class naming and source extraction remain external.