Corollary 4.11 — Polynomial program extraction for data specifications
OpenABHS2004V2.corollary_4_11An almost closed derivation of a relativized existence specification yields a program on canonical cleaned representations of data. Its reduction takes polynomially many steps in the original input syntax length. Its output represents a source data object meeting the specification, with output resource size and free-variable count at most the input totals plus a fixed constant.
import Definitions.Def_ABHS2004V2_Realizability
namespace ABHS2004V2
/-- Corollary 4.11. Extraction from an almost-closed derivation of a relativized
specification gives a program on the cleaned representations of data objects.
The program normalizes in polynomially many steps and yields a representation
of an output satisfying the original specification and the additive resource bound. -/
theorem corollary_4_11 {Δ Γ : ProofContext} {M : ProofTerm}
{xs : List Var} {y : Var} {A : Formula}
(hdata_xs : ∀ x ∈ xs, IsDataType x.ty)
(hdata_y : IsDataType y.ty)
(hnodup : (xs ++ [y]).Nodup)
(hA : IsExistAndDisjFree A)
(hac : IsAlmostClosedDerivation M)
(hd : Derives Δ Γ M
(Formula.allRel xs (.ex y (.tensor (.existPred y.ty (.var y)) A))))
(hfresh : FreshRealizerVars Δ Γ M
(Formula.allRel xs (.ex y (.tensor (.existPred y.ty (.var y)) A)))) :
∃ (B : Nat → Nat) (k : Nat),
BoundedByPolyOfDegree B (Nat.max (iterNesting (extractCleaned M)) 1) ∧
∀ ws : List Term,
ValidDataInputs (extractProof M) (xs.map Var.ty) ws →
∃ (cleanInputs : List Term) (steps : Nat) (w cleanOutput : Term),
CleansDataInputs (xs.map Var.ty) ws cleanInputs ∧
RedSteps steps
(if cleanTy y.ty == .unit then extractCleaned M
else Term.appMany (extractCleaned M) cleanInputs)
cleanOutput ∧
IsDataObject y.ty w ∧
IsDataObject (cleanTy y.ty) cleanOutput ∧
CleansData y.ty w cleanOutput ∧
steps ≤ B (totalTermLength ws) ∧
dataSize w ≤ totalDataSize ws + k ∧
freeVarCount w ≤ totalFreeVarCount ws + k ∧
Provable (mrContext (Δ ++ Γ)) []
(substFormulaMany A (xs.zip ws ++ [(y, w)])) := by sorry
end ABHS2004V2Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
Let be assumption contexts, a proof term, a list of typed variables, a typed variable, and a formula. Assume each and has a data type, and has no repeated pair of identifier and type. Assume is built from ordinary atoms by implication, tensor, additive conjunction, and either quantifier, including existential quantifiers. Assume every free variable of the cleaned extracted term has type . Set and for , with the typed existence atom. Assume derives in and satisfies the freshness condition below for .
There exist and with for all and some . For every term list valid for the raw extraction and the type list , written , there exist a list of terms, a natural number and terms with these properties.
- is obtained by relating each to a cleaned term at and discarding terms whose type parameter cleans to .
- Exactly ordinary steps lead to from if , and from the left-associated application of to otherwise. The terms are data objects at and respectively, and are related by data cleaning at .
- , , and .
- There is a proof term deriving with simultaneous assignments . Its first context is the concatenation of with each entry replaced by . Its second context is empty.
Data types are generated from by lists, tensors and sums. A data object has its indicated type by the rules that require disjoint free variables at application and closed steps at iteration. It has only -typed free variables and no ordinary reduct. A step is a root conversion or its placement through application and iterator children. The conversions are beta, tensor elimination on introduction, product projections on introduction, sum elimination on injections, and nil and cons iteration on a seed. Cons iteration requires a cons/nil-shaped tail. Zero steps give the start term. Valid inputs have exactly the indicated types and are data objects whose free variables are disjoint from those of the preceding application at each . The empty type list permits just the empty list, with empty and all three sums zero.
The length counts leaves and abstractions, counts cons constant occurrences including bare constants, and counts free variable occurrences with repetitions. The depth is zero on leaves, passes through abstractions, takes the maximum at applications, and is on . A simultaneous assignment takes the first matching replacement at each variable. Under quantifiers and abstractions it drops assignments to the binder, renaming the binder if free in any retained replacement to the same type with identifier one above the maximum in the old binder, body, and retained keys and values.
The realizing variable of is . Freshness means that numerical identifiers determine the entry on the concatenation of and all assumption occurrences and assumption-abstraction binders in , allowing identical repeats. Each from that list must be absent from the free variables of and of all assumption formulas in . Derivability here is the relation generated by the arithmetic core axioms, assumption and implication and universal rules, passification for unit-cleaned conclusions, contraction and list induction. The raw extraction uses for an assumption, the prescribed term for an axiom, lambda and application for assumption abstraction and proof application, the same extracted proof child for term abstraction and application, and iteration for list induction.
The type sends atoms to , other atoms to , the four binary formula constructors to function, tensor, product and sum, and quantifiers to the body's type. Type cleaning fixes , recurses through lists and sums, and drops unit factors of tensors and products. An arrow cleans to if its codomain does, to its cleaned codomain if just its domain cleans to , and to the arrow of cleaned types otherwise. The cleaning of uses weak type inference, leaving a term alone on inference failure and giving at an inferred type cleaning to . Otherwise it cleans constants and variables, removes unit-cleaned binders and arguments, and cleans iterator operands. An iterator element type cleaning to makes its cleaned step become with fresh of identifiers one and two above the maximum in .
The variable cleaning is , with when , and otherwise. The type code pairs a tag with for the two base types, with the child's code for a list, or with the pair of child codes for a binary type. The tags are for unit, diamond, list, function, tensor, product, sum. Data cleaning relates to itself, retains the injection of a sum while relating its payload and cleaning type tags, and changes nil's tag to the cleaned element type. It relates to for a variable and related elements and tails. At a tensor it relates both components and returns the cleaned left when the right type cleans to , the cleaned right when just the left type cleans to , and their retagged tensor introduction otherwise.
The formula replaces by and preserves ordinary atoms. In a quantifier with binder free in , it first renames the binder to a same-type identifier one above the maximum in the binder, , and the body. The quantifier otherwise keeps its binder, and either case translates its body with term . At an implication the result is . At tensor and additive conjunction it is additive conjunction of the respective translations using the two tensor selectors or product projections of . The tensor selectors are tensor elimination with and , with typed variables of identifiers . At the result is additive conjunction of and , with . The variable has type and identifier one above the maximum in in both the implication and disjunction clauses, and has type and the next identifier. These maxima include bound identifiers and default to zero.