Skip to main content

logicaffeine_proof/
certifier.rs

1//! The Certifier: Converts DerivationTrees to Kernel Terms.
2//!
3//! This is the Great Bridge between the Proof Engine and the Kernel.
4//! Via Curry-Howard, each proof rule maps to a term constructor:
5//!
6//! | DerivationTree Rule     | Kernel Term                           |
7//! |-------------------------|---------------------------------------|
8//! | Axiom / PremiseMatch    | Term::Global(name)                    |
9//! | ModusPonens [impl, arg] | Term::App(certify(impl), certify(arg))|
10//! | ConjunctionIntro [p, q] | conj P Q p_proof q_proof              |
11
12use logicaffeine_kernel::{Context, KernelError, KernelResult, Term};
13
14use crate::{DerivationTree, InferenceRule, ProofExpr, ProofTerm};
15
16// =============================================================================
17// INDUCTION STATE - Tracks context during induction certification
18// =============================================================================
19
20/// State for tracking induction during certification.
21/// When certifying a recursive case, IH references become recursive calls.
22/// A single case may bind several recursive arguments (e.g. `Node(l, r)`), so it
23/// carries one (recursive-argument variable, IH conclusion) entry per hypothesis.
24struct InductionState {
25    /// Name for self-reference in the fixpoint (e.g., "rec_n")
26    fix_name: String,
27    /// One entry per recursive argument: the bound variable and the IH it proves.
28    /// A `PremiseMatch` whose conclusion matches an entry's IH resolves to
29    /// `rec_name <var>` — the recursive call on that argument.
30    ihs: Vec<(String, ProofExpr)>,
31}
32
33// =============================================================================
34// CERTIFICATION CONTEXT
35// =============================================================================
36
37/// Context for certifying derivation trees into kernel terms.
38///
39/// Wraps a kernel [`Context`] and tracks additional state
40/// needed during certification:
41///
42/// - **Local variables**: Variables bound by lambda abstractions during traversal
43/// - **Induction state**: For resolving IH (inductive hypothesis) references in step cases
44///
45/// # Lifetime
46///
47/// The `'a` lifetime ties this context to the kernel context it wraps.
48/// The certification context borrows the kernel context immutably.
49///
50/// # Example
51///
52/// ```
53/// use logicaffeine_proof::certifier::CertificationContext;
54/// use logicaffeine_kernel::Context;
55///
56/// let kernel_ctx = Context::new();
57/// let cert_ctx = CertificationContext::new(&kernel_ctx);
58/// ```
59///
60/// # See Also
61///
62/// * [`certify`] - The main function that uses this context
63/// * [`Context`] - The underlying kernel context
64pub struct CertificationContext<'a> {
65    kernel_ctx: &'a Context,
66    /// Local variables in scope (from lambda abstractions)
67    locals: Vec<String>,
68    /// Local *hypotheses* in scope, keyed by the proposition they prove and
69    /// paired with the kernel term that witnesses it. Introduced by reductio
70    /// (the assumed proposition), case analysis (the case formula / its negation
71    /// in each branch), and existential elimination (the witness body and its
72    /// projected conjuncts). A `PremiseMatch` whose conclusion matches one of
73    /// these resolves to its witness term rather than to a global axiom. The
74    /// witness is usually a bound variable (`Term::Var`), but for a projected
75    /// conjunct of an `And` hypothesis it is a `Match` that eliminates the
76    /// conjunction.
77    /// Each entry is shared behind `Arc` so extending the context at a binder copies
78    /// pointers, not whole (proposition, witness) pairs — building a large certified
79    /// proof extends this thousands of times.
80    local_hyps: Vec<std::sync::Arc<(ProofExpr, Term)>>,
81    /// Induction state for IH resolution (only set during step case)
82    induction_state: Option<InductionState>,
83}
84
85impl<'a> CertificationContext<'a> {
86    pub fn new(kernel_ctx: &'a Context) -> Self {
87        Self {
88            kernel_ctx,
89            locals: Vec::new(),
90            local_hyps: Vec::new(),
91            induction_state: None,
92        }
93    }
94
95    /// Create a new context with an additional local variable.
96    fn with_local(&self, name: &str) -> Self {
97        let mut new_locals = self.locals.clone();
98        new_locals.push(name.to_string());
99        Self {
100            kernel_ctx: self.kernel_ctx,
101            locals: new_locals,
102            local_hyps: self.local_hyps.clone(),
103            induction_state: self.induction_state.clone(),
104        }
105    }
106
107    /// Create a new context with an additional local hypothesis: a proof of
108    /// `prop` is available under the name `var`.
109    fn with_local_hyp(&self, prop: &ProofExpr, var: &str) -> Self {
110        self.with_local_hyp_term(prop, Term::Var(var.to_string()))
111    }
112
113    /// Create a new context with an additional local hypothesis: a proof of
114    /// `prop` is given by the kernel term `witness`. Unlike [`with_local_hyp`],
115    /// the witness need not be a bare variable — e.g. a projection that
116    /// eliminates an `And` to recover one conjunct.
117    fn with_local_hyp_term(&self, prop: &ProofExpr, witness: Term) -> Self {
118        let mut new_hyps = self.local_hyps.clone();
119        new_hyps.push(std::sync::Arc::new((prop.clone(), witness)));
120        Self {
121            kernel_ctx: self.kernel_ctx,
122            locals: self.locals.clone(),
123            local_hyps: new_hyps,
124            induction_state: self.induction_state.clone(),
125        }
126    }
127
128    /// A fresh hypothesis variable name, unique along the current branch.
129    fn fresh_hyp_name(&self) -> String {
130        format!("_hyp{}", self.local_hyps.len())
131    }
132
133    /// If `conclusion` is proved by a local hypothesis, return its witness term.
134    fn get_local_hyp(&self, conclusion: &ProofExpr) -> Option<Term> {
135        self.local_hyps
136            .iter()
137            .rev()
138            .find(|h| h.0 == *conclusion)
139            .map(|h| h.1.clone())
140    }
141
142    /// Create a new context with single-IH induction state (the Nat/List step case).
143    fn with_induction(&self, fix_name: &str, step_var: &str, ih: ProofExpr) -> Self {
144        self.with_induction_multi(fix_name, vec![(step_var.to_string(), ih)])
145    }
146
147    /// Create a new context whose induction hypotheses are `ihs` — one entry per
148    /// recursive argument of the constructor case being certified.
149    fn with_induction_multi(&self, fix_name: &str, ihs: Vec<(String, ProofExpr)>) -> Self {
150        Self {
151            kernel_ctx: self.kernel_ctx,
152            locals: self.locals.clone(),
153            local_hyps: self.local_hyps.clone(),
154            induction_state: Some(InductionState {
155                fix_name: fix_name.to_string(),
156                ihs,
157            }),
158        }
159    }
160
161    /// Check if a name is a local variable.
162    fn is_local(&self, name: &str) -> bool {
163        self.locals.iter().any(|n| n == name)
164    }
165
166    /// Check if this conclusion matches one of the IHs in the current induction
167    /// context. Returns the corresponding recursive call `rec <var>` if it matches.
168    fn get_ih_term(&self, conclusion: &ProofExpr) -> Option<Term> {
169        let state = self.induction_state.as_ref()?;
170        for (var, ih) in &state.ihs {
171            if conclusions_match(conclusion, ih) {
172                // IH becomes a recursive call on that argument: rec <var>
173                return Some(Term::App(
174                    Box::new(Term::Var(state.fix_name.clone())),
175                    Box::new(Term::Var(var.clone())),
176                ));
177            }
178        }
179        None
180    }
181}
182
183impl Clone for InductionState {
184    fn clone(&self) -> Self {
185        Self {
186            fix_name: self.fix_name.clone(),
187            ihs: self.ihs.clone(),
188        }
189    }
190}
191
192/// Check if two ProofExprs are structurally equivalent (for IH matching).
193/// Uses PartialEq derivation.
194fn conclusions_match(a: &ProofExpr, b: &ProofExpr) -> bool {
195    a == b
196}
197
198/// Certify a derivation tree, producing a kernel term.
199///
200/// Converts a proof (derivation tree) into a typed lambda calculus term
201/// via the Curry-Howard correspondence. The resulting term, when type-checked
202/// by the kernel, should have the type corresponding to the tree's conclusion.
203///
204/// # Arguments
205///
206/// * `tree` - The derivation tree to certify
207/// * `ctx` - The certification context (wraps kernel context)
208///
209/// # Returns
210///
211/// * `Ok(term)` - The kernel term representing this proof
212/// * `Err(_)` - If certification fails (missing hypothesis, wrong premises, etc.)
213///
214/// # Curry-Howard Mapping
215///
216/// | Inference Rule | Kernel Term |
217/// |----------------|-------------|
218/// | `Axiom` / `PremiseMatch` | `Term::Global(name)` (hypothesis lookup) |
219/// | `ModusPonens` | `Term::App(certify(impl), certify(arg))` |
220/// | `ConjunctionIntro` | `conj P Q p_proof q_proof` |
221/// | `UniversalInst(w)` | `Term::App(forall_proof, w)` |
222/// | `UniversalIntro { var, type }` | `Term::Lambda { param: var, ... }` |
223/// | `StructuralInduction` | `Term::Fix { name, body: λn. match n ... }` |
224/// | `Rewrite { from, to }` | `Eq_rec A from P proof to eq_proof` |
225/// | `ExistentialIntro` | `witness A P w proof` |
226///
227/// # Induction Handling
228///
229/// Structural induction produces fixpoint terms. The step case certification
230/// tracks the induction variable so that IH references become recursive calls.
231///
232/// # See Also
233///
234/// * [`CertificationContext`] - The context passed to this function
235/// * [`DerivationTree`] - The input proof structure
236/// * [`InferenceRule`] - The rules being certified
237pub fn certify(tree: &DerivationTree, ctx: &CertificationContext) -> KernelResult<Term> {
238    match &tree.rule {
239        // Axiom or direct hypothesis reference
240        InferenceRule::Axiom | InferenceRule::PremiseMatch => {
241            certify_hypothesis(&tree.conclusion, ctx)
242        }
243
244        // Modus Ponens: App(impl_proof, arg_proof)
245        // P → Q, P ⊢ Q becomes (h1 h2) : Q
246        InferenceRule::ModusPonens => {
247            if tree.premises.len() != 2 {
248                return Err(KernelError::CertificationError(
249                    "ModusPonens requires exactly 2 premises".to_string(),
250                ));
251            }
252            let impl_term = certify(&tree.premises[0], ctx)?;
253            let arg_term = certify(&tree.premises[1], ctx)?;
254            Ok(Term::App(Box::new(impl_term), Box::new(arg_term)))
255        }
256
257        // Modus Tollens: P → Q, ¬Q ⊢ ¬P.  Since ¬P unfolds to P → False, the
258        // proof is λ(hp:P). neg_q (impl hp) — feed a hypothetical P through the
259        // implication to get Q, then through ¬Q (= Q → False) to get False.
260        InferenceRule::ModusTollens => {
261            if tree.premises.len() != 2 {
262                return Err(KernelError::CertificationError(
263                    "ModusTollens requires exactly 2 premises (implication, negated consequent)"
264                        .to_string(),
265                ));
266            }
267            let p = match &tree.conclusion {
268                ProofExpr::Not(p) => p.as_ref().clone(),
269                _ => {
270                    return Err(KernelError::CertificationError(
271                        "ModusTollens conclusion must be a negation".to_string(),
272                    ))
273                }
274            };
275            let p_type = proof_expr_to_type(&p)?;
276            let impl_proof = certify(&tree.premises[0], ctx)?;
277            let neg_q_proof = certify(&tree.premises[1], ctx)?;
278            let hp = "__mt_hp".to_string();
279            // λ(hp:P). neg_q_proof (impl_proof hp)  :  P → False  =  ¬P
280            Ok(Term::Lambda {
281                param: hp.clone(),
282                param_type: Box::new(p_type),
283                body: Box::new(Term::App(
284                    Box::new(neg_q_proof),
285                    Box::new(Term::App(Box::new(impl_proof), Box::new(Term::Var(hp)))),
286                )),
287            })
288        }
289
290        // Reflexivity of equality: a = a.  Curry-Howard: `refl T a`, where
291        // `refl : Π(A:Type). Π(x:A). Eq A x x`. The two sides are definitionally
292        // equal, so `refl T l : Eq T l l` reconciles with `Eq T l r`. The domain `T`
293        // is inferred from the operands (so a ground `le 2 5 = true`, where both
294        // sides reduce to `true : Bool`, certifies as `refl Bool (le 2 5)`).
295        InferenceRule::Reflexivity => {
296            let (l, r) = match &tree.conclusion {
297                ProofExpr::Identity(l, r) => (l, r),
298                _ => {
299                    return Err(KernelError::CertificationError(
300                        "Reflexivity conclusion must be an Identity".to_string(),
301                    ))
302                }
303            };
304            let domain = Term::Global(resolved_identity_domain(l, r, ctx.kernel_ctx));
305            let term = proof_term_to_kernel_term(l)?;
306            Ok(Term::App(
307                Box::new(Term::App(
308                    Box::new(Term::Global("refl".to_string())),
309                    Box::new(domain),
310                )),
311                Box::new(term),
312            ))
313        }
314
315        // Ex falso quodlibet: ⊥ ⊢ G.  False has no constructors, so its eliminator
316        // is a `match` with zero cases — `match false_proof return (λ_:False. G) {}`.
317        InferenceRule::ExFalso => {
318            if tree.premises.len() != 1 {
319                return Err(KernelError::CertificationError(
320                    "ExFalso requires exactly 1 premise (a proof of False)".to_string(),
321                ));
322            }
323            let false_proof = certify(&tree.premises[0], ctx)?;
324            let goal_type = proof_expr_to_type_ctx(&tree.conclusion, ctx.kernel_ctx)?;
325            Ok(Term::Match {
326                discriminant: Box::new(false_proof),
327                motive: Box::new(Term::Lambda {
328                    param: "_".to_string(),
329                    param_type: Box::new(Term::Global("False".to_string())),
330                    body: Box::new(goal_type),
331                }),
332                cases: vec![],
333            })
334        }
335
336        // Conjunction Introduction: conj P Q p_proof q_proof
337        // P, Q ⊢ P ∧ Q becomes (conj P Q p q) : And P Q
338        InferenceRule::ConjunctionIntro => {
339            if tree.premises.len() != 2 {
340                return Err(KernelError::CertificationError(
341                    "ConjunctionIntro requires exactly 2 premises".to_string(),
342                ));
343            }
344            let (p_type, q_type) = extract_and_types(&tree.conclusion)?;
345            let p_term = certify(&tree.premises[0], ctx)?;
346            let q_term = certify(&tree.premises[1], ctx)?;
347
348            // Build: conj P Q p_proof q_proof (fully curried)
349            let conj = Term::Global("conj".to_string());
350            let applied = Term::App(
351                Box::new(Term::App(
352                    Box::new(Term::App(
353                        Box::new(Term::App(Box::new(conj), Box::new(p_type))),
354                        Box::new(q_type),
355                    )),
356                    Box::new(p_term),
357                )),
358                Box::new(q_term),
359            );
360            Ok(applied)
361        }
362
363        // Disjunction Introduction: P ⊢ P ∨ Q  (or Q ⊢ P ∨ Q)
364        // Curry-Howard: `left P Q p` or `right P Q q`. The rule is side-agnostic;
365        // we recover the side by matching the proved premise against the disjuncts.
366        InferenceRule::DisjunctionIntro => {
367            if tree.premises.len() != 1 {
368                return Err(KernelError::CertificationError(
369                    "DisjunctionIntro requires exactly 1 premise".to_string(),
370                ));
371            }
372            let (p, q) = match &tree.conclusion {
373                ProofExpr::Or(p, q) => (p.as_ref().clone(), q.as_ref().clone()),
374                _ => {
375                    return Err(KernelError::CertificationError(
376                        "DisjunctionIntro conclusion must be Or".to_string(),
377                    ))
378                }
379            };
380            let proved = &tree.premises[0].conclusion;
381            let ctor = if proved == &p {
382                "left"
383            } else if proved == &q {
384                "right"
385            } else {
386                return Err(KernelError::CertificationError(
387                    "DisjunctionIntro premise proves neither disjunct".to_string(),
388                ));
389            };
390            let p_type = proof_expr_to_type(&p)?;
391            let q_type = proof_expr_to_type(&q)?;
392            let proof_term = certify(&tree.premises[0], ctx)?;
393
394            // left/right : Π(P:Prop). Π(Q:Prop). (P|Q) → Or P Q
395            let applied = Term::App(
396                Box::new(Term::App(
397                    Box::new(Term::App(
398                        Box::new(Term::Global(ctor.to_string())),
399                        Box::new(p_type),
400                    )),
401                    Box::new(q_type),
402                )),
403                Box::new(proof_term),
404            );
405            Ok(applied)
406        }
407
408        // Universal Instantiation: forall x.P(x) |- P(t)
409        // Curry-Howard: Apply the forall-proof (a function) to the witness term
410        InferenceRule::UniversalInst(witness) => {
411            if tree.premises.len() != 1 {
412                return Err(KernelError::CertificationError(
413                    "UniversalInst requires exactly 1 premise".to_string(),
414                ));
415            }
416            let forall_proof = certify(&tree.premises[0], ctx)?;
417            // Check if witness is a local variable (inside a lambda body)
418            let witness_term = if ctx.is_local(witness) {
419                Term::Var(witness.clone())
420            } else {
421                Term::Global(witness.clone())
422            };
423            Ok(Term::App(Box::new(forall_proof), Box::new(witness_term)))
424        }
425
426        // Universal Instantiation at an arbitrary witness TERM: the same
427        // Curry-Howard application, with the witness converted as a full term
428        // (compound witnesses like `add(a, Zero)` included).
429        InferenceRule::UniversalInstTerm(witness) => {
430            if tree.premises.len() != 1 {
431                return Err(KernelError::CertificationError(
432                    "UniversalInstTerm requires exactly 1 premise".to_string(),
433                ));
434            }
435            let forall_proof = certify(&tree.premises[0], ctx)?;
436            let witness_term = match witness {
437                ProofTerm::Constant(name) | ProofTerm::Variable(name) if ctx.is_local(name) => {
438                    Term::Var(name.clone())
439                }
440                _ => proof_term_to_kernel_term(witness)?,
441            };
442            Ok(Term::App(Box::new(forall_proof), Box::new(witness_term)))
443        }
444
445        // Universal Introduction: Γ, x:T ⊢ P(x) implies Γ ⊢ ∀x:T. P(x)
446        // Curry-Howard: Wrap the body proof in a Lambda
447        InferenceRule::UniversalIntro { variable, var_type } => {
448            if tree.premises.len() != 1 {
449                return Err(KernelError::CertificationError(
450                    "UniversalIntro requires exactly 1 premise".to_string(),
451                ));
452            }
453
454            // Type the binder by how the conclusion's body USES the variable, resolved against the
455            // kernel context (a var fed to `Mul`/`Add`/… is `Int`) — the SAME inference the goal type
456            // uses (`proof_expr_to_type_ctx` → `binder_domain`), so the abstraction and the goal Π
457            // agree. When usage is uninformative (`binder_domain` returns the `Entity` default — e.g.
458            // the body is `True` and never mentions the variable), the engine's EXPLICITLY declared
459            // `var_type` is authoritative (`∀x:Nat. True` must abstract `x:Nat`, not `x:Entity`).
460            let domain = match &tree.conclusion {
461                ProofExpr::ForAll { body, .. } => {
462                    let inferred = binder_domain(variable, body, ctx.kernel_ctx);
463                    if inferred == "Entity" && var_type != "Entity" {
464                        var_type.clone()
465                    } else {
466                        inferred
467                    }
468                }
469                _ => var_type.clone(),
470            };
471            let type_term = Term::Global(domain);
472
473            // Certify body with variable in scope
474            let extended_ctx = ctx.with_local(variable);
475            let body_term = certify(&tree.premises[0], &extended_ctx)?;
476
477            // Wrap in Lambda
478            Ok(Term::Lambda {
479                param: variable.clone(),
480                param_type: Box::new(type_term),
481                body: Box::new(body_term),
482            })
483        }
484
485        // Structural Induction: P(0), ∀k(P(k) → P(S(k))) ⊢ ∀n P(n)
486        // Curry-Howard: fix rec. λn. match n { Zero => base, Succ k => step }
487        InferenceRule::StructuralInduction {
488            variable: var_name,
489            ind_type,
490            step_var,
491        } => {
492            if tree.premises.len() != 2 {
493                return Err(KernelError::CertificationError(
494                    "StructuralInduction requires exactly 2 premises (base, step)".to_string(),
495                ));
496            }
497
498            // Extract motive body from ForAll conclusion
499            let motive_body = extract_motive_body(&tree.conclusion, var_name, ctx.kernel_ctx)?;
500
501            // Generate fix name
502            let fix_name = format!("rec_{}", var_name);
503
504            // === Certify Base Case ===
505            // Base case is certified in the current context (no IH)
506            let base_term = certify(&tree.premises[0], ctx)?;
507
508            // === Certify Step Case ===
509            // IH: P(k) - compute what IH looks like by substituting n -> k
510            let ih_conclusion = compute_ih_conclusion(&tree.conclusion, var_name, step_var)?;
511
512            // Create context with:
513            // 1. step_var as a local (bound by the Succ case lambda)
514            // 2. induction state (for IH resolution)
515            let step_ctx =
516                ctx.with_local(step_var)
517                    .with_induction(&fix_name, step_var, ih_conclusion);
518
519            let step_body = certify(&tree.premises[1], &step_ctx)?;
520
521            // Wrap step body in lambda: λk. step_body
522            let step_term = Term::Lambda {
523                param: step_var.clone(),
524                param_type: Box::new(Term::Global(ind_type.clone())),
525                body: Box::new(step_body),
526            };
527
528            // === Build Match ===
529            // match n return (λn:Nat. P(n)) with { Zero => base, Succ k => step }
530            // The motive uses var_name so body references are properly bound
531            let match_term = Term::Match {
532                discriminant: Box::new(Term::Var(var_name.clone())),
533                motive: Box::new(build_motive(ind_type, &motive_body, var_name)),
534                cases: vec![base_term, step_term],
535            };
536
537            // === Build Lambda ===
538            // λn:Nat. match n ...
539            let lambda_term = Term::Lambda {
540                param: var_name.clone(),
541                param_type: Box::new(Term::Global(ind_type.clone())),
542                body: Box::new(match_term),
543            };
544
545            // === Build Fixpoint ===
546            // fix rec_n. λn. match n ...
547            Ok(Term::Fix {
548                name: fix_name,
549                body: Box::new(lambda_term),
550            })
551        }
552
553        // Generic structural induction over an arbitrary inductive type: one case
554        // per constructor (in registration order), each recursive argument carrying
555        // its own induction hypothesis. Certifies to `fix rec. λx. match x { … }`,
556        // the dependent eliminator — the kernel re-checks coverage, case types, and
557        // the termination guard, so an ill-formed scheme is rejected here.
558        InferenceRule::InductionScheme {
559            variable,
560            ind_type,
561            cases,
562        } => {
563            if tree.premises.len() != cases.len() {
564                return Err(KernelError::CertificationError(format!(
565                    "InductionScheme requires one premise per constructor: {} cases, {} premises",
566                    cases.len(),
567                    tree.premises.len()
568                )));
569            }
570
571            let motive_body = extract_motive_body(&tree.conclusion, variable, ctx.kernel_ctx)?;
572            let fix_name = format!("rec_{}", variable);
573
574            let mut case_terms = Vec::with_capacity(cases.len());
575            for (case, premise) in cases.iter().zip(tree.premises.iter()) {
576                // Argument kernel types, peeled from the constructor's signature.
577                let arg_types = constructor_arg_types(ctx.kernel_ctx, &case.constructor)?;
578                if arg_types.len() != case.args.len() {
579                    return Err(KernelError::CertificationError(format!(
580                        "constructor {} takes {} arguments, case binds {}",
581                        case.constructor,
582                        arg_types.len(),
583                        case.args.len()
584                    )));
585                }
586
587                // Each recursive argument contributes an IH: the motive at that
588                // argument (the induction variable substituted by the argument name).
589                let mut ihs = Vec::new();
590                for arg in &case.args {
591                    if arg.recursive {
592                        let ih = compute_ih_conclusion(&tree.conclusion, variable, &arg.name)?;
593                        ihs.push((arg.name.clone(), ih));
594                    }
595                }
596
597                // Certify the case under a context binding every argument as a local
598                // and exposing the recursive IHs (so IH references become `rec <arg>`).
599                let mut case_ctx = ctx.with_induction_multi(&fix_name, ihs);
600                for arg in &case.args {
601                    case_ctx = case_ctx.with_local(&arg.name);
602                }
603                let case_body = certify(premise, &case_ctx)?;
604
605                // Wrap the body in one lambda per constructor argument:
606                // λ(a0:T0). … λ(aN:TN). body  (nullary constructors stay bare).
607                let mut term = case_body;
608                for (arg, ty) in case.args.iter().zip(arg_types.iter()).rev() {
609                    term = Term::Lambda {
610                        param: arg.name.clone(),
611                        param_type: Box::new(ty.clone()),
612                        body: Box::new(term),
613                    };
614                }
615                case_terms.push(term);
616            }
617
618            // match x return (λx:Ind. P(x)) with { case₀, …, caseₙ }
619            let match_term = Term::Match {
620                discriminant: Box::new(Term::Var(variable.clone())),
621                motive: Box::new(build_motive(ind_type, &motive_body, variable)),
622                cases: case_terms,
623            };
624
625            // fix rec_x. λx:Ind. match x { … }
626            let lambda_term = Term::Lambda {
627                param: variable.clone(),
628                param_type: Box::new(Term::Global(ind_type.clone())),
629                body: Box::new(match_term),
630            };
631
632            Ok(Term::Fix {
633                name: fix_name,
634                body: Box::new(lambda_term),
635            })
636        }
637
638        // Existential Introduction: P(w) ⊢ ∃x.P(x)
639        // Curry-Howard: witness A P w proof
640        InferenceRule::ExistentialIntro {
641            witness: witness_str,
642            witness_type,
643        } => {
644            if tree.premises.len() != 1 {
645                return Err(KernelError::CertificationError(
646                    "ExistentialIntro requires exactly 1 premise".to_string(),
647                ));
648            }
649
650            // Extract variable and body from Exists conclusion
651            let (variable, body) = match &tree.conclusion {
652                ProofExpr::Exists { variable, body } => (variable.clone(), body.as_ref().clone()),
653                _ => {
654                    return Err(KernelError::CertificationError(
655                        "ExistentialIntro conclusion must be Exists".to_string(),
656                    ))
657                }
658            };
659
660            // Determine witness term (local or global)
661            let witness_term = if ctx.is_local(witness_str) {
662                Term::Var(witness_str.clone())
663            } else {
664                Term::Global(witness_str.clone())
665            };
666
667            // Certify the premise (proof of P(witness))
668            let proof_term = certify(&tree.premises[0], ctx)?;
669
670            // The type A comes from the InferenceRule (EXPLICIT INTENT)
671            let type_a = Term::Global(witness_type.clone());
672
673            // Build predicate P = λvar:A. body_type — matching `proof_expr_to_type`'s
674            // encoding of `Exists` EXACTLY (no eta-contracted `P`-direct shortcut for
675            // the `∃y.P(y)` case), so the certified term's type and the goal type
676            // agree structurally without relying on eta-conversion in the kernel.
677            let predicate = Term::Lambda {
678                param: variable.clone(),
679                param_type: Box::new(type_a.clone()),
680                body: Box::new(proof_expr_to_type(&body)?),
681            };
682
683            // Build: witness A P w proof
684            // witness : Π(A:Type). Π(P:A→Prop). Π(x:A). P(x) → Ex A P
685            let witness_ctor = Term::Global("witness".to_string());
686
687            let applied = Term::App(
688                Box::new(Term::App(
689                    Box::new(Term::App(
690                        Box::new(Term::App(Box::new(witness_ctor), Box::new(type_a))),
691                        Box::new(predicate),
692                    )),
693                    Box::new(witness_term),
694                )),
695                Box::new(proof_term),
696            );
697
698            Ok(applied)
699        }
700
701        // Existential Introduction at an arbitrary witness TERM: P(t) ⊢ ∃x.P(x).
702        // Curry-Howard: `witness A P t proof`, exactly as the name-only arm above — the
703        // only difference is that the witness is LOWERED as a term instead of resolved as
704        // one identifier, so `use (n + 1)` has a faithful image. `witness_type` is the
705        // ∃-binder's domain and must be the one `proof_expr_to_type` gives the same
706        // `Exists` (both read `existential_domain`), or the certified term's type and the
707        // goal type differ by that domain and the kernel refuses the proof.
708        InferenceRule::ExistentialIntroTerm {
709            witness,
710            witness_type,
711        } => {
712            if tree.premises.len() != 1 {
713                return Err(KernelError::CertificationError(
714                    "ExistentialIntroTerm requires exactly 1 premise".to_string(),
715                ));
716            }
717            let (variable, body) = match &tree.conclusion {
718                ProofExpr::Exists { variable, body } => (variable.clone(), body.as_ref().clone()),
719                _ => {
720                    return Err(KernelError::CertificationError(
721                        "ExistentialIntroTerm conclusion must be Exists".to_string(),
722                    ))
723                }
724            };
725            let declared = existential_domain(&variable, &body);
726            if witness_type != &declared {
727                return Err(KernelError::CertificationError(format!(
728                    "ExistentialIntroTerm declares the ∃-binder `{variable}` to be \
729                     `{witness_type}`, but the body constrains it to `{declared}` — the \
730                     certified term would have type `Ex {witness_type} …` where the goal is \
731                     `Ex {declared} …`"
732                )));
733            }
734            let witness_term = proof_term_to_kernel_term(witness)?;
735            let proof_term = certify(&tree.premises[0], ctx)?;
736            let type_a = Term::Global(witness_type.clone());
737            let predicate = Term::Lambda {
738                param: variable.clone(),
739                param_type: Box::new(type_a.clone()),
740                body: Box::new(proof_expr_to_type(&body)?),
741            };
742            let applied = [type_a, predicate, witness_term, proof_term]
743                .into_iter()
744                .fold(Term::Global("witness".to_string()), |acc, arg| {
745                    Term::App(Box::new(acc), Box::new(arg))
746                });
747            Ok(applied)
748        }
749
750        // Existential Elimination: from ∃x.P(x) and a proof of the goal that uses
751        // a fresh witness `c` with hypothesis P(c), eliminate the existential.
752        // Curry-Howard: pattern-match the existential —
753        //   match ex return (λ_:Ex Entity P. Goal) with witness c h => <Goal proof>
754        // The witness `c` is the Match-bound variable, so within the body we turn
755        // the placeholder constant `c` into that bound variable. Two shapes flow
756        // through here: the prove-⊥ form (`cert_derive_falsum`, conclusion ⊥, body
757        // references the whole `P(c)`) and the forward form (`try_existential_
758        // elimination`, conclusion = the actual goal, body references the FLATTENED
759        // conjuncts of `P(c)`). The motive's body is the conclusion's type — ⊥
760        // gives `False`, recovering the prove-⊥ case unchanged — and the body
761        // proof sees both the whole `P(c)` and each of its conjuncts (the latter
762        // recovered by genuine ∧-elimination of `h`).
763        InferenceRule::ExistentialElim { witness } => {
764            if tree.premises.len() != 2 {
765                return Err(KernelError::CertificationError(
766                    "ExistentialElim requires exactly 2 premises (existential, body)".to_string(),
767                ));
768            }
769            let exist_premise = &tree.premises[0];
770            let body = &tree.premises[1];
771
772            let (var, p_body) = match &exist_premise.conclusion {
773                ProofExpr::Exists { variable, body } => (variable.clone(), body.as_ref().clone()),
774                _ => {
775                    return Err(KernelError::CertificationError(
776                        "ExistentialElim first premise must conclude an Exists".to_string(),
777                    ))
778                }
779            };
780
781            // P(c) as a ProofExpr — the witness substituted for the bound var.
782            let p_c_expr = crate::unify::instantiate_expr(
783                &p_body,
784                &var,
785                &ProofTerm::Constant(witness.clone()),
786            );
787
788            // Discriminant: the proof of the existential (type Ex Entity P).
789            let disc = certify(exist_premise, ctx)?;
790
791            // The witness body is proved by the bound hypothesis `h : P(c)`. Bind
792            // the whole body (the prove-⊥ form references it directly) AND every
793            // flattened conjunct, each recovered by ∧-eliminating `h` (the forward
794            // form references the conjuncts separately).
795            let h = format!("_exh_{}", witness);
796            let h_var = Term::Var(h.clone());
797            let mut body_ctx = ctx.with_local_hyp_term(&p_c_expr, h_var.clone());
798            for (conjunct, proj) in collect_conjunct_hyps(&p_c_expr, &h_var)? {
799                body_ctx = body_ctx.with_local_hyp_term(&conjunct, proj);
800            }
801
802            let body_raw = certify(body, &body_ctx)?;
803            let c_global = Term::Global(witness.clone());
804            let c_var = Term::Var(witness.clone());
805            let body_term = substitute_term_in_kernel(&body_raw, &c_global, &c_var);
806            let p_c_type =
807                substitute_term_in_kernel(&proof_expr_to_type(&p_c_expr)?, &c_global, &c_var);
808
809            // CONSTANT motive: the witness does not escape — the goal is closed (it does
810            // not mention `c`) — so pass the goal type raw and let the kernel synthesize
811            // `λ_:(Ex Entity P). Goal` from the discriminant's own type. (⊥ ↦ `False`,
812            // keeping the prove-⊥ form intact.)
813            let motive = proof_expr_to_type(&tree.conclusion)?;
814
815            // Case for `witness`: λ(c:Entity). λ(h:P(c)). <Goal proof>
816            let case = Term::Lambda {
817                param: witness.clone(),
818                param_type: Box::new(Term::Global("Entity".to_string())),
819                body: Box::new(Term::Lambda {
820                    param: h,
821                    param_type: Box::new(p_c_type),
822                    body: Box::new(body_term),
823                }),
824            };
825
826            Ok(Term::Match {
827                discriminant: Box::new(disc),
828                motive: Box::new(motive),
829                cases: vec![case],
830            })
831        }
832
833        // Equality Rewriting (Leibniz's Law)
834        // a = b, P(a) ⊢ P(b)
835        // Uses: Eq_rec A x P proof y eq_proof
836        InferenceRule::Rewrite { from, to } => {
837            if tree.premises.len() != 2 {
838                return Err(KernelError::CertificationError(
839                    "Rewrite requires exactly 2 premises (equality, source)".to_string(),
840                ));
841            }
842
843            // Certify both premises
844            let eq_proof = certify(&tree.premises[0], ctx)?;
845            let source_proof = certify(&tree.premises[1], ctx)?;
846
847            // Convert terms
848            let from_term = proof_term_to_kernel_term(from)?;
849            let to_term = proof_term_to_kernel_term(to)?;
850
851            // Build the predicate P as a lambda that wraps the goal
852            // P = λz. (goal with 'to' replaced by z)
853            let predicate = build_equality_predicate(&tree.conclusion, to, ctx.kernel_ctx)?;
854
855            // Eq_rec : Π(A:Type). Π(x:A). Π(P:A→Prop). P x → Π(y:A). Eq A x y → P y
856            // Build: Eq_rec D from P source_proof to eq_proof, where D is the domain of the
857            // rewritten terms — resolved against ctx so a declared `_ → Int` function reads as Int.
858            let eq_rec = Term::Global("Eq_rec".to_string());
859            let domain = Term::Global(resolved_domain(from, ctx.kernel_ctx));
860
861            let applied = Term::App(
862                Box::new(Term::App(
863                    Box::new(Term::App(
864                        Box::new(Term::App(
865                            Box::new(Term::App(
866                                Box::new(Term::App(Box::new(eq_rec), Box::new(domain))),
867                                Box::new(from_term),
868                            )),
869                            Box::new(predicate),
870                        )),
871                        Box::new(source_proof),
872                    )),
873                    Box::new(to_term),
874                )),
875                Box::new(eq_proof),
876            );
877
878            Ok(applied)
879        }
880
881        // POSITIONAL Leibniz: like `Rewrite`, but the motive abstracts exactly ONE
882        // occurrence of `to` — the `occurrence`-th, left to right. Everything else is the
883        // same `Eq_rec` application, which is what makes the index safe: the kernel checks
884        // `source_proof : P from`, so an index naming the wrong occurrence builds a motive
885        // the rewritten subgoal does not inhabit and the proof is refused, never believed.
886        InferenceRule::RewriteAt {
887            from,
888            to,
889            occurrence,
890        } => {
891            if tree.premises.len() != 2 {
892                return Err(KernelError::CertificationError(
893                    "RewriteAt requires exactly 2 premises (equality, source)".to_string(),
894                ));
895            }
896            let eq_proof = certify(&tree.premises[0], ctx)?;
897            let source_proof = certify(&tree.premises[1], ctx)?;
898            let from_term = proof_term_to_kernel_term(from)?;
899            let to_term = proof_term_to_kernel_term(to)?;
900            let predicate =
901                build_equality_predicate_at(&tree.conclusion, to, *occurrence, ctx.kernel_ctx)?;
902            let eq_rec = Term::Global("Eq_rec".to_string());
903            let domain = Term::Global(resolved_domain(from, ctx.kernel_ctx));
904            let applied = [from_term, predicate, source_proof, to_term, eq_proof]
905                .into_iter()
906                .fold(Term::App(Box::new(eq_rec), Box::new(domain)), |acc, arg| {
907                    Term::App(Box::new(acc), Box::new(arg))
908                });
909            Ok(applied)
910        }
911
912        // Equality Symmetry: a = b ⊢ b = a
913        // Uses: Eq_sym A x y proof
914        InferenceRule::EqualitySymmetry => {
915            if tree.premises.len() != 1 {
916                return Err(KernelError::CertificationError(
917                    "EqualitySymmetry requires exactly 1 premise".to_string(),
918                ));
919            }
920
921            let premise_proof = certify(&tree.premises[0], ctx)?;
922
923            // Extract x and y from the premise conclusion (x = y)
924            let (x, y, domain) = match &tree.premises[0].conclusion {
925                ProofExpr::Identity(l, r) => (
926                    proof_term_to_kernel_term(l)?,
927                    proof_term_to_kernel_term(r)?,
928                    Term::Global(resolved_identity_domain(l, r, ctx.kernel_ctx)),
929                ),
930                _ => {
931                    return Err(KernelError::CertificationError(
932                        "EqualitySymmetry premise must be an Identity".to_string(),
933                    ))
934                }
935            };
936
937            // Eq_sym : Π(A:Type). Π(x:A). Π(y:A). Eq A x y → Eq A y x
938            // Build: Eq_sym D x y proof, with D the operands' domain
939            // (Int for arithmetic, Bool for comparisons, else Entity).
940            let eq_sym = Term::Global("Eq_sym".to_string());
941
942            Ok(Term::App(
943                Box::new(Term::App(
944                    Box::new(Term::App(
945                        Box::new(Term::App(Box::new(eq_sym), Box::new(domain))),
946                        Box::new(x),
947                    )),
948                    Box::new(y),
949                )),
950                Box::new(premise_proof),
951            ))
952        }
953
954        // Equality Transitivity: a = b, b = c ⊢ a = c
955        // Uses: Eq_trans A x y z proof1 proof2
956        InferenceRule::EqualityTransitivity => {
957            if tree.premises.len() != 2 {
958                return Err(KernelError::CertificationError(
959                    "EqualityTransitivity requires exactly 2 premises".to_string(),
960                ));
961            }
962
963            let proof1 = certify(&tree.premises[0], ctx)?;
964            let proof2 = certify(&tree.premises[1], ctx)?;
965
966            // Extract x, y from first premise (x = y)
967            let (x, y, domain) = match &tree.premises[0].conclusion {
968                ProofExpr::Identity(l, r) => (
969                    proof_term_to_kernel_term(l)?,
970                    proof_term_to_kernel_term(r)?,
971                    Term::Global(resolved_identity_domain(l, r, ctx.kernel_ctx)),
972                ),
973                _ => {
974                    return Err(KernelError::CertificationError(
975                        "EqualityTransitivity first premise must be Identity".to_string(),
976                    ))
977                }
978            };
979
980            // Extract z from second premise (y = z)
981            let z = match &tree.premises[1].conclusion {
982                ProofExpr::Identity(_, r) => proof_term_to_kernel_term(r)?,
983                _ => {
984                    return Err(KernelError::CertificationError(
985                        "EqualityTransitivity second premise must be Identity".to_string(),
986                    ))
987                }
988            };
989
990            // Eq_trans : Π(A:Type). Π(x:A). Π(y:A). Π(z:A). Eq A x y → Eq A y z → Eq A x z
991            // Build: Eq_trans D x y z proof1 proof2, with D the operands' domain
992            // (Int for arithmetic, Bool for comparisons, else Entity).
993            let eq_trans = Term::Global("Eq_trans".to_string());
994
995            Ok(Term::App(
996                Box::new(Term::App(
997                    Box::new(Term::App(
998                        Box::new(Term::App(
999                            Box::new(Term::App(
1000                                Box::new(Term::App(Box::new(eq_trans), Box::new(domain))),
1001                                Box::new(x),
1002                            )),
1003                            Box::new(y),
1004                        )),
1005                        Box::new(z),
1006                    )),
1007                    Box::new(proof1),
1008                )),
1009                Box::new(proof2),
1010            ))
1011        }
1012
1013        // `a ≤ b`, `b ≤ c` ⊢ `a ≤ c`:  le_trans a b c p₀ p₁.  Inequalities are the
1014        // Prop `Eq Bool (le a b) true`; the middle term comes from the first premise.
1015        InferenceRule::LeTrans => {
1016            if tree.premises.len() != 2 {
1017                return Err(KernelError::CertificationError(
1018                    "LeTrans requires exactly 2 premises".to_string(),
1019                ));
1020            }
1021            let (a, b) = le_terms(&tree.conclusion)?;
1022            let (_, mid) = le_terms(&tree.premises[0].conclusion)?;
1023            let p0 = certify(&tree.premises[0], ctx)?;
1024            let p1 = certify(&tree.premises[1], ctx)?;
1025            let mut t = Term::Global("le_trans".to_string());
1026            for arg in [
1027                proof_term_to_kernel_term(&a)?,
1028                proof_term_to_kernel_term(&mid)?,
1029                proof_term_to_kernel_term(&b)?,
1030                p0,
1031                p1,
1032            ] {
1033                t = Term::App(Box::new(t), Box::new(arg));
1034            }
1035            Ok(t)
1036        }
1037
1038        // `⊢ a ≤ a`:  le_refl a.
1039        InferenceRule::LeRefl => {
1040            let (a, _) = le_terms(&tree.conclusion)?;
1041            Ok(Term::App(
1042                Box::new(Term::Global("le_refl".to_string())),
1043                Box::new(proof_term_to_kernel_term(&a)?),
1044            ))
1045        }
1046
1047        // `a ≤ b`, `c ≤ d` ⊢ `a + c ≤ b + d`:  le_add_mono a b c d p₀ p₁.
1048        InferenceRule::LeAddMono => {
1049            if tree.premises.len() != 2 {
1050                return Err(KernelError::CertificationError(
1051                    "LeAddMono requires exactly 2 premises".to_string(),
1052                ));
1053            }
1054            let (lhs, rhs) = le_terms(&tree.conclusion)?;
1055            let (a, c) = add_terms(&lhs)?;
1056            let (b, d) = add_terms(&rhs)?;
1057            let p0 = certify(&tree.premises[0], ctx)?;
1058            let p1 = certify(&tree.premises[1], ctx)?;
1059            let mut t = Term::Global("le_add_mono".to_string());
1060            for arg in [
1061                proof_term_to_kernel_term(&a)?,
1062                proof_term_to_kernel_term(&b)?,
1063                proof_term_to_kernel_term(&c)?,
1064                proof_term_to_kernel_term(&d)?,
1065                p0,
1066                p1,
1067            ] {
1068                t = Term::App(Box::new(t), Box::new(arg));
1069            }
1070            Ok(t)
1071        }
1072
1073        // Linear contradiction → ⊥: `premise[0] : le(m,n) = true` with `m > n` is, by
1074        // computation, a proof of `Eq Bool false true`; the Bool no-confusion
1075        // discriminator turns it into `False`.
1076        InferenceRule::LinFalse => {
1077            if tree.premises.len() != 1 {
1078                return Err(KernelError::CertificationError(
1079                    "LinFalse requires exactly 1 premise".to_string(),
1080                ));
1081            }
1082            let le_proof = certify(&tree.premises[0], ctx)?;
1083            Ok(build_bool_discriminator(le_proof))
1084        }
1085
1086        // `0 ≤ k`, `a ≤ b` ⊢ `k·a ≤ k·b`:  le_mul_nonneg k a b p₀ p₁.
1087        InferenceRule::LeMulNonneg => {
1088            if tree.premises.len() != 2 {
1089                return Err(KernelError::CertificationError(
1090                    "LeMulNonneg requires exactly 2 premises".to_string(),
1091                ));
1092            }
1093            let (lhs, rhs) = le_terms(&tree.conclusion)?;
1094            let (k, a) = binop_terms("mul", &lhs)?;
1095            let (_, b) = binop_terms("mul", &rhs)?;
1096            let p0 = certify(&tree.premises[0], ctx)?;
1097            let p1 = certify(&tree.premises[1], ctx)?;
1098            let mut t = Term::Global("le_mul_nonneg".to_string());
1099            for arg in [
1100                proof_term_to_kernel_term(&k)?,
1101                proof_term_to_kernel_term(&a)?,
1102                proof_term_to_kernel_term(&b)?,
1103                p0,
1104                p1,
1105            ] {
1106                t = Term::App(Box::new(t), Box::new(arg));
1107            }
1108            Ok(t)
1109        }
1110
1111        // `a ≤ b` ⊢ `0 ≤ b + (-1)·a`:  le_sub a b p₀.
1112        InferenceRule::LeSub => {
1113            if tree.premises.len() != 1 {
1114                return Err(KernelError::CertificationError(
1115                    "LeSub requires exactly 1 premise".to_string(),
1116                ));
1117            }
1118            let (_zero, diff) = le_terms(&tree.conclusion)?;
1119            let (b, neg_a) = binop_terms("add", &diff)?;
1120            let (_neg_one, a) = binop_terms("mul", &neg_a)?;
1121            let p0 = certify(&tree.premises[0], ctx)?;
1122            let mut t = Term::Global("le_sub".to_string());
1123            for arg in [
1124                proof_term_to_kernel_term(&a)?,
1125                proof_term_to_kernel_term(&b)?,
1126                p0,
1127            ] {
1128                t = Term::App(Box::new(t), Box::new(arg));
1129            }
1130            Ok(t)
1131        }
1132
1133        // `a < b` ⊢ `(a + 1) ≤ b` — integer discreteness. The conclusion is
1134        // `le(add a 1, b) = true`, so `a` is the first summand of the sum and `b`
1135        // the right operand; `premise[0]` proves `lt(a, b) = true`. Certifies to
1136        // `lt_succ_le a b p₀` — the kernel axiom application.
1137        InferenceRule::LtSuccLe => {
1138            if tree.premises.len() != 1 {
1139                return Err(KernelError::CertificationError(
1140                    "LtSuccLe requires exactly 1 premise".to_string(),
1141                ));
1142            }
1143            let (succ_a, b) = le_terms(&tree.conclusion)?;
1144            let (a, _one) = binop_terms("add", &succ_a)?;
1145            let p0 = certify(&tree.premises[0], ctx)?;
1146            let mut t = Term::Global("lt_succ_le".to_string());
1147            for arg in [
1148                proof_term_to_kernel_term(&a)?,
1149                proof_term_to_kernel_term(&b)?,
1150                p0,
1151            ] {
1152                t = Term::App(Box::new(t), Box::new(arg));
1153            }
1154            Ok(t)
1155        }
1156
1157        // `a < b + 1` ⊢ `a ≤ b`. The conclusion is `le(a, b) = true`; `premise[0]`
1158        // proves `lt(a, add b 1) = true`. Certifies to `lt_add1_le a b p₀`.
1159        InferenceRule::LtAdd1Le => {
1160            if tree.premises.len() != 1 {
1161                return Err(KernelError::CertificationError(
1162                    "LtAdd1Le requires exactly 1 premise".to_string(),
1163                ));
1164            }
1165            let (a, b) = le_terms(&tree.conclusion)?;
1166            let p0 = certify(&tree.premises[0], ctx)?;
1167            let mut t = Term::Global("lt_add1_le".to_string());
1168            for arg in [
1169                proof_term_to_kernel_term(&a)?,
1170                proof_term_to_kernel_term(&b)?,
1171                p0,
1172            ] {
1173                t = Term::App(Box::new(t), Box::new(arg));
1174            }
1175            Ok(t)
1176        }
1177
1178        // Arithmetic decision: discharge an Int equality with the proof-producing
1179        // oracle. The oracle is untrusted — the term it returns is type-checked by
1180        // the kernel (here, by the caller's `infer_type`), so a wrong proof is
1181        // rejected. Proofs are built from computation + the registered ring axioms.
1182        // `(a + 1) ≤ b` ⊢ `a < b`:  le_succ_lt a b p₀.  The converse of `LtSuccLe`, and the
1183        // only route to a strict CONCLUSION about symbolic operands. Certifies against the
1184        // prelude global `le_succ_lt`; while that axiom is unregistered the kernel refuses
1185        // this term, which is why every producer gates on
1186        // `engine::strict_conclusions_available` and none of them builds one today.
1187        InferenceRule::LeSuccLt => {
1188            if tree.premises.len() != 1 {
1189                return Err(KernelError::CertificationError(
1190                    "LeSuccLt requires exactly 1 premise (`a + 1 ≤ b`)".to_string(),
1191                ));
1192            }
1193            let (a, b) = lt_terms(&tree.conclusion)?;
1194            let premise = certify(&tree.premises[0], ctx)?;
1195            let applied = [
1196                proof_term_to_kernel_term(&a)?,
1197                proof_term_to_kernel_term(&b)?,
1198                premise,
1199            ]
1200            .into_iter()
1201            .fold(Term::Global("le_succ_lt".to_string()), |acc, arg| {
1202                Term::App(Box::new(acc), Box::new(arg))
1203            });
1204            Ok(applied)
1205        }
1206
1207        // Linear-order totality: `⊢ (a ≤ b) ∨ (b ≤ a)`.  le_total a b.
1208        // A leaf: the operands come from the CONCLUSION, so a node claiming a disjunction
1209        // that is not an instance of totality certifies to nothing.
1210        InferenceRule::LeTotal => {
1211            if !tree.premises.is_empty() {
1212                return Err(KernelError::CertificationError(
1213                    "LeTotal is a leaf (no premises)".to_string(),
1214                ));
1215            }
1216            let ProofExpr::Or(left, right) = &tree.conclusion else {
1217                return Err(KernelError::CertificationError(format!(
1218                    "LeTotal must conclude a disjunction of two ≤ facts, got {:?}",
1219                    tree.conclusion
1220                )));
1221            };
1222            let (a, b) = le_terms(left)?;
1223            let (b2, a2) = le_terms(right)?;
1224            if a != a2 || b != b2 {
1225                return Err(KernelError::CertificationError(format!(
1226                    "LeTotal must conclude `(a ≤ b) ∨ (b ≤ a)` for ONE pair; got \
1227                     `({a} ≤ {b}) ∨ ({b2} ≤ {a2})`"
1228                )));
1229            }
1230            let ka = proof_term_to_kernel_term(&a)?;
1231            let kb = proof_term_to_kernel_term(&b)?;
1232            Ok(Term::App(
1233                Box::new(Term::App(
1234                    Box::new(Term::Global("le_total".to_string())),
1235                    Box::new(ka),
1236                )),
1237                Box::new(kb),
1238            ))
1239        }
1240
1241        InferenceRule::ArithDecision => match &tree.conclusion {
1242            ProofExpr::Identity(l, r) => {
1243                let kl = proof_term_to_kernel_term(l)?;
1244                let kr = proof_term_to_kernel_term(r)?;
1245                crate::arith::prove_int_eq(ctx.kernel_ctx, &kl, &kr).ok_or_else(|| {
1246                    KernelError::CertificationError(
1247                        "ArithDecision: arithmetic oracle found no proof".to_string(),
1248                    )
1249                })
1250            }
1251            _ => Err(KernelError::CertificationError(
1252                "ArithDecision conclusion must be an Identity".to_string(),
1253            )),
1254        },
1255
1256        // Proof by kernel evaluation: the leaf carries only the claim. Build
1257        // the kernel proposition and its `Decidable` instance, then let
1258        // `native_decide` construct the `of_decide_eq_true`-shaped term — the
1259        // kernel re-checks it (via the `reduceBool` hook), so a false claim
1260        // certifies to nothing.
1261        InferenceRule::NativeDecide => {
1262            if !tree.premises.is_empty() {
1263                return Err(KernelError::CertificationError(
1264                    "NativeDecide is a leaf (no premises)".to_string(),
1265                ));
1266            }
1267            let prop = proof_expr_to_type_ctx(&tree.conclusion, ctx.kernel_ctx)?;
1268            let inst = decidable_instance_for(&prop, ctx.kernel_ctx).ok_or_else(|| {
1269                KernelError::CertificationError(
1270                    "NativeDecide: no Decidable instance for this proposition".to_string(),
1271                )
1272            })?;
1273            logicaffeine_kernel::native_decide(ctx.kernel_ctx, &prop, &inst).ok_or_else(|| {
1274                KernelError::CertificationError(
1275                    "NativeDecide: evaluation did not decide the goal true".to_string(),
1276                )
1277            })
1278        }
1279
1280        // Ground REFUTATION: `¬P` for a closed `P` that computes FALSE. A leaf — the
1281        // claim is re-decided here, in the kernel's own arithmetic, so a lying leaf
1282        // certifies to nothing.
1283        //
1284        // The term is `λ(h : P). <False>`, which is literally `Not P` in its unfolded
1285        // `P → False` form (the shape `proof_expr_to_type` emits for `Not`). How `h`
1286        // becomes `False` depends on the sort of the disequality, and both routes end at
1287        // the SAME `Bool` no-confusion discriminator `LinFalse` already uses:
1288        //
1289        // * `Eq Bool x y` with `x ⇝ false`, `y ⇝ true`: `h` IS `Eq Bool false true` up to
1290        //   computation. The reverse orientation goes through `Eq_sym` first.
1291        // * `Eq Int a b` with `a ⇝ m`, `b ⇝ n`, `m ≠ n`: TRANSPORT the true-by-computation
1292        //   `le a a` along `h` with `Eq_rec`, landing on `le a b` (or `le b a`, whichever
1293        //   the values make false) — a ground-false `Eq Bool … true`, then the
1294        //   discriminator. `Int` has no constructors, so it has no no-confusion of its own;
1295        //   this borrows `Bool`'s, and needs no `of_decide_eq_false` and no `Decidable`
1296        //   instance for `Int` equality (either would be a NEW AXIOM).
1297        InferenceRule::GroundRefutation => {
1298            if !tree.premises.is_empty() {
1299                return Err(KernelError::CertificationError(
1300                    "GroundRefutation is a leaf (no premises)".to_string(),
1301                ));
1302            }
1303            let ProofExpr::Not(inner) = &tree.conclusion else {
1304                return Err(KernelError::CertificationError(format!(
1305                    "GroundRefutation must conclude a negation, got {:?}",
1306                    tree.conclusion
1307                )));
1308            };
1309            let ProofExpr::Identity(l, r) = inner.as_ref() else {
1310                return Err(KernelError::CertificationError(format!(
1311                    "GroundRefutation refutes a ground (dis)equality; got {:?}",
1312                    inner
1313                )));
1314            };
1315            let kl = proof_term_to_kernel_term(l)?;
1316            let kr = proof_term_to_kernel_term(r)?;
1317            // The CONTEXT-FREE domain, deliberately: it is the one the goal type carries
1318            // (`proof_expr_to_type_ctx` delegates a `Not` wholesale to the context-free
1319            // form), and the λ below must have exactly that parameter type.
1320            let domain = identity_domain(l, r);
1321            let nl = logicaffeine_kernel::normalize(ctx.kernel_ctx, &kl);
1322            let nr = logicaffeine_kernel::normalize(ctx.kernel_ctx, &kr);
1323            let hyp_name = ctx.fresh_hyp_name();
1324            let h = Term::Var(hyp_name.clone());
1325            let body = match domain {
1326                "Bool" => match (bool_of_kernel_term(&nl), bool_of_kernel_term(&nr)) {
1327                    (Some(false), Some(true)) => build_bool_discriminator(h),
1328                    (Some(true), Some(false)) => build_bool_discriminator(
1329                        [Term::Global("Bool".to_string()), kl.clone(), kr.clone(), h]
1330                            .into_iter()
1331                            .fold(Term::Global("Eq_sym".to_string()), |acc, arg| {
1332                                Term::App(Box::new(acc), Box::new(arg))
1333                            }),
1334                    ),
1335                    (a, b) => {
1336                        return Err(KernelError::CertificationError(format!(
1337                            "GroundRefutation: `{l} = {r}` does not COMPUTE to two different \
1338                             Bool literals (got {a:?} vs {b:?}), so it is not a ground \
1339                             disequality — decide declines, it never guesses"
1340                        )))
1341                    }
1342                },
1343                "Int" => {
1344                    let (Some(vl), Some(vr)) = (int_of_kernel_term(&nl), int_of_kernel_term(&nr))
1345                    else {
1346                        return Err(KernelError::CertificationError(format!(
1347                            "GroundRefutation: `{l} = {r}` does not COMPUTE to two Int \
1348                             literals, so it is not a ground disequality"
1349                        )));
1350                    };
1351                    if vl == vr {
1352                        return Err(KernelError::CertificationError(format!(
1353                            "GroundRefutation: `{l} = {r}` computes to the SAME integer — the \
1354                             negation is FALSE and must never be certified"
1355                        )));
1356                    }
1357                    // `le` of the two in the order the values make false; `le a a` is true
1358                    // by computation either way, so the transported end is the false one.
1359                    let le = |x: Term, y: Term| {
1360                        Term::App(
1361                            Box::new(Term::App(
1362                                Box::new(Term::Global("le".to_string())),
1363                                Box::new(x),
1364                            )),
1365                            Box::new(y),
1366                        )
1367                    };
1368                    let eq_bool_true = |b: Term| {
1369                        [
1370                            Term::Global("Bool".to_string()),
1371                            b,
1372                            Term::Global("true".to_string()),
1373                        ]
1374                        .into_iter()
1375                        .fold(Term::Global("Eq".to_string()), |acc, arg| {
1376                            Term::App(Box::new(acc), Box::new(arg))
1377                        })
1378                    };
1379                    let z = Term::Var("_ground_z".to_string());
1380                    let motive_body = if vl > vr {
1381                        eq_bool_true(le(kl.clone(), z))
1382                    } else {
1383                        eq_bool_true(le(z, kl.clone()))
1384                    };
1385                    let motive = Term::Lambda {
1386                        param: "_ground_z".to_string(),
1387                        param_type: Box::new(Term::Global("Int".to_string())),
1388                        body: Box::new(motive_body),
1389                    };
1390                    // refl Bool true : Eq Bool true true ≡ motive l (le l l ⇝ true).
1391                    let refl_true = [
1392                        Term::Global("Bool".to_string()),
1393                        Term::Global("true".to_string()),
1394                    ]
1395                    .into_iter()
1396                    .fold(Term::Global("refl".to_string()), |acc, arg| {
1397                        Term::App(Box::new(acc), Box::new(arg))
1398                    });
1399                    let transported = [
1400                        Term::Global("Int".to_string()),
1401                        kl.clone(),
1402                        motive,
1403                        refl_true,
1404                        kr.clone(),
1405                        h,
1406                    ]
1407                    .into_iter()
1408                    .fold(Term::Global("Eq_rec".to_string()), |acc, arg| {
1409                        Term::App(Box::new(acc), Box::new(arg))
1410                    });
1411                    build_bool_discriminator(transported)
1412                }
1413                other => {
1414                    return Err(KernelError::CertificationError(format!(
1415                        "GroundRefutation: no ground refutation route for an `{other}` \
1416                         disequality — only `Int` (via Bool no-confusion after transport) \
1417                         and `Bool` (directly) compute"
1418                    )))
1419                }
1420            };
1421            Ok(Term::Lambda {
1422                param: hyp_name,
1423                param_type: Box::new(proof_expr_to_type(inner)?),
1424                body: Box::new(body),
1425            })
1426        }
1427
1428        // Contradiction: P and ¬P jointly yield ⊥.
1429        // Curry-Howard: ¬P is `P → False`, so applying the proof of ¬P to the
1430        // proof of P gives `False`. We detect which premise is the negation.
1431        InferenceRule::Contradiction => {
1432            if tree.premises.len() != 2 {
1433                return Err(KernelError::CertificationError(
1434                    "Contradiction requires exactly 2 premises (P and ¬P)".to_string(),
1435                ));
1436            }
1437            let a = &tree.premises[0];
1438            let b = &tree.premises[1];
1439            let (pos, neg) = if is_negation_of(&b.conclusion, &a.conclusion) {
1440                (a, b)
1441            } else if is_negation_of(&a.conclusion, &b.conclusion) {
1442                (b, a)
1443            } else {
1444                return Err(KernelError::CertificationError(format!(
1445                    "Contradiction premises are not a proposition and its negation: {:?} vs {:?}",
1446                    a.conclusion, b.conclusion
1447                )));
1448            };
1449            let pos_term = certify(pos, ctx)?;
1450            let neg_term = certify(neg, ctx)?;
1451            // (¬P) P : False
1452            Ok(Term::App(Box::new(neg_term), Box::new(pos_term)))
1453        }
1454
1455        // Reductio ad absurdum: assume P, derive ⊥, conclude ¬P.
1456        // Curry-Howard: λ(h:P). <⊥-proof using h> : P → False = Not P.
1457        // The assumption becomes a local hypothesis available to the ⊥-derivation.
1458        InferenceRule::ReductioAdAbsurdum => {
1459            if tree.premises.len() != 2 {
1460                return Err(KernelError::CertificationError(
1461                    "ReductioAdAbsurdum requires exactly 2 premises (assumption, ⊥-derivation)"
1462                        .to_string(),
1463                ));
1464            }
1465            let assumed = &tree.premises[0].conclusion;
1466            let contradiction = &tree.premises[1];
1467            let hyp_name = ctx.fresh_hyp_name();
1468            let branch_ctx = ctx.with_local_hyp(assumed, &hyp_name);
1469            let body = certify(contradiction, &branch_ctx)?;
1470            Ok(Term::Lambda {
1471                param: hyp_name,
1472                param_type: Box::new(proof_expr_to_type(assumed)?),
1473                body: Box::new(body),
1474            })
1475        }
1476
1477        // Case analysis where both cases reach ⊥. Intuitionistic form, needing
1478        // NO excluded middle: from the C-branch build `¬C : C → False`, from the
1479        // ¬C-branch build `¬¬C : (Not C) → False`, then `(¬¬C) (¬C) : False`.
1480        InferenceRule::CaseAnalysis { case_formula } => {
1481            if tree.premises.len() != 2 {
1482                return Err(KernelError::CertificationError(
1483                    "CaseAnalysis requires exactly 2 premises (C-branch, ¬C-branch)".to_string(),
1484                ));
1485            }
1486            let c = case_formula.as_ref();
1487            let not_c = ProofExpr::Not(Box::new(c.clone()));
1488
1489            let branch_c = unwrap_case_branch(&tree.premises[0]);
1490            let branch_nc = unwrap_case_branch(&tree.premises[1]);
1491
1492            // ¬C : C → False
1493            let h1 = ctx.fresh_hyp_name();
1494            let ctx_c = ctx.with_local_hyp(c, &h1);
1495            let neg_c = Term::Lambda {
1496                param: h1,
1497                param_type: Box::new(proof_expr_to_type(c)?),
1498                body: Box::new(certify(branch_c, &ctx_c)?),
1499            };
1500
1501            // ¬¬C : (Not C) → False  (fresh name distinct from h1)
1502            let h2 = ctx_c.fresh_hyp_name();
1503            let ctx_nc = ctx.with_local_hyp(&not_c, &h2);
1504            let neg_neg_c = Term::Lambda {
1505                param: h2,
1506                param_type: Box::new(proof_expr_to_type(&not_c)?),
1507                body: Box::new(certify(branch_nc, &ctx_nc)?),
1508            };
1509
1510            // (¬¬C) (¬C) : False
1511            Ok(Term::App(Box::new(neg_neg_c), Box::new(neg_c)))
1512        }
1513
1514        // Disjunctive syllogism: from `A ∨ B` and `¬A`, conclude `B` (and the
1515        // mirror `¬B` ⊢ `A`). Curry-Howard, intuitionistically (no excluded
1516        // middle): match the `Or A B` proof. In the branch whose disjunct is
1517        // refuted, apply the negation `Not X = X → False` to the bound proof of
1518        // `X`, obtaining `False`, then eliminate `False` into the goal (a match
1519        // with no cases — `False` has no constructors). The surviving branch
1520        // returns its bound proof, which IS the goal.
1521        InferenceRule::DisjunctionElim => {
1522            if tree.premises.len() != 2 {
1523                return Err(KernelError::CertificationError(
1524                    "DisjunctionElim requires exactly 2 premises (disjunction, negation)"
1525                        .to_string(),
1526                ));
1527            }
1528            let disj_premise = &tree.premises[0];
1529            let neg_premise = &tree.premises[1];
1530
1531            let (left, right) = match &disj_premise.conclusion {
1532                ProofExpr::Or(l, r) => (l.as_ref().clone(), r.as_ref().clone()),
1533                other => {
1534                    return Err(KernelError::CertificationError(format!(
1535                        "DisjunctionElim first premise must conclude a disjunction, got {:?}",
1536                        other
1537                    )))
1538                }
1539            };
1540            let refuted = match &neg_premise.conclusion {
1541                ProofExpr::Not(inner) => inner.as_ref().clone(),
1542                other => {
1543                    return Err(KernelError::CertificationError(format!(
1544                        "DisjunctionElim second premise must conclude a negation, got {:?}",
1545                        other
1546                    )))
1547                }
1548            };
1549
1550            let left_is_refuted = conclusions_match(&refuted, &left);
1551            let right_is_refuted = conclusions_match(&refuted, &right);
1552            if left_is_refuted == right_is_refuted {
1553                return Err(KernelError::CertificationError(format!(
1554                    "DisjunctionElim negation {:?} matches neither (or both) disjuncts of {:?}",
1555                    refuted, disj_premise.conclusion
1556                )));
1557            }
1558
1559            let goal_type = proof_expr_to_type(&tree.conclusion)?;
1560            let disc = certify(disj_premise, ctx)?;
1561            let neg_term = certify(neg_premise, ctx)?;
1562
1563            // CONSTANT motive: pass the goal type raw (see DisjunctionCases) — the kernel
1564            // rebuilds `λ_:disc_type. goal` from the discriminant's `Or` type.
1565            let motive = goal_type.clone();
1566
1567            // A branch that returns its bound proof directly (the surviving
1568            // disjunct equals the goal): λ(__d:D). __d.
1569            let return_case = |disjunct: &ProofExpr, binder: &str| -> KernelResult<Term> {
1570                Ok(Term::Lambda {
1571                    param: binder.to_string(),
1572                    param_type: Box::new(proof_expr_to_type(disjunct)?),
1573                    body: Box::new(Term::Var(binder.to_string())),
1574                })
1575            };
1576            // A branch whose disjunct is refuted: λ(__d:D). False_elim G ((¬D) __d).
1577            let absurd_case = |disjunct: &ProofExpr, binder: &str| -> KernelResult<Term> {
1578                let falsum = Term::App(
1579                    Box::new(neg_term.clone()),
1580                    Box::new(Term::Var(binder.to_string())),
1581                );
1582                let ex_falso = Term::Match {
1583                    discriminant: Box::new(falsum),
1584                    motive: Box::new(Term::Lambda {
1585                        param: "_".to_string(),
1586                        param_type: Box::new(Term::Global("False".to_string())),
1587                        body: Box::new(goal_type.clone()),
1588                    }),
1589                    cases: vec![],
1590                };
1591                Ok(Term::Lambda {
1592                    param: binder.to_string(),
1593                    param_type: Box::new(proof_expr_to_type(disjunct)?),
1594                    body: Box::new(ex_falso),
1595                })
1596            };
1597
1598            let left_case = if left_is_refuted {
1599                absurd_case(&left, "__dl")?
1600            } else {
1601                return_case(&left, "__dl")?
1602            };
1603            let right_case = if right_is_refuted {
1604                absurd_case(&right, "__dr")?
1605            } else {
1606                return_case(&right, "__dr")?
1607            };
1608
1609            Ok(Term::Match {
1610                discriminant: Box::new(disc),
1611                motive: Box::new(motive),
1612                cases: vec![left_case, right_case],
1613            })
1614        }
1615
1616        // Disjunction elimination to a COMMON conclusion (here always ⊥): from
1617        // `A ∨ B`, a proof of the goal assuming `A`, and a proof assuming `B`,
1618        // Curry-Howard matches the `Or` and runs the matching branch. Each branch
1619        // binds its disjunct — and, when the disjunct is a conjunction, each
1620        // conjunct (recovered by ∧-elimination, as in `ExistentialElim`) — as a
1621        // local hypothesis, so the branch proof may cite them directly. This is the
1622        // case analysis a grid's of-pair / either-or / closure clause needs, and it
1623        // is intuitionistic (no excluded middle).
1624        InferenceRule::DisjunctionCases => {
1625            if tree.premises.len() != 3 {
1626                return Err(KernelError::CertificationError(
1627                    "DisjunctionCases requires exactly 3 premises (disjunction, A-branch, B-branch)"
1628                        .to_string(),
1629                ));
1630            }
1631            let disj_premise = &tree.premises[0];
1632            let (left, right) = match &disj_premise.conclusion {
1633                ProofExpr::Or(l, r) => (l.as_ref().clone(), r.as_ref().clone()),
1634                other => {
1635                    return Err(KernelError::CertificationError(format!(
1636                        "DisjunctionCases first premise must conclude a disjunction, got {:?}",
1637                        other
1638                    )))
1639                }
1640            };
1641            let disc = certify(disj_premise, ctx)?;
1642            // CONSTANT motive (the goal is independent of which disjunct held): pass the
1643            // goal TYPE raw and let the kernel synthesize `λ_:disc_type. goal` from the
1644            // discriminant's `Or` type. This keeps the large, left-nested `Or` OUT of the
1645            // emitted term at EVERY nested case split — the O(n²) certification blowup.
1646            let motive = proof_expr_to_type_ctx(&tree.conclusion, ctx.kernel_ctx)?;
1647
1648            let build_arm = |disjunct: &ProofExpr,
1649                             branch: &DerivationTree,
1650                             binder: &str|
1651             -> KernelResult<Term> {
1652                let h_var = Term::Var(binder.to_string());
1653                let mut bctx = ctx.with_local_hyp_term(disjunct, h_var.clone());
1654                for (conjunct, proj) in collect_conjunct_hyps(disjunct, &h_var)? {
1655                    bctx = bctx.with_local_hyp_term(&conjunct, proj);
1656                }
1657                let body = certify(branch, &bctx)?;
1658                Ok(Term::Lambda {
1659                    param: binder.to_string(),
1660                    param_type: Box::new(proof_expr_to_type(disjunct)?),
1661                    body: Box::new(body),
1662                })
1663            };
1664
1665            // FRESH binder names (`_hyp{depth}`), not fixed `__dcl`/`__dcr`: a branch
1666            // may itself contain a nested case-analysis, and a reused name would let the
1667            // inner binder CAPTURE an outer disjunct hypothesis in the kernel term (a
1668            // leaf citing the outer disjunct resolves to the inner λ of the wrong type).
1669            let lname = ctx.fresh_hyp_name();
1670            let rname = ctx.fresh_hyp_name();
1671            let left_case = build_arm(&left, &tree.premises[1], &lname)?;
1672            let right_case = build_arm(&right, &tree.premises[2], &rname)?;
1673
1674            Ok(Term::Match {
1675                discriminant: Box::new(disc),
1676                motive: Box::new(motive),
1677                cases: vec![left_case, right_case],
1678            })
1679        }
1680
1681        // Biconditional introduction (↔I): `conj (P→Q) (Q→P) <pq> <qp>` — the pair of
1682        // direction proofs combined, matching the `Iff ≡ And (P→Q) (Q→P)` encoding.
1683        InferenceRule::BicondIntro => {
1684            if tree.premises.len() != 2 {
1685                return Err(KernelError::CertificationError(
1686                    "BicondIntro requires exactly 2 premises (P→Q, Q→P)".to_string(),
1687                ));
1688            }
1689            let (p, q) = match &tree.conclusion {
1690                ProofExpr::Iff(p, q) => (p.as_ref().clone(), q.as_ref().clone()),
1691                other => {
1692                    return Err(KernelError::CertificationError(format!(
1693                        "BicondIntro conclusion must be a biconditional, got {:?}",
1694                        other
1695                    )))
1696                }
1697            };
1698            let pq_type = proof_expr_to_type(&ProofExpr::Implies(
1699                Box::new(p.clone()),
1700                Box::new(q.clone()),
1701            ))?;
1702            let qp_type = proof_expr_to_type(&ProofExpr::Implies(Box::new(q), Box::new(p)))?;
1703            let pq_proof = certify(&tree.premises[0], ctx)?;
1704            let qp_proof = certify(&tree.premises[1], ctx)?;
1705            Ok(Term::App(
1706                Box::new(Term::App(
1707                    Box::new(Term::App(
1708                        Box::new(Term::App(
1709                            Box::new(Term::Global("conj".to_string())),
1710                            Box::new(pq_type),
1711                        )),
1712                        Box::new(qp_type),
1713                    )),
1714                    Box::new(pq_proof),
1715                )),
1716                Box::new(qp_proof),
1717            ))
1718        }
1719
1720        // Double-negation introduction (constructive): P ⊢ ¬¬P. With `¬X ≡ X→False`,
1721        // `¬¬P = (P→False)→False`, proved by `λ(hnp:¬P). hnp p`.
1722        InferenceRule::DoubleNegation => {
1723            if tree.premises.len() != 1 {
1724                return Err(KernelError::CertificationError(
1725                    "DoubleNegation requires exactly 1 premise (a proof of P)".to_string(),
1726                ));
1727            }
1728            let p = match &tree.conclusion {
1729                ProofExpr::Not(inner) => match inner.as_ref() {
1730                    ProofExpr::Not(core) => core.as_ref().clone(),
1731                    other => {
1732                        return Err(KernelError::CertificationError(format!(
1733                            "DoubleNegation conclusion must be ¬¬P, got ¬{:?}",
1734                            other
1735                        )))
1736                    }
1737                },
1738                other => {
1739                    return Err(KernelError::CertificationError(format!(
1740                        "DoubleNegation conclusion must be ¬¬P, got {:?}",
1741                        other
1742                    )))
1743                }
1744            };
1745            let p_type = proof_expr_to_type(&p)?;
1746            let p_proof = certify(&tree.premises[0], ctx)?;
1747            let not_p_type = Term::Pi {
1748                param: "_".to_string(),
1749                param_type: Box::new(p_type),
1750                body_type: Box::new(Term::Global("False".to_string())),
1751            };
1752            let hnp = "__dn_hnp".to_string();
1753            Ok(Term::Lambda {
1754                param: hnp.clone(),
1755                param_type: Box::new(not_p_type),
1756                body: Box::new(Term::App(Box::new(Term::Var(hnp)), Box::new(p_proof))),
1757            })
1758        }
1759
1760        // Classical reductio: assume ¬G, derive ⊥, conclude G via the `dne` axiom.
1761        // Build `dne G (λ(hng:¬G). <⊥-proof>)`, where `λ(hng:¬G). ⊥ : ¬¬G`.
1762        InferenceRule::ClassicalReductio => {
1763            if tree.premises.len() != 1 {
1764                return Err(KernelError::CertificationError(
1765                    "ClassicalReductio requires exactly 1 premise (a proof of False)".to_string(),
1766                ));
1767            }
1768            let g = tree.conclusion.clone();
1769            let g_type = proof_expr_to_type(&g)?;
1770            let neg_g = ProofExpr::Not(Box::new(g));
1771            let neg_g_type = proof_expr_to_type(&neg_g)?; // G → False
1772            let binder = ctx.fresh_hyp_name();
1773            let bctx = ctx.with_local_hyp_term(&neg_g, Term::Var(binder.clone()));
1774            let false_proof = certify(&tree.premises[0], &bctx)?;
1775            let nn_g = Term::Lambda {
1776                param: binder,
1777                param_type: Box::new(neg_g_type),
1778                body: Box::new(false_proof),
1779            };
1780            Ok(Term::App(
1781                Box::new(Term::App(
1782                    Box::new(Term::Global("dne".to_string())),
1783                    Box::new(g_type),
1784                )),
1785                Box::new(nn_g),
1786            ))
1787        }
1788
1789        // Implication introduction (→I): `λ(hp:P). <Q-proof>`, binding the antecedent
1790        // P as a local hypothesis the consequent proof may cite — and, when P is a
1791        // conjunction, each conjunct by ∧-elimination (same as DisjunctionCases).
1792        InferenceRule::ImpliesIntro => {
1793            if tree.premises.len() != 1 {
1794                return Err(KernelError::CertificationError(
1795                    "ImpliesIntro requires exactly 1 premise (the consequent proof)".to_string(),
1796                ));
1797            }
1798            let ant = match &tree.conclusion {
1799                ProofExpr::Implies(a, _) => a.as_ref().clone(),
1800                // `¬p` IS `p → False`: `proof_expr_to_type` lowers both to `Π(_:p). False`, so a
1801                // negation goal is discharged by exactly the same λ. Only this structural match
1802                // ever told them apart, which is why `intro` on a negation had no image.
1803                ProofExpr::Not(a) => a.as_ref().clone(),
1804                other => {
1805                    return Err(KernelError::CertificationError(format!(
1806                        "ImpliesIntro conclusion must be an implication or a negation, got {:?}",
1807                        other
1808                    )))
1809                }
1810            };
1811            let binder = ctx.fresh_hyp_name();
1812            let h_var = Term::Var(binder.clone());
1813            let mut bctx = ctx.with_local_hyp_term(&ant, h_var.clone());
1814            for (conjunct, proj) in collect_conjunct_hyps(&ant, &h_var)? {
1815                bctx = bctx.with_local_hyp_term(&conjunct, proj);
1816            }
1817            let body = certify(&tree.premises[0], &bctx)?;
1818            Ok(Term::Lambda {
1819                param: binder,
1820                param_type: Box::new(proof_expr_to_type(&ant)?),
1821                body: Box::new(body),
1822            })
1823        }
1824
1825        // Conjunction elimination: from a proof of `A ∧ B`, recover the conjunct
1826        // (`A` or `B`, whichever the conclusion names) by `∧`-elimination.
1827        InferenceRule::ConjunctionElim => {
1828            if tree.premises.len() != 1 {
1829                return Err(KernelError::CertificationError(
1830                    "ConjunctionElim requires exactly 1 premise (the conjunction)".to_string(),
1831                ));
1832            }
1833            let conj_premise = &tree.premises[0];
1834            let (a, b) = match &conj_premise.conclusion {
1835                ProofExpr::And(l, r) => (l.as_ref().clone(), r.as_ref().clone()),
1836                // Iff P Q ≡ And (P → Q) (Q → P) in the kernel encoding, so an
1837                // Iff premise projects to either implication.
1838                ProofExpr::Iff(l, r) => (
1839                    ProofExpr::Implies(l.clone(), r.clone()),
1840                    ProofExpr::Implies(r.clone(), l.clone()),
1841                ),
1842                other => {
1843                    return Err(KernelError::CertificationError(format!(
1844                        "ConjunctionElim premise must conclude a conjunction, got {:?}",
1845                        other
1846                    )))
1847                }
1848            };
1849            let take_left = conclusions_match(&tree.conclusion, &a);
1850            if !take_left && !conclusions_match(&tree.conclusion, &b) {
1851                return Err(KernelError::CertificationError(format!(
1852                    "ConjunctionElim conclusion {:?} matches neither conjunct of {:?}",
1853                    tree.conclusion, conj_premise.conclusion
1854                )));
1855            }
1856            let disc = certify(conj_premise, ctx)?;
1857            let left_type = proof_expr_to_type(&a)?;
1858            let right_type = proof_expr_to_type(&b)?;
1859            Ok(project_conjunct(&disc, &left_type, &right_type, take_left))
1860        }
1861
1862        // Z3 oracle results are deliberately NOT certifiable. The oracle attests
1863        // *satisfiability* but hands back no checkable proof term — so it can
1864        // never be turned into a kernel certificate, and a goal discharged only
1865        // by the oracle is reported as unverified by the trusted door. (For
1866        // arithmetic, the proof-producing `ArithDecision` path yields a real
1867        // certificate instead.) Making this explicit keeps Z3 firmly outside the
1868        // trusted base.
1869        InferenceRule::OracleVerification(detail) => Err(KernelError::CertificationError(format!(
1870            "oracle (Z3) results are not kernel-certifiable — they attest \
1871             satisfiability but produce no checkable proof term ({})",
1872            detail
1873        ))),
1874
1875        // The seven DECLARED-BUT-DEAD rules: modal access / generalization and the
1876        // five temporal ones. Each names a proof shape that has a perfectly good
1877        // translation into rules above, and none of them has ever had an arm here.
1878        //
1879        // This arm exists so the refusal is DELIBERATE. Reaching it through a
1880        // catch-all produced "Certification not implemented for X", which reads like
1881        // a kernel limitation and invites a producer to retry, widen its search, or
1882        // blame the input — when the truth is that the tree it built was never
1883        // certifiable and must be rebuilt out of live rules. The message therefore
1884        // names the variant, says no arm exists, and states the live translation
1885        // ([`InferenceRule::uncertifiable_reason`] carries the per-rule advice).
1886        //
1887        // The match is EXHAUSTIVE — there is no `_` arm — so a forty-seventh variant
1888        // cannot be added to `InferenceRule` without a decision here, which is the
1889        // only thing that keeps the enum and this dispatch from drifting apart.
1890        rule @ (InferenceRule::ModalAccess
1891        | InferenceRule::ModalGeneralization
1892        | InferenceRule::TemporalTransitivity
1893        | InferenceRule::TemporalInduction
1894        | InferenceRule::TemporalUnfolding
1895        | InferenceRule::EventualityProgress
1896        | InferenceRule::UntilInduction) => Err(KernelError::CertificationError(format!(
1897            "E_DEAD_INFERENCE_RULE: {:?} — {}. This derivation was never certifiable: \
1898             rebuild it from live rules, or reject the input. Do not report this as the \
1899             kernel refusing a proof.",
1900            rule,
1901            rule.uncertifiable_reason()
1902                .expect("a dead rule states why it is dead")
1903        ))),
1904    }
1905}
1906
1907/// Whether `neg` is syntactically the negation of `pos` (i.e. `neg = ¬pos`).
1908fn is_negation_of(neg: &ProofExpr, pos: &ProofExpr) -> bool {
1909    matches!(neg, ProofExpr::Not(inner) if inner.as_ref() == pos)
1910}
1911
1912/// Unwrap a case-analysis branch. The engine wraps each branch's ⊥-derivation
1913/// in a trivial `PremiseMatch(⊥)` node with a single child; the real proof is
1914/// that child. Any other shape is returned as-is.
1915fn unwrap_case_branch(tree: &DerivationTree) -> &DerivationTree {
1916    if matches!(tree.rule, InferenceRule::PremiseMatch) && tree.premises.len() == 1 {
1917        &tree.premises[0]
1918    } else {
1919        tree
1920    }
1921}
1922
1923/// Build the equality predicate for rewriting.
1924/// Given goal P(y) and term y, extracts P.
1925///
1926/// For simple predicates like `mortal(Superman)`, returns `mortal` directly.
1927/// For complex goals, builds `λz. (goal with y replaced by z)`.
1928fn build_equality_predicate(
1929    goal: &ProofExpr,
1930    replace_term: &ProofTerm,
1931    kctx: &Context,
1932) -> KernelResult<Term> {
1933    // Simple case: if the goal is P(y), just use P as the predicate
1934    // This avoids the beta-reduction issue with (λz. P(z)) x
1935    if let ProofExpr::Predicate { name, args, .. } = goal {
1936        if args.len() == 1 && &args[0] == replace_term {
1937            return Ok(Term::Global(name.clone()));
1938        }
1939    }
1940
1941    // General case: build λz. (goal with replace_term replaced by z). Resolve the goal's equality
1942    // domain against ctx so a bare `Int`-sequence goal reads as `Eq Int`, matching the `Eq_rec` domain.
1943    let goal_type = proof_expr_to_type_ctx(goal, kctx)?;
1944    let param_name = "_eq_var".to_string();
1945    let substituted = substitute_term_in_kernel(
1946        &goal_type,
1947        &proof_term_to_kernel_term(replace_term)?,
1948        &Term::Var(param_name.clone()),
1949    );
1950
1951    Ok(Term::Lambda {
1952        param: param_name,
1953        // The bound variable replaces `replace_term`, so it has that term's domain — resolved
1954        // against ctx so a declared `_ → Int` function (or `Int` constant) reads as Int,
1955        // matching the Eq_rec domain.
1956        param_type: Box::new(Term::Global(resolved_domain(replace_term, kctx))),
1957        body: Box::new(substituted),
1958    })
1959}
1960
1961/// Like [`build_equality_predicate`] but abstracting exactly ONE occurrence of
1962/// `replace_term` — the `occurrence`-th, counted left to right in a pre-order walk of the
1963/// kernel term.
1964///
1965/// The walk order is the one the tactic layer counts in: an application's function before
1966/// its argument, so a predicate's arguments and an equality's two sides come out
1967/// left-to-right; a matched subterm is NOT descended into (it is replaced whole), exactly as
1968/// the all-occurrences [`substitute_term_in_kernel`] does. The two counters agree on the
1969/// LEFTMOST occurrence for every shape, which is the one `ProofState::rewrite` uses; for a
1970/// deeper index they can differ where one `ProofExpr` node expands to several kernel
1971/// positions (`Iff` becomes a pair of `Pi`s), and the kernel is the check — a motive the
1972/// source subgoal does not inhabit is refused, never believed.
1973fn build_equality_predicate_at(
1974    goal: &ProofExpr,
1975    replace_term: &ProofTerm,
1976    occurrence: usize,
1977    kctx: &Context,
1978) -> KernelResult<Term> {
1979    let goal_type = proof_expr_to_type_ctx(goal, kctx)?;
1980    let param_name = "_eq_var".to_string();
1981    let from = proof_term_to_kernel_term(replace_term)?;
1982    let mut seen = 0usize;
1983    let substituted = substitute_nth_in_kernel(
1984        &goal_type,
1985        &from,
1986        &Term::Var(param_name.clone()),
1987        occurrence,
1988        &mut seen,
1989    );
1990    if seen <= occurrence {
1991        return Err(KernelError::CertificationError(format!(
1992            "RewriteAt names occurrence {occurrence} of `{replace_term}`, but the goal has \
1993             only {seen}"
1994        )));
1995    }
1996    Ok(Term::Lambda {
1997        param: param_name,
1998        param_type: Box::new(Term::Global(resolved_domain(replace_term, kctx))),
1999        body: Box::new(substituted),
2000    })
2001}
2002
2003/// Replace the `target`-th occurrence of `from` in `term` with `to`, counting every
2004/// occurrence into `seen` (so the caller can tell "there is no such occurrence" from
2005/// "there is, and here it is"). Pre-order, function before argument.
2006fn substitute_nth_in_kernel(
2007    term: &Term,
2008    from: &Term,
2009    to: &Term,
2010    target: usize,
2011    seen: &mut usize,
2012) -> Term {
2013    if term == from {
2014        let here = *seen;
2015        *seen += 1;
2016        return if here == target {
2017            to.clone()
2018        } else {
2019            term.clone()
2020        };
2021    }
2022    let mut go = |t: &Term, seen: &mut usize| substitute_nth_in_kernel(t, from, to, target, seen);
2023    match term {
2024        Term::App(f, a) => {
2025            let f2 = go(f, seen);
2026            let a2 = go(a, seen);
2027            Term::App(Box::new(f2), Box::new(a2))
2028        }
2029        Term::Pi {
2030            param,
2031            param_type,
2032            body_type,
2033        } => {
2034            let p2 = go(param_type, seen);
2035            let b2 = go(body_type, seen);
2036            Term::Pi {
2037                param: param.clone(),
2038                param_type: Box::new(p2),
2039                body_type: Box::new(b2),
2040            }
2041        }
2042        Term::Lambda {
2043            param,
2044            param_type,
2045            body,
2046        } => {
2047            let p2 = go(param_type, seen);
2048            let b2 = go(body, seen);
2049            Term::Lambda {
2050                param: param.clone(),
2051                param_type: Box::new(p2),
2052                body: Box::new(b2),
2053            }
2054        }
2055        Term::Match {
2056            discriminant,
2057            motive,
2058            cases,
2059        } => {
2060            let d2 = go(discriminant, seen);
2061            let m2 = go(motive, seen);
2062            let mut cs = Vec::with_capacity(cases.len());
2063            for c in cases {
2064                cs.push(go(c, seen));
2065            }
2066            Term::Match {
2067                discriminant: Box::new(d2),
2068                motive: Box::new(m2),
2069                cases: cs,
2070            }
2071        }
2072        other => other.clone(),
2073    }
2074}
2075
2076/// The `Bool` literal a normalized kernel term denotes, if it is one.
2077fn bool_of_kernel_term(t: &Term) -> Option<bool> {
2078    match t {
2079        Term::Global(g) if g == "true" => Some(true),
2080        Term::Global(g) if g == "false" => Some(false),
2081        _ => None,
2082    }
2083}
2084
2085/// The exact integer a normalized kernel term denotes, if it is an integer literal.
2086/// Arbitrary precision: a `BigInt` literal is a number here, not an opaque atom.
2087fn int_of_kernel_term(t: &Term) -> Option<logicaffeine_base::BigInt> {
2088    match t {
2089        Term::Lit(lit) => logicaffeine_kernel::lit_bigint(lit),
2090        _ => None,
2091    }
2092}
2093
2094/// The kernel DOMAIN of an `∃`-bound variable, read off how the body uses it.
2095///
2096/// `Exists` used to lower to `Ex Entity (λx:Entity. …)` unconditionally, which is right for
2097/// the first-order default and WRONG the moment the body is arithmetic: `∃m. m = n + 1`
2098/// became `Ex Entity (λm:Entity. Eq Int m (add n 1))`, whose body is not even well-typed —
2099/// `Eq Int` demands an `Int`. So a compound arithmetic witness could not be certified for a
2100/// reason that had nothing to do with the witness.
2101///
2102/// One function answers it for both sides of the trust door: [`proof_expr_to_type`] builds
2103/// the binder with it, and the tactic layer stamps the same answer into
2104/// [`InferenceRule::ExistentialIntroTerm`]'s `witness_type`, which the certifier then
2105/// re-derives and compares. Only a NON-`Entity` constraint overrides the default, so every
2106/// existing entity-domain existential is unchanged.
2107pub(crate) fn existential_domain(variable: &str, body: &ProofExpr) -> String {
2108    let mut found: Option<String> = None;
2109    binder_sort_from_expr(variable, body, &mut found);
2110    found.unwrap_or_else(|| "Entity".to_string())
2111}
2112
2113fn is_named_var(t: &ProofTerm, name: &str) -> bool {
2114    matches!(t, ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == name)
2115}
2116
2117/// Record the sort `variable` is forced into by one expression, if any. `Bool` beats `Int`
2118/// beats nothing, mirroring [`identity_domain`]'s precedence.
2119fn binder_sort_from_expr(variable: &str, e: &ProofExpr, found: &mut Option<String>) {
2120    fn note(d: &str, found: &mut Option<String>) {
2121        if d != "Entity" && (found.is_none() || d == "Bool") {
2122            *found = Some(d.to_string());
2123        }
2124    }
2125    match e {
2126        // An EXPLICIT type annotation wins outright — it is what the search already stamps
2127        // into `ExistentialIntro`'s `witness_type` (`extract_type_from_exists_body`), so
2128        // reading it here is what makes the goal type and the certificate agree on `Ex Nat`.
2129        ProofExpr::TypedVar { name, typename } if name == variable => {
2130            *found = Some(typename.clone());
2131        }
2132        // An operand of an equality has the equality's own domain: `m = n + 1` types `m`
2133        // `Int`, because that is exactly the `Eq` the goal type will carry.
2134        ProofExpr::Identity(l, r) => {
2135            if is_named_var(l, variable) || is_named_var(r, variable) {
2136                note(identity_domain(l, r), found);
2137            }
2138            binder_sort_from_term(variable, l, found);
2139            binder_sort_from_term(variable, r, found);
2140        }
2141        ProofExpr::Predicate { args, .. } => {
2142            for a in args {
2143                binder_sort_from_term(variable, a, found);
2144            }
2145        }
2146        ProofExpr::And(l, r)
2147        | ProofExpr::Or(l, r)
2148        | ProofExpr::Implies(l, r)
2149        | ProofExpr::Iff(l, r) => {
2150            binder_sort_from_expr(variable, l, found);
2151            binder_sort_from_expr(variable, r, found);
2152        }
2153        ProofExpr::Not(p) | ProofExpr::Temporal { body: p, .. } => {
2154            binder_sort_from_expr(variable, p, found)
2155        }
2156        // A nested binder of the SAME name shadows ours: beneath it the occurrences are a
2157        // different variable and say nothing about our domain.
2158        ProofExpr::ForAll { variable: v, body } | ProofExpr::Exists { variable: v, body } => {
2159            if v != variable {
2160                binder_sort_from_expr(variable, body, found);
2161            }
2162        }
2163        _ => {}
2164    }
2165}
2166
2167/// A DIRECT argument of an arithmetic or comparison builtin is an `Int`.
2168fn binder_sort_from_term(variable: &str, t: &ProofTerm, found: &mut Option<String>) {
2169    if let ProofTerm::Function(name, args) = t {
2170        let arith = is_arith_builtin(name);
2171        for a in args {
2172            if arith && is_named_var(a, variable) && found.is_none() {
2173                *found = Some("Int".to_string());
2174            }
2175            binder_sort_from_term(variable, a, found);
2176        }
2177    }
2178}
2179
2180/// Substitute a kernel term for another in a kernel Term.
2181fn substitute_term_in_kernel(term: &Term, from: &Term, to: &Term) -> Term {
2182    if term == from {
2183        return to.clone();
2184    }
2185    match term {
2186        Term::App(f, a) => Term::App(
2187            Box::new(substitute_term_in_kernel(f, from, to)),
2188            Box::new(substitute_term_in_kernel(a, from, to)),
2189        ),
2190        Term::Pi {
2191            param,
2192            param_type,
2193            body_type,
2194        } => Term::Pi {
2195            param: param.clone(),
2196            param_type: Box::new(substitute_term_in_kernel(param_type, from, to)),
2197            body_type: Box::new(substitute_term_in_kernel(body_type, from, to)),
2198        },
2199        Term::Lambda {
2200            param,
2201            param_type,
2202            body,
2203        } => Term::Lambda {
2204            param: param.clone(),
2205            param_type: Box::new(substitute_term_in_kernel(param_type, from, to)),
2206            body: Box::new(substitute_term_in_kernel(body, from, to)),
2207        },
2208        Term::Match {
2209            discriminant,
2210            motive,
2211            cases,
2212        } => Term::Match {
2213            discriminant: Box::new(substitute_term_in_kernel(discriminant, from, to)),
2214            motive: Box::new(substitute_term_in_kernel(motive, from, to)),
2215            cases: cases
2216                .iter()
2217                .map(|c| substitute_term_in_kernel(c, from, to))
2218                .collect(),
2219        },
2220        Term::Fix { name, body } => Term::Fix {
2221            name: name.clone(),
2222            body: Box::new(substitute_term_in_kernel(body, from, to)),
2223        },
2224        other => other.clone(),
2225    }
2226}
2227
2228/// Eliminate an `And A B` proof `disc` to recover one conjunct.
2229///
2230/// Builds `match disc return C with conj => λ(__l:A).λ(__r:B). __x`
2231/// (a CONSTANT motive — the kernel re-derives `λ_:And A B. C` from `disc`'s type)
2232/// where `C` is the chosen conjunct's type and `__x` is the corresponding bound
2233/// proof. This is genuine ∧-elimination — `And` is the inductive with the single
2234/// constructor `conj : Π P Q. P → Q → And P Q`, so the singleton-eliminator match
2235/// is total and the recovered term has exactly the conjunct's type.
2236fn project_conjunct(disc: &Term, left_type: &Term, right_type: &Term, take_left: bool) -> Term {
2237    let chosen = if take_left { left_type } else { right_type };
2238    let result = if take_left { "__l" } else { "__r" };
2239    let case = Term::Lambda {
2240        param: "__l".to_string(),
2241        param_type: Box::new(left_type.clone()),
2242        body: Box::new(Term::Lambda {
2243            param: "__r".to_string(),
2244            param_type: Box::new(right_type.clone()),
2245            body: Box::new(Term::Var(result.to_string())),
2246        }),
2247    };
2248    Term::Match {
2249        discriminant: Box::new(disc.clone()),
2250        // CONSTANT motive: pass the chosen conjunct's type raw; the kernel synthesizes
2251        // `λ_:disc_type. C` from the discriminant's own `And A B` type (type_checker's
2252        // Match arm wraps a Sort-typed motive automatically), keeping the conjunction
2253        // — which carries the of-pair's nested XOR — OUT of the emitted term.
2254        motive: Box::new(chosen.clone()),
2255        cases: vec![case],
2256    }
2257}
2258
2259/// Collect each leaf conjunct of `expr` paired with a kernel term that proves it,
2260/// derived from `witness` (a proof of `proof_expr_to_type(expr)`). A non-`And`
2261/// proposition is its own single leaf, proved directly by `witness`. An
2262/// `And(l, r)` yields the leaves of `l` (proved by projecting `l` out of
2263/// `witness`) followed by the leaves of `r` (projecting `r`). This mirrors the
2264/// engine's `flatten_conjunction`, so the body proof — which references the
2265/// flattened conjuncts as separate premises — finds each one as a local
2266/// hypothesis backed by a sound ∧-elimination.
2267fn collect_conjunct_hyps(expr: &ProofExpr, witness: &Term) -> KernelResult<Vec<(ProofExpr, Term)>> {
2268    match expr {
2269        ProofExpr::And(l, r) => {
2270            let left_type = proof_expr_to_type(l)?;
2271            let right_type = proof_expr_to_type(r)?;
2272
2273            let left_proj = project_conjunct(witness, &left_type, &right_type, true);
2274            let right_proj = project_conjunct(witness, &left_type, &right_type, false);
2275
2276            let mut hyps = collect_conjunct_hyps(l, &left_proj)?;
2277            hyps.extend(collect_conjunct_hyps(r, &right_proj)?);
2278            Ok(hyps)
2279        }
2280        _ => Ok(vec![(expr.clone(), witness.clone())]),
2281    }
2282}
2283
2284/// Certify a hypothesis reference (Axiom or PremiseMatch).
2285fn certify_hypothesis(conclusion: &ProofExpr, ctx: &CertificationContext) -> KernelResult<Term> {
2286    // Check if this is an IH reference (MUST check first!)
2287    if let Some(ih_term) = ctx.get_ih_term(conclusion) {
2288        return Ok(ih_term);
2289    }
2290
2291    // A locally-assumed proposition (from reductio / case analysis) resolves to
2292    // its bound variable, regardless of the proposition's shape.
2293    if let Some(hyp) = ctx.get_local_hyp(conclusion) {
2294        return Ok(hyp);
2295    }
2296
2297    match conclusion {
2298        ProofExpr::Atom(name) => {
2299            // Check locals first (for lambda-bound variables)
2300            if ctx.is_local(name) {
2301                return Ok(Term::Var(name.clone()));
2302            }
2303            // Then check globals
2304            if ctx.kernel_ctx.get_global(name).is_some() {
2305                Ok(Term::Global(name.clone()))
2306            } else {
2307                Err(KernelError::CertificationError(format!(
2308                    "Unknown hypothesis: {}",
2309                    name
2310                )))
2311            }
2312        }
2313        // For predicate hypotheses, look up by type in kernel context
2314        ProofExpr::Predicate { name, args, .. } => {
2315            // Build the target type: P(a, b, ...) as nested application. Entity-position
2316            // lowering (predicate arguments are entities) so the lookup type matches the
2317            // hypothesis as registered — a numeric label `2004` is `Global`, not `Int`.
2318            let mut target_type = Term::Global(name.clone());
2319            for arg in args {
2320                let arg_term = proof_term_to_kernel_term_entity(arg)?;
2321                target_type = Term::App(Box::new(target_type), Box::new(arg_term));
2322            }
2323
2324            // Search declarations for one with matching type
2325            for (decl_name, decl_type) in ctx.kernel_ctx.iter_declarations() {
2326                if types_structurally_match(&target_type, decl_type) {
2327                    return Ok(Term::Global(decl_name.to_string()));
2328                }
2329            }
2330
2331            Err(KernelError::CertificationError(format!(
2332                "Cannot find hypothesis with type: {:?}",
2333                conclusion
2334            )))
2335        }
2336        // Any other proposition (ForAll, Implies, Identity, Not, Or, And, …):
2337        // convert to its kernel type and look it up among the registered
2338        // hypotheses by structural match.
2339        _ => {
2340            // Context-aware so a `∀`-premise registered with a `Nat` binder (induction)
2341            // is found — its lookup type must match the binder domain it was declared with.
2342            let target_type = proof_expr_to_type_ctx(conclusion, ctx.kernel_ctx).map_err(|_| {
2343                KernelError::CertificationError(format!(
2344                    "Cannot certify hypothesis: {:?}",
2345                    conclusion
2346                ))
2347            })?;
2348
2349            for (name, decl_type) in ctx.kernel_ctx.iter_declarations() {
2350                if types_structurally_match(&target_type, decl_type) {
2351                    return Ok(Term::Global(name.to_string()));
2352                }
2353            }
2354
2355            Err(KernelError::CertificationError(format!(
2356                "Cannot find hypothesis with type matching: {:?}",
2357                conclusion
2358            )))
2359        }
2360    }
2361}
2362
2363/// Check if two kernel terms are alpha-equivalent.
2364/// Two terms are alpha-equivalent if they are the same up to renaming of bound variables.
2365fn types_structurally_match(a: &Term, b: &Term) -> bool {
2366    // Use a helper with a mapping from bound vars in a to bound vars in b
2367    types_alpha_equiv(a, b, &mut Vec::new())
2368}
2369
2370/// Check alpha-equivalence with a mapping of bound variable pairs.
2371/// `bindings` tracks pairs of corresponding bound variable names.
2372fn types_alpha_equiv(a: &Term, b: &Term, bindings: &mut Vec<(String, String)>) -> bool {
2373    match (a, b) {
2374        (Term::Sort(u1), Term::Sort(u2)) => u1 == u2,
2375        (Term::Var(v1), Term::Var(v2)) => {
2376            // Check if these are corresponding bound variables
2377            for (bound_a, bound_b) in bindings.iter().rev() {
2378                if v1 == bound_a {
2379                    return v2 == bound_b;
2380                }
2381                if v2 == bound_b {
2382                    return false; // v2 is bound but v1 doesn't match
2383                }
2384            }
2385            // Both are free variables - must have same name
2386            v1 == v2
2387        }
2388        (Term::Global(g1), Term::Global(g2)) => g1 == g2,
2389        (Term::Lit(l1), Term::Lit(l2)) => l1 == l2,
2390        (Term::App(f1, a1), Term::App(f2, a2)) => {
2391            types_alpha_equiv(f1, f2, bindings) && types_alpha_equiv(a1, a2, bindings)
2392        }
2393        (
2394            Term::Pi {
2395                param: p1,
2396                param_type: pt1,
2397                body_type: bt1,
2398            },
2399            Term::Pi {
2400                param: p2,
2401                param_type: pt2,
2402                body_type: bt2,
2403            },
2404        ) => {
2405            // Parameter types must match in current scope
2406            if !types_alpha_equiv(pt1, pt2, bindings) {
2407                return false;
2408            }
2409            // Body types must match with the new binding
2410            bindings.push((p1.clone(), p2.clone()));
2411            let result = types_alpha_equiv(bt1, bt2, bindings);
2412            bindings.pop();
2413            result
2414        }
2415        (
2416            Term::Lambda {
2417                param: p1,
2418                param_type: pt1,
2419                body: b1,
2420            },
2421            Term::Lambda {
2422                param: p2,
2423                param_type: pt2,
2424                body: b2,
2425            },
2426        ) => {
2427            // Parameter types must match in current scope
2428            if !types_alpha_equiv(pt1, pt2, bindings) {
2429                return false;
2430            }
2431            // Bodies must match with the new binding
2432            bindings.push((p1.clone(), p2.clone()));
2433            let result = types_alpha_equiv(b1, b2, bindings);
2434            bindings.pop();
2435            result
2436        }
2437        _ => false,
2438    }
2439}
2440
2441/// Extract P and Q types from an And(P, Q) conclusion.
2442fn extract_and_types(conclusion: &ProofExpr) -> KernelResult<(Term, Term)> {
2443    match conclusion {
2444        ProofExpr::And(p, q) => {
2445            let p_term = proof_expr_to_type(p)?;
2446            let q_term = proof_expr_to_type(q)?;
2447            Ok((p_term, q_term))
2448        }
2449        _ => Err(KernelError::CertificationError(format!(
2450            "Expected And, got {:?}",
2451            conclusion
2452        ))),
2453    }
2454}
2455
2456/// The domain (the `Global` type name) of parameter `pos` in the registered
2457/// signature of `name`: peel its `Π`s and return the `pos`-th parameter type when it
2458/// is a `Global`. The seam that lets binder typing read a symbol's declared shape
2459/// instead of hardcoding constructor names.
2460fn param_domain(ctx: &Context, name: &str, pos: usize) -> Option<String> {
2461    // Look the signature up under the kernel name: the ProofTerm layer's canonical arithmetic heads
2462    // are capitalized (`Mul`/`Add`/…), but the prelude declares the lowercase ring globals — so a
2463    // `∀`-binder used in `Mul(a, b)` still resolves its operand domain to `Int`.
2464    let mut ty = ctx.get_global(kernel_arith_name(name))?;
2465    let mut i = 0;
2466    while let Term::Pi {
2467        param_type,
2468        body_type,
2469        ..
2470    } = ty
2471    {
2472        if i == pos {
2473            return match param_type.as_ref() {
2474                Term::Global(g) => Some(g.clone()),
2475                _ => None,
2476            };
2477        }
2478        ty = body_type;
2479        i += 1;
2480    }
2481    None
2482}
2483
2484/// Collect every kernel domain `variable` is constrained to within `t`: a DIRECT
2485/// argument at position `j` of a function/constructor whose signature types that
2486/// parameter `Global(g)` contributes `g`. Recurses through nested arguments, so a
2487/// variable under `Succ` (⇒ `Nat`) or in `Cons`'s tail (⇒ `List`) is found.
2488fn collect_var_domains_term(t: &ProofTerm, variable: &str, ctx: &Context, out: &mut Vec<String>) {
2489    match t {
2490        ProofTerm::Function(name, args) => {
2491            for (j, a) in args.iter().enumerate() {
2492                if matches!(a, ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == variable)
2493                {
2494                    if let Some(g) = param_domain(ctx, name, j) {
2495                        out.push(g);
2496                    }
2497                }
2498                collect_var_domains_term(a, variable, ctx, out);
2499            }
2500        }
2501        ProofTerm::Group(args) => {
2502            for a in args {
2503                collect_var_domains_term(a, variable, ctx, out);
2504            }
2505        }
2506        _ => {}
2507    }
2508}
2509
2510/// Like [`collect_var_domains_term`] but over a proposition: a variable fed DIRECTLY
2511/// to a predicate at position `j` is constrained to that predicate's `j`-th parameter
2512/// domain (so `P(t)` with `P : List → Prop` makes `t` a `List`).
2513fn collect_var_domains_expr(e: &ProofExpr, variable: &str, ctx: &Context, out: &mut Vec<String>) {
2514    match e {
2515        ProofExpr::Predicate { name, args, .. } => {
2516            for (j, a) in args.iter().enumerate() {
2517                if matches!(a, ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == variable)
2518                {
2519                    if let Some(g) = param_domain(ctx, name, j) {
2520                        out.push(g);
2521                    }
2522                }
2523                collect_var_domains_term(a, variable, ctx, out);
2524            }
2525        }
2526        ProofExpr::Identity(l, r) => {
2527            collect_var_domains_term(l, variable, ctx, out);
2528            collect_var_domains_term(r, variable, ctx, out);
2529        }
2530        ProofExpr::And(l, r)
2531        | ProofExpr::Or(l, r)
2532        | ProofExpr::Implies(l, r)
2533        | ProofExpr::Iff(l, r) => {
2534            collect_var_domains_expr(l, variable, ctx, out);
2535            collect_var_domains_expr(r, variable, ctx, out);
2536        }
2537        ProofExpr::Not(p)
2538        | ProofExpr::ForAll { body: p, .. }
2539        | ProofExpr::Exists { body: p, .. } => collect_var_domains_expr(p, variable, ctx, out),
2540        _ => {}
2541    }
2542}
2543
2544/// Infer the kernel domain of a `∀`-bound `variable` from how `body` uses it, by
2545/// reading the registered signatures of the predicates/constructors it is an argument
2546/// of: an inductive constraint (`Nat` from `Succ` or a `Nat`-predicate, `List` from a
2547/// `List`-predicate or `Cons`'s tail) wins over the `Entity` default, while `Cons`'s
2548/// head position correctly stays `Entity`. The slice of elaboration that lets a
2549/// context-free proposition acquire the binder type its symbols imply.
2550fn binder_domain(variable: &str, body: &ProofExpr, ctx: &Context) -> String {
2551    let mut domains = Vec::new();
2552    collect_var_domains_expr(body, variable, ctx, &mut domains);
2553    domains
2554        .into_iter()
2555        .find(|d| d != "Entity")
2556        .unwrap_or_else(|| "Entity".to_string())
2557}
2558
2559/// Like [`proof_expr_to_type`] but resolves `∀`-binder domains against `ctx` (so a
2560/// quantifier over a `Nat`-used variable types as `Π(n:Nat). …`). Used where the
2561/// binder type is load-bearing — premise registration and the goal-type check —
2562/// while the context-free version still serves the inner certifier arms.
2563pub(crate) fn proof_expr_to_type_ctx(expr: &ProofExpr, ctx: &Context) -> KernelResult<Term> {
2564    if let ProofExpr::ForAll { variable, body } = expr {
2565        let dom = binder_domain(variable, body, ctx);
2566        let body_type = proof_expr_to_type_ctx(body, ctx)?;
2567        return Ok(Term::Pi {
2568            param: variable.clone(),
2569            param_type: Box::new(Term::Global(dom)),
2570            body_type: Box::new(body_type),
2571        });
2572    }
2573    // Resolve the equality domain against `ctx` too, so a ∀n goal whose body is a bare
2574    // `Int`-valued sequence identity (e.g. `trt n = tr n`, no add/mul) types as `Eq Int` in the
2575    // induction motive rather than the syntactic `Eq Entity` default.
2576    if let ProofExpr::Identity(l, r) = expr {
2577        let l_term = proof_term_to_kernel_term(l)?;
2578        let r_term = proof_term_to_kernel_term(r)?;
2579        let domain = Term::Global(resolved_identity_domain(l, r, ctx));
2580        return Ok(Term::App(
2581            Box::new(Term::App(
2582                Box::new(Term::App(
2583                    Box::new(Term::Global("Eq".to_string())),
2584                    Box::new(domain),
2585                )),
2586                Box::new(l_term),
2587            )),
2588            Box::new(r_term),
2589        ));
2590    }
2591    proof_expr_to_type(expr)
2592}
2593
2594pub(crate) fn proof_expr_to_type(expr: &ProofExpr) -> KernelResult<Term> {
2595    match expr {
2596        // Falsum maps to the kernel's `False : Prop`; other atoms are
2597        // propositional constants named directly.
2598        ProofExpr::Atom(name) if name == "⊥" || name == "False" || name == "false" => {
2599            Ok(Term::Global("False".to_string()))
2600        }
2601        ProofExpr::Atom(name) => Ok(Term::Global(name.clone())),
2602        // ¬P is `Not P`, which the kernel *defines* as `P → False`. We emit the
2603        // unfolded Pi form directly so the proposition is syntactically a
2604        // function in every position (application, hypothesis lookup, lambda
2605        // parameter types) without relying on delta-unfolding mid-typecheck.
2606        ProofExpr::Not(p) => Ok(Term::Pi {
2607            param: "_".to_string(),
2608            param_type: Box::new(proof_expr_to_type(p)?),
2609            body_type: Box::new(Term::Global("False".to_string())),
2610        }),
2611        ProofExpr::And(p, q) => Ok(Term::App(
2612            Box::new(Term::App(
2613                Box::new(Term::Global("And".to_string())),
2614                Box::new(proof_expr_to_type(p)?),
2615            )),
2616            Box::new(proof_expr_to_type(q)?),
2617        )),
2618        ProofExpr::Or(p, q) => Ok(Term::App(
2619            Box::new(Term::App(
2620                Box::new(Term::Global("Or".to_string())),
2621                Box::new(proof_expr_to_type(p)?),
2622            )),
2623            Box::new(proof_expr_to_type(q)?),
2624        )),
2625        ProofExpr::Implies(p, q) => Ok(Term::Pi {
2626            param: "_".to_string(),
2627            param_type: Box::new(proof_expr_to_type(p)?),
2628            body_type: Box::new(proof_expr_to_type(q)?),
2629        }),
2630        // Iff P Q ≡ And (P → Q) (Q → P) — the same encoding `verify.rs:expand_iff`
2631        // uses for Iff premises, so Iff goals and Iff hypotheses agree.
2632        ProofExpr::Iff(p, q) => {
2633            let pt = proof_expr_to_type(p)?;
2634            let qt = proof_expr_to_type(q)?;
2635            let pq = Term::Pi {
2636                param: "_".to_string(),
2637                param_type: Box::new(pt.clone()),
2638                body_type: Box::new(qt.clone()),
2639            };
2640            let qp = Term::Pi {
2641                param: "_".to_string(),
2642                param_type: Box::new(qt),
2643                body_type: Box::new(pt),
2644            };
2645            Ok(Term::App(
2646                Box::new(Term::App(
2647                    Box::new(Term::Global("And".to_string())),
2648                    Box::new(pq),
2649                )),
2650                Box::new(qp),
2651            ))
2652        }
2653        // ForAll ∀x.P(x) becomes Π(x:Entity). P(x)
2654        ProofExpr::ForAll { variable, body } => {
2655            let body_type = proof_expr_to_type(body)?;
2656            Ok(Term::Pi {
2657                param: variable.clone(),
2658                param_type: Box::new(Term::Global("Entity".to_string())),
2659                body_type: Box::new(body_type),
2660            })
2661        }
2662        // Predicate P(x, y, ...) becomes (P x y ...). A predicate is an uninterpreted
2663        // `Entity → … → Prop` relation, so its arguments are entities — a numeric
2664        // argument is an opaque label (a grid year `2004`), not an arithmetic literal.
2665        ProofExpr::Predicate { name, args, .. } => {
2666            let mut result = Term::Global(name.clone());
2667            for arg in args {
2668                let arg_term = proof_term_to_kernel_term_entity(arg)?;
2669                result = Term::App(Box::new(result), Box::new(arg_term));
2670            }
2671            Ok(result)
2672        }
2673        // Identity t1 = t2 becomes (Eq T t1 t2). The domain T is inferred from the
2674        // operands: a comparison (`le`/`lt`/…) or a Bool literal makes it `Eq Bool`
2675        // (the encoding `le a b = true` for `a ≤ b`); an arithmetic operator or
2676        // integer literal makes it `Eq Int`; otherwise the FOL default `Eq Entity`.
2677        ProofExpr::Identity(l, r) => {
2678            let l_term = proof_term_to_kernel_term(l)?;
2679            let r_term = proof_term_to_kernel_term(r)?;
2680            let domain = Term::Global(identity_domain(l, r).to_string());
2681            Ok(Term::App(
2682                Box::new(Term::App(
2683                    Box::new(Term::App(
2684                        Box::new(Term::Global("Eq".to_string())),
2685                        Box::new(domain),
2686                    )),
2687                    Box::new(l_term),
2688                )),
2689                Box::new(r_term),
2690            ))
2691        }
2692        // Exists ∃x.P(x) becomes Ex Entity (λx.P(x)). FOL quantifies over
2693        // entities (matching the ForAll arm); `ExistentialIntro` may still carry
2694        // an explicit witness type for other domains.
2695        ProofExpr::Exists { variable, body } => {
2696            let var_type = Term::Global(existential_domain(variable, body));
2697            let body_type = proof_expr_to_type(body)?;
2698
2699            // Build: Ex VarType (λvar. body_type)
2700            let predicate = Term::Lambda {
2701                param: variable.clone(),
2702                param_type: Box::new(var_type.clone()),
2703                body: Box::new(body_type),
2704            };
2705
2706            Ok(Term::App(
2707                Box::new(Term::App(
2708                    Box::new(Term::Global("Ex".to_string())),
2709                    Box::new(var_type),
2710                )),
2711                Box::new(predicate),
2712            ))
2713        }
2714        // A temporal modality `Op(P)` — "he was seen" is `Past(see(butler))` —
2715        // is an opaque unary operator on propositions. It lowers to `(Op P)` with
2716        // `Op : Prop → Prop` (registered by the symbol collector), keeping
2717        // `Past(P)` a distinct proposition from `P` so a modus-tollens chain over
2718        // tensed premises certifies without conflating the two.
2719        ProofExpr::Temporal { operator, body } => Ok(Term::App(
2720            Box::new(Term::Global(operator.clone())),
2721            Box::new(proof_expr_to_type(body)?),
2722        )),
2723        _ => Err(KernelError::CertificationError(format!(
2724            "Cannot convert {:?} to kernel type",
2725            expr
2726        ))),
2727    }
2728}
2729
2730/// Convert a ProofTerm to a kernel Term.
2731///
2732/// This bridges the proof engine's term representation to the kernel's.
2733/// Used for converting witness terms in quantifier instantiation.
2734/// Translate the shared IR's canonical arithmetic function names to the kernel's
2735/// internal ring vocabulary. The proof IR is canonicalised to `Add`/`Sub`/`Mul`/
2736/// `Div` (so the SMT oracle recognises it); the kernel's LIA prover ([`crate::arith`])
2737/// and its ring axioms are written in lowercase `add`/`sub`/`mul`/`div`. This is the
2738/// single translation boundary — every other name passes through verbatim.
2739fn kernel_arith_name(name: &str) -> &str {
2740    match name {
2741        "Add" => "add",
2742        "Sub" => "sub",
2743        "Mul" => "mul",
2744        "Div" => "div",
2745        other => other,
2746    }
2747}
2748
2749/// Is `name` an arithmetic or comparison builtin? Its operands are `Int` (so the
2750/// kernel's δ-rules compute on them — `add 2 3 ⇝ 5`, `le 2 5 ⇝ true`); every other
2751/// function is uninterpreted and `Entity`-valued. Mirrors the operand classification in
2752/// `symbols::SymbolCollector` so registration and lowering agree on which numerics are Int.
2753fn is_arith_builtin(name: &str) -> bool {
2754    matches!(
2755        name,
2756        "le" | "lt"
2757            | "ge"
2758            | "gt"
2759            | "add"
2760            | "sub"
2761            | "mul"
2762            | "div"
2763            | "mod"
2764            | "Add"
2765            | "Sub"
2766            | "Mul"
2767            | "Div"
2768    )
2769}
2770
2771/// Lower a proof term at an ENTITY position — a predicate argument, an uninterpreted
2772/// function's argument, an entity-domain identity operand. A bare numeric constant here
2773/// is an opaque `Entity` LABEL (a grid year `2004`, a jersey number) carried by a
2774/// first-order relation, NOT an arithmetic literal: it lowers to `Global "2004"` (which
2775/// resolves to the `Entity` constant `verify.rs` registers for it) so a monomorphic
2776/// relation like `in : Entity → Entity → Prop` — shared by a grid's year and state
2777/// columns — stays well-typed. A numeric nested under an arithmetic builtin still lowers
2778/// to an `Int` literal so the δ-rules fire. The position chooses the sort; the same
2779/// constant is one or the other by where it sits, never both. The entity-position dual of
2780/// [`proof_term_to_kernel_term`] (which lowers numerics as `Int`).
2781fn proof_term_to_kernel_term_entity(term: &ProofTerm) -> KernelResult<Term> {
2782    match term {
2783        ProofTerm::Constant(name) => Ok(Term::Global(name.clone())),
2784        ProofTerm::Variable(name) | ProofTerm::BoundVarRef(name) => Ok(Term::Var(name.clone())),
2785        ProofTerm::Function(name, args) => {
2786            let arith = is_arith_builtin(name);
2787            let mut result = Term::Global(kernel_arith_name(name).to_string());
2788            for arg in args {
2789                let arg_term = if arith {
2790                    proof_term_to_kernel_term(arg)?
2791                } else {
2792                    proof_term_to_kernel_term_entity(arg)?
2793                };
2794                result = Term::App(Box::new(result), Box::new(arg_term));
2795            }
2796            Ok(result)
2797        }
2798        ProofTerm::Group(_) => Err(KernelError::CertificationError(
2799            "Cannot convert Group to kernel term".to_string(),
2800        )),
2801    }
2802}
2803
2804pub(crate) fn proof_term_to_kernel_term(term: &ProofTerm) -> KernelResult<Term> {
2805    match term {
2806        // A numeric constant is an integer literal — it must be `Lit(Int)` (not an
2807        // opaque `Global`) so the kernel's arithmetic/comparison delta rules fire
2808        // (`add 2 3 ⇝ 5`, `le 2 5 ⇝ true`), deciding ground facts by computation.
2809        ProofTerm::Constant(name) => match crate::numeral::literal_of_constant(name) {
2810            Some(lit) => Ok(Term::Lit(lit)),
2811            None => Ok(Term::Global(name.clone())),
2812        },
2813        ProofTerm::Variable(name) => Ok(Term::Var(name.clone())),
2814        ProofTerm::BoundVarRef(name) => Ok(Term::Var(name.clone())),
2815        ProofTerm::Function(name, args) => {
2816            // Build nested applications: f(a, b) -> ((f a) b). Canonical arithmetic
2817            // names are lowered to the kernel's ring vocabulary at this boundary.
2818            let mut result = Term::Global(kernel_arith_name(name).to_string());
2819            for arg in args {
2820                let arg_term = proof_term_to_kernel_term(arg)?;
2821                result = Term::App(Box::new(result), Box::new(arg_term));
2822            }
2823            Ok(result)
2824        }
2825        ProofTerm::Group(_) => Err(KernelError::CertificationError(
2826            "Cannot convert Group to kernel term".to_string(),
2827        )),
2828    }
2829}
2830
2831/// The `Decidable` instance term for a kernel proposition — RESOLVED against the context,
2832/// the way Lean's `decide` resolves one, rather than read off a table of type names.
2833///
2834/// This used to be two hard-coded arms (`Eq Bool ↦ decEqBool`, `Eq Nat ↦ decEqNat`), which is
2835/// the defect the corpus case names: `decide` covered a LIST OF TYPES, so every proposition
2836/// decidable by any other means — a new instance in the prelude, a `Decidable (le a b)`, a
2837/// user-registered decision procedure — was outside it by construction, and widening the
2838/// tactic meant editing the certifier. Now any declaration or definition whose type is
2839/// `Π x̄. Decidable <pattern>` is an instance: the pattern is matched against `prop` with the
2840/// Π-binders as metavariables, and the instance is applied to what they matched.
2841///
2842/// Two deliberate exclusions:
2843///
2844/// * An instance whose subject is a BARE binder variable — `Classical_propDecidable :
2845///   Π(p:Prop). Decidable p` — matches every proposition and decides none of them: it is built
2846///   from `Classical_choice`, so the evaluator cannot reduce `decide p` at all. Taking it would
2847///   shadow every real instance with one that always fails, and it would drag the classical
2848///   axiom into the footprint of a computation.
2849/// * A pattern whose metavariables the match does not determine, which would leave the applied
2850///   instance with a free variable.
2851///
2852/// Candidates are ordered by NAME so the choice is deterministic — the context's maps are
2853/// hashed, and a proof term that depended on iteration order would not be reproducible.
2854fn decidable_instance_for(prop: &Term, kctx: &Context) -> Option<Term> {
2855    let mut candidates: Vec<(String, Term)> = Vec::new();
2856    let types = kctx
2857        .iter_definitions()
2858        .map(|(n, ty, _)| (n, ty))
2859        .chain(kctx.iter_declarations());
2860    for (name, ty) in types {
2861        let mut binders: Vec<String> = Vec::new();
2862        let mut cur = ty;
2863        while let Term::Pi {
2864            param, body_type, ..
2865        } = cur
2866        {
2867            binders.push(param.clone());
2868            cur = body_type;
2869        }
2870        let Term::App(head, pattern) = cur else {
2871            continue;
2872        };
2873        if !matches!(head.as_ref(), Term::Global(g) if g == "Decidable") {
2874            continue;
2875        }
2876        // The universal classical instance: matches anything, computes nothing.
2877        if let Term::Var(subject) = pattern.as_ref() {
2878            if binders.iter().any(|b| b == subject) {
2879                continue;
2880            }
2881        }
2882        let mut bound: std::collections::HashMap<String, Term> = std::collections::HashMap::new();
2883        if !match_instance_pattern(pattern, prop, &binders, &mut bound) {
2884            continue;
2885        }
2886        let mut applied = Term::Global(name.to_string());
2887        let mut complete = true;
2888        for b in &binders {
2889            match bound.get(b) {
2890                Some(t) => applied = Term::App(Box::new(applied), Box::new(t.clone())),
2891                None => {
2892                    complete = false;
2893                    break;
2894                }
2895            }
2896        }
2897        if complete {
2898            candidates.push((name.to_string(), applied));
2899        }
2900    }
2901    candidates.sort_by(|a, b| a.0.cmp(&b.0));
2902    candidates.into_iter().next().map(|(_, t)| t)
2903}
2904
2905/// First-order structural match of an instance's `Decidable` subject against a concrete
2906/// proposition. `metas` are the instance's Π-binders; every other node must match exactly.
2907fn match_instance_pattern(
2908    pattern: &Term,
2909    target: &Term,
2910    metas: &[String],
2911    bound: &mut std::collections::HashMap<String, Term>,
2912) -> bool {
2913    if let Term::Var(name) = pattern {
2914        if metas.iter().any(|m| m == name) {
2915            return match bound.get(name) {
2916                Some(seen) => seen == target,
2917                None => {
2918                    bound.insert(name.clone(), target.clone());
2919                    true
2920                }
2921            };
2922        }
2923    }
2924    match (pattern, target) {
2925        (Term::App(pf, pa), Term::App(tf, ta)) => {
2926            match_instance_pattern(pf, tf, metas, bound)
2927                && match_instance_pattern(pa, ta, metas, bound)
2928        }
2929        (p, t) => p == t,
2930    }
2931}
2932
2933/// Infer the `Eq` domain for an `Identity` from its operands (see the `Identity`
2934/// arm of [`proof_expr_to_type`]). A comparison (`le`/`lt`/…) or a Bool literal →
2935/// `Bool`; an arithmetic operator or integer literal → `Int`; otherwise the
2936/// first-order default `Entity`.
2937fn identity_domain(l: &ProofTerm, r: &ProofTerm) -> &'static str {
2938    match (term_domain(l), term_domain(r)) {
2939        ("Bool", _) | (_, "Bool") => "Bool",
2940        ("Int", _) | (_, "Int") => "Int",
2941        _ => "Entity",
2942    }
2943}
2944
2945/// The kernel domain a single term belongs to: a comparison / Bool literal → `Bool`;
2946/// an arithmetic operator or integer literal → `Int`; otherwise `Entity`.
2947fn term_domain(t: &ProofTerm) -> &'static str {
2948    match t {
2949        ProofTerm::Function(n, _) if matches!(n.as_str(), "le" | "lt" | "ge" | "gt") => "Bool",
2950        ProofTerm::Function(n, _)
2951            if matches!(
2952                n.as_str(),
2953                "add" | "sub" | "mul" | "div" | "mod" | "Add" | "Sub" | "Mul" | "Div"
2954            ) =>
2955        {
2956            "Int"
2957        }
2958        ProofTerm::Constant(s) if s == "true" || s == "false" => "Bool",
2959        ProofTerm::Constant(s) if crate::numeral::is_numeral(s) => "Int",
2960        _ => "Entity",
2961    }
2962}
2963
2964/// The equality domain of a term, resolved against the kernel context. Syntactic classification
2965/// ([`term_domain`]) only knows the arithmetic/comparison builtins, so a DECLARED function like
2966/// `tr : Nat → Int` classifies as the `Entity` default even though its values are `Int`. This walks
2967/// the declared type's codomain to recover the real domain — so a Leibniz rewrite of `tr k` builds
2968/// `Eq Int`, not `Eq Entity`. Only overrides the `Entity` default (an arithmetic/Bool term keeps its
2969/// syntactic domain), so it never changes an already-correct classification.
2970fn resolved_domain(t: &ProofTerm, kctx: &Context) -> String {
2971    let syntactic = term_domain(t);
2972    if syntactic != "Entity" {
2973        return syntactic.to_string();
2974    }
2975    match t {
2976        ProofTerm::Function(name, _) => {
2977            if let Some(ty) = kctx.get_global(name) {
2978                let mut cur = ty;
2979                while let Term::Pi { body_type, .. } = cur {
2980                    cur = body_type;
2981                }
2982                if let Term::Global(g) = cur {
2983                    return g.clone();
2984                }
2985            }
2986        }
2987        // A declared ATOM resolves the same way. `verify::SymbolCollector` types every name
2988        // in an arithmetic or comparison position `Int`, so a bare `a` used in `le(a, d)` IS
2989        // an `Int` — and the `Eq Entity a b` the purely syntactic default produced for
2990        // `a = b` is not merely imprecise, it is ILL-TYPED: `Eq`'s domain must be the sort of
2991        // its operands. Nothing noticed until a Leibniz rewrite needed `Eq_rec` at that sort
2992        // and the kernel reported "expected Entity, found Int" about a correct proof. Names
2993        // registered `Entity` still resolve to `Entity`, so this only moves the cases that
2994        // were wrong.
2995        ProofTerm::Constant(name) | ProofTerm::Variable(name) | ProofTerm::BoundVarRef(name) => {
2996            if let Some(Term::Global(g)) = kctx.get_global(name).or_else(|| kctx.get(name)) {
2997                return g.clone();
2998            }
2999        }
3000        _ => {}
3001    }
3002    syntactic.to_string()
3003}
3004
3005/// Like [`identity_domain`] but resolves each operand against the kernel context, so an equality of
3006/// declared `Int`-valued sequence terms (e.g. `tr k = trt k`, both `Nat → Int` applications) types as
3007/// `Eq Int`, not the `Eq Entity` the purely-syntactic classifier would pick. `Bool` dominates, then
3008/// `Int`, then the first concrete non-`Entity` resolved domain, else `Entity`.
3009fn resolved_identity_domain(l: &ProofTerm, r: &ProofTerm, kctx: &Context) -> String {
3010    let (dl, dr) = (resolved_domain(l, kctx), resolved_domain(r, kctx));
3011    if dl == "Bool" || dr == "Bool" {
3012        "Bool".to_string()
3013    } else if dl == "Int" || dr == "Int" {
3014        "Int".to_string()
3015    } else if dl != "Entity" {
3016        dl
3017    } else {
3018        dr
3019    }
3020}
3021
3022/// Extract `(a, b)` from a STRICT inequality conclusion `lt(a, b) = true`.
3023fn lt_terms(expr: &ProofExpr) -> KernelResult<(ProofTerm, ProofTerm)> {
3024    if let ProofExpr::Identity(lhs, rhs) = expr {
3025        if let (ProofTerm::Function(name, args), ProofTerm::Constant(t)) = (lhs, rhs) {
3026            if name == "lt" && args.len() == 2 && t == "true" {
3027                return Ok((args[0].clone(), args[1].clone()));
3028            }
3029        }
3030    }
3031    Err(KernelError::CertificationError(format!(
3032        "expected a strict inequality `lt(a, b) = true`, got {expr:?}"
3033    )))
3034}
3035
3036/// Extract `(a, b)` from an inequality conclusion `le(a, b) = true`, encoded in the
3037/// proof layer as `Identity(Function("le", [a, b]), Constant("true"))`.
3038fn le_terms(expr: &ProofExpr) -> KernelResult<(ProofTerm, ProofTerm)> {
3039    if let ProofExpr::Identity(lhs, _) = expr {
3040        if let ProofTerm::Function(name, args) = lhs {
3041            if name == "le" && args.len() == 2 {
3042                return Ok((args[0].clone(), args[1].clone()));
3043            }
3044        }
3045    }
3046    Err(KernelError::CertificationError(format!(
3047        "expected an `le(a, b) = true` inequality, got {:?}",
3048        expr
3049    )))
3050}
3051
3052/// Extract `(x, y)` from a sum `add(x, y)`.
3053fn add_terms(t: &ProofTerm) -> KernelResult<(ProofTerm, ProofTerm)> {
3054    binop_terms("add", t)
3055}
3056
3057/// Extract `(x, y)` from a binary application `op(x, y)`.
3058fn binop_terms(op: &str, t: &ProofTerm) -> KernelResult<(ProofTerm, ProofTerm)> {
3059    if let ProofTerm::Function(name, args) = t {
3060        if name == op && args.len() == 2 {
3061            return Ok((args[0].clone(), args[1].clone()));
3062        }
3063    }
3064    Err(KernelError::CertificationError(format!(
3065        "expected `{}(x, y)`, got {:?}",
3066        op, t
3067    )))
3068}
3069
3070/// `Eq_rec Bool false P I true h : False`, where `h : Eq Bool false true` (or, by
3071/// computation, any `Eq Bool (le m n) true` with `m > n`). The motive
3072/// `P b = match b with true ⇒ False | false ⇒ True` is the Bool no-confusion
3073/// discriminator — turning a derived ground-false inequality into `⊥`.
3074fn build_bool_discriminator(h: Term) -> Term {
3075    let g = |s: &str| Term::Global(s.to_string());
3076    // P = λb:Bool. match b return (λ_:Bool. Prop) with | true ⇒ False | false ⇒ True
3077    let motive = Term::Lambda {
3078        param: "b".to_string(),
3079        param_type: Box::new(g("Bool")),
3080        body: Box::new(Term::Match {
3081            discriminant: Box::new(Term::Var("b".to_string())),
3082            motive: Box::new(Term::Lambda {
3083                param: "_".to_string(),
3084                param_type: Box::new(g("Bool")),
3085                body: Box::new(Term::Sort(logicaffeine_kernel::Universe::Prop)),
3086            }),
3087            cases: vec![g("False"), g("True")],
3088        }),
3089    };
3090    [g("Bool"), g("false"), motive, g("I"), g("true"), h]
3091        .into_iter()
3092        .fold(g("Eq_rec"), |acc, arg| {
3093            Term::App(Box::new(acc), Box::new(arg))
3094        })
3095}
3096
3097// =============================================================================
3098// INDUCTION HELPER FUNCTIONS
3099// =============================================================================
3100
3101/// Extract motive body from ForAll conclusion.
3102/// The motive is the predicate body of the ForAll that we're proving by induction.
3103fn extract_motive_body(
3104    conclusion: &ProofExpr,
3105    var_name: &str,
3106    kctx: &Context,
3107) -> KernelResult<Term> {
3108    match conclusion {
3109        ProofExpr::ForAll { variable, body } if variable == var_name => {
3110            // Convert body to kernel type (the motive body), resolving the equality domain against
3111            // the context so a bare `Int`-valued sequence goal (`trt n = tr n`) types as `Eq Int` and
3112            // agrees with the `Eq Int` base/step proofs — not the syntactic `Eq Entity`.
3113            proof_expr_to_type_ctx(body, kctx)
3114        }
3115        _ => Err(KernelError::CertificationError(format!(
3116            "StructuralInduction conclusion must be ForAll over {}, got {:?}",
3117            var_name, conclusion
3118        ))),
3119    }
3120}
3121
3122/// Compute what the IH conclusion looks like: P(k) when proving P(n).
3123/// Substitutes the induction variable with the step variable in the ForAll body.
3124fn compute_ih_conclusion(
3125    conclusion: &ProofExpr,
3126    orig_var: &str,
3127    step_var: &str,
3128) -> KernelResult<ProofExpr> {
3129    match conclusion {
3130        ProofExpr::ForAll { body, .. } => Ok(substitute_var_in_expr(body, orig_var, step_var)),
3131        _ => Err(KernelError::CertificationError(
3132            "Expected ForAll for IH computation".to_string(),
3133        )),
3134    }
3135}
3136
3137/// Peel a constructor's argument types from its signature. A monomorphic
3138/// inductive's constructor has type `Π(a₀:T₀). … Π(aₙ:Tₙ). Ind`, so the argument
3139/// types are exactly the `Pi` parameter types in order (a nullary constructor
3140/// yields an empty list). Used to type the case lambdas of a generic
3141/// [`InferenceRule::InductionScheme`] eliminator.
3142fn constructor_arg_types(ctx: &Context, constructor: &str) -> KernelResult<Vec<Term>> {
3143    let mut ty = ctx
3144        .get_global(constructor)
3145        .ok_or_else(|| {
3146            KernelError::CertificationError(format!("unknown constructor {}", constructor))
3147        })?
3148        .clone();
3149    let mut args = Vec::new();
3150    while let Term::Pi {
3151        param_type,
3152        body_type,
3153        ..
3154    } = ty
3155    {
3156        args.push(*param_type);
3157        ty = *body_type;
3158    }
3159    Ok(args)
3160}
3161
3162/// Build the match motive: λn:IndType. ResultType
3163/// The motive_param should be the same variable name used in the body
3164/// so that the body's references are properly captured.
3165fn build_motive(ind_type: &str, result_type: &Term, motive_param: &str) -> Term {
3166    Term::Lambda {
3167        param: motive_param.to_string(),
3168        param_type: Box::new(Term::Global(ind_type.to_string())),
3169        body: Box::new(result_type.clone()),
3170    }
3171}
3172
3173/// Substitute variable name in ProofExpr (recursive).
3174fn substitute_var_in_expr(expr: &ProofExpr, from: &str, to: &str) -> ProofExpr {
3175    match expr {
3176        ProofExpr::Atom(s) if s == from => ProofExpr::Atom(to.to_string()),
3177        ProofExpr::Atom(s) => ProofExpr::Atom(s.clone()),
3178
3179        ProofExpr::TypedVar { name, typename } => ProofExpr::TypedVar {
3180            name: if name == from {
3181                to.to_string()
3182            } else {
3183                name.clone()
3184            },
3185            typename: typename.clone(),
3186        },
3187
3188        ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
3189            name: name.clone(),
3190            args: args
3191                .iter()
3192                .map(|a| substitute_var_in_term(a, from, to))
3193                .collect(),
3194            world: world.clone(),
3195        },
3196
3197        ProofExpr::Identity(l, r) => ProofExpr::Identity(
3198            substitute_var_in_term(l, from, to),
3199            substitute_var_in_term(r, from, to),
3200        ),
3201
3202        ProofExpr::And(l, r) => ProofExpr::And(
3203            Box::new(substitute_var_in_expr(l, from, to)),
3204            Box::new(substitute_var_in_expr(r, from, to)),
3205        ),
3206
3207        ProofExpr::Or(l, r) => ProofExpr::Or(
3208            Box::new(substitute_var_in_expr(l, from, to)),
3209            Box::new(substitute_var_in_expr(r, from, to)),
3210        ),
3211
3212        ProofExpr::Implies(l, r) => ProofExpr::Implies(
3213            Box::new(substitute_var_in_expr(l, from, to)),
3214            Box::new(substitute_var_in_expr(r, from, to)),
3215        ),
3216
3217        ProofExpr::Iff(l, r) => ProofExpr::Iff(
3218            Box::new(substitute_var_in_expr(l, from, to)),
3219            Box::new(substitute_var_in_expr(r, from, to)),
3220        ),
3221
3222        ProofExpr::Not(inner) => ProofExpr::Not(Box::new(substitute_var_in_expr(inner, from, to))),
3223
3224        // Don't substitute inside binding that shadows
3225        ProofExpr::ForAll { variable, body } if variable != from => ProofExpr::ForAll {
3226            variable: variable.clone(),
3227            body: Box::new(substitute_var_in_expr(body, from, to)),
3228        },
3229
3230        ProofExpr::Exists { variable, body } if variable != from => ProofExpr::Exists {
3231            variable: variable.clone(),
3232            body: Box::new(substitute_var_in_expr(body, from, to)),
3233        },
3234
3235        ProofExpr::Lambda { variable, body } if variable != from => ProofExpr::Lambda {
3236            variable: variable.clone(),
3237            body: Box::new(substitute_var_in_expr(body, from, to)),
3238        },
3239
3240        ProofExpr::App(f, a) => ProofExpr::App(
3241            Box::new(substitute_var_in_expr(f, from, to)),
3242            Box::new(substitute_var_in_expr(a, from, to)),
3243        ),
3244
3245        ProofExpr::Term(t) => ProofExpr::Term(substitute_var_in_term(t, from, to)),
3246
3247        ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
3248            name: name.clone(),
3249            args: args
3250                .iter()
3251                .map(|a| substitute_var_in_expr(a, from, to))
3252                .collect(),
3253        },
3254
3255        // For anything else (shadowed bindings, modals, temporals, etc.), clone as-is
3256        other => other.clone(),
3257    }
3258}
3259
3260/// Substitute variable name in ProofTerm.
3261fn substitute_var_in_term(term: &ProofTerm, from: &str, to: &str) -> ProofTerm {
3262    match term {
3263        ProofTerm::Variable(s) if s == from => ProofTerm::Variable(to.to_string()),
3264        ProofTerm::Variable(s) => ProofTerm::Variable(s.clone()),
3265        ProofTerm::Constant(s) => ProofTerm::Constant(s.clone()),
3266        ProofTerm::BoundVarRef(s) if s == from => ProofTerm::BoundVarRef(to.to_string()),
3267        ProofTerm::BoundVarRef(s) => ProofTerm::BoundVarRef(s.clone()),
3268        ProofTerm::Function(name, args) => ProofTerm::Function(
3269            name.clone(),
3270            args.iter()
3271                .map(|a| substitute_var_in_term(a, from, to))
3272                .collect(),
3273        ),
3274        ProofTerm::Group(terms) => ProofTerm::Group(
3275            terms
3276                .iter()
3277                .map(|t| substitute_var_in_term(t, from, to))
3278                .collect(),
3279        ),
3280    }
3281}
3282
3283#[cfg(test)]
3284#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/certifier/canonical_arith_boundary_tests.rs"]
3285mod canonical_arith_boundary_tests;
3286
3287#[cfg(test)]
3288#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/certifier/connective_lowering_tests.rs"]
3289mod connective_lowering_tests;