### 2014 Logic Seminar

#### 2014年度後期

• [発表者] 2015.02.06 佐藤 隆 （東北大学大学院理学研究科） Reverse Mathematics of Group Theory: Where Axioms Lurk In this talk, 1. We quickly review the story of reverse mathematics of group theory, 2. I show new results and its applications in which a strong tool from recursion theory plays an active role, 3. I give an informal anecdote about extracting out set existence axioms from mathematical statements other than from group theory. The new results are as follows (including of a joint work with Fumiya Nakashima). 1. The existence of a nontrivial proper subgroup (respectively a finitely generated nontrivial proper subgroup) in a nontrivial countable group which is not a cyclic group of prime order is equivalent to WKL0 (respectively ACA0) over RCA0. 2. The existence of the direct sum, the normalizer, the derived subgroup, and an essential closure (a neat hull) in a countable group is equivalent to ACA0 over RCA0 respectively.
•  2015.01.23, 2015.01.30 修士論文発表練習
• [発表者] 2015.01.16 藤原 誠 （東北大学大学院理学研究科） Intuitionistic and uniform provability in reverse mathematics For existence theorems, it has been recently established that their intuitionistic provability is closely related to their uniform provability in RCA. In this talk, we first show a metatheorem which states these two are equivalent for practical existence theorems. Secondly, we present another metatheorem which enables us to apply classical reverse mathematics to constructive mathematics.The second part is a joint work with Ulrich Kohlenbach.
•  2015.01.02 年始休みです．
•  2014.12.26 今週は休みです(RIMS研究集会へ多数参加のため)．
• [発表者] 2014.12.15 Emanuele Frittaion （東北大学大学院理学研究科） From well-quasi orders to Noetherian spaces in reverse mathematics I will talk about reverse mathematics and Noetherian spaces. This is an ongoing project with Alberto Marcone, Paul Shafer, Jeroen Van Der Meeren and Matt Hendtlass. All the statements we consider are of the form "If Q is a well-quasi order, then \Gamma(Q) is a Noetherian topological space", where \Gamma is a functor from quasi-orders to topological spaces. We show that most of these theorems are equivalent to \ACA0. I will give some insight on the computability aspects of these reversals.
• [発表者] 2014.12.12 沖坂 祥平 （東北大学大学院理学研究科） Reverse mathematics of lattice theory
•  2014.12.05 集中講義のため休みです．
• [発表者] [題目] 2014.12.01 数学専攻談話会 石原 哉 (北陸先端科学技術大学院大学 情報科学研究科） 構成的逆数学と非構成的原理 [slides]
• [発表者] 2014.11.28 Sam Sanders (Ghent University） Taming the Reverse Mathematics zoo [slides] Reverse Mathematics is a program in the foundations of mathematics. Its results give rise to an elegant classification of theorems of ordinary mathematics based on computability. In particular, the majority of theorems fall into only five categories of which the associated logical systems are dubbed the Big Five'. Recently, a lot of effort has been directed towards finding exceptional principles, i.e. which fall outside the Big Five categories. The so-called Reverse Mathematics zoo is a collection of such exceptional principles (and their relations). During this talk, I show that the uniform versions of the principles from this zoo are equivalent to arithmetical comprehension, i.e. the zoo disappears at the uniform level.
• [発表者] [題目] 2014.11.21 修士論文報告会(後半) 猪爪 智 （東北大学大学院理学研究科） 二階算術における順序と位相 川原 雅弘 （東北大学大学院理学研究科） 無限アーベル群論の逆数学
• [発表者] [題目] 2014.11.14 修士論文報告会(前半) 鈴木 仁哉 （東北大学大学院理学研究科） On Weihrauch degrees of some theorems in algebra 中嶋 郁弥 （東北大学大学院理学研究科） 代数的部分構造と逆数学
• [発表者] 2014.11.07 横山 啓太 （北陸先端科学技術大学院大学 情報科学研究科） A thought on incompleteness It is well-known that there is no consistent complete recursive theory extending PA. Then, for a given consistent recursive T extending PA, can we find a consistent recursive theory T' extending T+Con(T) such that for any formula A, either A is provable in T or "A is not provable in T" is provable in T'? In Algorithmic Randomness meeting in Singapore, June 2014, Mingzhong Cai answered to this question and gave a generalized question. In this talk, I will introduce the answer to Cai's question by Beklemishev, and discuss a more general form. Angeliki Koutsoukou-Argyraki （Technische Universitat Darmstadt） Proof mining and partial differential equations; Rates of convergence and metastability for abstract Cauchy problems generated by accretive operators [pdf]
• [発表者] 2014.10.31 黒田 覚 （群馬県立女子大学文学部） Toda theorem in bounded arithmetic 山形 頼之 （産業技術総合研究所） CONSISTENCY PROOF OF A FEASIBLE ARITHMETIC INSIDE A BOUNDED ARITHMETIC In this talk, we prove that S12 can prove consistency of PV−, the system obtained from Cook and Urquhart’s PV [3] by removing induction. This apparently contradicts Buss and Ignjatovi ́c [2], since they prove that PV does not prove Con(PV−). However, what they actually prove is unprovability of consistency of the system which is obtained from PV− by addition of propositional logic and BASICe-axioms. On the other hand, our PV− is strictly equational and our proof relies on it.
• [発表者] 2014.10.24 Florian Pelupessy （東北大学大学院理学研究科） On the finitary' Ramsey theorem We examine the strength of a variant of Ramsey's theorem which is inspired by Gaspar, Kohlenbach and Tao's `finitary' infinite pigeonhole principle.
• [発表者] 2014.10.17 Weiguang Peng （東北大学大学院理学研究科） Fixed point theorems on reverse mathematics The fixed point theorem asserts that under certain conditions, there exists a point x of function f, such that f(x)=x. In this talk, we will pick up some fixed point theorems and check them on reverse mathematics.
• [発表者] 2014.10.10 田中 一之 （東北大学大学院理学研究科） Variants of infinite games and their strength Recently, much effort has been made to characterize the determinacy of Gale-Stewart Borel games within second order arithmetic. On the other hand, Borel hierarchies and Wadge hierarchies based on less powerful machines have been extensively studied in theoretical computer science, and so a winning strategy of a game in such a hierarchy is very often computable. In this talk, I will review these two lines of studies and their relations, and consider some problems in the intersecting area.

#### 2014年度前期

• [発表者] [題目] 2014.08.01 修士論文発表練習 Wenjuan Li （東北大学大学院理学研究科） On topological complexity in infinite pushdown games
• [発表者] [題目] 2014.07.25 修士論文経過報告会4 川原 雅弘 （東北大学大学院理学研究科） 無限アーベル群論の逆数学
• [発表者] 2014.07.18 砂辺 祐哉 （東北大学大学院理学研究科） 束論の逆数学 （修士論文経過報告会3） 仲川 聡子 （東京工業大学 情報理工学研究科） 様相μ計算の完全性について 様相μ計算は様相論理Kに最小・最大不動点演算子を加えて得られる論理体系であり、一般的には1983年にKozenが提唱した体系を指す。その完全性は1990年代後半にWalukiewiczによって示されたのだが、その論文[1]は非常に複雑なことで知られている。game semanticsやautomata theoryなど様々な知識を必要とするだけでなく、タブローを利用した細かい手法が必要となるためである。本発表では様相μ計算の紹介を行い、[1]の概要について説明を行う。 [1] Igor Walukiewicz, "Completeness of Kozen's Axiomatisation of the Propositional $\mu$-Calculus.'' Information and Computation 157.1 (2000): 142-182.
• [発表者] [題目] 2014.07.11 修士論文経過報告会2 猪爪 智 （東北大学大学院理学研究科） 順序理論の逆数学
• [発表者] 2014.07.04 高嶋 大翼 （東北大学大学院理学研究科） 計算量理論の基礎
• [発表者] [題目] 2014.06.27 修士論文経過報告会1 中嶋 郁弥 （東北大学大学院理学研究科） 半群論の逆数学 鈴木 仁哉 （東北大学大学院理学研究科） 無限アーベル群論の逆数学
• [発表者] 2014.06.20 佐藤 隆 （東北大学大学院理学研究科） Some hull operations and arithmetical comprehension [slides] Hull operations (also known as closure operations) appear in several scenes of mathematics. In this talk I will introduce three examples of hull operations from algebra whose proof theoretic power is exactly equivalent to the arithmetical comprehension axiom. Integral closures from the ring theory, essential closures from the group theory and neat hulls from the group theory will be brought up. They include new results on reverse mathematics established in the RA seminar.
• [発表者] 2014.06.13 Wenjuan Li （東北大学大学院理学研究科） On the topological complexity in infinite pushdown games Infinite two-player games have been intensively studied in Descriptive Set Theory. Especially, determinacy and topological complexity are two central topics for infinite games. In this talk, we will first recall one kind of well-known infinite two-player games, Gale Stewart games, and introduce some basic and recent determinacy results on it. Next, we would like to move on to Wadge games and its applications. Then, recalling pushdown automata and omega context free languages, we will consider pushdown games with winning conditions of various Borel complexity. Finally, we would like to discuss some remaining problems.
• [発表者] 2014.06.06 Weiguang Peng （東北大学大学院理学研究科） The Axiom of Blackwell Determinacy The notion of Blackwell determinacy was introduced for finite games by Neumann, and generalized to infinite games by Blackwell who showed the determinacy over open and $G_{\delta}$ sets. Vervoort extended the determinacy of Blackwell games to $G_{\delta \sigma}$ sets. In 1998, Tony Martin proved that the Axiom of Determinacy AD implies the Axiom of Determinacy AD-BL, and conjectured that the converse holds. Until now, the conjecture remains open. In this talk, I shall introduce some consequences of Axiom of Blackwell Determinacy and progress on Martin’s conjecture.
•  2014.05.30 今週は休みです.
• [発表者] 2014.05.23 Florian Pelupessy （東北大学大学院理学研究科） Upper bound of the finite Maclagans Theorem using Ramsey [slides] Maclagan's finite theorem on monomial ideals is known to be independent of I\Sigma_2. In fact, the usual proof of this independence also shows that this theorem implies 1-consistency of I\Sigma_2 (over EFA). In this talk, using the Paris-Harrington theorem and Friedman's finite adjacent Ramsey theorem, we will show that the converse is also true.
• [発表者] 2014.05.16 藤原 誠 （東北大学大学院理学研究科） Framework for intuitionistic reverse mathematics The finite type arithmetic is employed as the framework for intuitionistic reverse mathematics along with classical higher order reverse mathematics. In this talk, I would introduce the finite arithmetic and its feature with respect to reverse mathematics. The miscellaneous facts on the system, including some of my small results, are presented.
• [発表者] 2014.05.09 松田 直祐 （東京工業大学 情報理工学研究科） ラムダ計算とコンビネータ理論の対応関係について （１）ラムダ項の計算を実装する際，α同値な項の扱いやα変換の扱いが問題になってくる．その問題を避けるアイディアをいくつか紹介する．（２）上で紹介するもののひとつにコンビネータを用いる方法があるが，ラムダ計算とコンビネータ理論の対応関係は，未だに万人の納得のいくものが見つかっていない状況である．そのことについて，以下の参考資料を基に説明をする．参考：J.R.Hindley, "Curry's Last Problem : Imitating lambda-beta-reduction in Combinatory Logic", MLG(1998)講演資料
• [発表者] 2014.05.02 村上 翔太 （東北大学大学院理学研究科） A generalization of weak Ramseyan factorization In the recent study of reverse mathematics, the strength of (logically) weak statements, especially Ramsey's theorem for pairs (RT22), has been studied by many researchers. In a joint work with T. Yamazaki and K. Yokoyama, we found a theorem equivalent to RT22, which is called Ramseyan factorization theorem for pairs. We also proved that a weaker version of Ramseyan factorization theorem is in between CAC and ADS, both strictly weaker than RT22. In this talk, we introduce a natural generalization of weak Ramseyan factorization theorem and discuss its strength.
• [発表者] 2014.04.25 猪爪 智 （東北大学大学院理学研究科） 順序理論の逆数学 現在仙台ロジックグループでは複数のプロジェクトに分かれて研究を行っています。今回の発表では、順序理論・束論の逆数学に関する研究プロジェクトを代表して、この半年間の研究成果についてご紹介します。
• [発表者] 2014.04.18 鈴木 仁哉 （東北大学大学院理学研究科） Prime Ideal Factorization in Second Order Arithmetic 現在仙台ロジックグループでは, いくつかの分野毎に逆数学の共同研究を行うプロジェクトを作って活動しています. 今回の発表では, 代数学における素イデアル分解定理についての研究の, 途中経過を紹介します.
• [発表者] 2014.04.11 山崎 武 （東北大学大学院理学研究科） Reverse Mathematics over Weak Systems Reverse mathematics is an ongoing research program to classify mathematical theorems according to their equivalence to one of subsystems of 2nd order arithmetic. Our group has been studying reverse mathematics on theorems in diverse fields including countable algebra, real and complex analysis, infinite combinatorics etc. The results we have gotten are mainly the equivalence between theorems and ACA_0 or below. Now we welcome new members. Then, in this talk, I would like to give a short introduction to reverse mathematics over such comparatively weak subsystems, sometimes using my small results as examples.

• #### 2010年度

Devised by NingNing Peng and managed by Shota Murakami.