mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
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]>
748 lines
31 KiB
HTML
748 lines
31 KiB
HTML
<!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>"How do I formalize this mathematical concept?"</li><li>"How do I prove termination of this recursion?"</li><li>"How do I automate these repetitive proofs?"</li><li>"How do I structure a large formalization?"</li><li>"How do I use quotient types?"</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'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
|
||
| [] => 0
|
||
| _::xs => 1 + sizeOf_list xs
|
||
|
||
-- Structural recursion (automatic termination)
|
||
def length {α : Type} : List α → Nat
|
||
| [] => 0
|
||
| _::xs => 1 + length xs
|
||
|
||
-- Well-founded recursion with custom measure
|
||
def ackermann (m n : Nat) : Nat :=
|
||
match m, n with
|
||
| 0, n => n + 1
|
||
| m+1, 0 => ackermann m 1
|
||
| m+1, n+1 => ackermann m (ackermann (m+1) n)
|
||
termination_by (m, n) -- Lexicographic ordering
|
||
|
||
-- Custom well-founded relation
|
||
def div2 (n : Nat) : Nat :=
|
||
if h : n < 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) => a + d = b + c
|
||
|
||
-- Prove it's an equivalence
|
||
instance : Setoid (Nat × Nat) where
|
||
r := IntEqv
|
||
iseqv := {
|
||
refl := fun (a, b) => rfl
|
||
symm := fun h => h.symm
|
||
trans := fun h1 h2 => 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) => Quotient.mk _ (a + c, b + d))
|
||
(by
|
||
intro (a, b) (a', b') (c, d) (c', d') 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 <;> 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 (· < · : Nat → Nat → Prop) :=
|
||
⟨fun n => by
|
||
induction n with
|
||
| zero =>
|
||
constructor
|
||
intro y h
|
||
omega
|
||
| succ n ih =>
|
||
constructor
|
||
intro y h
|
||
cases Nat.lt_or_eq_of_le (Nat.le_of_lt_succ h) with
|
||
| inl h' => exact ih.inv y h'
|
||
| inr h' => rw [←h']; 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 => ys
|
||
| .cons x xs, ys => .cons x (xs.append ys)
|
||
|
||
-- Type-safe head
|
||
def Vec.head {α : Type} : Vec α (n + 1) → α
|
||
| .cons x _ => x
|
||
|
||
-- Dependent pattern matching
|
||
def Vec.tail {α : Type} : Vec α (n + 1) → Vec α n
|
||
| .cons _ xs => 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 "solve_nat_eq" : tactic =>
|
||
`(tactic| omega)
|
||
|
||
example (n : Nat) : n + 0 = n := by solve_nat_eq
|
||
|
||
-- Macro with arguments
|
||
macro "rw_all" t:term : tactic =>
|
||
`(tactic| rw [$t] at *)
|
||
|
||
-- Custom notation
|
||
notation:65 lhs:65 " ≈ " rhs:66 => 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 < n → p m) → p n) :
|
||
∀ n, p n := by
|
||
intro n
|
||
suffices ∀ m, m < 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 => 0
|
||
| 1 => 1
|
||
| n+2 => 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 _ => x
|
||
|
||
def Stream.tail : Stream α → Stream α
|
||
| .cons _ xs => 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 > 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 => true
|
||
| n+1 => odd n
|
||
|
||
def odd : Nat → Bool
|
||
| 0 => false
|
||
| n+1 => even n
|
||
end
|
||
|
||
-- Prove properties mutually
|
||
mutual
|
||
theorem even_iff : even n = true ↔ n % 2 = 0 := by
|
||
cases n <;> simp [even, odd_iff, *]
|
||
|
||
theorem odd_iff : odd n = true ↔ n % 2 = 1 := by
|
||
cases n <;> 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 => (List.map_comp_map f g).symm
|
||
|
||
-- Generic theorems
|
||
theorem functor_preserves_const {F : Type → Type} [Functor F]
|
||
(x : α) (c : β) :
|
||
Functor.map (fun _ => c) (Functor.map (fun _ => x) fa) =
|
||
Functor.map (fun _ => 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 => h2 (h1 hp)
|
||
|
||
-- Proof lifting
|
||
def lift_iff {p q : Prop} (h : p ↔ q) : (p → r) ↔ (q → r) :=
|
||
⟨fun hpr hq => hpr (h.mpr hq), fun hqr hp => 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 => 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 => ...
|
||
| recursive_case => ... 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
|
||
| [] => 0
|
||
| x::xs => x + list_sum_nat xs
|
||
|
||
-- GOOD: Generic with type classes
|
||
def list_sum {α : Type} [Add α] [Zero α] : List α → α
|
||
| [] => 0
|
||
| x::xs => 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 => rfl
|
||
| succ a ih =>
|
||
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⟩ => ⟨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 => 0
|
||
| .node _ l r => 1 + l.size + r.size
|
||
|
||
-- Mirror function
|
||
def Tree.mirror {α : Type} : Tree α → Tree α
|
||
| .leaf => .leaf
|
||
| .node x l r => .node x r.mirror l.mirror
|
||
|
||
-- Prove involution
|
||
theorem Tree.mirror_involutive {α : Type} (t : Tree α) :
|
||
t.mirror.mirror = t := by
|
||
induction t with
|
||
| leaf => rfl
|
||
| node x l r ihl ihr =>
|
||
simp [mirror, ihl, ihr]
|
||
|
||
-- Prove size preservation
|
||
theorem Tree.size_mirror {α : Type} (t : Tree α) :
|
||
t.mirror.size = t.size := by
|
||
induction t with
|
||
| leaf => rfl
|
||
| node x l r ihl ihr =>
|
||
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 => n + 1
|
||
| m + 1, 0 => ackermann m 1
|
||
| m + 1, n + 1 => ackermann m (ackermann (m + 1) n)
|
||
termination_by m n => (m, n)
|
||
|
||
-- Properties
|
||
theorem ackermann_pos (m n : Nat) : 0 < ackermann m n := by
|
||
match m, n with
|
||
| 0, n => omega
|
||
| m + 1, 0 =>
|
||
have : 0 < ackermann m 1 := ackermann_pos m 1
|
||
exact this
|
||
| m + 1, n + 1 =>
|
||
have : 0 < ackermann m (ackermann (m + 1) n) :=
|
||
ackermann_pos m (ackermann (m + 1) n)
|
||
exact this
|
||
termination_by m n => (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) => a * d = b * c
|
||
|
||
instance : Setoid (Int × Int) where
|
||
r := RatEqv
|
||
iseqv := {
|
||
refl := fun (a, b) => rfl
|
||
symm := fun h => h.symm
|
||
trans := fun {x y z} h1 h2 => 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> |