Logic Seminar in Semester I AY 2021/2022

• Wednesday 11/08/2021, 16:00 hrs, Week 1, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Frank Stephan. A survey on the structures realised by positive equivalence relations.
  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 η, 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 η. In other words, the given r.e. structure divided by η is the structure realised by η. Now questions studied by Khoussainov and his coworkers included questions like "What is the partial ordering on positive equivalence relations η,ρ where η is below ρ iff every structure in the given set of structures which is realised by η is also realised by ρ? 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.
  Slides are available as ps-file and pdf-file.
  
  
• Wednesday 18/08/2021, 16:00 hrs, Week 2, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Yu Liang. Generalizing Besicovitch-Davis theorem.
  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 Σ¹₂-sets under Martin's axiom.
  This is joint work with Peng Yinhe and Wu Liuzhen. The slides are here as pdf.
  
  
• Wednesday 25/08/2021, 16:00 hrs, Week 3, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Ng Keng Meng. Are the rationals dense?
  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.
  
  
• Wednesday 01/09/2021, 16:00 hrs, Week 4, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Rupert Hölzl. The reverse mathematics of inductive inference.
  We investigates inductive inference from the perspective of reverse mathematics. Reverse mathematics is a framework that allows gauging the proof strength of theorems and axioms in many areas of mathematics. We apply its methods to basic notions of algorithmic learning theory such as Angluin's tell-tale criterion and its variants for learning in the limit and for conservative learning, as well as to the more general scenario of partial learning. These notions are studied in the reverse mathematics context for uniformly and weakly represented families of languages. The results are stated in terms of axioms referring to induction strength and to domination of weakly represented families of functions.
  
  
• Wednesday 08/09/2021, 16:00 hrs, Week 5, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Bakhadyr Khoussainov and Frank Stephan. Parity Games - Background and Algorithms.
  Parity games are games where a marker is moved on a finite graph and each node is annotated with a natural number; the game runs forever and the largest number in an infinitely often visited node decides the winner, if it is even then player Anke wins else player Boris wins. Marcin Jurdzinski showed that this game is in UP intersected coUP and also provided the first not fully exponential algorithm for it; however, the exact time complexity remained unresolved. In 2017, Calude, Jain, Khoussainov, Li and Stephan found a quasipolynomial time algorithm which Jurdzinski and Lazic as well as Schewe and his collaborators improved to be in polynomial space as well. The talk provides the way this algorithm was found and the implications it has for the fixed-parameter-tracktability of parity games and related problems like coloured Muller games. Though now quite a number of quasipolynomial time algorithms are known and there is quite extensive research in this topic, the question on whether parity games can even be solved in polynomial time is still unresolved.
  This talk is given by Bakhadyr Khoussainov and Frank Stephan jointly also on behalf of their coauthors Cristian Calude, Sanjay Jain and Wei Li.
  
  
• Wednesday 15/09/2021, 16:00 hrs, Week 6, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Bakhadyr Khoussainov. Probability Structures.
  This talk belongs to the area of probabilistic logic semantics.
  The first contribution of this work is the introduction of probability structures. Probability structures are the algebraic structures equipped with probability functions on the domains and the atomic predicates. These structures extend type 1 probability structures introduced by Halpern and Bacchus.
  Type 1 probability structures contain probability functions on domains only. Our probability structures possess an additional statistical knowledge, - probability functions on atomic predicates.
  We present a method that builds probability spaces for the first order logic formulas and prove that our semantics is sound.
  The second contribution of this work is the introduction of smooth probability structures.
  The smooth probability structures carefully refine probability structures so that we have a better control of the probability spaces defined by first order logic formulas. For these structures we initiate the study of first order probability logic (FOPLS), investigate axiomatizability of FOPLS, and address decidability and undecidability questions of the sets of valid formulas. We also study a few algorithmic questions on probability structures.
  The work is joint with Mingyu Xiao (UESTC) and Jiamou Liu (The University of Auckland).
  
  
• Wednesday 29/09/2021, 16:00 hrs, Week 7, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  No talk.
  
  
• Wednesday 06/10/2021, 16:00 hrs, Week 8, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Chong Chitat. First-order strength of tree colorings.
  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¹, 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-Läuchli Theorem.
  
  
• Wednesday 13/10/2021, 16:00 hrs, Week 9, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Liao Yuke. Computable Coloring Without Π₃ Solution for Hindman's Theorem.
  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 Π₃ set can be homogeneous.
  
  
• Wednesday 20/10/2021, 16:00 hrs, Week 10, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Yang Yue. A recursive coloring without Δ₃ solutions for Hindman's Theorem.
  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 subsets 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).
  
  
• Wednesday 27/10/2021, 17:00 hrs, Week 11, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Mars Yamaleev. On the Shoare-Stob Theorem.
  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 a 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.
  
  
• Wednesday 03/11/2021, 16:00 hrs, Week 12, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Wu Guohua. Domains: where Scott and Ershov met without appointment.
  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.
  
  
• Wednesday 10/11/2021, 16:00 hrs, Week 13, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Manat Mustafa. Rogers semilattices of punctual numberings.
  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 N. Bazhenov and S. Ospichev.