2013 Logic Seminar


  • 2014.02.21
    Sendai Logic School 2014 at Tokyo Tech (web site)
  • 2014.02.14
    [発表者] Jeroen Van der Meeren (Ghent University)
    [題目]Structures with the gap-embeddability relation [Slide]
    [概要]Kruskal’s theorem is a well-known statement in mathematics, stating that the set of trees is a well-partial-ordering. It is for example used in computer science with regard to termination orderings. In 1985, Harvey Friedman proved that Kruskal’s theorem is not provable in ATR_0. Furthermore, he introduced a new kind of embeddability relation between finite labelled rooted trees (the gap-embeddability relation). With this ordering relation, the set of trees is still a well-partial-ordering, but this fact is now unprovable in Pi11-comprehension! One can see that, going from a normal ordering to an ordering with a gap-condition is really adding strength to your statement! Therefore, it is interesting to study structures with the gap-embeddability relation. In this talk, I will give a general overview of structures with the gap-embeddability relation (trees and sequences) and discuss already known results. Furthermore, I will talk about its connections with the theta-functions and some new results concerning this topic. Additionally, I will present some new progress about the proof-theoretical ordinal of theories which appear in this context.
    [発表者]Sam Sanders (Ghent University)
    [題目]A new approach to Hilbert’s program via Nonstandard Analysis
    [概要] David Hilbert’s program for the foundations of mathematics was an attempt at reducing infinitary mathematics to finitary mathematics, as a way of establishing mathematics on firm and secure grounding, namely finitistic arithmetic. Thus, the original aim of proof theory was to reduce all of mathematics to so-called finitistic arithmetic (later formalized in the system PRA), and to prove the consistency of finitistic mathematics inside the latter. However, Kurt Goedel’s famous incompleteness theorems imply that such a consistency proof is impossible, i.e. that Hilbert program cannot be accomplished in the aforementioned way. In this talk, we show how Nonstandard Analysis allows us to salvage Hilbert’s program; In particular, we show how infinitary objects (from both classical and intuitionistic mathematics) can be reduced to nonstandard finitary objects in an elegant and straightforward way. Ulrich Kohlenbach’s so-called higher-order Reverse Mathematics plays a central role.
    [発表者]Paul Shafer (Ghent University)
    [題目]Examples of problems that cannot be solved by randomness and examples of problems that can be solved by randomness [Slide]
    [概要]The computational difficulty of a mathematical problem can be analyzed by considering the computable instances of the problem and determining how much extra information is needed to compute solutions to these instances. Often this can be accomplished by coding a well-known algorithmically unsolvable problem, such as the halting problem, into an instance of the problem being analyzed. However, many problems are weaker than the halting problem in the sense that such a coding is impossible. In this talk, we consider several problems weaker than the halting problem and classify them according to whether or not access to randomness can help solve them.
  • 2014.02.07
    [発表者]Weiguang Peng (東北大学大学院理学研究科)
    [題目]Blackwell Games with a Constraint function
  • 2014.01.31(修士論文発表練習)
    [発表者]沖坂 祥平 (東北大学大学院理学研究科)
    [発表者]芳賀 辰哉 (東北大学大学院理学研究科)
  • 2014.01.24
    [発表者]村上 翔太 (東北大学大学院理学研究科)
    [題目]Variations of Ramseyan factorization in reverse mathematics II
  • 2014.01.17
    [発表者]鈴木 登志雄 (首都大学東京 理工学研究科)
    [題目]Equilibriums of Independent Distributions on an AND-OR Tree under Constraints
    [概要]We study a probability distribution d on the truth assignments to a uniform binary AND-OR tree. Liu and Tanaka [2007, Inform. Process. Lett.] show the following: If d achieves the equlibrium among independent distributions (ID) then d is an identical independent distribution (IID). We show a stronger form of the above result: Under a condtraint on the probability at the root, the resut still holds. The proof is elementary, but employs a clever trick of induction.
  • 2014.01.10
    [発表者]Florian Pelupessy (東北大学大学院理学研究科)
    [題目]Phase transitions in logic
    [概要]We examine the transition threshold for Friedman's finite adjacent Ramsey theorem. This statement follows the general heuristics for phase transitions, where estimates on witnesses for theorem \varphi_c with constant parameter c determine the transition threshold for the theorem \varphi_f with parameter function f:N \rightarrow N.
  • 2013.12.27, 2014.01.03
  • 2013.12.20
    [発表者]井澤 昇平 (東北大学大学院理学研究科)
    [題目]行列積による代数系の分解 [Slide]
  • 2013.12.13
  • 2013.12.06
    [発表者]佐藤 隆 (東北大学大学院理学研究科)
    [題目]Constructing Algebraic Systems and Reverse Mathematics
    [概要]We often construct a new algebraic system from given one. For example, we can construct \Z from \N and \Q from \Z. In the setting of reverse mathematics of second order arithmetic, we examine which set existence axioms are required to construct a field of fractions, a ring of total quotients and so on. This talk gives simple examples of reverse mathematics of algebra including new one.
  • 2013.11.29
    [発表者]芳賀 辰哉 (東北大学大学院理学研究科)
  • 2013.11.22
    [発表者]鈴木 仁哉 (東北大学大学院理学研究科)
    [題目]代数学の逆数学 -p進数と付値体の逆数学へ-
  • 2013.11.15
    [発表者]沖坂 祥平 (東北大学大学院理学研究科)
  • 2013.11.08
    [発表者]横山 啓太 (北陸先端科学技術大学院大学 情報科学研究科)
    [題目]A strengthened version of Ramsey's theorem and its finite iteration [Slide]
    [概要]It is well-known that several finite variations of Ramsey's theorem provide independent statements from PA. The first such example was found by Paris by using an iteration of finite Ramsey's theorem plus relatively largeness condition. Later, that statement is simplified by Harrington, and nowadays, it is known as the famous Paris-Harrington principle. However, the original "iteration version" has the advantage that it can approximate the infinite version of Ramsey's theorem. This fact also shows the limitation of the power of infinite Ramsey's theorem, in other words, infinite Ramsey's theorem as itself cannot prove the statement "for any m, m-th iteration of finite Ramsey's theorem holds". In this talk, we try to fill this gap. A natural question arising from the above is "what is a version of infinite Ramsey's theorem which implies iterated finite Ramsey's theorem?" Of course a naive answer to this question is a (finite) iteration of infinite Ramsey's theorem. However, this does not succeed, since the iterated version of infinite Ramsey's theorem is just equivalent to the original one. Thus, we will introduce a slightly strengthened version of infinite Ramsey's theorem, which is still equivalent to the original one over WKL0, and then consider the iterated version of it.
  • 2013.11.01
  • 2013.10.25
    [発表者]Florian Pelupessy (東北大学大学院理学研究科)
    [題目]An introduction to unprovability in Peano Arithmetic
    [概要]Since the Gödel incompleteness theorems we know that there exist statements which are true in the natural numbers but which cannot be proven in PA. We provide a gentle introduction to natural examples of such theorems.
  • 2013.10.18
    [発表者]山崎 武 (東北大学大学院理学研究科)
  • 2013.10.11
    [発表者]藤原 誠 (東北大学大学院理学研究科)
  • 2013.10.04
    [発表者]田中 一之 (東北大学大学院理学研究科)


  • 2013.07.26(博士論文・修士論文発表練習)
    [発表者]NingNing Peng (東北大学大学院理学研究科)
    [題目]Computability and Relative Randomness
    [発表者]Weiguang Peng (東北大学大学院理学研究科)
    [題目]Logical Investigations on Infinite Stochastic Games
  • 2013.07.19
    [発表者]John Pardo (Pennsylvania State University / JAIST)
    [題目]A Discussion on the Reverse Mathematics of Ramsey's Theorem
    [概要] I will give a brief survey of the reverse mathematical/computability theoretic properties of different versions of Ramsey's Theorem, in particular Ramsey's Theorem for pairs, based on Chapter 6 of Hirschfeldt's notes entitled "Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles." I will in particular give a partial proof of a famous result by Friedman, McAloon and Simpson that Ramsey's Theorem is equivalent to ACA_0' over RCA_0.
    [発表者]横山 啓太 (北陸先端科学技術大学院大学 情報科学研究科)
    [題目]Pi^1_1-conservative extensions of subsystems of second-order arithmetic
    [概要]For the study of reverse mathematics, (Pi^1_1-)conservation results between two different systems are very important. Many important theorems are well-known, e.g., WKL_0 and RCA_0^+ are Pi^1_1-conservative extensions of RCA_0. Moreover, we can show the following: for given a Pi^1_2-theory T, there exists a maximal Pi^1_2-theory which is Pi^1_1-conservative over T. Then, what is the maximal extension of RCA_0, ACA_0, etc. in this sense? In this talk, I will give a survey on this topic including Henry Towsner's resent results.
  • 2013.07.12
    [発表者]吉居 啓輔 (東北大学大学院理学研究科)
    [題目]Determinacy of games, inductive definitions, and transfinite recursion
  • 2013.07.05
    [発表者]根元 多佳子 (北陸先端科学技術大学院大学 情報科学研究科)
    [題目]Determinacy and ordinal analysis [Slide]
    [概要]カントール空間における無限ゲームの決定性は二階算術の多くの体系を特徴付けることが知られているが、 今回は ATRo の部分体系がどのように特徴付けられるか、特に証明論的強さがどのように強くなっていくかを見ていく。
  • 2013.06.28
    [発表者]Weiguang Peng (東北大学大学院理学研究科)
    [題目]Introduction to two-player stochastic games [Slide]
  • 2013.06.21
    [発表者]村上 翔太 (東北大学大学院理学研究科)
    [題目]Variations of Ramseyan Factorization in Reverse Mathematics
  • 2013.06.14
    [発表者]何 青玉 (揚州大学, COLABSプログラム交換留学生)
    [題目]Introduction to Domain Theory and Semicontinuous Lattices [Slide]
  • 2013.06.07
    [発表者]井澤 昇平 (東北大学大学院理学研究科)
    [題目]被覆恒等式をみたさない最大の演算集合 [Slide]
  • 2013.05.31
  • 2013.05.24
    [発表者]NingNing Peng (東北大学大学院理学研究科)
    [題目]Reverse Mathematics On Probability Theory
  • 2013.05.17
    [発表者]沖坂 祥平 (東北大学大学院理学研究科)
    [題目]Introduction to Descriptive Complexity [Slide]
  • 2013.05.10
    [発表者]佐藤 隆
    [題目]Reverse Algebra and Isbell's Zig-Zag Theorem [Slide]
  • 2013.04.19
    [発表者]藤原 誠 (東北大学大学院理学研究科)
    [題目]Uniform provability in reverse mathematics and intuitionistic provability [Slide]
  • 2013.04.12
    [発表者]山崎 武 (東北大学大学院理学研究科)
    [題目]Filters and Reverse Mathematics [Slide]

Devised by NingNing Peng and managed by Shota Murakami.

Copyright 2011 Sendai Logic All Rights Reserved.