Lean 4 Cross-Check

The HOL kernel verifies your proofs from first principles. But how do you know the kernel itself is correct? Lean 4 cross-checking provides a genuine second opinion from a completely independent mathematical system, so a false result would have to survive two differently-built checkers at once.

After this page you will understand what the trusted computing base is, why an independent second checker matters, what gets cross-checked, how to read a cross-check result, and which plans include it.

Lean 4 cross-check is part of Backbuild Prove, which is launching soon, and is included on the Business and Enterprise plans. It is also included with Backbuild Science, which is available now and free for verified students and faculty. See the pricing page.

One proof is checked by two independent paths. Path one sends it to the HOL kernel, built on a small fixed set of axioms and primitive rules, which returns Verified. Path two exports and translates the same proof to Lean 4, a separate system with different foundations, team, and implementation, which returns Confirmed. The two results meet at an Agree gate; when both agree, assurance is strongest. A note reads: a false result would have to survive both engines at once.
The same proof is checked by two independent engines. Agreement between them is the strongest assurance available, because a false result would have to fool both at once.

What It Is

Lean 4 is an independent proof assistant. Lean was created by Leonardo de Moura at Microsoft Research, and Lean 4 is now stewarded by the nonprofit Lean Focused Research Organization, known as the Lean FRO, together with the Lean community. It has its own mathematical foundations (the Calculus of Inductive Constructions), its own implementation, and its own development team. It shares nothing with the HOL kernel that Backbuild Prove uses for primary verification.

Lean 4 cross-checking means that after the HOL kernel verifies a proof, the kernel exports its work to Lean 4, translating HOL terms, types, and proof steps into Lean 4’s language. Lean 4 then independently checks the translated proof. If both systems agree, you have strong evidence that the proof is correct, because a bug would need to exist in both systems simultaneously to produce a false positive.

How It Works

The cross-check process has four stages:

  1. Primary verification. The HOL kernel verifies the pf2 annotation using its own axioms and inference rules, exactly as it does normally.
  2. Export. The kernel translates the verified proof into Lean 4’s language. HOL types map to Lean 4 types, HOL terms map to Lean 4 terms, and HOL inference steps map to Lean 4 tactics or term-mode proofs.
  3. Independent check. Lean 4 processes the translated proof using its own type checker and proof kernel. This is not a superficial syntax check; Lean 4 rebuilds the proof from its own foundational axioms.
  4. Semantic equivalence. The system verifies that the HOL and Lean 4 representations are semantically equivalent, meaning they express the same mathematical statement and both proof kernels agree it is valid.

Why This Matters

A single proof system can have bugs. If the HOL kernel has a soundness bug, it might accept an invalid proof. Cross-checking with Lean 4 makes this dramatically less likely, because:

  • Different foundations. HOL uses classical higher-order logic with the axiom of choice. Lean 4 uses the Calculus of Inductive Constructions. A bug in one set of foundations does not imply a bug in the other.
  • Different implementation. The HOL kernel and Lean 4 are written by different teams in different languages with different architectures. Implementation bugs are unlikely to coincide.
  • Different team. The Lean 4 team is independent of Backbuild. There is no shared codebase, no shared development process, and no shared assumptions.

For a false positive to survive cross-checking, both systems would need to have compatible bugs that accept the same invalid proof. This is extraordinarily unlikely.

What Gets Cross-Checked

Not every aspect of a proof translates identically between HOL and Lean 4. The cross-check covers:

  • Theorem statements. The mathematical claim being proven is translated and verified for semantic equivalence.
  • Proof steps. Each step in the HOL proof is translated to a corresponding Lean 4 proof term or tactic.
  • Type structure. HOL types are mapped to Lean 4 types, preserving the mathematical structure.
  • Axiom usage. Any axioms used in the HOL proof are mapped to their Lean 4 equivalents.

Cross-Check Results

Each theorem receives a cross-check status:

  • Confirmed: Lean 4 independently verified the translated proof and the two representations are semantically equivalent (and, where possible, fully theorem-equivalent). Both systems agree.
  • Translation failed: the proof could not be translated to Lean 4’s language. This does not mean the proof is wrong; it means the translation layer does not yet support the constructs used.
  • Lean 4 rejected: Lean 4 did not accept the translated proof. This is a significant finding that triggers investigation into whether the HOL proof is valid.

Cross-check results are stored alongside the primary verification results and are visible in the CLI output, VS Code extension, and project status.

Certificates and Cross-Checks

When you publish a certification bundle, Lean 4 cross-check results are included in the lean4_results.json file within the bundle. The public verification page reports whether the bundle passed Lean 4 cross-check alongside its primary verification results.

Certificates with full Lean 4 cross-check confirmation provide the strongest level of assurance: two independent mathematical systems agree that your code is correct.

Availability

Lean 4 cross-checking is available on the Business and Enterprise Backbuild Prove pricing tiers. Prove Pro and Team tiers receive primary HOL verification only. It is also included with Backbuild Science, which is available now and free for verified students and faculty with a valid academic ID.

See Prove pricing and Science pricing.

If the prover says "proved," what exactly am I trusting?
For primary verification, a small fixed core of foundational axioms and primitive inference rules, to which every proof is reduced. That trusted computing base is deliberately small and does not grow with your proofs. Lean 4 then re-derives the result independently, so trust does not rest on a single implementation.

How is the second check genuinely independent?
Lean 4 is built by a different team, on different mathematical foundations, in a different implementation. It shares no code and no assumptions with the HOL kernel. A false positive would require both systems to carry compatible bugs that accept the same invalid proof.

A proof passed the HOL kernel but the cross-check says "Translation failed." Is my proof wrong?
Not necessarily. Translation failed means the translation layer does not yet support a construct the proof uses, not that the proof is invalid. Lean 4 rejected is the significant case that triggers investigation. See Troubleshooting.

Next Steps