Theorem 4.9 — Soundness of modified realizability
OpenABHS2004V2.theorem_4_9Given a derivation and fresh assumption-realizer names, the arithmetic proves that its extracted term realizes the conclusion, under the realizability translations of its proof assumptions.
import Definitions.Def_ABHS2004V2_Realizability
namespace ABHS2004V2
/-- Theorem 4.9. A derivation proves that its extracted term realizes the
conclusion, under the translated realizability assumptions. -/
theorem theorem_4_9 {Δ Γ : ProofContext} {M : ProofTerm} {A : Formula}
(hd : Derives Δ Γ M A)
(hfresh : FreshRealizerVars Δ Γ M A) :
Provable (mrContext (Δ ++ Γ)) [] (mr (extractProof M) A) := 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. Then there exists a proof term deriving , with empty second context and first context obtained as follows. Concatenate and in that order, then replace each entry by . This map retains the identifier and position of every entry. If and are empty the resulting proof has two empty contexts.
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 .
Here sends typed existence atoms to and other atoms to the unit type . It translates implication, tensor, additive conjunction, and disjunction into function, tensor, product, and sum types respectively, and takes the body's type at either quantifier. The symbols in the formula translation are constructors of arithmetic formulas.
The formula leaves ordinary predicate atoms as they are and replaces by the equality atom . For either quantifier , it gives if is absent from the free variables of . Otherwise it first renames the binder and its free occurrences in the body to the same type at identifier . Maximum identifiers include binder identifiers and use zero when there are none. For let and , and let . The implication case is with . For a tensor it is , using tensor elimination on with selectors and of types and , with identifiers for . For additive conjunction it is . For disjunction it is
with and .
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.