Sendai Logic Seminar
直近のセミナー
- Time: 2018.11.9 (金) / 16:00 - 17:00
- Speaker: Yasuhiko Omata (Tohoku University)
- Title: 2階算術のコード化モデルと実数の集合のRamsey性
History
- Time: 16:00 - 17:00
- Speaker: 小俣 安彦 氏 (東北大学大学院 理学研究科)
- Title: 弱Paris-Harrington原理とDicksonの補題
- Abstract: The weak Paris-Harrington principle is a weak version of the Paris-Harrington principle, which was originally used as a convenient intermediate version in showing lower bounds for the Paris-Harrington principle for pairs [1]. We compare it with Dickson's lemma, which is a combinatorial theorem originally used in algebra, in particular for showing Hilbert's basis theorem [2]. We give a construction which shows the direct, level by level, equivalence between the weak Paris-Harrington principle for pairs and the Friedman-style miniaturization of Dickson's lemma. Our studies result in a cascade of consequences: - An explicit expression for weak Ramsey numbers for pairs. - A sharp classification of the complexity classes of weak Paris-Harrington-Ramsey numbers. - Bounds for weak Ramsey numbers in higher dimensions. - A phase transition for the weak Paris-Harrington principle which is different from that for the Paris-Harrington principle [3]. - Level by level equivalence of Dickson's lemma and a relativized version of the weak Paris-Harrington principle. All of these are established in RCA_0^*. This is a joint work with Florian Pelupessy.
- Time: 16:00 - 17:00
- Speaker: 高嶋 大翼 氏 (東北大学大学院 理学研究科)
- Title: 限定算術上の強制法の基礎
- Abstract: 限定算術と計算量クラスには対応関係があることが知られている． これにより，計算量クラスの分離問題を， 対応する公理の証明能力の違いのように考えることが出来る． 竹内外史と安本雅洋によって，１９９６年に， 限定算術上でブール値モデルを構成する論文が発表された． 本発表では，限定算術と計算量クラスの対応関係を確認し， 限定算術上でブール値モデルを構成する方法について概説する．
- Time: 16:00 - 17:00
- Speaker: 中林 美郷 氏 (東北大学大学院 理学研究科)
- Title: Rabinの定理と無限木オートマトン
- Abstract: Rabinの定理とは，無限二分木のMonadic second-order theoryがdecidableであることを主張する定理である．本発表ではオートマトンの基本事項について述べながら，Rabinの定理の証明を行う．
- Time: 16:00 - 17:00
- Speaker: 横山 啓太 氏 (北陸先端科学技術大学院大学)
- Title: 一階算術・二階算術とラムゼイの定理
- Abstract: ラムゼイの定理は算術において様々な角度から研究されている。有限ラムゼイの定理の亜種であるパリス-ハーリントンの命題はペアノ算術から独立な命題の例としてよく知られている。一方、無限ラムゼイの定理の強さは二階算術において逆数学の立場から深く研究されている。本講演では諸種の有限ラムゼイの定理と無限ラムゼイの定理の関係性について算術の証明論・モデル理論の両面から比較し、関連する最近の結果について紹介する。
- Time: 16:00 - 17:00
- Speaker: 古川 大樹 氏 (東北大学大学院 理学研究科)
- Title: RCA_0におけるハーリントンの定理とπ^1_ 1式の証明の長さの比較
- Abstract: ハーリントンの定理はWKL_0とRCA_0の間にπ^1_ 1保存拡大が成り立つことを主張する定理であるが、その証明は普通、モデル論的になされる。しかし、 この証明をRCA_0内で形式的に証明し直すことでWKL_ 0におけるπ^1_1式の証明をRCA_ 0における証明に変換する具体的な手続きが与えられる。これを考察することで、RCA_0における証明の長さがWKL_ 0における元の証明の長さの多項式で抑えられることがわかる。
- Time: 16:00 - 17:00
- Speaker: 田中 一之 氏 (東北大学大学院 理学研究科)
- Title: 無限ゲームと様相μ計算
- Abstract: GaleとStewartによって導入された無限ゲームは二階算術の言葉で自然に記述できるが，二階算術のフル体系Z_2はもとより通常の公理的集合論でもうまく分析できない（例．決定性が証明できない）．様相μ計算は不動点演算子をもった様相論理であるが，二階算術の部分体系ともみなせる．本講演では様相μ計算の基本事項をおさらいしたあと，それによって扱える無限ゲームの決定性の限界や，諸性質の分離などについて述べる．