From Logic to Code: Understanding the Curry–Howard Correspondence in Lean

t rejects any program lacking a valid witness for its stated invariants. This enables correct-by-construction software where logical guarantees are baked into the type system, not bolted on afterward.

Core Solution

Implementing the Curry–Howard bridge requires shifting from "functions that compute" to "functions that compute and prove". The following walkthrough demonstrates how to build a verified list deduplication function in Lean 4, where the output type explicitly demands evidence that duplicates have been removed and the original element multiset is preserved.

Step 1: Define the Logical Specification

First, we model the correctness criteria as inductive propositions. In Lean, Prop is the universe of logical statements. Proofs in Prop are proof-irrelevant and erased during compilation, ensuring zero runtime cost.

inductive IsDeduplicated : List α → Prop
| empty : IsDeduplicated []
| single (x : α) : IsDeduplicated [x]
| cons (x : α) (xs : List α) :
    ¬ List.elem x xs →
    IsDeduplicated xs →
    IsDeduplicated (x :: xs)

This definition states that a list is deduplicated if:

• It is empty
• It contains a single element
• Its head does not appear in the tail, and the tail itself is deduplicated

Step 2: Construct the Dependent Function Signature

Instead of returning a plain List α, the function returns a Sigma type (dependent pair). This bundles the computed list with a proof that satisfies the specification.

def verifyDeduplicate (input : List α) [DecidableEq α] :
    Σ (output : List α), IsDeduplicated output ∧ Multiset.ofList input = Multiset.ofList output :=
  sorry

The signature explicitly requests:

1. An output list
2. Proof that the output is deduplicated
3. Proof that the input and output contain the same elements (multiset equality)

Step 3: Implement the Computational Core

We separate the algorithmic logic from the proof construction. The computational part handles list traversal and duplicate filtering.

def deduplicateCore (input : List α) [DecidableEq α] : List α :=
  input.foldl (fun acc x =>
    if List.elem x acc then acc else x :: acc
  ) [] |>.reverse

Step 4: Assemble the Proof Term

Lean's tactic mode allows us to construct the proof incrementally. Each tactic manipulates the proof state, transforming goals into subgoals until they resolve to axioms or previously proven lemmas.

theorem verifyDeduplicate (input : List α) [DecidableEq α] :
    Σ (output : List α), IsDeduplicated output ∧ Multiset.ofList input = Multiset.ofList output := by
  use deduplicateCore input
  constructor
  · -- Prove deduplication invariant
    induction input with
    | nil => exact IsDeduplicated.empty
    | cons x xs ih =>
      unfold deduplicateCore
      simp [List.foldl]
      -- Detailed proof steps would go here using `cases`, `simp`, `apply`
      sorry
  · -- Prove multiset preservation
    unfold deduplicateCore
    simp [Multiset.ofList, List.foldl]
    -- Inductive proof over list structure
    sorry

Architecture Decisions and Rationale

• Why Sigma types? Dependent pairs allow functions to return data alongside logical witnesses without polluting the runtime representation. The proof component exists only during compilation.
• Why separate Prop from Type? Lean's universe hierarchy ensures that logical statements (Prop) are computationally irrelevant. The compiler erases them during code generation, preserving performance while maintaining verification guarantees.
• Why tactic mode over term mode? Tactic mode provides a structured, stepwise environment for proof construction. Term mode requires writing fully explicit proof terms, which becomes unreadable for non-trivial invariants. Tactic mode bridges human reasoning and machine verification.

Pitfall Guide

Pitfall	Explanation	Fix
Universe Confusion	Mixing Prop and Type causes compilation errors or runtime bloat. Prop is for proofs; Type is for data.	Always declare specifications in Prop. Use Type only for computational structures. Verify universe levels with #check.
Over-Specification	Encoding too many invariants makes proofs impossible or functions unusable.	Start with minimal necessary invariants. Add constraints incrementally as the system evolves.
Proof Pattern Matching	Attempting to destructure proofs in Prop violates proof irrelevance and breaks compilation.	Never pattern match on Prop values. Use cases or simp on the computational data instead.
Tactic State Drift	Losing track of the proof goal leads to circular reasoning or unprovable subgoals.	Use show to annotate intermediate goals. Keep tactic scripts short and modular.
Ignoring Computational Content	Writing proofs that require heavy computation slows down type checking.	Keep proofs computational-light. Use decide or simp for decidable properties. Offload complex reasoning to external solvers if needed.
Runtime Proof Leakage	Accidentally placing proofs in Type prevents erasure, increasing binary size and execution time.	Audit function signatures. Ensure all logical witnesses reside in Prop or are wrapped in Sigma with Prop components.
False Confidence in Type Checking	Assuming a compiling program is fully correct overlooks specification gaps.	Treat the type signature as a contract, not a complete specification. Validate that the encoded invariants match domain requirements.

Production Bundle

Action Checklist

• Define inductive propositions for all behavioral invariants before writing implementations
• Use Sigma types to bundle computational results with logical witnesses
• Keep all specifications in Prop to ensure compile-time erasure
• Separate algorithmic logic from proof construction using helper functions
• Annotate tactic states with show to maintain proof readability
• Validate that encoded invariants align with actual domain requirements
• Run lean --verify in CI to catch proof regressions early
• Profile compilation time; refactor heavy proofs if type checking exceeds thresholds

Decision Matrix

Scenario	Recommended Approach	Why	Cost Impact
Internal utility with low failure tolerance	Curry–Howard dependent types	Guarantees correctness at compile time; eliminates runtime test overhead	High initial development cost; low long-term maintenance
Rapid prototyping or MVP	Traditional typing + property-based testing	Faster iteration; lower verification overhead	Moderate testing cost; higher risk of logical bugs
Cryptographic or safety-critical kernel	Full dependent verification + external proof audit	Mathematical certainty; compliance with regulatory standards	Very high development cost; requires specialized expertise
High-throughput data pipeline	Dependent types for invariants + runtime metrics	Balances compile-time guarantees with observability	Moderate cost; requires monitoring infrastructure

Configuration Template

# lakefile.toml
name = "verified-core"
version = "0.1.0"
keywords = ["verification", "dependent-types", "lean4"]
defaultTargets = ["VerifiedCore"]

[[lean_lib]]
name = "VerifiedCore"
root = "Src"

[[require]]
mathlib = { git = "https://github.com/leanprover-community/mathlib4", rev = "master" }

-- Src/VerifiedCore.lean
import Mathlib.Data.List.Basic
import Mathlib.Data.Multiset.Basic

namespace VerifiedCore

-- Specification types
inductive IsDeduplicated : List α → Prop
| empty : IsDeduplicated []
| single (x : α) : IsDeduplicated [x]
| cons (x : α) (xs : List α) :
    ¬ List.elem x xs →
    IsDeduplicated xs →
    IsDeduplicated (x :: xs)

-- Computational core
def deduplicateCore (input : List α) [DecidableEq α] : List α :=
  input.foldl (fun acc x =>
    if List.elem x acc then acc else x :: acc
  ) [] |>.reverse

-- Verified interface
theorem verifyDeduplicate (input : List α) [DecidableEq α] :
    Σ (output : List α), IsDeduplicated output ∧ Multiset.ofList input = Multiset.ofList output := by
  use deduplicateCore input
  constructor
  · -- Proof construction placeholder
    sorry
  · -- Multiset equality placeholder
    sorry

end VerifiedCore

Quick Start Guide

1. Initialize the project: Run lake new verified-core math to scaffold a Lean 4 project with Mathlib dependencies.
2. Define specifications: Create inductive Prop types that capture your domain invariants. Keep them minimal and decidable where possible.
3. Implement computational cores: Write pure functions that perform the required transformations. Avoid embedding proof logic in the algorithmic path.
4. Construct dependent signatures: Use Σ types to pair outputs with logical witnesses. Ensure all proof components reside in Prop.
5. Compile and iterate: Run lake build. The compiler will reject any function lacking a valid proof term. Use tactic mode to incrementally resolve proof goals until the build succeeds.