通常は無視される奇妙な無限集合を研究する記述集合論が、アントン・バーンシュタイン氏の発見によりコンピューター科学と深いつながりを持つことが判明した。この発見は、無限を扱う数学と有限を扱うコンピューター科学の間の予想外の架け橋となり、両分野に新たな研究の地平を開いている。
現代数学はすべて、抽象的な集まりをどのように整理するかを研究する「集合論」の上に成り立っている。だが一般的に、数学者は何らかの問題を解く際に集合論を意識する必要はない。集合が期待どおりに振る舞うという前提のもとで、自分の研究に取り組めばよい。
だが、記述集合論を研究する場合は例外だ。記述集合論研究者は数こそ少ないが、集合の根本的な性質の探究をやめず、主にほかの数学者が無視してきた奇妙な無限集合を中心に研究を続けてきた。
ところが最近になって、突然仲間が増えた。2023年、アントン・バーンシュタインという数学者が、記述集合論という辺境の数学と現代コンピューター科学とのあいだに驚くべき深いつながりを発見し、論文を発表したことがきっかけだった。
バーンシュタインは、特定の無限集合に関係するすべての問題がコンピューターネットワークの通信問題として書き換えられることを証明した。ふたつの分野のあいだにそのような橋が架かっている事実は、双方の研究者にとって意外だった。集合論の研究者は論理学の言語を使い、コンピューター科学の研究者はアルゴリズムの言語を用いる。集合論は無限を扱うが、コンピューター科学が扱うのは有限だ。双方の問題が関連している理由はなく、ましてや等価であるとは到底思えなかった。
「本当に奇妙なことです」と、プラハにあるカレル大学のコンピューター科学者であるヴァーツラフ・ロズホニは言う。「あるはずがない、といった感じです」
バーンシュタインの研究結果が発表されて以来、同僚たちはこの橋を行き来しながら、両側で新しい定理を証明する方法や、その橋を新たな問題の分野へと拡張する方法を模索してきた。一部の記述集合論の研究者は、コンピューター科学側からの知見を応用して、自分たちの分野全体の地図を塗り替え、無限をどのように理解するかという考え方さえ見直し始めている。
「これまで両分野の学者は、互いに情報交換することもなく、非常によく似た問題に取り組んでいたことになる」と、カーネギーメロン大学の記述集合論の研究者クリントン・コンリーは説明する。「これによって、新しいコラボレーションへの扉が開かれた」
バーンシュタインが大学生だったころ、記述集合論は、かつては重要だったがいまでは忘れ去られた分野の代表例として紹介された。それから1年以上が経って、その教授が間違っていたことが明らかになった。
14年、イリノイ大学大学院の1年生だったバーンシュタインは、アヌーシュ・ツェルニャンの論理学の授業を受けた。のちに彼の指導教官となる彼女がその誤解を正した。「わたしがこの分野で活躍できているのは彼女のおかげです」とバーンシュタインは語る。「彼女がいたからこそ、論理学と集合論は数学のさまざまな部分をつなぐ接着剤のような存在だと考えるようになりました」
1874年、数学者のゲオルク・カントールが無限にはさまざまな大きさがあることを証明し、これをきっかけに記述集合論という分野が始まった。例えば、整数の集合（0、1、2、3、……）は、すべての分数の集合と同じ大きさだが、すべての実数の集合よりは小さい。
当時の数学者たちは、無限にもさまざまな種類があるという考え方そのものに不快感を覚えていた。「これを頭で理解するのは難しい」と、現在カリフォルニア大学ロサンゼルス校に所属するバーンシュタインは言う。
部分的にはこの不快感に対する反発からだろう、数学者は新たな「大きさ」の概念を考案した。集合に含まれる要素の数を記述するのではなく、その集合がどれだけの長さや面積、体積を占めるかを表すのだ。
この大きさの概念は集合の「測度」と呼ばれている（それに対して、カントールの大きさの概念は「濃度」と呼ばれる）。最も単純な測度のひとつである「ルベーグ測度」は、集合の長さを定量化する。0から1までの実数の集合と、0から10までの実数の集合は、どちらも無限で同じ濃度をもつが、前者のルベーグ測度は1で、後者のルベーグ測度は10だ。
より複雑な集合を研究する際には、数学者は別の種類の測度を用いる。集合が醜ければ醜いほど、それを測定する方法は少なくなる。記述集合論の研究者は、どの集合がさまざまな「測度」のどれによって測定できるかを問い、その答えに基づいて集合を階層的に配置する。
最上層には、容易に構成でき、どのタイプの測度を使っても研究できる集合が位置する。最下層には、あまりに複雑でまったく測定できないため「非可測」と呼ばれる集合が位置する。「学者はよく『病的（pathological）』という言葉を使います」とバーンシュタインは言う。「非可測集合は本当に厄介で、直感に反し、行儀が悪いのです」
この階層構造は、集合論の研究者が自分たちの分野の地図を描くのに役立つだけでなく、数学のほかの分野でより典型的な問題に取り組む際に、どのツールが使えるかを見極める基準にもなる。力学系、群論、確率論といった分野に携わる数学者は、自分が扱っている集合の大きさに関する情報を必要とする。特定の集合が階層構造のどこに位置するかによって、問題を解くために使えるツールが決まるのだ。
この意味で、記述集合論の研究者はさまざまな種類の無限集合（およびそれらを測定するさまざまな方法）が並ぶ巨大な本棚を管理する図書館司書のような存在だ。もち込まれた問題について、それを解くのにどれほど複雑な集合が必要かを判断し、適切な棚に配置するのが図書館司書の仕事だ。その仕事があるからこそ、ほかの数学者は自分に必要なものを参照できる。
バーンシュタインは、「辺（エッジ）」で結ばれた無数の「頂点（ノード）」の集合に関する問題を分類する司書のひとりだ。この種の集合は「グラフ」と呼ばれる。彼が主に研究しているのは、無限個の独立した部分から成り、それぞれに無限個のノードを含むグラフだ。
ほとんどのグラフ理論研究者はこの種のグラフを扱おうとせず、有限のグラフに焦点を当てる。だがバーンシュタインが研究する無限グラフは、力学系やほかの重要な種類の集合を表現し、それらについての情報を与えることができるため、記述集合論の研究者にとって強い関心の対象となっている。
バーンシュタインや同僚たちが研究対象としている無限グラフの一例を紹介しよう。まず円がある。円周には無限の点が含まれている。そのうちの任意の点を選ぶ。それが最初のノードとなる。次に、円周に沿って一定の距離だけ移動する。そこが第2のノードとなる。 例えば、円周の5分の1だけ進んだとしよう。ふたつのノードを結ぶとエッジができる。同じ距離だけ進み、第3のノードを前のノードと結ぶ。これを繰り返す。 毎回5分の1ずつ進めば、5ステップで元の位置に戻る。基本的に、分数で表せる距離だけ進むと、ノードは閉じたループを形成する。だが、分数で表せない距離を進んだ場合、このプロセスは永遠に続く。無限個の連結したノードが得られる。
それでも、この無限に続くシーケンスが形成するのは、グラフの最初の部分にすぎない。無限個のノードを含んでいても、円周上のすべての点を含んでいるわけではない。グラフのほかの部分を生成するには、別の点から始める。そして最初と同じ距離を各ステップで進む。最初のシーケンスとはつながっていない、第二の無限に続くノードのシーケンスができあがる。 円周上のすべての新しい出発点について同じ操作を行なうと、無限個の独立した部分から成るグラフが得られ、その各部分もまた無限個のノードから成っている。
ここで数学者は、このグラフのノードを特定のルールに従って彩色できるかどうかを問う。例えば、2色だけを使う場合、隣接するふたつのノードが同じ色にならないように、グラフのすべてのノードを色分けできるだろうか？ 答えは簡単に思えるかもしれない。まず、グラフの最初の部分でノードのひとつのノードを青に塗る。残りのノードに黄、青、黄、青と交互に塗っていく。同じことをグラフに含まれるすべての部分についても行なう。ひとつのノードを選び、そこから青、次に別の色というように交互に色を付ける。最後には、2色だけでこの作業を完了できるはずだ。
だが、この色分けを実行するには、集合論の研究者が「選択公理」と呼ぶ仮定を暗黙のうちに用いる必要がある。「たくさんの集合がある場合、さらには無限個の集合がある場合でも、それぞれの集合からひとつの要素を選んで新たな集合をつくることができる」とする公理で、数学の基礎をなす9つの構成要素のひとつに数えられている。 これを用いることでさまざまな数学的問題を解くことができるため、数学者にとっては便利な公理だ。だが同時に奇妙なパラドックスも引き起こすため、記述集合論の研究者はこれを用いようとしない。
あなたのグラフには無限個の部分があった。これは集合の数が無限であることを意味する。そして各集合からひとつの要素を選んだ。各部分で最初に青く塗ることにした点だ。こうして最初に選んだ青い点のすべてが新しい集合を形成する。この時点で、あなたは選択公理を使ったことになる。
これにより、残りのノードを青と黄の交互のパターンで彩色しようとすると問題が生じる。先ほどは、各ノード（長さはゼロ）を個別に彩色したが、その際、グラフの異なる部分に属するノード同士がどのように関係しているかを把握していなかった。 そのため、グラフのすべての青いノードの集合についても、すべての黄色いノードの集合についても、その長さを説明することができない。言い換えれば、これらの集合は測定できない、つまり非可測だ。非可測集合については、数学者は有益なことを何も言えないのだ。
記述集合論の研究者にとって、これは満足のいく状況ではない。そこで研究者たちは、グラフを連続的な方法で彩色する方法を見つけようとした。選択公理を使わず、測度可能な集合が得られる方法だ。
グラフの最初の部分をどのように構築したかを思い出してみよう。円周上の1点を選び、一定の距離だけ離れた第2のノードと結んだ。今回は、最初のノードを青で、第2のノードを黄で、そのあいだの弧を青で彩色してみる。第2と第3のノードのあいだの弧は黄色にする。その次の弧は再び青にする。これを繰り返す。 やがて、円周をほぼ一周することになる。つまり、小さな残りのセグメントに含まれるノードを除けば、グラフのすべてのノードに色を割り当てたことになる。その時点で最後の弧が黄色だったとしよう。では、残った短いセグメントはどのように色づけできるだろうか？ 青は使えない。青くすると、最初に青で彩色した弧のノードにつながってしまうからだ。黄色も使えない。直前の弧の黄色のノードにつながってしまう。 そのため、3つ目の色を使うしかない。ここでは緑を使うことにしよう。 それでも、最終的に得られる青、黄、緑のノードの集合は、選択公理を用いたときに得られた点の散在ではなく、円周の一部を構成する。これらの集合の長さは計算できる。測定可能、つまり可測なのだ。
そのため、記述集合論の研究者は2色バージョンの問題を階層のいちばん下の棚（非可測集合の棚）に置き、3色バージョンの問題ははるか上の棚、言い換えれば、測度のさまざまな概念を適用できる問題の棚に配置する。
バーンシュタインは大学院時代にこのような彩色問題を研究し、本棚を順に埋めていった。学位を取得してまもなく、これらを一度に分類できるかもしれない方法を──そしてこれらの問題が誰も気づかなかったほど深く数学的に結びついた構造をもっていることを証明する方法を偶然発見した。
バーンシュタインはときどきコンピューター科学の講演を聞きに行く。コンピューター科学では、グラフはコンピューターのネットワークを意味し、有限のものとして扱われる。 19年、そのような講演のひとつが彼のキャリアの転機となった。それは「分散アルゴリズム」についての講演で、中央のコーディネーターなしにネットワーク内の複数のコンピューターが同時にタスクを実行するための命令の集合を指す。 建物内にたくさんのWi-Fiルーターがあると想像してみよう。近くのルーターが同じ周波数チャンネルを使うと互いに干渉する恐れがあるため、どのルーターも隣接するルーターが使っていないチャンネルを選ぶ必要がある。 コンピューター科学者はこれをグラフの彩色問題に言い換えることができるだろう。ルーターがノードで、ルーター同士の接続がエッジだ。2色（ふたつの異なる周波数チャンネル）だけを使い、隣接するふたつのノードが同じ色にならないように各ノードに色を割り当てる方法を見つけるのだ。 だが、そこには条件がある。ノードは、いわゆる局所アルゴリズムを用いて、直接隣接するノードとしか通信できない。まず、各ノードが同じアルゴリズムを実行し、自分に色を割り当てる。次に、隣接するノードと通信して、周囲の小さな領域でほかのノードがどの色をもっているかを把握する。そしてアルゴリズムを再度実行し、自分の色を変更するかどうかを決める。ネットワーク全体が適切に彩色されるまで、このステップを繰り返す。 コンピューター科学者は、あるアルゴリズムが何ステップで実行できるかを明らかにしようとする。例えば、ルーター問題を2色だけで解く局所アルゴリズムは、例外なく驚くほど非効率的になる。ところが、3色目の使用を認めるだけで、非常に効率的な局所アルゴリズムが見つかる。
バーンシュタインが出席した講演で、講演者はさまざまな問題の解決に必要な色の数、つまり効率性の閾値について論じていた。そのうちのひとつが、記述集合論の世界に存在する閾値にとてもよく似ていることに、バーンシュタインは気づいた。特定の無限グラフを測度可能な方法で彩色するために必要な色の閾値だ。 バーンシュタインは、この一致は単なる偶然ではないと考えた。コンピューター科学者もまた図書館司書のような存在で、アルゴリズムの効率性に基づいて問題を棚に分類しているだけとは思えなかった。コンピューター科学者たちが扱う問題も、たんにグラフと彩色の問題として記述できるというだけの話ではなさそうだ。 集合論とコンピューター科学というふたつの本棚にはもっと大きな共通点がある──バーンシュタインはそう考えた。両分野のあいだには、はるかに深いつながりがあるのではないか、と。
バーンシュタインは自分の研究分野が発展することで、集合論の研究者の仕事に対する現役数学者たちの見方が変わることを期待している。集合論が現実の数学の世界からかけ離れた辺境の数学だとはもう思われないようにしたいのだと。「わたしはこの状況を変えたいんです」とバーンシュタインは言う。「みんなに、無限について考えることに慣れてもらいたいのです」
※本記事は、サイモンズ財団が運営する『Quanta Magazine』（編集については同財団から独立）から許可を得て、転載されたオリジナルストーリーである。同財団は、数学および物理・生命科学の研究開発と動向を取り上げることによって、科学に対する一般の理解を深めることを使命としている。
※『WIRED』による数学の関連記事はこちら。