Logic Seminar in Semester II AY 2019/2020

• Wednesday 15/01/2020, 17:00 hrs, Week 1, S17#04-06.
  Frank Stephan Measure and Conquer for Max Hamming Distance XSAT.
  This talk gives an overview of the joint work of the speaker's recent work on the Hamming XSAT problem. This problem asks for an algorithm to determine which, given an XSAT instance, determines the maximum Hamming distance between two solutions of this instance. The problem has been studied by Dahlöf in 2005 in an ISAAC paper who provided an O(1.83848ⁿ) algorithm for this problem. Later Fu, Zhu and Yin presented at JFCST 2012 an O(1.6760ⁿ) algorithm for the related Max Hamming X3SAT problem where all clauses have at most three literals. The current paper provides for the general Max Hamming XSAT problem an O(1.4983ⁿ) algorithm which applies also the technique "Measure and Conquer" in order to prove a better bound than the algorithm would give otherwise. Furthermore, the algorithm does not only provide the maximum Hamming distance of two solutions of the instance, but instead for each k between 0 and n the number of pairs of solutions which have Hamming distance k.
  The paper is available at the webpage of the conference through the link https://drops.dagstuhl.de/opus/volltexte/2019/11511/pdf/LIPIcs-ISAAC-2019-15.pdf and also from the second author's personal webpage as a ps-file (long version). This is joint work with Gordon Hoi.
  
  
• Wednesday, 22/01/2020, 17:00 hrs, Week 2, S17#04-06.
  Asger Dag Törnquist. Mad, med, mcg and other maximal combinatorial objects.
  This talk is about the descriptive set theory and infinitary combinatorics.
  In the past 6 years, a number of long-standing problems related to the definability (in the sense of effective descriptive set theory) of so-called maximal almost disjoint (mad) families, maximal eventually different (med) families, and maximal cofinitary groups (mcg) have been solved by an array of authors. I will give an overview of these developments.
  Almost disjoint families are families of infinite subsets of ω where any two distinct elements of the family intersect finitely; eventually different families are families of functions from ω to ω such that any two distinct functions in the family are eventually different; and cofinitary groups are subgroups of the group of all permutations of ω with the property that all non-identity elements of the group have at most finitely many fixed points. Maximality of such objects in all cases means maximal under inclusion (among such families).
  A classical result due to Adrian Mathias states that no analytic infinite mad families. A slew of recent results shed light on this classical result by showing that under suitable descriptive set-theoretic regularity assumptions, there are no mad families at all (and this localizes to suitable pointclasses, especially to analytic sets). In a totally unexpected twist, Horowitz and Shelah showed in 2016 that there are Borel med families and mcg, solving a long-standing problem. I will finish the talk by discussing some related, still unsolved problems, especially the following: Is there a maximal (infinite) analytic set of pairwise Turing-incomparable reals?
  
  
• Wednesday 29/01/2020, 17:00 hrs, Week 3, S17#04-06.
  Wang Wei. 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. Like in N, every element of a non-standard model M has a binary expansion, which can be regarded as the characteristic function of a subset of N. The standard system of M is the collection of all such subsets of N. It is known that standard systems of non-standard models are always Scott sets and every Scott set of cardinality less than or equal to the first uncountable cardinal is the standard system of some non-standard model. However, the general Scott set problem, whether every Scott set is the standard system of some non-standard model, remains one of the major open problems in the model theory of arithmetic. This talk will present some history of Scott set problem, as well as two constructions of non-standard models with uncountable standard systems.
  
  
• Wednesday 05/02/2020, 17:00 hrs, Week 4, S17#04-06.
  Péter Komjáth. Applications of coloring number of infinite graphs.
  After stating some of the basic results of the coloring number of infinite graphs, we show some surprising (to me, at least) applications.
  
  
• Wednesday 12/02/2020, 17:00 hrs, Week 5, S17#04-06.
  Ashutosh Kumar. On some problems in set-theoretic Eucildean Ramsey theory.
  We shall discuss some questions in Euclidean Ramsey theory where techniques from set theory have played a role.
  
  
• Wednesday 19/02/2020, 17:00 hrs, Week 6, S17#04-06.
  Thilo Weinert. Polarised partition relation for order types.
  This logic seminar is cancelled and moved to 11/03/2020 in Week 8.
  
  
• Wednesday 04/03/2020, 17:00 hrs, Week 7, S17#04-06.
  Andre Nies. Analogs of combinatorial cardinal characteristics in computability theory.
  Our basic objects are infinite sets of natural numbers. In set theory, the MAD number is the least cardinality of a maximal almost disjoint class of sets of natural numbers. The ultrafilter number is the least size of an ultrafilter base.
  We study computability theoretic analogs of these cardinals. In our approach, all the basic objects will be infinite computable sets. A class of such basic objects is encoded as the set of columns of a set R, which allows us to study the Turing complexity of the class.
  We show that each non-low oracle computes a MAD class R, give a finitary construction of a c.e. MAD set (compatible with permitting), and on the other hand show that a 1-generic below the halting problem does not compute a MAD class.
  We show that the Turing degrees of ultrafilter bases are precisely the high degrees.
  This is mostly joint work with Steffen Lempp, Joseph S. Miller and Mariya Soskova. For more details, see Section 8 in Part 3 of the Logic Blog 2019. The slides are available here.
  
  
• Wednesday 11/03/2020, 17:00 hrs, Week 8, S17#04-06.
  Thilo Weinert. Polarised partition relation for order types.
  We analyse partitions of products with two ordered factors in two classes where both factors are countable or well-ordered and at least one of them is countable. This relates the partition properties of these products to cardinal characteristics of the continuum. We build on work by Erdös, Garti, Jones, Orr, Rado, Shelah and Szemerédi. In particular, we show that a theorem of Jones extends from the natural numbers to the rational ones but consistently extends only to three further equimorphism classes of countable orderings. This is made possible by applying a thirteen-year old theorem of Orr about embedding a given order into a sum of finite orders indexed over the given order.
  This is joint work with Lukas Klausner; a technical report is available on the internet at https://arxiv.org/abs/1810.13316.
  
  
• Wednesday 18/03/2020, 17:00 hrs, Week 9, S17#04-06.
  Borisa Kuzeljevic. Cofinal types on the the second uncountable cardinal.
  Unfortunately this seminar needed to be cancelled.
  In the talk we will present some basic results about the Tukey ordering of the class of all directed sets whose cofinality is the second uncountable cardinal. We will isolate some basic directed sets in this class, and then show which of them have immediate successors in this ordering.
  This is a joint work with Stevo Todorcevic.
  
  
• Wednesday 25/03/2020, 17:00 hrs, Week 10, S17#04-06.
  No Logic Seminar.
  
  
• Wednesday 01/04/2020, 17:00 hrs, Week 11
  Zoom: https://nus-sg.zoom.us/j/138746532 and Meeting id: 138746532.
  Frank Stephan. Lower bounds for the strong n-conjecture.
  In 2009, Coen Ramaekers published at the end of his bachelor thesis the strong n-conjecture which is a generalisation of the abc-conjecture and states, for n=3,4,..., that if one takes the limit superior of the quality of n-tuples (a₁,a₂,...,a_n) of integers which are relatively coprime, have the sum zero but do not have nontrivial subsums which give 0, then this limit superior is, for each n, exactly 1. Here the quality of an n-tuple is the logarithm of the largest member (by absolute value) divided by the logarithm of the largest square-free factor of the product of all members of the tuple. This conjecture found its way onto the Wikipedia page of the related n-conjecture and is there misattributed to Vojta (at least so far as we can judge). Literature search showed that Browkin discussed in the year 2000 a similarly formulated conjecture where he did not postulate the avoidance of nontrivial subsums and Konyagin (as reported there) proved that the limit superior of the qualities in the case of an odd n greater equal 5 for that version is at least 3/2. The proof for n=5 can be transferred with some adjustments to Ramaeker's strong n-conjecture.
  The work presented here (ps-file and pdf-file) improves this bound to 5/3 for odd n ≥ 5 and to 5/4 for even n ≥ 6. For n=3 and n=4, Raemakers strong n-conjecture remains unresolved, note that n=3 is the famous case of the abc-conjecture. Furthermore, it is shown that for all n ≥ 6, one can obtain the limit superior of 5/4 and in addition obtain that the tuples witnessing this limit superior satisfy that no member is divisible by any number in a given finite subset of {3,4,5,6,...}. A similar result is shown for the Gaussian integers (= complex integers), here the limit superior 5/3 is obtained and the result holds for all n greater equal 4.
  The slides are available as ps-file and pdf-file. This is joint work of Aquinas Hobor, Rupert Hölzl, Elaine Li and Frank Stephan.
  
  
• Wednesday 08/04/2020, 17:00 hrs, Week 12.
  S17#04-06.
  Zoom: Meeting URL is https://nus-sg.zoom.us/j/786053022 and Meeting ID is 786 053 022.
  Wu Guohua. Members of thin Π⁰₁ classes and their Turing degrees.
  Martin and Pour-El constructed in 1970 a consistent r.e. theory with few r.e. extensions. Motivated by this work, Cenzer, Downey, Jockusch and Shore raised the notion of thin Π⁰₁ classes in their paper in 1993, where a Π⁰₁ class P is thin if every Π⁰₁ subclass of P is the intersection of P and some clopen set. While they put focus on various Turing degrees of members in these classes, they also constructed degrees below 0', one r.e., and one minimal, containing no members of any thin Π⁰₁ classes. In this talk, I will present basic ideas of the constructions and provide some recent progress along this topic.
  The slides are available as pdf-file.
  
  
• Wednesday 15/04/2020, 17:00 hrs, Week 13, S17#04-06.
  Dilip Raghavan.
  Talk Postponed.