Date/Time : 18 Mar 2021 10:00
Venue : via Zoom
Speaker : Ko Liling,

oin Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Given a finite lattice L that can be embedded in the recursively enumerable (r.e.) Turing degrees (R,<) we do not in general know how to characterize the degrees d in R below which L can be bounded. The important characterizations known so far are of the L_7 and 1-3-1 lattices, where the former is bounded exactly by the degrees with fickleness strictly above omega and the latter is bounded exactly by the degrees containing sets of fickleness greater equal omega^omega. Given that the fickleness hierarchy collapses exactly to the powers of omega with the first few levels being 0,omega,omega^2,…,omega^omega, we want to find a lattice that characterizes the levels strictly above omega^2. We begin by exhausting the lattices L that are as “small” as L_7 and 1-3-1, but these lattices turn out to characterize the levels strictly above omega or from omega^omega onwards, if L is not already embeddable below all non-zero r.e. degrees. We even considered small infinite lattices but they too behave like L_7 or 1-3-1. We discovered three lattices besides 1-3-1 that also characterize the levels from omega^omega onwards. Our search for a candidate characterising the levels strictly above omega^2 therefore involves the lattice-theoretic problem of finding lattices that do not contain any of the four sublattices which characterise the levels from omega^omega onwards as a sublattice. Using this criterion as a heuristic we introduce the wide diamond lattice as a candidate, though we conjecture that this lattice also behaves like 1-3-1.

Add to calendar :

Date/Time : 10 Mar 2021 17:00
Venue : via Zoom
Speaker : Zekun Jia,

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract: There are a lot of theorems in Ramsey theory whose proof explicitly or implicitly uses the Axiom of Choice. This talk will focus on Ramsey’s Theorem and Open Ramsey Theorem in three models of set theory where the Axiom of Choice fails (the basic Cohen model, the basic Fraenkel model, and the ordered Mostowski model), as well as some consistency and independence results that follow. Also, the usual proof of Open Ramsey Theorem on omega given by Galvin and Prikry assumes the Axiom of Dependent Choice, and this talk will sketch an improvement on that proof to make it purely constructive. This project is advised by Zach Norwood.

Add to calendar :

Date/Time : 03 Mar 2021 17:00
Venue : via Zoom
Speaker : Desmond Lau,

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract: Martin’s Maximum^{++} and Woodin’s axiom (*) are two statements independent of, but consistent with, ZFC. I will present the common reasons they are appealing as set-theoretic axioms, before comparing the sense in which they are “maximal”. I will also run through an exposition of the recent work by Aspero and Schindler, which shows Martin’s Maximum^{++} implies (*), effectively “unifying” the statements.

Add to calendar :

Date/Time : 17 Feb 2021 17:00
Venue : via Zoom
Speaker : Xiao Ming, National University of Singapore

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract: Order dimension is a classical combinatorial object and has been widely studied by set theorists, combinatorists and computer scientists since its introduction by Dushnik and Miller in 1941. We focus on the partial orderings that are definable as a Borel subsets in a Polish space and analyze the order dimension that can be realized by Borel definable orders and show that there are some interesting behaviors that can be quite different from the classical order dimension using arbitrary realization. This is a joint work with Dilip Raghavan.

Add to calendar :

Date/Time : 03 Feb 2021 17:00
Venue : via Zoom
Speaker : Wong Tin Lok, National University of Singapore

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract: Arithmetic generally does not admit any non-trivial quantifier elimination. I will talk about one exception, where the negation of an induction axiom is included in the theory. Here the Weak Koenig’s Lemma from reverse mathematics arises as a model completion. This work is joint with Marta Fiori-Carones, Leszek Aleksander Kolodziejczyk and Keita Yokoyama.

Add to calendar :

Date/Time : 11 Nov 2020 17:00
Venue : via Zoom
Speaker : Philipp Schlicht, University of Vienna

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract:  Similarities between c.e., Pi^1_1 and Sigma^1_2 sets can be explained by representing Pi^1_1 and Sigma^1_2 sets as c.e. with respect to a transfinite enumeration procedure. This representation is important for classical results about Pi^1_1 and Sigma^1_2 sets, but also for recent results, for instance about randomness at the level of Pi^1_1 by Hjorth and Nies and structural results about Sigma^1_2 sets by Chong, Wu and Yu. In the main result, we calculate the lengths of enumerations. More precisely, we isolate a certain countable ordinal tau and show that the length of an enumeration of a Pi^1_1 or Sigma^1_2 set either equals omega_1 or is below tau, and tau is optimal. This ordinal has many other interesting characterisations. For example, we show that tau is the optimal bound for the countable ranks of wellfounded Sigma^1_2 relations, in analogy with the Kunen-Martin theorem. We will further touch on related structural problems such as calculating Borel ranks of Pi^1_1 and Sigma^1_2 Borel sets. This is joint work with Philip Welch and Merlin Carl.

Add to calendar :

Date/Time : 04 Nov 2020 17:00
Venue : via Zoom
Speaker : Andre Nies, University of Auckland

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? 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-Löf (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, evidence of an internal structure has been found. Most of these results can be phrased in the language of a mysterious  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  generalise these approaches using so-called cost functions.  They also show that each K-trivial set  is ML-equivalent to a c.e. K-trivial. Alternative reducibilities on the K-trivials will be considered near the end of the talk. One of them is related to the extreme lowness notion of strong jump traceability, and appears to be orthogonal to ML-reducibility. Very recent work with Greenberg and Turetsky provides manyfold characterisations in terms of cost functions, and random oracles.

Add to calendar :

Date/Time : 28 Oct 2020 17:00
Venue : via Zoom
Speaker : Liao Yuke, National University of Singapore

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract:  TTE-computable is one of the major definitions of computable real functions. We focus on a generalisation of TTE  and check the basic cases of computability of Julia sets. We prove quadratic polynomials with Siegel disc incomputable in TTE is still incomputable in generalisation.

Add to calendar :

Date/Time : 21 Oct 2020 17:00
Venue : via Zoom
Speaker : Rupert Hoelzl, Universitaet der Bundeswehr Muenchen

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Abstract:  We introduce Monte Carlo computability as a probabilistic concept of computability on infinite objects and prove that Monte Carlo computable functions are closed under composition. We then mutually separate the following classes of functions from each other: the class of multi-valued functions that are non-deterministically computable, that of Las Vegas computable functions, and that of Monte Carlo computable functions. We give natural examples of computational problems witnessing these separations. As a specific problem which is Monte Carlo computable but neither Las Vegas computable nor non-deterministically computable, we study the problem of sorting infinite sequences that was recently introduced by Neumann and Pauly. Their results allow us to draw conclusions about the relation between algebraic models and Monte Carlo computability.

Add to calendar :