Date/Time : 03 Feb 2022 16:00
Venue : via Zoom
Speaker : Andre Nies, The University of Auckland

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Chaitin introduced this notion in about 1975, and showed that each K-trivial is Turing below the halting set. Shortly after, Solovay proved that a K-trivial set can be noncomputable.

In the past two decades, many alternative characterisations of this class have been found: properties such as being low for K, low for Martin-Loef (ML) randomness, and a basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially, the class of noncomputable K-trivials appeared to be amorphous. More recently, an internal structure has been found. Most of these results can be phrased in the language of a reducibility on the K-trivials which is weaker than Turing’s:

A is ML-below B if each ML-random computing B also computes A.

Bienvenu, Greenberg, Kucera, Nies and Turetsky (JEMS 2016) showed that there an ML complete K-trivial set. Greenberg, Miller and Nies (JML, 2019) established a dense hierarchy of subclasses of the K-trivials based on fragments of Omega computing the set, and each such subclass is an initial segment for ML. More recent results (see arxiv.org/abs/1707.00258, updated and submitted Dec 2020) generalise these approaches using cost functions. They also show that each K-trivial set is ML-equivalent to a c.e. K-trivial.

The extreme lowness of K-trivials, far from being an obstacle, allows for methods which don’t work in a wider setting. The talk provides an overview and discusses open questions. For instance, is ML-completeness an arithmetical property of K-trivials?

This is joint work with Noam Greenberg, Joseph Miller and Dan Turetsky.

Add to calendar :

Date/Time : 26 Jan 2022 16:00
Venue : via Zoom
Speaker : Zhang Jing, National University of Singapore

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract:  Structures like trees, linear orders, partial orders, graphs have been widely studied in different areas of mathematics. The Ramsey-type theorems we will discuss usually take the following form: for any given coloring of the structure, there exists a “large sub-structure” that intersects “very few” color classes. One example is a theorem of Laver that states for any finite coloring of Q x Q (ordered pairs of rationals), there exists X, Y order isomorphic to Q, such that X x Y intersects at most 2 color classes. We will discuss the uncountable analogues of these statements and their consistency. In particular, a diagonal version of the Halpern-Lauchli theorem plays a key role. The differences between countable combinatorics and uncountable combinatorics will be highlighted.

Add to calendar :

Date/Time : 19 Jan 2022 16:00
Venue : via Zoom
Speaker : Ye Jinhe, Institut de Mathematiques de Jussieu - Paris Rive Gauche

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: Consider the class of fields with Char(K)=0 and x^4+y^4=1 has only 4 solutions in K, we show that this class has a model companion, which we denote by curve-excluding fields. Curve-excluding fields provides (counter)examples to various questions. Model theoretically, they are model complete. Field theoretically, they are not large and unbounded. Time permitting, we will discuss other aspects such as decidability of such fields.

Joint work with Will Johnson and Erik Walsberg.

Add to calendar :

Date/Time : 10 Nov 2021 16:00
Venue : via Zoom
Speaker : Manat Mustafa, Nazarbayev University

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: The talk employs the punctuality paradigm in the studies of numberings. We consider the punctual numberings, i.e. uniform computations for families of primitive recursive functions. The punctual reducibility between numberings is induced by primitive recursive functions. This approach gives rise to upper semilattices of degrees, which are called Rogers pr-semilattices. The main focus of the talk will be the structural properties of Rogers pr-semilattices. We will show several examples, which highlight further contrasts between the punctual framework and the classical theory of computable numberings.

All results are obtained in joint work with Nikolay Bazhenov and Sergei Ospichev.

Add to calendar :

Date/Time : 03 Nov 2021 16:00
Venue : via Zoom
Speaker : Wu Guohua, Nanyang Technological University

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract:   Domain theory was contrived by Dana Scott in 1969 as a theory of approximating computations. This topic was also raised by Ershov independently. In this talk, I will give a brief introduction of domain theory first, hopefully, from the beginning, and then move to the comparison of various substitutions of Hausdorff property, including sobriety, well-filteredness and monotone convergence.

Add to calendar :

Date/Time : 27 Oct 2021 17:00
Venue : via Zoom
Speaker : Mars Yamaleev, Kazan Federal University

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 83049258042
Passcode: 1729=x3+y3

Abstract: In our talk we consider relative enumerability of 2-c.e. Turing degrees in c.e. degrees below them. We focus on an old question which arises from the well-known work of Soare and Stob in 1982. The Soare-Stob theorem says that for any noncomputable low c.e. Turing degree a there exists a non-c.e. Turing degree d which is above a and relative enumerable in a. The question is whether the degree d can always be chosen as 2-c.e. We answer this question by showing that for some the degree d must be beyond 2-c.e., and discuss the ideas of proof.  Also we consider possible generalizations of this result.

All results are obtained in a joint work with Arslanov M.M. and Batyrshin I.I.

Add to calendar :

Date/Time : 20 Oct 2021 16:00
Venue : via Zoom
Speaker : Yang Yue, National University of Singapore

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract:  This is a follow up of Liao Yuke’s talk last week. I will explain in detail his result which says that there exists a recursive coloring f: N -> {0,1} such that for all infinite subset X of N, if FS(X) is homogeneous for f, then X is not recursive in 0”. Here FS(X) is the set of all finite sums of distinct elements of X. Liao Yuke’s result improved Blass, Hirst and Simpson’s theorem in 1987 (from no 0′
recursive solutions to no 0” recursive ones).

Add to calendar :

Date/Time : 13 Oct 2021 16:00
Venue : via Zoom
Speaker : Liao Yuke,

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract: Hindman’s theorem is a Ramsey type theorem related to finite sum while its proof-theoretic strength still has a huge gap. One form of the question is that if any computable coloring function would have an arithmetic solution (homogeneous set). We will construct a computable coloring functions that no Pi-3 set can be homogeneous.

Add to calendar :

Date/Time : 06 Oct 2021 16:00
Venue : via Zoom
Speaker : Chong Chi Tat, National University of Singapore

Join Zoom Meeting
https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09

Meeting ID: 830 4925 8042
Passcode: 1729=x3+y3

Abstract:   In this talk we discuss the proof-theoretic strength, from the reverse mathematics perspective, of combinatorial principles concerning the coloring of binary trees and finite products of binary trees.  Beginning with the principle TT^1, which states that every finite coloring of the full binary tree has an isomorphic monochromatic subtree, we will cover its strengthening to the existence of a strong monochromatic subtree, and to the full generalization of the latter known as the Halpern-Laeuchli Theorem.

Add to calendar :