Fudan Logic Seminar 2019

December 15

Wei Wang 王玮, Sun Yat-Sen University

Time: 9:30 - 11:30. Location: HGW2403. Slides

Non-standard models of arithmetic and their standard systems

PA is the first order fragment of Peano's axiomatization of the natural numbers. The natural numbers, N, is called the standard model of PA. But by compactness theorem in first order logic, there are also models of PA different from N, which are called non-standard models of arithmetic. There have been many fascinating stories about non-standard models, some of them are about the information of N coded in such models, wrapped as structures called standard systems. I shall try to present this talk as an introductory tour to standard systems, an incomplete narration of the history, and also a tutorial to related techniques.

November 15

Yue Yang 杨跃, National University of Singapore

Time: 9:30 - 11:30. Location: HGW2403.

Ramsey's Theorem on Trees and Reverse Mathematics

Ramsey's Theorem for Pairs (RT$^2_2$) has been studied intensively in reverse mathematics. The first part of the talk is to introduce the background of reverse mathematics and RT$^2_2$. With the recent result by Monin and Patey, which separates the stable version SRT$^2_2$ and RT$^2_2$, most of the major problems related to RT$^2_2$ have been solved.
The second part of the talk will be on Ramsey's Theorem on trees. Let TT$^2_k$ denote the combinatorial principle stating that every $k$-coloring of pairs of compatible nodes on the full binary tree has a homogeneous solution, i.e.~an infinite perfect tree in which all pairs of compatible nodes have the same color. We show that over the base system $\mathsf{RCA}_0$, TT$^2_k$ doe not imply weak König's lemma. This is joint work with Chitat Chong, Li Wei and Liu Lu. Liu Lu's techniques, used in his proof of RT$^2_2$ does not imply (a weaker version of) weak König's lemma, played a major role here.

October 13

Lu Liu 刘路, Central South University

Time: 9:30 - 12:00. Location: HGW2403. Slides

可计算性理论的组合数学推论

我们介绍Joe Miller与Solomon提出的问题“是否任何有穷0-1序列的2-染色都存在可计算的VWI解”（目前尚未解决）。我们证明该问题与一个Ramsey型组合数学问题等价。
We introduce an open question raised by Joe Miller and Solomon: Does every 2-coloring of finite length 0-1 sequences admit a computable VWI solution. We show that this question is equivalent to a Ramsey type combinatorial question.

September 27

Liang Yu 喻良, Nanjing University

Time: 14:30 - 18:00. Location: HGW2401. Slides

算法随机性理论：它的哲学和数学方面

历史上人们从各种不同的观点出发给出过随机性的不同定义。我们将简要地回顾这些随机性定义。然后我们将介绍算法随机性理论的一些介于数学和哲学之间的一些结论。即这一理论是怎样从信息论上将混沌和有序区分开的。最后我们介绍这一理论可能的对于数学其它分支例如数论，分析的应用。

May 15

Jinhe Ye 叶谨赫, University of Notre Dame

Time: 9:55 - 12:30. Location: H6205.

The Lascar group as a fundamental group

In this talk, we will discuss how the Lascar galois group of a first-order theory, T, can be naturally identified as the fundamental group of the classifying space associated to the category of models, Mod(T). We will then discuss some examples illustrating how tools from algebraic topology can be used to compute the Lascar group of a theory. We will also talk about generalizations to the context of AECs and questions concerning their higher homotopy. This is joint work with Tim Campion and Greg Cousins.

May 10

Yong Liu 刘勇, Nanyang Technological University

Time: 14:00 - 18:00. Location: HGW2403. Slides

An introduction to priority arguments

Priority argument plays an important role in studying Turing degrees, especially those which are below K, the halting problem. With this method, many interesting properties about Turing degrees are revealed. For example, Friedberg-Muchnik Theorem shows that there are Turing incomparable r.e. degrees; Sacks Splitting Theorem shows that r.e. degrees are downward dense; Sacks Density theorem shows that r.e. degrees are dense. Besides theorems about r.e. degrees, we also have the d.r.e. splitting theorem and d.r.e. non-Density Theorem using this method. In this talk, we will introduce the priority argument and select some theorems to discuss.

April 12

Cheng Peng 彭程, Nankai University

Time: 14:00 - 18:00. Location: HGW2403. Slides

An introduction to infinite time decidable equivalence relation theory

Infinite time Turing machines were first studied and introduced by Hamkins, Kidder and Lewis. With infinite time Turing machines, we have infinitary analogues of classical concepts. An infinite time analogue of Borel equivalence relation theory is the theory of equivalence relations that are decidable by an infinite time Turing machine, i.e., the Borel reductions are replaced by the infinite time computable reducibility. This approach retains much of the Borel analysis and results, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel. In this talk, we will introduce the basic idea of infinite time decidable equivalence relations and some interesting questions in this area.

March 8

Junhua Yu 俞珺华, Tsinghua University

Time: 14:00 - 18:00. Location: HGW2403. Slides

Proof theory of instantial neighborhood logic

Instantial neighborhood logic (INL) is classical propositional logic enriched by a two-sorted operator $\Box$. In a neighborhood model, a formula like $\Box(\alpha_1,\ldots,\alpha_j;\alpha_0)$ (for an arbitrary natural number $j$) means that, the current point has a neighborhood in which $\alpha_0$ universally holds and none of $\alpha_1,\ldots ,\alpha_j$ universally fails. Setting $j = 0$, it reduces to the known `monotone neighborhood logic'. This talk starts from INL's semantics, which naturally leads to its tableau system. Turning the tableau up-side-down, a hyper-sequent calculus arises, and with some indexical care, so does a (regular) sequent calculus G3inl. We conclude the talk by showing how a splitting version of G3inl helps in proving INL's Lyndon interpolation property constructively.

January 11, 14

Will Johnson, Fudan University

Time: 14:00 - 16:00. Location: HGW2403.

$dp$-minimal fields I and II

The class of NIP theories generalizes the class of stable theories.  On NIP structures, there is a well-behaved cardinal-valued rank on type-definable sets, known as "$dp$-rank."  Structures of $dp$-rank 1 are called "$dp$-minimal." The class of $dp$-minimal structures includes the well-studied classes of strongly minimal and $o$-minimal structures, as well as several theories of valued fields including the $p$-adics.  In the first talk, we review the basic theory of NIP, VC-minimality, and $dp$-rank, explaining why {strong, $o$-, VC-}minimality implies $dp$-minimality implies NIP.  We also review some of the useful machinery available in NIP theories, namely $G^{00}$, honest definitions, and the subadditivity of $dp$-rank.  In the second talk, we use this machinery to construct a canonical field topology on any $dp$-minimal field.  We sketch how this leads to a classification of $dp$-minimal fields up to elementary equivalence in the language of rings.  For example, it turns out that every VC-minimal field is real closed or algebraically closed.