Sendai Logic Seminar

直近のセミナー

  • Time: 2019.1.25 (金) / 16:00 - 17:00
  • Speaker: 古川 大樹 氏,中林 美郷 氏 (東北大学大学院)
  • Title: 2階算術の部分体系間の保存拡大に関する研究,On one-variable modal mu-calculus and weak ATA.
  • Abstract: 修士論文発表会の練習を行います.

History

  • Time: 16:00 - 17:00
  • Speaker: Paul-Elliot Anglès D'Auriac 氏 (パリ・エスト・クレテイユ大学)
  • Title: On Infinite Time Turing Machine and and its related ordinals.
  • Abstract: In 1998, Hamkins and Lewis introduced Infinite Time Turing Machines (ITTMs), a version of Turing Machines where time is allowed to run through the ordinals instead of the integers. This model of computation revealed itself to have interesting connections with set theory and in particular Godel's constructible hierarchy. In this talk, we will be interested in the properties of the ordinals that naturally arises in the study of ITTMs, such as those that correspond to halting time, or that have a code that can be written on the tape of an ITTM. If time allows, we will prove the λ-ζ-Σ-Theorem from Welch, and the fact that supremum of halting times and writable ordinals are the same.

  • 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: 限定算術と計算量クラスには対応関係があることが知られている. これにより,計算量クラスの分離問題を, 対応する公理の証明能力の違いのように考えることが出来る. 竹内外史と安本雅洋によって,1996年に, 限定算術上でブール値モデルを構成する論文が発表された. 本発表では,限定算術と計算量クラスの対応関係を確認し, 限定算術上でブール値モデルを構成する方法について概説する.

  • 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はもとより通常の公理的集合論でもうまく分析できない(例.決定性が証明できない).様相μ計算は不動点演算子をもった様相論理であるが,二階算術の部分体系ともみなせる.本講演では様相μ計算の基本事項をおさらいしたあと,それによって扱える無限ゲームの決定性の限界や,諸性質の分離などについて述べる.

過去のセミナー

  • Seminar in 2017
  • Seminar in 2016
  • Seminar in 2015
  • Seminar in 2014
  • Seminar in 2013
  • Seminar in 2012
  • Seminar in 2011
  • Seminar in 2010