Files
skills/public/curry-howard.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

551 lines
24 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>curry-howard</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="/curry-howard.md">
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/curry-howard">
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/curry-howard.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>curry-howard</h1><p class="lede">Curry-Howard correspondence relating proofs and programs, propositions and types</p><h1>Curry-Howard Correspondence</h1>
<p><strong>Scope</strong>: Propositions as types, proofs as programs, logical connectives as type constructors <strong>Lines</strong>: ~380 <strong>Last Updated</strong>: 2025-10-25</p>
<h2>When to Use This Skill</h2>
<p>Activate this skill when:</p>
<ul><li>Understanding connection between logic and programming</li><li>Working with proof assistants (Lean, Coq, Agda)</li><li>Extracting programs from constructive proofs</li><li>Designing type systems with logical foundations</li><li>Proving program properties via types</li><li>Studying intuitionistic logic and type theory</li></ul>
<h2>Core Concepts</h2>
<h3>The Correspondence</h3>
<p><strong>Curry-Howard Isomorphism</strong>: Deep connection between:</p>
<ul><li>Propositions ↔ Types</li><li>Proofs ↔ Programs</li><li>Proof normalization ↔ Program evaluation</li></ul>
<p>| Logic | Type Theory | Programming | |-------|-------------|-------------| | Proposition P | Type P | Type P | | Proof of P | Term of type P | Value of type P | | P → Q | Function type P → Q | Function from P to Q | | P ∧ Q | Product type P × Q | Pair (p, q) | | P ∨ Q | Sum type P + Q | Either left(p) or right(q) | | ⊤ (true) | Unit type 1 | () | | ⊥ (false) | Empty type 0 | No values | | ¬P | P → ⊥ | Function from P to absurdity | | ∀x. P(x) | Π(x:A). P(x) | Dependent function | | ∃x. P(x) | Σ(x:A). P(x) | Dependent pair |</p>
<pre><code class="lang-python">from dataclasses import dataclass
from typing import Union
# Propositions as types
@dataclass
class Implies:
&quot;&quot;&quot;P → Q&quot;&quot;&quot;
premise: &#x27;Prop&#x27;
conclusion: &#x27;Prop&#x27;
def __repr__(self):
return f&quot;({self.premise} → {self.conclusion})&quot;
@dataclass
class And:
&quot;&quot;&quot;P ∧ Q&quot;&quot;&quot;
left: &#x27;Prop&#x27;
right: &#x27;Prop&#x27;
def __repr__(self):
return f&quot;({self.left} ∧ {self.right})&quot;
@dataclass
class Or:
&quot;&quot;&quot;P ∨ Q&quot;&quot;&quot;
left: &#x27;Prop&#x27;
right: &#x27;Prop&#x27;
def __repr__(self):
return f&quot;({self.left} ∨ {self.right})&quot;
@dataclass
class Not:
&quot;&quot;&quot;¬P ≡ P → ⊥&quot;&quot;&quot;
prop: &#x27;Prop&#x27;
def __repr__(self):
return f&quot;¬{self.prop}&quot;
@dataclass
class True_:
&quot;&quot;&quot;⊤&quot;&quot;&quot;
def __repr__(self):
return &quot;⊤&quot;
@dataclass
class False_:
&quot;&quot;&quot;⊥&quot;&quot;&quot;
def __repr__(self):
return &quot;⊥&quot;
Prop = Union[Implies, And, Or, Not, True_, False_]
# Proofs as programs
@dataclass
class Lambda:
&quot;&quot;&quot;λx. M - proof of P → Q&quot;&quot;&quot;
var: str
body: &#x27;Proof&#x27;
@dataclass
class Pair:
&quot;&quot;&quot;(M, N) - proof of P ∧ Q&quot;&quot;&quot;
fst: &#x27;Proof&#x27;
snd: &#x27;Proof&#x27;
@dataclass
class Inl:
&quot;&quot;&quot;inl(M) - proof of P ∨ Q (left)&quot;&quot;&quot;
proof: &#x27;Proof&#x27;
@dataclass
class Inr:
&quot;&quot;&quot;inr(N) - proof of P ∨ Q (right)&quot;&quot;&quot;
proof: &#x27;Proof&#x27;
@dataclass
class Unit:
&quot;&quot;&quot;() - proof of ⊤&quot;&quot;&quot;
pass
Proof = Union[Lambda, Pair, Inl, Inr, Unit]
print(&quot;Proposition P → Q corresponds to function type P → Q&quot;)
print(&quot;Proof of P → Q is a function taking proof of P to proof of Q&quot;)</code></pre>
<h3>Logical Connectives as Types</h3>
<p><strong>Implication (→)</strong>:</p>
<pre><code class="lang-python"># P → Q corresponds to function type P → Q
# Proof: λx:P. M : Q (function taking P to Q)
# Example: Prove A → A (identity)
# Proof: λx. x
# In Lean 4:
&quot;&quot;&quot;
theorem id (A : Prop) : A → A := fun x =&gt; x
-- Or with tactics:
theorem id&#x27; (A : Prop) : A → A := by
intro x
exact x
&quot;&quot;&quot;
def prove_implication_id():
&quot;&quot;&quot;A → A: identity function&quot;&quot;&quot;
return Lambda(&#x27;x&#x27;, Variable(&#x27;x&#x27;))
print(&quot;Proof of A → A is the identity function: λx. x&quot;)</code></pre>
<p><strong>Conjunction (∧)</strong>:</p>
<pre><code class="lang-python"># P ∧ Q corresponds to product type P × Q
# Proof: (M, N) where M : P, N : Q
# Example: Prove (A ∧ B) → (B ∧ A) (commutativity)
# Proof: λp. (snd p, fst p)
# In Lean 4:
&quot;&quot;&quot;
theorem and_comm (A B : Prop) : A ∧ B → B ∧ A := by
intro ⟨a, b⟩
exact ⟨b, a⟩
-- Equivalent:
theorem and_comm&#x27; (A B : Prop) : A ∧ B → B ∧ A :=
fun ⟨a, b⟩ =&gt; ⟨b, a⟩
&quot;&quot;&quot;
def prove_and_comm():
&quot;&quot;&quot;(A ∧ B) → (B ∧ A)&quot;&quot;&quot;
return Lambda(&#x27;p&#x27;, Pair(Project2(Variable(&#x27;p&#x27;)), Project1(Variable(&#x27;p&#x27;))))
print(&quot;Proof of (A ∧ B) → (B ∧ A) swaps pair components&quot;)</code></pre>
<p><strong>Disjunction (∨)</strong>:</p>
<pre><code class="lang-python"># P ∨ Q corresponds to sum type P + Q
# Proof: inl(M) : P ∨ Q or inr(N) : P ∨ Q
# Example: Prove A → (A ∨ B)
# Proof: λx. inl(x)
# In Lean 4:
&quot;&quot;&quot;
theorem or_intro_left (A B : Prop) : A → A ∨ B := by
intro a
left
exact a
-- Equivalent:
theorem or_intro_left&#x27; (A B : Prop) : A → A ∨ B :=
fun a =&gt; Or.inl a
&quot;&quot;&quot;
def prove_or_intro_left():
&quot;&quot;&quot;A → (A ∨ B)&quot;&quot;&quot;
return Lambda(&#x27;x&#x27;, Inl(Variable(&#x27;x&#x27;)))
print(&quot;Proof of A → (A ∨ B) injects A into left side&quot;)</code></pre>
<p><strong>Negation (¬)</strong>:</p>
<pre><code class="lang-python"># ¬P ≡ P → ⊥
# Proof of ¬P is a function from P to absurdity
# Example: Prove ¬(A ∧ ¬A) (non-contradiction)
# Proof: λp. (snd p) (fst p)
# In Lean 4:
&quot;&quot;&quot;
theorem not_and_not (A : Prop) : ¬(A ∧ ¬A) := by
intro ⟨a, na⟩
exact na a
-- Equivalent:
theorem not_and_not&#x27; (A : Prop) : ¬(A ∧ ¬A) :=
fun ⟨a, na⟩ =&gt; na a
&quot;&quot;&quot;
def prove_non_contradiction():
&quot;&quot;&quot;¬(A ∧ ¬A)&quot;&quot;&quot;
# (A ∧ ¬A) → ⊥
# λp. (snd p) (fst p) [where snd p : A → ⊥, fst p : A]
return Lambda(&#x27;p&#x27;, Apply(Project2(Variable(&#x27;p&#x27;)), Project1(Variable(&#x27;p&#x27;))))
print(&quot;Proof of ¬(A ∧ ¬A): apply ¬A to A to get ⊥&quot;)</code></pre>
<h3>Proof Extraction</h3>
<p><strong>Extracting programs from proofs</strong>:</p>
<pre><code class="lang-python"># Lean 4 example: Extracting program from constructive proof
&quot;&quot;&quot;
-- Prove: ∃(x:Nat). x &gt; 0
theorem exists_positive : ∃(x:Nat), x &gt; 0 := by
use 1
norm_num
-- Extract witness:
#eval (exists_positive.choose : Nat) -- 1
-- Extracting a sorting function from proof of sorting correctness:
def sort (xs : List Nat) : {ys : List Nat // Sorted ys ∧ Permutation xs ys} := ...
-- Type ensures:
-- 1. Result is sorted
-- 2. Result is permutation of input
-- Program AND proof in one!
&quot;&quot;&quot;
print(&quot;Proofs in constructive logic contain computational content&quot;)
print(&quot;Can extract programs from proofs&quot;)</code></pre>
<h3>Classical vs Intuitionistic Logic</h3>
<p><strong>Law of Excluded Middle (LEM)</strong>: P ∨ ¬P</p>
<pre><code class="lang-python"># LEM is NOT provable in intuitionistic logic
# Cannot construct P ∨ ¬P without knowing which one holds
# In classical logic (Lean with Classical axiom):
&quot;&quot;&quot;
open Classical
theorem lem (P : Prop) : P ∨ ¬P := em P
-- Non-constructive proof by contradiction:
theorem sqrt_2_irrational : Irrational (√2) := by
by_contra h
-- Assume √2 is rational, derive contradiction
...
&quot;&quot;&quot;
# In intuitionistic logic:
&quot;&quot;&quot;
-- Can only prove double negation of LEM:
theorem not_not_lem (P : Prop) : ¬¬(P ∨ ¬P) := by
intro h
apply h
right
intro p
apply h
left
exact p
&quot;&quot;&quot;
print(&quot;Classical logic: P ∨ ¬P always holds&quot;)
print(&quot;Intuitionistic logic: Need explicit construction of P or ¬P&quot;)</code></pre>
<h3>Quantifiers</h3>
<p><strong>Universal quantification (∀)</strong>:</p>
<pre><code class="lang-python"># ∀(x:A). P(x) corresponds to Π(x:A). P(x)
# Proof: function from x to proof of P(x)
# Example: Prove ∀(n:Nat). n = n
# Proof: λn. refl
# In Lean 4:
&quot;&quot;&quot;
theorem forall_eq (n : Nat) : n = n := rfl
-- Explicitly as ∀:
theorem forall_eq&#x27; : ∀(n : Nat), n = n := fun n =&gt; rfl
&quot;&quot;&quot;
print(&quot;Proof of ∀(n:Nat). P(n) is a function λn. proof of P(n)&quot;)</code></pre>
<p><strong>Existential quantification (∃)</strong>:</p>
<pre><code class="lang-python"># ∃(x:A). P(x) corresponds to Σ(x:A). P(x)
# Proof: pair (witness, proof that witness satisfies P)
# Example: Prove ∃(n:Nat). n &gt; 5
# Proof: (6, proof that 6 &gt; 5)
# In Lean 4:
&quot;&quot;&quot;
theorem exists_gt_5 : ∃(n : Nat), n &gt; 5 := by
use 6
norm_num
-- Equivalent:
theorem exists_gt_5&#x27; : ∃(n : Nat), n &gt; 5 :=
⟨6, by norm_num⟩
&quot;&quot;&quot;
print(&quot;Proof of ∃(n:Nat). P(n) is a pair: (witness, proof P(witness))&quot;)</code></pre>
<hr>
<h2>Patterns</h2>
<h3>Pattern 1: Modus Ponens</h3>
<pre><code class="lang-lean">-- Lean 4
theorem modus_ponens (P Q : Prop) : (P → Q) → P → Q :=
fun f p =&gt; f p
-- Program: function application!</code></pre>
<h3>Pattern 2: Curry/Uncurry</h3>
<pre><code class="lang-lean">-- Lean 4
theorem curry (A B C : Prop) : ((A ∧ B) → C) → (A → B → C) :=
fun f a b =&gt; f ⟨a, b⟩
theorem uncurry (A B C : Prop) : (A → B → C) → ((A ∧ B) → C) :=
fun f ⟨a, b⟩ =&gt; f a b</code></pre>
<h3>Pattern 3: De Morgan&#x27;s Laws</h3>
<pre><code class="lang-lean">-- Lean 4
-- Intuitionistically valid:
theorem de_morgan_1 (A B : Prop) : ¬(A ∨ B) → ¬A ∧ ¬B := by
intro h
constructor
· intro a; apply h; left; exact a
· intro b; apply h; right; exact b
-- Requires classical logic:
theorem de_morgan_2 (A B : Prop) : ¬A ∧ ¬B → ¬(A ∨ B) := by
intro ⟨na, nb⟩ h
cases h with
| inl a =&gt; exact na a
| inr b =&gt; exact nb b</code></pre>
<hr>
<h2>Quick Reference</h2>
<h3>Correspondence Table</h3>
<p>| Logic | Type | Proof Term | |-------|------|------------| | P → Q | P → Q | λx:P. M | | P ∧ Q | P × Q | (M, N) | | P ∨ Q | P + Q | inl(M) \| inr(N) | | ⊤ | Unit | () | | ⊥ | Empty | (no terms) | | ¬P | P → ⊥ | λx:P. absurd | | ∀x. P(x) | Π(x:A). P(x) | λx. M | | ∃x. P(x) | Σ(x:A). P(x) | (a, M) |</p>
<h3>Proof Tactics (Lean 4)</h3>
<pre><code class="lang-lean">intro -- Introduce hypothesis (λ)
exact -- Provide exact proof
constructor -- Build ∧ or ∃
left/right -- Build ∨
cases -- Case split on ∨ or ∃
apply -- Function application</code></pre>
<hr>
<h2>Anti-Patterns</h2>
<p>❌ <strong>Using classical logic unnecessarily</strong>: LEM makes proofs non-constructive ✅ Prefer constructive proofs when possible (extract programs)</p>
<p>❌ <strong>Confusing provability and truth</strong>: ¬¬P doesn&#x27;t imply P intuitionistically ✅ Understand difference between classical and intuitionistic logic</p>
<p>❌ <strong>Ignoring computational content</strong>: Proofs are programs! ✅ Exploit Curry-Howard to extract verified programs</p>
<hr>
<h2>Related Skills</h2>
<ul><li><code>lambda-calculus.md</code> - Untyped foundation</li><li><code>type-systems.md</code> - Typed λ-calculus</li><li><code>dependent-types.md</code> - Dependent functions (∀) and pairs (∃)</li><li><code>formal/lean-proof-basics.md</code> - Practical proof development</li><li><code>program-verification.md</code> - Using proofs to verify programs</li></ul>
<hr>
<p><strong>Last Updated</strong>: 2025-10-25 <strong>Format Version</strong>: 1.0 (Atomic)</p>
<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="/curry-howard.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>