Date/Time : 25 Aug 2021 16:00
Venue : via Zoom
Speaker : Ng Keng Meng,

Join Zoom Meeting https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09 Meeting ID: 830 4925 8042 Passcode: 1729=x3+y3 There has been a recent revival in the interest in sub-computable mathematics. One of these approaches is to consider “primitive recursive” or punctual structures. This has led to a greater understanding in the effective content of well-known objects and proofs in classical computability theory. When considering the punctual anaologies of classical computabilitiy we often obtain strange and surprising results. I will discuss some recent work in progress in this area, focussing particularly on structural results. URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html  

Add to calendar :

Date/Time : 18 Aug 2021 16:00
Venue : via Zoom
Speaker : Yu Liang, Nanjing University

Join Zoom Meeting https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09 Meeting ID: 830 4925 8042 Passcode: 1729=x3+y3 Besicovitch-Davis theorem says that the Hausdorff dimension of every analytic set can be approximated by its closed subset. But the Besicovitch-Davis theorem fails for co-analytic sets under the assumption V=L as observed by Slaman. We prove that the theorem holds for arbitrary sets under ZF+sTD. We also prove that the theorem holds for Sigma-1-2-sets under Martin’s axiom. This is joint work with Peng Yinhe and Wu Liuzhen.

Add to calendar :

Date/Time : 11 Aug 2021 16:00
Venue : via Zoom
Speaker : Frank Stephan, National University of Singapore

Join Zoom Meeting https://nus-sg.zoom.us/j/83049258042?pwd=UWViaWNvTFUrdFdhOHJCdEVydnVkdz09 Meeting ID: 830 4925 8042 Password: 1729=x3+y3 Let a positive equivalence relation to be an r.e. equivalence relation on the set of natural numbers with infinitely many equivalence relations. Khoussainov initiated with coauthors a deep study of the following question: Given a positive equivalence relation eta, which structures from a given set of structures does this equivalence relation realise? Here realisation means that functions in the structure are recursive and relations are r.e. with the equality itself given by the equivalence relation eta. In other words, the given r.e. structure divided by eta is the structure realised by eta. Now questions studied by Khoussainov and his coworkers included questions like “What is the partial ordering on positive equivalence relations eta,rho where eta is below rho iff every structure of the given type realised by eta is also realised by rho? Besides algebraic structures and orders, it has also been studied how the learnability notions behave with respect to uniformly r.e. one-one families realised by positive equivalence relations.

Add to calendar :

Date/Time : 14 Apr 2021 17:00
Venue : via Zoom
Speaker : Karen Seidel, University of Potsdam

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? Learning from positive and negative information, so called informant, is one of the models for human and machine learning introduced by Gold. We review existing classical and recent results regarding the learning power of associated settings.

Add to calendar :

Date/Time : 07 Apr 2021 17:00
Venue : via Zoom
Speaker : Frank Stephan, National University of Singapore

Talk via Zoom: https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? In the year 2013, Keng Meng Ng, Frank Stephan, Yue Yang and Liang Yu published the paper “Computational Aspects of the Hyperimmune-free Degrees” and one of the results was given without a proof. The current talk gives the full proof of this result. In particular, the talk provides the full details of the construction of an co-r.e.\ infinite binary tree with uncountablly many branches which are all hyperimmune-free, Schnorr-trivial, jump traceable, generalised low and of minimal Turing degree. Hyperimmune-free means that every function Turing reducible to it is majorised by a recursive function. Jump traceable means that for every e one can compute an explicit bound on the number of elements which some further set also depending on e enumerates and that finite set contains the Jump value at e. Generalised low means that the jump of A is recursive in the join of A and K. A minimal Turing degree is a nonrecursive Turing degree below which is only the recursive one. Schnorr trivial means that for every f truth-table reducible to the set there is a recursive function which lists out for each input x a set of x+1 many values with one of them being f(x).

Add to calendar :

Date/Time : 31 Mar 2021 17:00
Venue : via Zoom
Speaker : Lars Kristiansen, University of Oslo

Join Zoom Meeting https://nus-sg.zoom.us/j/96860201432?pwd=cVdwZmd2clVFaEhaTmJjaGdXMFdmdz09 Meeting ID: 968 6020 1432 Password: Is P=NP? We will address the following question: Do we need, or do we not need, unbounded search in order to convert one representation of an irrational number into another representation? We will consider well known representations like Cauchy sequences, Dedekind cuts, base-2 expansions, base-10 expansions and continued fractions, and maybe a few less well-know representations.

Add to calendar :

Date/Time : 24 Mar 2021 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: While descriptive set theory studies definable sets of words of length omega, generalised descriptive set theory studies words of uncountable regular length. The talk will begin with an introduction to this field and its applications. I will then talk about how one can characterise when a definable set is small or admits a colouring with few colours with respect to an open graph. This is joint work with Dorottya Sziraki.

Add to calendar :

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 :