本文へジャンプ

数学の定理の難しさ・複雑さを理解する

小川研究室 OGAWA Laboratory
講師:横山 啓太(Yokoyama Keita)

E-mail:
[研究分野]
数理論理学、数学基礎論、理論計算機科学
[キーワード]
数理論理学、数学基礎論、証明論、計算可能性、算術体系、超準モデル、逆数学

研究を始めるのに必要な知識・能力

時間をかけて数学の論証・証明を掘り下げるための根気と意欲と体力。集合や写像の基本的な扱いを始めとした数学の基礎事項(大学1〜2年程度)が必要ですが、数学の知識は研究と並行して身につけていくこともできます。例えばツォルンの補題(知らなければ調べてみてください)の証明を自分の言葉で説明できますか?証明に何を使いましたか?こうしたことを丁寧に掘り下げ理解しようとする心が大事です。そしてこのような数学の議論と思考を楽しめ、興味を継続していけることが必須です。

この研究で身につく能力

論理的思考力と数学的な理解力、およびそれらを通じた問題解決能力。物事を数学の視点を用いて論理的に考察する能力は科学技術を研究する上での基本的な能力と言えるでしょう。数学の論証に慣れ、「数学的に理解する」ことを身につけることで研究の基盤となる論証能力を身につけることができます。また「理解した」状態を理解することは「分からない」や「難しい」ことを客観的にとらえることでもあります。何が分からないかを正しく理解することは、問題解決の最も重要な糸口となります。

研究内容

 自然数の基本的な性質を表した自然数の公理体系(算術体系と呼ばれる)の上で表現される数学の様々な定理(命題)の強さ・複雑さ・難しさと言ったものを数学的に分析する「逆数学」と呼ばれる研究を中心に行っています。自然数の公理体系の上で表現される命題は幅広く、代数・解析・幾何学の基本的な命題から組み合わせ命題や理論計算機科学の問題といった様々な命題の難しさを調べることができます。定理の強さを分析する尺度には、証明の形式化に必要な公理や推論規則の強さ、計算機による計算可能性の視点からの複雑さ、導出される自然数上の関数の増加速度、といった様々なものがあります。これらの尺度を駆使しながら多面的に研究を進めています。また、これらの尺度の性質自体を調べるフレームワーク研究も並行して進めています。

組み合わせ論の逆数学研究

 ラムゼイの定理を代表とする無限・有限の組み合わせ命題の多くは数学的に非常に複雑な構造を持っています。有限ラムゼイの定理やその亜種が現実の計算機ではとても計算できないような急増加関数を導くことはよく知られています。実はその背景には無限ラムゼイの定理の難しさがあります。実際、無限ラムゼイの定理は計算可能性の視点から非常に複雑な解を持つ場合があることが知られており、このことが有限ラムゼイの定理の解の大きさを推定する難しさと密接に関わっています。一方、ラムゼイの定理は理論計算機科学にも様々な応用を持ちます。その一つがプログラムの停止性検証で、ラムゼイの定理の数学的に精密な分析からは、例えば一定の条件を満たす停止性検証プログラムの理論的な限界を知ることができます。

公理の強さと証明の長さ

 数学の定理を計算機にも検証できるような形で記述するためには数学の証明を形式化する必要があります。この証明の形式化により、数学の証明に用いられる公理の強さや証明の複雑さを分析することができます。一つの定理を証明する際に、もし使う前提をできるだけ少なくしようとすれば長い証明が必要になるかもしれません。一方、強い公理や既存の別の定理を用いれば、同じ定理をはるかに短く証明できることもあります。このような証明の長さや複雑性を数学の道具で分析します。こうした研究では、形式的な証明体系の能力の数学的な限界を与えた「ゲーデルの不完全性定理」が重要な意味を持ちます。

自然数の超準モデル

 自然数の代数構造と数学的帰納法を数学のための公理として捉えると、自然数と同じ代数構造と帰納法の性質を満たしながら、自然数全体とは同型にならないような数学的な構造(超準モデル)を構成することができます。超準モデルの構造を理解することで公理の強さ・証明の不可能性・自然数命題の複雑さと言った直感的に理解しがたい概念をより具体的なイメージで理解することができます。

上記のテーマを含め、多くのテーマについて米国、シンガポール、中国、英国、フランス、ベルギー、ポーランドなどの研究者と幅広く共同研究を行っています。

主な研究業績

  1. Ludovic Patey and Keita Yokoyama, The proof-theoretic strength of Ramsey’s theorem for pairs and two colors, to appear in Advances in Mathematics.
  2. Alexander P. Kreuzer and Keita Yokoyama, On principles between Σ1- and Σ2-induction, and monotone enumerations, Journal of Mathematical Logic 16, no.1, 21 pages, 2016.
  3. Silvia Steila and Keita Yokoyama, Reverse mathematical bounds for the Termination Theorem, Annals of Pure and Applied Logic 167, pages: 1213–1241, 2016.

使用装置

紙と鉛筆とコーヒー

研究室の指導方針

研究課題は数理論理学に関連する数学のテーマで指導教員の指導できる範囲であれば自由に選ぶことができます。英語で教科書や文献を読み、証明を理解し、セミナーでそれを説明し、内容を自らの言葉で再構成する、というステップを繰り返しながら研究テーマの理解を深めていきます。調べることよりも、証明を考え、理解することに重点がおかれます。また、自身の研究の範囲に留まらず、研究室内外の他のセミナーに参加したり自主ゼミを行うことなどにより他の研究分野にも興味を広げることを推奨します。研究室を訪問する国内外の多くの研究者との積極的なコミュニケーションも重要です。自力で理解を掘り下げながら、コミュニティの中で研究の幅を広げ、質を高めていけるよう努めましょう。

[研究室HP] URL:http://www.jaist.ac.jp/~y-keita/

ページの先頭へもどる