Files
skills/public/formal-lean-theorem-proving.html
zeekayandHanzo Dev 9e10c1c10e Each llms index points at the other two
hanzoskills.com/llms.txt now opens with the install line, the API
reference index and the company index, so an agent that lands on any
one of the three can find the rest.

robots.txt claimed 537 documents while llms.txt counts 920. The number
is gone from robots.txt; llms.txt derives it.

public/ is regenerated from scripts/site.py, which it had fallen
behind: the copy-prompt menu and agent bar were in the generator and
not in the committed pages. tests/site.mjs passes against the result.

Co-authored-by: Hanzo Dev <[email protected]>
2026-09-11 00:27:59 -07:00

748 lines
31 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>formal-lean-theorem-proving</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="alternate" type="text/markdown" href="/formal-lean-theorem-proving.md">
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/formal-lean-theorem-proving">
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/formal-lean-theorem-proving.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>formal-lean-theorem-proving</h1><p class="lede">Formalizing complex mathematics</p><h1>Lean 4 Theorem Proving</h1>
<h2>Overview</h2>
<p>Advanced formalization strategies, proof patterns, and architectural techniques for complex mathematical theorem proving and formal verification in Lean 4.</p>
<h2>Scope</h2>
<p><strong>Included:</strong></p>
<ul><li>Inductive type design</li><li>Well-founded recursion and termination</li><li>Quotient types and setoids</li><li>Proof by reflection</li><li>Automation strategies</li><li>Proof refactoring patterns</li><li>Large-scale formalization architecture</li><li>Abstraction and generalization techniques</li><li>Computational reflection</li><li>Tactic programming basics</li></ul>
<p><strong>Excluded:</strong></p>
<ul><li>Basic proof tactics (see <code>lean-proof-basics.md</code>)</li><li>Standard tactic library (see <code>lean-tactics.md</code>)</li><li>mathlib4 library usage (see <code>lean-mathlib4.md</code>)</li><li>Full metaprogramming (separate advanced skill)</li></ul>
<h2>When to Use This Skill</h2>
<p><strong>Primary use cases:</strong></p>
<ul><li>Formalizing complex mathematics</li><li>Designing custom inductive types</li><li>Proving termination of recursive functions</li><li>Building proof automation for domain</li><li>Refactoring large proof developments</li><li>Research-level formalization</li><li>Verified software development</li></ul>
<p><strong>Indicators you need this:</strong></p>
<ul><li>&quot;How do I formalize this mathematical concept?&quot;</li><li>&quot;How do I prove termination of this recursion?&quot;</li><li>&quot;How do I automate these repetitive proofs?&quot;</li><li>&quot;How do I structure a large formalization?&quot;</li><li>&quot;How do I use quotient types?&quot;</li></ul>
<p><strong>When to use other skills instead:</strong></p>
<ul><li>Learning basics → <code>lean-proof-basics.md</code></li><li>Standard tactics → <code>lean-tactics.md</code></li><li>Library search → <code>lean-mathlib4.md</code></li></ul>
<h2>Prerequisites</h2>
<p><strong>Required knowledge:</strong></p>
<ul><li>Lean 4 fundamentals (<code>lean-proof-basics.md</code>)</li><li>Advanced tactics (<code>lean-tactics.md</code>)</li><li>Type theory basics (dependent types, universe levels)</li><li>Mathematical maturity</li></ul>
<p><strong>Required setup:</strong></p>
<pre><code class="lang-bash"># Lean 4 with mathlib4
lake +leanprover/lean4:nightly-2024-01-15 new my_formalization math
cd my_formalization
lake exe cache get
lake build</code></pre>
<h2>Core Concepts</h2>
<h3>1. Inductive Types</h3>
<p>Foundation of Lean&#x27;s logic and data structures.</p>
<pre><code class="lang-lean">-- Simple inductive type
inductive MyNat where
| zero : MyNat
| succ : MyNat → MyNat
-- Indexed inductive type (dependent)
inductive Vec (α : Type u) : Nat → Type u where
| nil : Vec α 0
| cons : α → Vec α n → Vec α (n + 1)
-- Mutually inductive types
mutual
inductive Even : Nat → Prop where
| zero : Even 0
| succ_odd : Odd n → Even (n + 1)
inductive Odd : Nat → Prop where
| succ_even : Even n → Odd (n + 1)
end
-- Inductive predicates
inductive Le : Nat → Nat → Prop where
| refl : Le n n
| step : Le n m → Le n (m + 1)</code></pre>
<h3>2. Well-Founded Recursion</h3>
<p>Proving termination for complex recursive functions.</p>
<pre><code class="lang-lean">-- Well-founded relation
def sizeOf_list {α : Type} : List α → Nat
| [] =&gt; 0
| _::xs =&gt; 1 + sizeOf_list xs
-- Structural recursion (automatic termination)
def length {α : Type} : List α → Nat
| [] =&gt; 0
| _::xs =&gt; 1 + length xs
-- Well-founded recursion with custom measure
def ackermann (m n : Nat) : Nat :=
match m, n with
| 0, n =&gt; n + 1
| m+1, 0 =&gt; ackermann m 1
| m+1, n+1 =&gt; ackermann m (ackermann (m+1) n)
termination_by (m, n) -- Lexicographic ordering
-- Custom well-founded relation
def div2 (n : Nat) : Nat :=
if h : n &lt; 2 then 0
else 1 + div2 (n - 2)
termination_by n
decreasing_by simp_wf; omega</code></pre>
<h3>3. Quotient Types</h3>
<p>Formal quotients by equivalence relations.</p>
<pre><code class="lang-lean">-- Define equivalence relation
def IntEqv : (Nat × Nat) → (Nat × Nat) → Prop :=
fun (a, b) (c, d) =&gt; a + d = b + c
-- Prove it&#x27;s an equivalence
instance : Setoid (Nat × Nat) where
r := IntEqv
iseqv := {
refl := fun (a, b) =&gt; rfl
symm := fun h =&gt; h.symm
trans := fun h1 h2 =&gt; by
simp [IntEqv] at *
omega
}
-- Define quotient
def MyInt : Type := Quotient (inferInstanceAs (Setoid (Nat × Nat)))
-- Lift operations
def MyInt.add : MyInt → MyInt → MyInt :=
Quotient.lift₂
(fun (a, b) (c, d) =&gt; Quotient.mk _ (a + c, b + d))
(by
intro (a, b) (a&#x27;, b&#x27;) (c, d) (c&#x27;, d&#x27;) hab hcd
apply Quotient.sound
simp [IntEqv] at *
omega)</code></pre>
<h3>4. Proof by Reflection</h3>
<p>Prove properties by computation.</p>
<pre><code class="lang-lean">-- Decidable propositions via computation
def isEven (n : Nat) : Bool :=
n % 2 == 0
-- Reflect to proposition
theorem even_4 : isEven 4 = true := rfl
-- General reflection pattern
theorem even_iff_mod_eq_zero (n : Nat) :
isEven n = true ↔ n % 2 = 0 := by
simp [isEven]
cases Nat.decEq (n % 2) 0 &lt;;&gt; simp [*]
-- Use reflection for automation
theorem even_100 : 100 % 2 = 0 := by
have : isEven 100 = true := rfl
exact (even_iff_mod_eq_zero 100).mp this</code></pre>
<h2>Advanced Patterns</h2>
<h3>Pattern 1: Custom Inductive Predicates</h3>
<pre><code class="lang-lean">-- Define accessibility predicate
inductive Acc {α : Type} (r : α → α → Prop) : α → Prop where
| intro : (∀ y, r y x → Acc r y) → Acc r x
-- Prove well-foundedness
theorem natLt_wf : WellFounded (· &lt; · : Nat → Nat → Prop) :=
⟨fun n =&gt; by
induction n with
| zero =&gt;
constructor
intro y h
omega
| succ n ih =&gt;
constructor
intro y h
cases Nat.lt_or_eq_of_le (Nat.le_of_lt_succ h) with
| inl h&#x27; =&gt; exact ih.inv y h&#x27;
| inr h&#x27; =&gt; rw [←h&#x27;]; exact ih
⟩</code></pre>
<h3>Pattern 2: Sized Types</h3>
<pre><code class="lang-lean">-- Size-indexed vector operations
def Vec.append {α : Type} : Vec α m → Vec α n → Vec α (m + n)
| .nil, ys =&gt; ys
| .cons x xs, ys =&gt; .cons x (xs.append ys)
-- Type-safe head
def Vec.head {α : Type} : Vec α (n + 1) → α
| .cons x _ =&gt; x
-- Dependent pattern matching
def Vec.tail {α : Type} : Vec α (n + 1) → Vec α n
| .cons _ xs =&gt; xs</code></pre>
<h3>Pattern 3: Propositional Truncation</h3>
<pre><code class="lang-lean">-- Existential without data
structure Nonempty (α : Type u) : Prop where
intro :: (val : α)
-- Use for proof irrelevance
theorem exists_of_nonempty {α : Type} {p : α → Prop}
(h : Nonempty α) : (∃ x, True) :=
⟨h.val, trivial⟩
-- Squash for propositions
def TruncatedExists (p : α → Prop) : Prop :=
∃ x, p x -- Already in Prop, so truncated</code></pre>
<h3>Pattern 4: Proof Automation with Macros</h3>
<pre><code class="lang-lean">-- Simple tactic macro
macro &quot;solve_nat_eq&quot; : tactic =&gt;
`(tactic| omega)
example (n : Nat) : n + 0 = n := by solve_nat_eq
-- Macro with arguments
macro &quot;rw_all&quot; t:term : tactic =&gt;
`(tactic| rw [$t] at *)
-- Custom notation
notation:65 lhs:65 &quot; ≈ &quot; rhs:66 =&gt; Equivalence lhs rhs</code></pre>
<h3>Pattern 5: Well-Founded Induction Principles</h3>
<pre><code class="lang-lean">-- Define custom induction principle
theorem nat_strong_induction {p : Nat → Prop}
(h : ∀ n, (∀ m, m &lt; n → p m) → p n) :
∀ n, p n := by
intro n
suffices ∀ m, m &lt; n → p m from h n this
intro m hm
apply nat_strong_induction h
-- Use for complex recursion
def fastFib (n : Nat) : Nat :=
match n with
| 0 =&gt; 0
| 1 =&gt; 1
| n+2 =&gt; fastFib (n+1) + fastFib n
termination_by n</code></pre>
<h3>Pattern 6: Coinductive Types</h3>
<pre><code class="lang-lean">-- Infinite streams (coinductive)
coinductive Stream (α : Type u) : Type u where
| cons : α → Stream α → Stream α
-- Operations on streams
def Stream.head : Stream α → α
| .cons x _ =&gt; x
def Stream.tail : Stream α → Stream α
| .cons _ xs =&gt; xs
-- Bisimulation for equality
def Stream.bisim (R : Stream α → Stream α → Prop) : Prop :=
∀ s1 s2, R s1 s2 →
s1.head = s2.head ∧ R s1.tail s2.tail</code></pre>
<h3>Pattern 7: Proof Irrelevance Patterns</h3>
<pre><code class="lang-lean">-- Use Subtype for computationally relevant data
def Pos : Type := { n : Nat // n &gt; 0 }
def Pos.toNat (p : Pos) : Nat := p.val
-- Proofs are irrelevant
theorem pos_eq_of_val_eq (p q : Pos) (h : p.val = q.val) : p = q := by
cases p; cases q
simp at h
subst h
rfl
-- Use for predicate subtypes
def Even : Type := { n : Nat // n % 2 = 0 }</code></pre>
<h3>Pattern 8: Recursion-Recursion</h3>
<pre><code class="lang-lean">-- Mutually recursive functions
mutual
def even : Nat → Bool
| 0 =&gt; true
| n+1 =&gt; odd n
def odd : Nat → Bool
| 0 =&gt; false
| n+1 =&gt; even n
end
-- Prove properties mutually
mutual
theorem even_iff : even n = true ↔ n % 2 = 0 := by
cases n &lt;;&gt; simp [even, odd_iff, *]
theorem odd_iff : odd n = true ↔ n % 2 = 1 := by
cases n &lt;;&gt; simp [even, odd, even_iff, *]
end</code></pre>
<h3>Pattern 9: Abstract Nonsense (Category Theory Style)</h3>
<pre><code class="lang-lean">-- Abstract interface
class Functor (F : Type u → Type v) where
map : (α → β) → F α → F β
map_id : map (id : α → α) = id
map_comp : map (g ∘ f) = map g ∘ map f
-- Concrete instances
instance : Functor List where
map := List.map
map_id := List.map_id
map_comp := fun f g =&gt; (List.map_comp_map f g).symm
-- Generic theorems
theorem functor_preserves_const {F : Type → Type} [Functor F]
(x : α) (c : β) :
Functor.map (fun _ =&gt; c) (Functor.map (fun _ =&gt; x) fa) =
Functor.map (fun _ =&gt; c) fa := by
rw [←Functor.map_comp]
rfl</code></pre>
<h3>Pattern 10: Proof Combinators</h3>
<pre><code class="lang-lean">-- Compose proofs
def proof_comp {p q r : Prop} (h1 : p → q) (h2 : q → r) : p → r :=
fun hp =&gt; h2 (h1 hp)
-- Proof lifting
def lift_iff {p q : Prop} (h : p ↔ q) : (p → r) ↔ (q → r) :=
⟨fun hpr hq =&gt; hpr (h.mpr hq), fun hqr hp =&gt; hqr (h.mp hp)⟩
-- Proof functoriality
theorem map_proof {p q r s : Prop}
(hpq : p → q) (hrs : r → s)
(hqr : q → r) : p → s :=
fun hp =&gt; hrs (hqr (hpq hp))</code></pre>
<h2>Formalization Architecture</h2>
<h3>Large-Scale Organization</h3>
<pre><code class="lang-lean">-- File: MyProject/Basic.lean
-- Foundational definitions
-- File: MyProject/Properties.lean
import MyProject.Basic
-- Basic properties and lemmas
-- File: MyProject/Advanced.lean
import MyProject.Properties
-- Advanced theorems
-- File: MyProject/Automation.lean
import MyProject.Properties
-- Custom tactics and automation</code></pre>
<h3>Abstraction Levels</h3>
<pre><code class="lang-lean">-- Level 1: Raw definition
def raw_gcd (a b : Nat) : Nat := sorry
-- Level 2: Specification
theorem gcd_spec (a b : Nat) :
(raw_gcd a b ∣ a) ∧
(raw_gcd a b ∣ b) ∧
(∀ d, d ∣ a → d ∣ b → d ∣ raw_gcd a b) := sorry
-- Level 3: Interface
class GCD (α : Type) [Dvd α] where
gcd : α → α → α
gcd_dvd_left : ∀ a b, gcd a b ∣ a
gcd_dvd_right : ∀ a b, gcd a b ∣ b
dvd_gcd : ∀ a b d, d ∣ a → d ∣ b → d ∣ gcd a b</code></pre>
<h3>Modular Proofs</h3>
<pre><code class="lang-lean">-- Separate concerns
namespace IntegerProps
theorem add_comm : ∀ a b : Int, a + b = b + a := sorry
theorem mul_comm : ∀ a b : Int, a * b = b * a := sorry
end IntegerProps
namespace RingProps
variable [Ring R]
theorem distrib : ∀ a b c : R, a * (b + c) = a * b + a * c := sorry
end RingProps</code></pre>
<h2>Quick Reference</h2>
<h3>Inductive Type Checklist</h3>
<pre><code class="lang-lean">-- 1. Define constructors
inductive MyType where
| constructor1 : ...
| constructor2 : ...
-- 2. Define recursion principle (if needed)
def MyType.rec ...
-- 3. Prove induction principle
theorem MyType.induction ...
-- 4. Define operations
def MyType.operation ...
-- 5. Prove properties
theorem MyType.property ...</code></pre>
<h3>Well-Founded Recursion Template</h3>
<pre><code class="lang-lean">def recursiveFunction (x : α) : β :=
match ... with
| base_case =&gt; ...
| recursive_case =&gt; ... recursiveFunction ...
termination_by measure_function x
decreasing_by
-- Prove recursive calls decrease measure
simp_wf
-- Additional tactics (omega, etc.)</code></pre>
<h3>Quotient Type Template</h3>
<pre><code class="lang-lean">-- 1. Define relation
def myRel : α → α → Prop := ...
-- 2. Prove equivalence
instance : Setoid α where
r := myRel
iseqv := ⟨refl_proof, symm_proof, trans_proof⟩
-- 3. Define quotient
def MyQuotient := Quotient (inferInstanceAs (Setoid α))
-- 4. Lift operations
def MyQuotient.op := Quotient.lift (raw_op) (congruence_proof)</code></pre>
<h2>Anti-Patterns</h2>
<h3>Anti-Pattern 1: Poor Abstraction</h3>
<pre><code class="lang-lean">-- BAD: Over-concrete definition
def list_sum_nat : List Nat → Nat
| [] =&gt; 0
| x::xs =&gt; x + list_sum_nat xs
-- GOOD: Generic with type classes
def list_sum {α : Type} [Add α] [Zero α] : List α → α
| [] =&gt; 0
| x::xs =&gt; x + list_sum xs</code></pre>
<h3>Anti-Pattern 2: Ignoring Automation</h3>
<pre><code class="lang-lean">-- BAD: Manual proof
theorem add_assoc (a b c : Nat) : (a + b) + c = a + (b + c) := by
induction a with
| zero =&gt; rfl
| succ a ih =&gt;
simp [Nat.add_succ]
rw [ih]
-- GOOD: Use automation
theorem add_assoc (a b c : Nat) : (a + b) + c = a + (b + c) := by
omega</code></pre>
<h3>Anti-Pattern 3: Verbose Proofs</h3>
<pre><code class="lang-lean">-- BAD: Overly detailed
theorem my_theorem : p ∧ q → q ∧ p := by
intro h
have hp := h.left
have hq := h.right
have hq_again := hq
have hp_again := hp
exact ⟨hq_again, hp_again⟩
-- GOOD: Concise
theorem my_theorem : p ∧ q → q ∧ p := by
intro ⟨hp, hq⟩
exact ⟨hq, hp⟩
-- BEST: Term mode
theorem my_theorem : p ∧ q → q ∧ p :=
fun ⟨hp, hq⟩ =&gt; ⟨hq, hp⟩</code></pre>
<h3>Anti-Pattern 4: Not Using calc</h3>
<pre><code class="lang-lean">-- BAD: Manual chaining
theorem transitivity (h1 : a = b) (h2 : b = c) (h3 : c = d) : a = d := by
rw [h1, h2, h3]
-- GOOD: calc for clarity
theorem transitivity (h1 : a = b) (h2 : b = c) (h3 : c = d) : a = d :=
calc a = b := h1
_ = c := h2
_ = d := h3</code></pre>
<h3>Anti-Pattern 5: Monolithic Proofs</h3>
<pre><code class="lang-lean">-- BAD: 100-line proof
theorem huge_theorem : complicated_statement := by
-- 100 lines of tactics
sorry
-- GOOD: Modular with lemmas
theorem helper_lemma1 : ... := by ...
theorem helper_lemma2 : ... := by ...
theorem huge_theorem : complicated_statement := by
have h1 := helper_lemma1
have h2 := helper_lemma2
-- Short proof using h1, h2</code></pre>
<h3>Anti-Pattern 6: Ignoring Type Universe Issues</h3>
<pre><code class="lang-lean">-- BAD: Type errors due to universe levels
def bad_list_of_types : List Type := [Nat, String]
-- Error: Type : Type 1, not Type 0
-- GOOD: Explicit universe polymorphism
def good_wrapper {α : Type u} (x : α) : { β : Type u // β = α } :=
⟨α, rfl⟩</code></pre>
<h2>Related Skills</h2>
<ul><li><strong>lean-proof-basics.md</strong>: Foundational proof techniques</li><li><strong>lean-tactics.md</strong>: Tactic library and automation</li><li><strong>lean-mathlib4.md</strong>: Using mathlib4 library</li><li><strong>lean-metaprogramming.md</strong>: Advanced custom tactics (advanced skill)</li><li><strong>smt-theory-applications.md</strong>: Automated reasoning with SMT</li></ul>
<h2>References</h2>
<ul><li><a href="https://lean-lang.org/theorem_proving_in_lean4/">Theorem Proving in Lean 4</a></li><li><a href="https://lean-lang.org/functional_programming_in_lean/">Functional Programming in Lean</a></li><li><a href="https://lean-lang.org/lean4/doc/reference.html">The Lean 4 Reference Manual</a></li><li><a href="https://github.com/leanprover-community/mathlib4/tree/master/Archive">mathlib4 Archive</a></li><li><a href="https://leanprover.zulipchat.com/">Lean Zulip (for questions)</a></li></ul>
<h2>Examples</h2>
<h3>Example 1: Binary Trees with Proofs</h3>
<pre><code class="lang-lean">-- Define binary tree
inductive Tree (α : Type) where
| leaf : Tree α
| node : α → Tree α → Tree α → Tree α
-- Size function
def Tree.size {α : Type} : Tree α → Nat
| .leaf =&gt; 0
| .node _ l r =&gt; 1 + l.size + r.size
-- Mirror function
def Tree.mirror {α : Type} : Tree α → Tree α
| .leaf =&gt; .leaf
| .node x l r =&gt; .node x r.mirror l.mirror
-- Prove involution
theorem Tree.mirror_involutive {α : Type} (t : Tree α) :
t.mirror.mirror = t := by
induction t with
| leaf =&gt; rfl
| node x l r ihl ihr =&gt;
simp [mirror, ihl, ihr]
-- Prove size preservation
theorem Tree.size_mirror {α : Type} (t : Tree α) :
t.mirror.size = t.size := by
induction t with
| leaf =&gt; rfl
| node x l r ihl ihr =&gt;
simp [mirror, size, ihl, ihr]
omega</code></pre>
<h3>Example 2: Ackermann Function with Termination</h3>
<pre><code class="lang-lean">-- Ackermann function (classic well-founded recursion)
def ackermann : Nat → Nat → Nat
| 0, n =&gt; n + 1
| m + 1, 0 =&gt; ackermann m 1
| m + 1, n + 1 =&gt; ackermann m (ackermann (m + 1) n)
termination_by m n =&gt; (m, n)
-- Properties
theorem ackermann_pos (m n : Nat) : 0 &lt; ackermann m n := by
match m, n with
| 0, n =&gt; omega
| m + 1, 0 =&gt;
have : 0 &lt; ackermann m 1 := ackermann_pos m 1
exact this
| m + 1, n + 1 =&gt;
have : 0 &lt; ackermann m (ackermann (m + 1) n) :=
ackermann_pos m (ackermann (m + 1) n)
exact this
termination_by m n =&gt; (m, n)</code></pre>
<h3>Example 3: Quotient for Rational Numbers</h3>
<pre><code class="lang-lean">-- Rational numbers as quotient
def RatEqv : (Int × Int) → (Int × Int) → Prop :=
fun (a, b) (c, d) =&gt; a * d = b * c
instance : Setoid (Int × Int) where
r := RatEqv
iseqv := {
refl := fun (a, b) =&gt; rfl
symm := fun h =&gt; h.symm
trans := fun {x y z} h1 h2 =&gt; by
obtain ⟨a, b⟩ := x
obtain ⟨c, d⟩ := y
obtain ⟨e, f⟩ := z
simp [RatEqv] at *
-- Proof by ring manipulation
have : a * f * (c * d) = b * e * (c * d) := by
calc a * f * (c * d) = (a * d) * (c * f) := by ring
_ = (b * c) * (c * f) := by rw [h1]
_ = b * (c * c * f) := by ring
_ = b * (c * e * d) := by rw [h2]; ring
_ = b * e * (c * d) := by ring
sorry -- Need non-zero denominators
}
def Rat : Type := Quotient (inferInstanceAs (Setoid (Int × Int)))</code></pre>
<hr>
<p><strong>Skill Metadata:</strong></p>
<ul><li>Scope: Advanced Lean 4 theorem proving and formalization</li><li>Complexity: Advanced</li><li>Prerequisites: lean-proof-basics.md, lean-tactics.md, lean-mathlib4.md</li><li>Related: lean-metaprogramming.md, smt-theory-applications.md</li></ul>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/formal-lean-theorem-proving.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>