Logic Seminar in Semester I AY 2017/2018

• Wednesday 16/08/2017, 17:00 hrs, Week 1, S17#04-04.
  No Talk, IMS Programme at this Time.
  
  
• Wednesday 23/08/2017, 17:00 hrs, Week 2, S17#04-04.
  No Talk, IMS Programme at this Time.
  
  
• Wednesday 30/08/2017, 17:00 hrs, Week 3, S17#04-04.
  No Talk, IMS Programme at this Time.
  
  
• Wednesday 06/09/2017, 17:00 hrs, Week 4, S17#04-04.
  No Talk, IMS Programme at this Time.
  
  
• Wednesday 13/09/2017, 17:00 hrs, Week 5, S17#04-04.
  No Talk, IMS Programme at this Time.
  
  
• Wednesday 20/09/2017, 17:00 hrs, Week 6, S17#04-04.
  No Talk.
  
  
• Wednesday 04/10/2017, 17:00 hrs, Week 7, S17#04-04.
  No Talk.
  
  
• Wednesday 11/10/2017, 17:00 hrs, Week 8, S17#04-04.
  Gao Ziyuan. Erasing pattern languages distinguishable by a finite number of strings.
  Pattern languages have been an object of study in various subfields of computer science for decades. We introduce and study a decision problem on patterns called the finite distinguishability problem: given a pattern π, are there finite sets T⁺ of positive and T^- of negative example string such that the only pattern language containing all positive example strings and no negative example strings is the one generated by π? This problem is related to the complexity of teacher-directed learning, as studied in computational learning theory, as well as to the long-standing open question whether the equivalence of two patterns is decidable. We show that finite distinguishability is decidable if the underlying alphabet is of size other than 2 or 3, and provide a number of related results, such as (i) partial solutions for alphabet sizes 2 and 3, and (ii) decidability proofs for variants of the problem for special subclasses of patterns, namely, regular, 1-variable, and non-cross patterns. For the same subclasses, we further determine the values of two complexity parameters in teacher-directed learning, namely the teaching dimension and the recursive teaching dimension.
  
  
• Wednesday 18/10/2017, 17:00 hrs, Week 9, S17#04-04.
  No talk, Deepavali.
  
  
• Wednesday 25/10/2017, 17:00 hrs, Week 10, S17#04-04.
  Yu Liang. Two basis theorems on Σ¹₂ sets.
  We prove the following two basis theorems on Σ¹₂ sets of reals:
  (1) Every non-thin Σ¹₂ set has a perfect Δ¹₂ subset if and only if there is a nonconstructible reals in the set;
  (2) Every uncountable Σ¹₂ sets of reals has an uncountable Δ¹₂ subset if and only if either every real is constructible or (ω₁)^L is countable.
  This is joint work with Chong Chi Tat and Wu Liuzhen.
  
  
• Wednesday 01/11/2017, 17:00 hrs, Week 11, S17#04-04.
  Peng Cheng. On transfinite levels of the Ershov hierarchy.
  In this talk, we first present some classical properties about the finite levels of the Ershov hierarchy, especially in the d.r.e. case. Some properties about d.r.e. sets are related to the transfinite levels of the Ershov hierarchy. We will present some results which we are considering and show the weak density theorem and nondensity theorem for transfinite levels.
  
  
• Wednesday 08/11/2017, 17:00 hrs, Week 12, S17#04-04.
  Desmond Lau. p, t and me.
  The question of whether p, the pseudointersection number, and t, the tower number, are equal had been longstanding open problem until it was proven in the affirmative by Malliaris and Shelah in 2012 in a preprint. The proof involves the study of a new class of problems called cofinality spectrum problems. Malliaris and Shelah would go on to develop their cofinality spectrum theory to solve many other model theoretic problems.
  In 2016, I gave a month-long seminar on the first main theorem of cofinality spectrum theory and how it is used to prove p = t. This talk is about the things I learned in that seminar.
  
  
• Wednesday 15/11/2017, 17:00 hrs, Week 13, S17#04-04.
  Lim Wei Quan. Complete predicative type theory.
  Russell's paradox is frequently misused to argue that every reasonable foundation for mathematics cannot have a universal type. But that is in fact false. I shall describe a new foundational system that takes seriously the philosophical cogency of a universal type, and avoids the usual paradoxes in a philosophically meaningful way. CPTT is based on 3-valued logic, but still interprets (classical) higher-order arithmetic. Also, CPTT is self-reflective, having a native meta logic. Finally, CPTT is meant to be user-friendly and yet fully formal. CPTT arose from my personal search for an alternative practical foundation for mathematics that has a 'clear' yet 'complete' ontology, and I wish to ask for feedback on it.