---
title: Theorem Proving in Lean4 を読む会#5 ― 第4章
tags: 
author: [Yuki Imamura](https://image.docswell.com/user/imamuray)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/2EV4L29MJQ.jpg?width=480
description: 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以降
published: November 14, 26
canonical: https://image.docswell.com/s/imamuray/5VJWJV-2026-11-14-182835
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/2EV4L29MJQ.jpg)

Theorem Proving in Lean 4
を読む会#5
4. Quantifiers and Equality
2026/11/13 21:30~
1


# Page. 2

![Page Image](https://bcdn.docswell.com/page/57G1XRZXEL.jpg)

4. Quantifiers and Equality
2


# Page. 3

![Page Image](https://bcdn.docswell.com/page/4EQD8VL5JP.jpg)

4.1
全称量化子（Universal Quantifier）
「すべての〜について」を表す
は「すべての x : α について p x が成立する」という命題
p : α → Prop は、型 α の値を受け取って命題を返す関数（述語）
r : α → α → Prop は、2つの値の関係を表す関数
例えば、 r x y は「 x と y の間に関係 r が成立する」という意味。
∀ x : α, p x
3


# Page. 4

![Page Image](https://bcdn.docswell.com/page/KJ4Z2MDV71.jpg)

全称量化子には2つの規則がある
規則
内容
導入 任意の x について p x を証明すれば、 ∀ x, p x を証明できる
除去 ∀ x, p x があれば、任意の値 t について p t を得られる
4


# Page. 5

![Page Image](https://bcdn.docswell.com/page/LE1RM8Z4EG.jpg)

全称量化子の導入と除去
例：
example (α : Type) (p q : α → Prop) :
(∀ x : α, p x ∧ q x) → ∀ y : α, p y :=
fun h : ∀ x : α, p x ∧ q x =&gt;
fun y : α =&gt;
show p y from (h y).left
証明の流れ
1. h は、任意の x について p x ∧ q x が成立するという証明。
2. fun y =&gt; で任意の y を受け取る （全称量化子の導入）
。
3. h y によって p y ∧ q y の証明を得る （全称量化子の除去）
。
4. .left で左側の p y を取り出す。
5


# Page. 6

![Page Image](https://bcdn.docswell.com/page/GEW13Z9Z72.jpg)

全称量化子と関数
全称量化子は依存関数型の別表記
次の2つはLeanでは同じ意味を持つ。
variable (α : Type) (p : α → Prop)
-#check ∀ x : α, p x
#check (x : α) → p x
全称命題の証明は、任意の値を受け取って、その値についての証明を返す関数として
表現できる。
6


# Page. 7

![Page Image](https://bcdn.docswell.com/page/47ZPV19LE3.jpg)

含意 → との関係
は、入力に関係なく戻り値の型が β である関数型。
(x : α) → p x は、戻り値の型が入力 x に依存する関数型。
p → q も、 ∀ x : p, q の特殊な場合と考えられる。
α → β
7


# Page. 8

![Page Image](https://bcdn.docswell.com/page/YJ6M5LKM7V.jpg)

暗黙の引数
推移律の例：
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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/GJ5ZY1PQE4.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/LE39513ZE5.jpg)

等式の証明と計算
rfl
は計算で等しい式も証明できる
は、同じ項どうしの等しさを証明する
Leanでは、計算によって同じ形になる式も等しいと判断される
rfl は Eq.refl _ の記法
Eq.refl
variable (α β : Type)
example (f : α → β) (a : α) : (fun x =&gt; f x) a = f a := rfl
example (a : α) (b : β) : (a, b).1 = a := rfl
example : 2 + 3 = 5 := rfl
関数適用や直積の射影、数値計算なども、簡約によって等しいと確認できる
10


# Page. 11

![Page Image](https://bcdn.docswell.com/page/8EDGDX44EG.jpg)

等式を使った置換
等しいものは置き換えられる
があり、 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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/V7P3XPMVJ8.jpg)

関数の引数や関数そのものが等しい場合には、次の補助的な定理も使える
定理 置き換える対象
congrArg 関数の引数
congrFun 適用する関数
congr
関数と引数の両方
12


# Page. 13

![Page Image](https://bcdn.docswell.com/page/2JV4L29R7Q.jpg)

等式を組み合わせる
ライブラリの定理を活用する
のライブラリには、よく使う等式が定理として用意されている
例えば自然数の加算・乗算には、次のような定理がある
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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/5EG1XRZ6JL.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/4JQD8VL27P.jpg)

中間結果をつないで証明する
例： 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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/K74Z2MDPE1.jpg)

等式以外の関係も扱える
異なる関係を組み合わせる
は等式だけでなく、推移律を持つ関係にも使える
途中で異なる関係を組み合わせることもできる
calc
variable (a b c d : Nat)
example (h1 : a = b) (h2 : b ≤ c)
(h3 : c + 1 &lt; d) : a &lt; d :=
calc
a = b := h1
_ &lt; b + 1 := Nat.lt_succ_self b
_ ≤ c + 1 := Nat.succ_le_succ h2
_ &lt; d := h3
16


# Page. 17

![Page Image](https://bcdn.docswell.com/page/LJ1RM8ZXJG.jpg)

rw
calc
rw
と simp
で示した等式の証明を rw や simp でも書くことができる。
指定した等式を使って、ゴールを書き換える
複数の等式を順番に適用できる
書き換え後に t = t になれば、反射律で証明される
simp
登録された等式などを繰り返し適用して式を簡約する
適用できる場所を探しながら書き換える
可換性なども考慮して、無限に書き換えが続くことを避ける
17


# Page. 18

![Page Image](https://bcdn.docswell.com/page/GJW13Z9KE2.jpg)

例：
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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/4EZPV19NJ3.jpg)

4.4 The Existential Quantifier
存在量化子 ∃
は「条件 p x を満たす値 x が存在する」という命題
exists x : α, p x と ∃ x : α, p x は同じ意味
Leanでは Exists (fun x : α =&gt; p x) の略記として定義されている
∃ x : α, p x
19


# Page. 20

![Page Image](https://bcdn.docswell.com/page/Y76M5LK9EV.jpg)

存在を証明するには、具体的な値とその証明を示す。
example : ∃ x : Nat, x &gt; 0 :=
have h : 1 &gt; 0 := Nat.zero_lt_succ 0
Exists.intro 1 h
が条件を満たす値（witness：存在を示す具体例）
h が 1 &gt; 0 の証明
Exists.intro は値と証明から存在命題を構成する
1
20


# Page. 21

![Page Image](https://bcdn.docswell.com/page/G75ZY1PDJ4.jpg)

存在量化子の導入
⟨値, 証明⟩
で簡潔に書く
Exists.intro t h
の代わりに、匿名コンストラクタ記法 ⟨t, h⟩ を使える
example : ∃ x : Nat, x &gt; 0 :=
have h : 1 &gt; 0 := Nat.zero_lt_succ 0
⟨1, h⟩
example (x : Nat) (h : x &gt; 0) : ∃ y, y &lt; x :=
⟨0, h⟩
21


# Page. 22

![Page Image](https://bcdn.docswell.com/page/9J2RG1ZM7R.jpg)

匿名コンストラクタ記法が入れ子になる場合、 ⟨⟩ を省略できる。
ただし、省略できるのは末尾が ⟨⟩ の場合に限る
-- 外側が Exists、内側が And を構成している
example (x y z : Nat) (hxy : x &lt; y) (hyz : y &lt; z) :
∃ w, x &lt; w ∧ w &lt; z :=
⟨y, ⟨hxy, hyz⟩⟩
-- ⟨⟩ を省略した例
example (x y z : Nat) (hxy : x &lt; y) (hyz : y &lt; z) :
∃ w, x &lt; w ∧ w &lt; z :=
⟨y, hxy, hyz⟩
22


# Page. 23

![Page Image](https://bcdn.docswell.com/page/DEYDVZRPEM.jpg)

存在量化子の除去
存在する値を取り出して使う
∃ x, p x
が分かっているとき、条件を満たす値を一時的に w と名付けて利用で
きる
ただし、その値が何であるかを決め打ちすることはできない
Exists.elim は存在命題から別の命題を証明するための除去規則
23


# Page. 24

![Page Image](https://bcdn.docswell.com/page/VJN6M3DMJ8.jpg)

例：
variable (α : Type) (p q : α → Prop)
example (h : ∃ x, p x ∧ q x) : ∃ x, q x ∧ p x :=
Exists.elim h
(fun w =&gt;
fun hw : p w ∧ q w =&gt;
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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/YE9LN9GW73.jpg)

match
による取り出し
パターンマッチで分解する
Exists.elim
の代わりに、 match を使って存在命題を分解できる。
example (h : ∃ x, p x ∧ q x) : ∃ x, q x ∧ p x :=
match h with
| ⟨w, hw⟩ =&gt; ⟨w, hw.right, hw.left⟩
で、存在する値とその証明を取り出す
hw の中の p w と q w も利用できる
let や fun の引数でも、同様のパターンマッチを使える
⟨w, hw⟩
25


# Page. 26

![Page Image](https://bcdn.docswell.com/page/GE8XK9VRJD.jpg)

直観主義論理と古典論理における存在量化子
直観主義論理の「または」が古典論理の「または」よりも強いのと同様に、直観主義
論理の「存在する」も古典論理の「存在する」より強い。
26


# Page. 27

![Page Image](https://bcdn.docswell.com/page/LEL8ZW527R.jpg)

古典論理での存在命題の証明例
open Classical
variable (p : α → Prop)
example (h : ¬ ∀ x, ¬ p x) : ∃ x, p x :=
byContradiction
(fun h1 : ¬ ∃ x, p x =&gt;
have h2 : ∀ x, ¬ p x :=
fun x =&gt;
fun h3 : p x =&gt;
have h4 : ∃ x, p x := ⟨x, h3⟩
show False from h1 h4
show False from h h2)
27


# Page. 28

![Page Image](https://bcdn.docswell.com/page/4JM6V939EW.jpg)

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


# Page. 29

![Page Image](https://bcdn.docswell.com/page/PJRP2GQ9E9.jpg)

仮定から証明を見つける
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


# Page. 30

![Page Image](https://bcdn.docswell.com/page/PEX3DX53JX.jpg)

‹p›
による証明の参照
と書くと、コンテキストから命題 p の証明を探してくれる
by assumption と異なり、探してほしい命題を明示できる
\f&lt; と \f&gt; で、それぞれ ‹ と › を入力できる
‹p›
notation &quot;‹&quot; p &quot;›&quot; =&gt; show p by assumption
30


# Page. 31

![Page Image](https://bcdn.docswell.com/page/3EKYXW6NJD.jpg)

‹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 =&gt;
fun _ : f 1 ≥ f 2 =&gt;
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


# Page. 32

![Page Image](https://bcdn.docswell.com/page/L739516Z75.jpg)

命題だけでなく、データの型を指定して値を取り出すこともできる
example (n : Nat) : Nat := ‹Nat›
はコンテキスト中から Nat 型の項を探す
このように、 ‹p› を使うと、仮定に名前を付けずに必要な証明や値を参照できる。
‹Nat›
32


# Page. 33

![Page Image](https://bcdn.docswell.com/page/87DGDXV47G.jpg)

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


# Page. 34

![Page Image](https://bcdn.docswell.com/page/VJP3XPVVE8.jpg)

次回
金
11/20( ) 21:30-22:30
第5章から
34


