>100 Views
November 14, 26
スライド概要
2026/11/13 [Lean] Theorem proving in Lean4 読書会 /ゆるIT勉強会 で発表した資料です。
https://yurufuwait-hmmt-online.connpass.com/event/412604/
Theorem Proving in Lean 4 を Lean 入門者向けに解説しています。
原文はこちら:https://leanprover.github.io/theorem_proving_in_lean4/
初回:Theorem Proving in Lean4 を読む会#1 ― 第1章
https://www.docswell.com/s/imamuray/ZJWVME-2026-10-22-201931
前回:Theorem Proving in Lean4 を読む会#4 ― 第3章 3.3-3.7
https://www.docswell.com/s/imamuray/Z3JVVP-2026-11-07-084758
次回:11/20以降
ぷろぐらま
Theorem Proving in Lean 4 を読む会#5 4. Quantifiers and Equality 2026/11/13 21:30~ 1
4. Quantifiers and Equality 2
4.1 全称量化子(Universal Quantifier) 「すべての〜について」を表す は「すべての x : α について p x が成立する」という命題 p : α → Prop は、型 α の値を受け取って命題を返す関数(述語) r : α → α → Prop は、2つの値の関係を表す関数 例えば、 r x y は「 x と y の間に関係 r が成立する」という意味。 ∀ x : α, p x 3
全称量化子には2つの規則がある 規則 内容 導入 任意の x について p x を証明すれば、 ∀ x, p x を証明できる 除去 ∀ x, p x があれば、任意の値 t について p t を得られる 4
全称量化子の導入と除去 例: example (α : Type) (p q : α → Prop) : (∀ x : α, p x ∧ q x) → ∀ y : α, p y := fun h : ∀ x : α, p x ∧ q x => fun y : α => show p y from (h y).left 証明の流れ 1. h は、任意の x について p x ∧ q x が成立するという証明。 2. fun y => で任意の y を受け取る (全称量化子の導入) 。 3. h y によって p y ∧ q y の証明を得る (全称量化子の除去) 。 4. .left で左側の p y を取り出す。 5
全称量化子と関数 全称量化子は依存関数型の別表記 次の2つはLeanでは同じ意味を持つ。 variable (α : Type) (p : α → Prop) -#check ∀ x : α, p x #check (x : α) → p x 全称命題の証明は、任意の値を受け取って、その値についての証明を返す関数として 表現できる。 6
含意 → との関係 は、入力に関係なく戻り値の型が β である関数型。 (x : α) → p x は、戻り値の型が入力 x に依存する関数型。 p → q も、 ∀ x : p, q の特殊な場合と考えられる。 α → β 7
暗黙の引数 推移律の例: variable (α : Type) (r : α → α → Prop) variable (trans_r : ∀ {x y z}, r x y → r y z → r x z) variable (a b c : α) variable (hab : r a b) (hbc : r b c) trans_r hab hbc は暗黙の引数。 hab と hbc からLeanが値を推論する。 明示的に a b c を渡さなくても、 r a c の証明を得られる。 ただし、推論に必要な情報が不足している場合は、Leanが値を特定できないこと もある。 {x y z} 8
4.2 Equality における等式 Lean では a = b によって、2つの項が等しいことを表す 等式は同値関係として、次の性質を持つ 性質 Leanでの表現 反射律 Eq.refl : a = a 対称律 Eq.symm : a = b → b = a 推移律 Eq.trans : a = b → b = c → a = c これらの性質を使って、等式を組み合わせた証明を作れる Lean 9
等式の証明と計算 rfl は計算で等しい式も証明できる は、同じ項どうしの等しさを証明する Leanでは、計算によって同じ形になる式も等しいと判断される rfl は Eq.refl _ の記法 Eq.refl variable (α β : Type) example (f : α → β) (a : α) : (fun x => f x) a = f a := rfl example (a : α) (b : β) : (a, b).1 = a := rfl example : 2 + 3 = 5 := rfl 関数適用や直積の射影、数値計算なども、簡約によって等しいと確認できる 10
等式を使った置換 等しいものは置き換えられる があり、 h2 : p a が証明できているとする a を b に置き換えても、命題が成立することを証明できる Eq.subst または ▸ ( \t と入力)を使う ▸ は Eq.subst と Eq.symm をもとにしたマクロ h1 : a = b variable (α β : Type) example (α : Type) (a b : α) (p : α → Prop) (h1 : a = b) (h2 : p a) : p b := Eq.subst h1 h2 example (α : Type) (a b : α) (p : α → Prop) (h1 : a = b) (h2 : p a) : p b := h1 ▸ h2 11
関数の引数や関数そのものが等しい場合には、次の補助的な定理も使える 定理 置き換える対象 congrArg 関数の引数 congrFun 適用する関数 congr 関数と引数の両方 12
等式を組み合わせる ライブラリの定理を活用する のライブラリには、よく使う等式が定理として用意されている 例えば自然数の加算・乗算には、次のような定理がある Lean variable (a b c : Nat) example : a + 0 = a := Nat.add_zero a example : a + b = b + a := Nat.add_comm a b example : a + b + c = a + (b + c) := Nat.add_assoc a b c example : a * (b + c) = a * b + a * c := Nat.left_distrib a b c 等式の推移律や対称律と、加法・乗法の性質を組み合わせて、複雑な式も証明で きる 13
4.3 Calculational Proofs calc による計算的な証明 計算的な証明(calculational proof) とは、中間結果を順番につないで結論を導く 方法。等式の推移律などを使い、複数の証明を1本の流れとして表現する Leanでは calc キーワードを使う calc expr₀ `op₁` expr₁ := proof₁ _ `op₂` expr₂ := proof₂ _ `op₃` expr₃ := proof₃ 各行の proof は、その行の左辺と右辺が op_n の関係にあることの証明 _ は直前の行の右辺を表す 各行は同じインデントにそろえる 14
中間結果をつないで証明する 例: a = e の証明 variable (a b c d e : Nat) theorem T (h1 : a = b) (h2 : b = c + 1) (h3 : c = d) (h4 : e = 1 + d) : a = e := calc a = b := h1 _ = c + 1 := h2 _ = d + 1 := congrArg Nat.succ h3 _ = 1 + d := Nat.add_comm d 1 _ = e := Eq.symm h4 15
等式以外の関係も扱える 異なる関係を組み合わせる は等式だけでなく、推移律を持つ関係にも使える 途中で異なる関係を組み合わせることもできる calc variable (a b c d : Nat) example (h1 : a = b) (h2 : b ≤ c) (h3 : c + 1 < d) : a < d := calc a = b := h1 _ < b + 1 := Nat.lt_succ_self b _ ≤ c + 1 := Nat.succ_le_succ h2 _ < d := h3 16
rw calc rw と simp で示した等式の証明を rw や simp でも書くことができる。 指定した等式を使って、ゴールを書き換える 複数の等式を順番に適用できる 書き換え後に t = t になれば、反射律で証明される simp 登録された等式などを繰り返し適用して式を簡約する 適用できる場所を探しながら書き換える 可換性なども考慮して、無限に書き換えが続くことを避ける 17
例: theorem T (h1 : a = b) (h2 : b = c + 1) (h3 : c = d) (h4 : e = 1 + d) : a = e := by simp [h1, h2, h3, Nat.add_comm, h4] は証明の道筋を明示したい場合に、 rw や simp は書き換えを簡潔に表現した い場合に役立つ。 calc 18
4.4 The Existential Quantifier 存在量化子 ∃ は「条件 p x を満たす値 x が存在する」という命題 exists x : α, p x と ∃ x : α, p x は同じ意味 Leanでは Exists (fun x : α => p x) の略記として定義されている ∃ x : α, p x 19
存在を証明するには、具体的な値とその証明を示す。 example : ∃ x : Nat, x > 0 := have h : 1 > 0 := Nat.zero_lt_succ 0 Exists.intro 1 h が条件を満たす値(witness:存在を示す具体例) h が 1 > 0 の証明 Exists.intro は値と証明から存在命題を構成する 1 20
存在量化子の導入 ⟨値, 証明⟩ で簡潔に書く Exists.intro t h の代わりに、匿名コンストラクタ記法 ⟨t, h⟩ を使える example : ∃ x : Nat, x > 0 := have h : 1 > 0 := Nat.zero_lt_succ 0 ⟨1, h⟩ example (x : Nat) (h : x > 0) : ∃ y, y < x := ⟨0, h⟩ 21
匿名コンストラクタ記法が入れ子になる場合、 ⟨⟩ を省略できる。 ただし、省略できるのは末尾が ⟨⟩ の場合に限る -- 外側が Exists、内側が And を構成している example (x y z : Nat) (hxy : x < y) (hyz : y < z) : ∃ w, x < w ∧ w < z := ⟨y, ⟨hxy, hyz⟩⟩ -- ⟨⟩ を省略した例 example (x y z : Nat) (hxy : x < y) (hyz : y < z) : ∃ w, x < w ∧ w < z := ⟨y, hxy, hyz⟩ 22
存在量化子の除去 存在する値を取り出して使う ∃ x, p x が分かっているとき、条件を満たす値を一時的に w と名付けて利用で きる ただし、その値が何であるかを決め打ちすることはできない Exists.elim は存在命題から別の命題を証明するための除去規則 23
例: variable (α : Type) (p q : α → Prop) example (h : ∃ x, p x ∧ q x) : ∃ x, q x ∧ p x := Exists.elim h (fun w => fun hw : p w ∧ q w => show ∃ x, q x ∧ p x from ⟨w, hw.right, hw.left⟩) から、条件を満たす値 w と証明 hw を取り出す hw.left が p w 、 hw.right が q w 同じ w を使って、順序を入れ替えた存在命題を構成する h 24
match による取り出し パターンマッチで分解する Exists.elim の代わりに、 match を使って存在命題を分解できる。 example (h : ∃ x, p x ∧ q x) : ∃ x, q x ∧ p x := match h with | ⟨w, hw⟩ => ⟨w, hw.right, hw.left⟩ で、存在する値とその証明を取り出す hw の中の p w と q w も利用できる let や fun の引数でも、同様のパターンマッチを使える ⟨w, hw⟩ 25
直観主義論理と古典論理における存在量化子 直観主義論理の「または」が古典論理の「または」よりも強いのと同様に、直観主義 論理の「存在する」も古典論理の「存在する」より強い。 26
古典論理での存在命題の証明例 open Classical variable (p : α → Prop) example (h : ¬ ∀ x, ¬ p x) : ∃ x, p x := byContradiction (fun h1 : ¬ ∃ x, p x => have h2 : ∀ x, ¬ p x := fun x => fun h3 : p x => have h4 : ∃ x, p x := ⟨x, h3⟩ show False from h1 h4 show False from h h2) 27
4.5 More on the Proof Language 名前のない have と this 通常は have h : P := ... のように名前を付ける 名前を省略した have : P := ... も使える 直前に導入した名前のない事実は this で参照できる variable (f : Nat → Nat) variable (h : ∀ x : Nat, f x ≤ f (x + 1)) example : f 0 ≤ f 3 := have : f 0 ≤ f 1 := h 0 have : f 0 ≤ f 2 := Nat.le_trans this (h 1) show f 0 ≤ f 3 from Nat.le_trans this (h 2) 28
仮定から証明を見つける by assumption ゴールと一致する型の仮定がコンテキストにあれば、 by assumption で証明でき る Leanがコンテキストから適切な仮定を探す この処理を行う assumption タクティクは、次章で詳しく扱う example : f 0 ≤ f 3 := have : f 0 ≤ f 1 := h 0 have : f 0 ≤ f 2 := Nat.le_trans (by assumption) (h 1) show f 0 ≤ f 3 from Nat.le_trans (by assumption) (h 2) 29
‹p› による証明の参照 と書くと、コンテキストから命題 p の証明を探してくれる by assumption と異なり、探してほしい命題を明示できる \f< と \f> で、それぞれ ‹ と › を入力できる ‹p› notation "‹" p "›" => show p by assumption 30
‹p› の例 variable (f : Nat → Nat) variable (h : ∀ x : Nat, f x ≤ f (x + 1)) example : f 0 ≥ f 1 → f 1 ≥ f 2 → f 0 = f 2 := fun _ : f 0 ≥ f 1 => fun _ : f 1 ≥ f 2 => have : f 0 ≥ f 2 := Nat.le_trans ‹f 1 ≥ f 2› ‹f 0 ≥ f 1› have : f 0 ≤ f 2 := Nat.le_trans (h 0) (h 1) show f 0 = f 2 from Nat.le_antisymm this ‹f 0 ≥ f 2› のように、必要な命題を指定して証明を取り出す ‹p› は名前のない have で導入した事実に限らず、コンテキスト中の任意の仮定 を参照できる ‹f 1 ≥ f 2› 31
命題だけでなく、データの型を指定して値を取り出すこともできる example (n : Nat) : Nat := ‹Nat› はコンテキスト中から Nat 型の項を探す このように、 ‹p› を使うと、仮定に名前を付けずに必要な証明や値を参照できる。 ‹Nat› 32
4.6. Exercises 勉強会では以下の2問を解きました。 variable (α : Type) (p q : α → Prop) example : (∀ x, p x ∧ q x) ↔ (∀ x, p x) ∧ (∀ x, q x) := sorry example : (∀ x, p x → q x) → (∀ x, p x) → (∀ x, q x) := sorry 33
次回 金 11/20( ) 21:30-22:30 第5章から 34