Constraint satisfaction problems, compactness and non-measurable sets

この論文は、有限関係構造のコンパクト性が幅 1 の場合に ZF 公理系で証明可能である一方、それ以外の場合は 3 次元空間における非可測集合の存在を意味することを示しています。

要約

この論文は、一見すると全く関係なさそうな**「パズル（制約充足問題）」と「数学の基礎（集合論や測度）」**が、実は深く結びついていることを発見した驚くべき研究です。

著者のクロード・タルディフさんは、以下のような面白い問いに答えました。

「あるパズルを、無限に大きな世界で解けるかどうかは、そのパズルの『難易度』と、私たちが使う『数学のルール（公理）』によって決まるのか？」

これを、日常の言葉と面白い比喩を使って解説しましょう。

---

1. 物語の舞台：「パズル」と「無限の城」

まず、**「制約充足問題（CSP）」**というものを想像してください。
これは、 Sudoku（数独）や、ある条件を満たすように色を塗るパズルのようなものです。

• ルール： 「隣り合うマスは同じ色にできない」「特定の数字はここにしか入らない」など。
• 目標： 与えられたルールに従って、全体を正しく埋め尽くすこと。

ここで問題になるのは、そのパズルが**「無限に大きな城」**（無限のグラフや構造）の場合です。

• 「城の小さな部屋（有限の部分）だけを見れば、ルール通りに色を塗れることが分かっている」
• 「でも、城全体（無限）を一度に塗れるだろうか？」

この「小さな部屋で可能なら、全体でも可能か？」という性質を、数学では**「コンパクト性（Compactness）」**と呼びます。

2. 2 つのタイプの「パズル」

この論文は、パズルを大きく 2 つのタイプに分けました。

タイプ A：「簡単すぎるパズル（幅 1 の構造）」

• 特徴： 非常に単純なルール。例えば「2 色で塗れるか？」（二部グラフ）のようなもの。
• 解決方法： 「 consistency check（整合性チェック）」という、小学生でも思いつきそうな単純なアルゴリズムで解けます。
  • 比喩： 「隣の色を見て、自分の色を決める」だけ。
• 数学的な性質： このタイプのパズルは、「普通の数学のルール（ZF 公理系）」だけで、「無限の城でも解ける」ことが証明できます。特別な魔法（選択公理など）は不要です。

タイプ B：「難しいパズル（幅 1 ではない構造）」

• 特徴： 複雑なルール。例えば「3 色以上で塗る必要がある」ようなもの。
• 解決方法： 単純なチェックでは解けません。
• 数学的な性質： これが面白いポイントです。
  • もし「この難しいパズルも、無限の城で解ける（コンパクト性を持つ）」と主張するなら、**「普通の数学のルールだけでは不十分」**です。
  • さらに、その主張が真であるためには、**「3 次元空間に『測れない（計量できない）』物体が存在する」**ことを認めなければなりません。

3. 核心：「測れない物体」と「バナッハ・タルスキーのパラドックス」

ここで、**「測れない物体（非可測集合）」とは何でしょうか？
それは、「体積（大きさ）を定義できない不思議な物体」**です。

• バナッハ・タルスキーのパラドックス：
  選択公理（数学の強力な魔法）を使えば、1 つの球をバラバラにして、同じ大きさの球を2 つ作れてしまう（体積が保存されない）という、物理的にはあり得ないことが数学的に証明されます。これには「測れない物体」の存在が不可欠です。

論文の結論（定理 1.2）を一言で言うと：

「もし、あなたが『複雑なパズルも無限に解ける』と言いたいなら、あなたは『バナッハ・タルスキーのパラドックス』のような、体積の定義できない不思議な物体が 3 次元空間に存在することを認める必要がある」

つまり、**「パズルの難しさ」と「数学の奥深さ（非可測集合の存在）」**は、表裏一体なのです。

4. 著者が使った「魔法の道具」：バナッハ・タルスキー・グラフ

著者は、この関係を証明するために、**「バナッハ・タルスキー・グラフ」**という架空の巨大なネットワークを作りました。

• 仕組み：
  このグラフは、球面上の点を結んだものです。その結び方は、回転の魔法（自由群）を使って作られています。
• 不思議な性質：
  • このグラフの**「小さな部分」**だけを見れば、2 色で塗れる（二部グラフ）ことが分かります。
  • しかし、**「全体」を 2 色で塗ろうとすると、「測れない物体」**を使わないと不可能になります。
  • もし「測れない物体」が存在しない（すべての物体は測れる）という世界（ソロベイモデル）だと、このグラフは 2 色で塗ることができなくなります。

5. 全体のメッセージ：なぜこれが重要なのか？

この研究は、**「計算複雑性理論（アルゴリズムの難しさ）」と「集合論（数学の基礎）」**という、一見無関係な 2 つの分野を橋渡ししました。

• 簡単なパズル（幅 1）： 普通の数学（ZF）で扱える。
• 難しいパズル（幅 1 以外）： 「非可測集合」という、数学の最も奥深い・不思議な領域を越えないと扱えない。

比喩でまとめると：

「簡単なパズルは、普通の道具箱（ZF 公理）で解ける。
でも、超難問のパズルを解こうとすると、その道具箱には入っていない『魔法の杖（非可測集合の存在）』が必要になる。
もし魔法の杖を使いたくないなら、その超難問は『解けない（あるいは解ける保証がない）』ということになる。」

結論

この論文は、「アルゴリズムの難しさ」と「数学の真理」は、実は同じコインの裏表であることを示唆しています。

私たちが「NP ≠ P（P 以上の問題は難しい）」と信じているのは、単に計算機の性能の問題ではなく、**「数学の世界には、測れないほど複雑な構造が潜んでいるから」**なのかもしれません。

もし「測れない物体」が存在しない世界に住んでいるなら、私たちが考える「最も難しいパズル」の多くは、実は「解けない」か、「解けるはずがない」ものになってしまうのです。

技術概要

Claude Tardif による論文「制約充足問題、コンパクト性、および非可測集合」の技術的な詳細な要約を以下に提示します。

1. 研究の背景と問題設定

この論文は、制約充足問題（CSP: Constraint Satisfaction Problems）の計算複雑性と**集合論の公理系（特に選択公理や超フィルター公理）**の間の深い関連性を明らかにすることを目的としています。

• コンパクト性の定義: 有限関係構造 $A$ が「コンパクト」であるとは、任意の無限関係構造 $B$ に対して、「$B$ から $A$ への準同型写像が存在する」ことと、「$B$ のすべての有限部分構造から $A$ への準同型写像が存在する」ことが同値であることを指します。
• 既知の事実: 選択公理（AC）は、すべての有限関係構造がコンパクトであることを示唆します（超フィルター公理と同値）。しかし、AC を使わずに（ZF 系だけで）証明できるコンパクト性と、AC やそれ以上の公理を必要とするコンパクト性の境界は不明瞭でした。
• CSP との関連: CSP($A$) は、入力構造 $B$ が $A$ へ準同型写像を持つかを判定する問題です。Bulatov と Zhuk によって証明された「CSP の二分法」によると、$A$ が「巡回多項写像（cyclic polymorphism）」を持つ場合、CSP($A$) は多項式時間で解けます（ tractable）。そうでない場合は NP 完全です。
• 核心となる問い: 構造 $A$ の「コンパクト性」が ZF 系だけで証明可能なのか、それとも非可測集合の存在（選択公理の強い形式）を必要とするのか、その境界は CSP の計算複雑性（特に「幅 1」の性質）と対応しているのか？

2. 手法と主要な概念

著者は、集合論的モデル（特に非可測集合の存在）と、Banach-Tarski のパラドックスの構成を応用したグラフ理論を組み合わせて証明を行います。

• 幅 1（Width 1）と木双対性:

  • CSP($A$) が「一貫性チェック（consistency check）」アルゴリズムで解ける場合、$A$ は「幅 1」を持つと定義されます。
  • これは、構造 $U(A)$（$A$ の空でない部分集合の集合を宇宙とする構造）から $A$ への準同型写像 $\omega: U(A) \to A$ の存在と同値です。
  • 既知の結果（RTW17）により、幅 1 の構造 $A$ については、そのコンパクト性は ZF 系だけで証明可能です。

• Banach-Tarski グラフの構成:

  • 証明の核心は、$A$ が幅 1 を持たない場合に、Banach-Tarski のパラドックスの幾何学的構造を用いた無限グラフ $T$（Banach-Tarski グラフ）を構成することです。
  • 3 次元回転群の自由部分群（2 個の生成元を持つ自由群を含む）を用いて、球面 $S^2$ 上の点の軌道からなるグラフを定義します。
  • このグラフ $T$ は、局所的には木（tree）構造を持ち、すべての有限部分構造は $A$ へ準同型写像を持つことが示されます（幅 1 の構造 $U(A)$ の性質を利用）。

• Steinhaus 定理の適応と測度論的議論:

  • もし $A$ がコンパクトであり、かつ $\mathbb{R}^3$ のすべての集合がルベーグ可測であると仮定すると、Banach-Tarski グラフ $T$ から $A$ への準同型写像 $\phi$ が存在します（補題 4.2）。
  • この写像 $\phi$ を用いて、特定の集合 $Fish_{f,D}$（$\mathbb{R}^3$ の部分集合）を定義します。
  • 補題 4.3: もし $Fish_{f,D}$ が可測であれば、その測度は 0 であることが示されます（Steinhaus 定理の適応版）。これは、回転による不変性と測度の加法性を用いた矛盾論法によるものです。

3. 主要な結果と定理

論文の中心的な成果は以下の定理です。

定理 1.2:
$A$ を関係構造とする。もし $A$ が「幅 1」を持たない場合、$A$ がコンパクトであるという公理は、$\mathbb{R}^3$ における非可測集合の存在を意味する。

• 帰結:
  • 幅 1 の構造 $\iff$ ZF 系で証明可能なコンパクト性。
  • 幅 1 ではない構造 $\iff$ コンパクト性が非可測集合の存在（選択公理の強い形式）を必要とする。
  • これは、CSP の計算複雑性（多項式時間解けるか否か）と、集合論的公理の強さの間に完全な対応（二分法）が存在することを示しています。

定理 1.1（K´atay, T´oth, Vidny´anszky の結果の引用）:
有限関係構造 $A$ について、$A$ のコンパクト性が超フィルター公理を意味するのは、$A$ が巡回多項写像を持たない場合に限られる。

4. 結論と意義

• 計算複雑性と集合論の統合:
  この研究は、アルゴリズムの「難しさ（NP 完全性）」と、数学的基礎論における「公理の強さ（非可測集合の存在）」が密接に結びついていることを示しました。具体的には、最も一般的なコンパクト性公理（超フィルター公理や非可測集合の存在）が、最も計算的に困難な CSP（幅 1 を持たないもの）に対応しています。

• Borel 構造との関係:
  結論部分では、Borel 関係構造と Borel 準同型写像の文脈にも言及しています。Banach-Tarski グラフ $T$ は Borel 構造ですが、有限色数での適切な彩色（Borel 彩色）は存在しません。これは、幅 1 の構造のみが、Borel 構造からの任意の準同型写像の存在と、Borel 準同型写像の存在を一致させることを示唆しています（Thornton の結果）。

• 未解決問題:
  著者は、グラフの彩色問題に関する一般化（$S(n)$: 有限部分グラフが 3 彩色可能なら $n$ 彩色可能か）が超フィルター公理を意味するかどうかという未解決問題を提起しています。これは、CSP の複雑性予想（$P \neq NP$）が、集合論的公理の階層を予測している可能性を示唆しています。

総括:
Claude Tardif は、Banach-Tarski パラドックスの幾何学的構成と測度論的矛盾を用いることで、CSP の「幅 1」の性質が、ZF 系内でコンパクト性を証明できるかどうかの厳密な境界線であることを証明しました。これは、計算理論と集合論の交差点における画期的な結果であり、数学的基礎の構造に対する新たな洞察を提供しています。