2026/09/05 5:20
Dummit and Foote の『抽象代数学』に存在するバグを発見する
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
以下に示す改良版は、主たるメッセージを維持しつつ、キーポイントリストに含まれていた欠落している具体的な事項を取り入れ、必要な場合定義の明確化も行ったものとなる：
Recurse Center の第 2 週目において、著者は Dummit and Foote の Abstract Algebra テキストブックを Rocq で形式化する作業を開始した。標準的な命題として、「関数 $f: A \to B$ が全単射であることと、すべての $a \in A$ について $g(f(a)) = a$ を満たす左逆関数 $g: B \to A$ が存在することとの同値性」が主張されている。この命題を形式化するには、以下の点を注意する必要がある：
- 関数は、$A$ の異なる 2 つの要素が $B$ の同一の要素へ写像しないときに全単射である（例：整数上の $f(x)=x^2$ は全単射ではない）。
- 左逆関数が存在するのは、ちょうど $B$ から $A$ への写像が存在し、それが $f$ を打ち消す場合のみである。
この命題は、$A = {}$ および $B = {1}$ の場合に成り立たない。ここで、唯一つの関数 $f: \emptyset \to {1}$（ペアの集合が空となる）は自明的に全単射であるが、関数 $g: {1} \to \emptyset$ は存在しないため、左逆関数は存在しない。著者はこの同値性を証明するために、追加の仮定が必要であることを示すしかなかった（例えば、$A$ が inhabited であるか、あるいは $B$ が空集合である場合など）。Rocq でこれを証明する試みが続いた後、著者はテキストブックの記述が誤っていることに気づき、書籍の Errata を確認して既にその誤りが記録されていることを確認した。このエピソードは、形式検証が広く使用されているテキストにおいても微妙な過ちを捉えるための価値を示すと同時に、標準的な演習に頼る際には Errata の確認が必要であるという点も強調する。
本文
デミット・アンド・フォートの『抽象代数』におけるバグ発見：rocQ を使った検証
リカースセンターの 2 ヶ月目以降、デミットとフォートの教科書**『抽象代数』を rocQ で形式化する作業に取り組んでいました。 最初の証明演習では特に苦労しましたが、それは記された証明の目標自体が成立しないこと**に気づいたためです。この発見は、挫折感と同時に興奮を呼び起こしました。
関数と単射の定義
rocQ の文脈における基本概念を確認します。
関数の定義
集合 $A$ から集合 $B$ への関数 $f$（表記：
f: A -> B- 各対の第 1 要素は必ず A に属する。
- 各対の第 2 要素は必ず B に属する。
- A の任意の要素は、かつちょうど 1 つの対において第 1 要素となる。
注釈: プログラミングの視点では、関数は入力と出力からなる対全体で定義され、決定論的である必要があります。
単射（Injective）
ある関数 $f$ が単射とは、異なる 2 つの入力が同じ出力へ写像しないことを意味します。
- 例: $f: \text{整数} \to \text{整数}$ で $f(x) = x^2$ とする。
- $f(1) = f(-1)$ となるため、これは単射ではない。
左逆元（Left Inverse）
関数 $f: A \to B$ が左逆元を持つとは、以下の条件を満たす関数 $g: B \to A$ が存在することです。
$$ \forall a \in A, \quad g(f(a)) = a $$
つまり、$f$ の左逆元 $g$ は $f$ を「取り消す」役割を果たします。
命題の誤り：空集合による角ケース（Corner Case）
本書の最初の演習では、「ある関数が単射であること」と「その関数が左逆元を持つこと」は同値であると示せとされていました。しかし、この命題は誤りです。
カウンターエクスンプルの構成
以下の設定を考えます：
- $A = \emptyset$（空集合）
- $B = {1}$
検証プロセス
-
関数としての成り立ち:
- このとき、$f: A \to B$ は $f = \emptyset$（空関数）となります。
- 関数の定義上の 3 つの条件はすべて満たすため、$f$ は正しい関数です。
-
単射としての成り立ち:
- 「異なる 2 つの入力が同じ出力へ写像しない」という性質は、A が要素を持たないため（自明に）成り立ちます。
- よって、$f$ は単射であると言えます。
-
左逆元の有無:
- $B \to A$ の関数 $g$ を考える必要がありますが、$A$ が空集合のため、条件を満たす $g$ は存在しません（実際には定義可能ですが、左逆元の等式 $g(f(a))=a$ を満たすような $f$ への対応は意味をなしません。より直接的には、空集合から非空集合への写像の逆関数が存在しないため）。
- 結果として、$f$ は左逆元を持ちません。
結論
- 単射である $\iff$ 左逆元を持つという命題は、$A=\emptyset, B \neq \emptyset$ の場合に反例になります。
rocQ による発見プロセス
もしこの演習を紙の上で行っていた場合、おそらくこのような角ケースには気づかなかっただろうと考えられます。
- rocQ を使用したからこそ、命題の記された形で証明しようとするとつまずかずに済みました。
- 私が見つけたあらゆる証明アプローチは、以下のいずれかの制約を必要としました：
- $A$ が空でない場合
- $B$ が空である場合
- 長い時間を費やして「そもそもこの命題自体が成立していないのではないか？」と疑い始めました。
記事執筆中に確認したところ、本書の**誤謬表（Errata）**には既にこのミスは記載されていました。