Title: Forbidden Induced Subgraphs and the Los Tarski Theorem
Venue: Complex A 801 and online(zoom)
Time: 15:00-
Abstract: Let C be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Los-Tarski Theorem from classical model theory implies that
(*) C is definable in first-order logic (FO) if and only if C has a finite set of forbidden induced subgraphs.
In this talk I will discuss some applications of (*) and its limitations. Among others:
- Any class of graphs of bounded tree-depth can be characterized by a finite set of forbidden subgraphs. Our proof differs from the original proof of [Ding, 1992] by circumventing the machinery of well-quasi ordering.
- The forbidden subgraphs can be arbitrarily complex (e.g., not computable) compared to the FO-sentence defining the class C.
This is joint work with Joerg Flum.
Title: Theorems lying at the first level of the pseudo-hyperjump hierarchy
Venue: Complex A 801
Time: 15:00-
Abstract: The system Pi^1_1-CA_0 is characterized by a Pi^1_3 axiom ``every set has its hyperjump". To study the set of Pi^1_2 theorems provable from Pi^1_1-CA_0, Yokoyama and I introduced Pi^1_2-approximations of this axiom which we call pseudo-hyperjumps. Using pseudo-hyperjumps, we found a hierarchy that clarifies the structure of the set of Pi^1_2 theorems provable from Pi^1_1-CA_0.
In this talk, I will summarize theorems lying at the first level of the pseudo-jump hierarchy.
Title: Cut-free sequent calculus for a combination of intuitionistic and classical logic.
Venue: Complex A 801
Time: 15:00-
Abstract: After Brouwer’s intuitionism and Heyting’s formulation of intuitionistic logic, the discussions between advocates of intuitionistic logic and those of classical logic have been occurring in philosophy of mathematics, logic, and language. It is a reasonable idea to handle a ``combination’' of intuitionistic and classical logic in order to codify the discussion, where a logic L is stipulated as a combination of the two logics L1 and L2 if L is a conservative extension of both L1 and L2. Based on this idea, this talk provides a sequent calculus for a combination of intuitionistic and classical propositional logic. Our calculus employs the ordinary notion of a sequent and cut-free, the latter implying that it satisfies the subformula property. Our calculus is sound and strongly complete to the Kripke semantics for a combination of intuitionistic and classical propositional logic, provided by Humberstone’s (1979) and del Cerro and Herizg (1996). As a corollary of the cut elimination, we establish the Craig interpolation theorem for the logic proposed by Humberstone and del Cerro and Herzig, using Maehara method. We also mention how to expand the calculus to a first-order level.
Note: This work is a joint-work with Katsuhiko Sano (Hokkaido University)
Title: Some results on doubly partially conservative sentences
Venue: Complex A 801 (via online)
Time: 15:00-
Abstract: In this talk, we present several results from [1, 2] concerning variants of Solovay’s theorem on the existence of doubly partially conservative sentences. Among other things, we prove that the existence of a Δ_{n+1}(PA) sentence that is doubly (Σ_n, Σ_n)-conservative over T is equivalent to the Σ_{n+1}-inconsistency of T over PA.
[1] H. Kogure and T. Kurahashi, A variety of partially conservative sentences, arXiv:2412.08208.
[2] H. Kogure and T. Kurahashi, Doubly partially conservative sentences, arXiv:2503.12373.
Title: NQC上の算術(PA)を通した論理公理の分析
Venue: Complex A 801
Time: 15:00-
Abstract: NQCを直観主義論理のpositive fragmentを持ち, 否定の公理に関して(A⇔B)→(¬A⇔¬B)を持つ述語論理とする. NQC上で展開される算術(PA)を通して, 論理の役割を分析する.
Title: On the reverse mathematics of Peano categoricity
Venue: Complex A 801
Time: 15:00-
Abstract: It is important in the foundations of mathematics that the natural number system is characterizable as a system of 0 and a successor function by second-order logic. In other words, the following Peano categoricity theorem holds: every Peano system (P,e,F) is isomorphic to the natural number system (N,0,S). In this talk, we will investigate the Peano categoricity theorem and other similar statements. We will first do reverse mathematics over RCA0, and then weaken the base theory.
Title: Fun with Model theory!
Venue: Online
Time: 15:00-
Abstract: We provide an introductory talk on Model theory of fields. The study of model companions is a fundamental issue in certain fields with operators, such as differential fields and difference fields.
The geometry of minimal types and the trichotomy problems in each setting give us profound insight, and we’ll see concrete examples of such a classification of algebraically closed fields, differentially closed fields, and difference closed fields. In particular, we focus on the examples: the Weierstrass ℘-function, the modular j-function, and the Painlevé equations.
Following those celebrated works, we observe a few directions I am currently working on. For instance, how can we possibly build a bridge from those studies to the case of positive characteristics?
Title: 部分体系WWKL_0の紹介
Venue: Complex A 801
Time: 15:00-
Abstract: 二階算術の部分体系WWKL_0を紹介します。これはWKL_0より真に弱い部分体系で、Martin-Lof randomnessとの深い関係が知られているほか、逆数学の観点からは、測度の可算加法性やVitaliの被覆定理などの、測度に関する基本的な主張とのRCA_0上での同値性が知られています。
今回は、WWKL_0を導入し、その測度論との関係やω-modelの構成について簡単に説明します。時間があれば、測度や関数列の収束に関する一般論を避けて、RCA_0上で特異積分論を扱う方法と、その課題について説明します。
Title: Modal logic in second-order arithmetic
Venue: Complex A 801
Time: 15:00-
Abstract: 逆数学は数学の諸定理を公理系との導出関係に着目して分析・分類する学問である. 逆数学で扱う数学の対象は多岐にわたり, その中にはロジック自身も含まれる. ロジックの逆数学的分析としては, S.SimpsonによるGödelの完全性定理とWKL_0のRCA_0上における同値性やT.Yamazakiによる直観主義論理のKripke強完全性定理とACA_0のRCA_0上における同値性などが知られている. 本発表では逆数学の紹介を行うとともに, 完全性定理を中心とした様相論理の諸定理の逆数学的分析について, 判明しているいくつかの結果と今後の展望について解説する.