Theorem 4.7 — Typing soundness of program extraction
OpenABHS2004V2.theorem_4_7With the paper’s convention for fresh assumption names, extraction gives a weakly typed term of the realizer type whose free variables come from the two proof contexts. The cleaned term is affinely typed at the cleaned realizer type and uses only realizers from the active context.
import Definitions.Def_ABHS2004V2_Realizability
namespace ABHS2004V2
/-- Theorem 4.7. The extracted term is weakly typed and refers only to realizers
of the proof assumptions. The cleaned extracted term is affinely typed and its
free variables come from the active context. -/
theorem theorem_4_7 {Δ Γ : ProofContext} {M : ProofTerm} {A : Formula}
(hd : Derives Δ Γ M A)
(hfresh : FreshRealizerVars Δ Γ M A) :
WeaklyTyped (extractProof M) (tau A) ∧
(∀ v ∈ freeVarOccurrences (extractProof M),
v ∈ extractCtx Δ ∨ v ∈ extractCtx Γ) ∧
HasType (extractCleaned M) (tauClean A) ∧
(∀ v ∈ freeVarOccurrences (extractCleaned M),
v ∈ extractCleanCtx Γ) := by sorry
end ABHS2004V2Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
For every pair of assumption contexts , proof term and formula , assume derives in and satisfies the freshness condition for below. Four conditions follow. First, the raw extraction has weak type . Second, every free variable occurrence of belongs to the list obtained by mapping over or to that obtained by mapping over . Third, the cleaned extraction has type by the typing rules that require disjoint free variables at application and a closed step at iteration. Fourth, every free variable occurrence of belongs to the list obtained from alone by keeping entries with and mapping over the retained entries. The membership conclusions hold even if either list of free variable occurrences is empty.
For an assumption entry , write for its typed realizer variable. The freshness hypothesis for a conclusion uses the concatenation of the two context lists with all assumption occurrence and assumption-abstraction binder entries in . Any two entries of that list having the same numerical identifier must be the same entry. For each in the list, is absent from the free term variables of and of every formula in the two contexts. Free term variables use the types as part of variable identity, come from the arguments of atoms, are pooled across binary formulas, and omit the quantified variable in a quantifier. Repeated copies of the same assumption entry satisfy the identifier agreement test.
The raw extracted term is computed on proof syntax. An assumption extracts the variable . An axiom instance extracts its prescribed term, with primitive introduction or elimination constants for the corresponding connective axioms and a recursively specified dummy at of the axiom formula for the default cases. An assumption abstraction extracts a lambda over , and a proof application extracts a term application. Term-variable abstractions and applications keep only the extraction of the proof child. An induction with list-existence proof and step proof extracts .
The associated type sends to , other predicate atoms to , implication to a function arrow, tensor to tensor, additive conjunction to product, and disjunction to sum. It takes the type of the body at either quantifier. The type cleaning fixes and maps recursively through lists and sums. In a tensor or product of cleaned factors it drops a unit factor, giving when both are unit. For a function type, a cleaned codomain of gives , otherwise a cleaned domain of gives the cleaned codomain, and otherwise it keeps the arrow between the cleaned types.
The cleaned extraction cleans using type inference with the weak typing rules. At a term where inference fails it returns the original term. An inferred type that cleans to gives . Otherwise it cleans variables by , cleans constants with the rules for their cleaned types, drops abstraction binders and application arguments whose types clean to , and cleans both iterator operands. If the iterator's element type cleans to , its cleaned step is wrapped as for fresh whose identifiers are one and two above the largest identifier in . The pairing is if , and otherwise. The type code pairs a tag with for , with the element code for a list, and with the pair of operand codes for binary types. The respective tags for , list, function, tensor, product and sum are .
In both typing judgments, variables and constants have their recorded types, abstractions form function types, applications require matching input types, and the iterator takes operands of types and to give type . The weak judgment has exactly these rules without the application disjointness and iterator closure premises of the full judgment.
A context lists pairs of a natural-number assumption identifier and a formula. Derivations are generated by valid core axioms, active assumptions, implication and universal rules, passification for unit-cleaned conclusions, contraction, and list induction. A context union checks disjoint identifiers across the inputs, equality of list entries with equal identifiers in the output, and membership of exactly the entries found in the inputs. Provability is the existence of a derivation proof term.