Logic Seminar in Semester I AY 2013/2014

• 14/08/2013, 17:00 hrs, Week 1, S17#04-05.
  Iskander Kalimullin. Families of c.e. sets and their degree spectra.
  We are studying the degrees in which a fixed family of sets is uniformly enumerable. In particular, we can point out families which are uniformly enumerable precisely in the non-superlow degrees and precisely in the non-K-trivial degrees.
  
  
• 21/08/2013, 17:00 hrs, Week 2, S17#04-05.
  Dilip Raghavan. Suslin trees and partition relations.
  We investigate the influence of the existence of Suslin trees on the ordinary partition relation, particularly at the successors singular cardinals of cofinality \omega. The results I will present are preliminary (they are only a couple of weeks old), and this is still work in progress. In the first part of the talk, I will give a quick introduction to partition calculus.
  
  
• 28/08/2013, 17:00 hrs, Week 3, S17#04-06.
  Frank Stephan. A survey on recent results on partial learning.
  A partial learner identifies an r.e. set L iff it outputs one index e of the set L infinitely often and outputs all other indices only finitely often. Osherson, Stob and Weinstein showed in 1986 that there is a partial learner which succeeds to learn every r.e. set under this learning criterion. Therefore, subsequent investigations refined the question to what happens if the partial learner has to satisfy additional constraints like consistency, conservativeness, confidence and reliability. The talk gives an overview of recent investigations on this topic.
  This talk will also be presented at the Asian Logic Conference 2013 and is based on joint work with Ziyuan Gao, Sanjay Jain, Guohua Wu, Akihiro Yamamoto and Sandra Zilles.
  
  
• 04/09/2013, 17:00 hrs, Week 4, S17#04-06.
  Ian Herbert. Kolmogorov Complexity, Lowness Notions, and Finite Self-Information.
  The (prefix-free) Kolmogorov complexity of a finite binary string is the length of the shortest description of the string, and can be thought of as a measure of that string's information content. This notion can be extended to deal with reals (i.e. infinite binary strings) either by taking the Kolmogorov complexity of finite initial segments of the real or by examining the effect on the Kolmogorov complexities of strings when using the real as an oracle. Each of these notions has an associated notion of the `minimal possible' amount of information of a real. We examine a definition of mutual information for reals due to Levin which induces its own lowness notion: having finite self-information, which is a real's mutual information with itself. The talk will examine the interactions between these lowness notions and related concepts.
  
  
• 11/09/2013, 17:15 hrs, Week 5, S17#04-06.
  Rodney G. Downey. More on Integer Valued Randoms.
  Analysing betting strategies where only integer values are allowed, perhaps for a given set F, gives an interesting variant on algorithmic randomness where category and measure intersect. We build on earlier work of Bienvenu, Stephan, and Teutsch, and study reals random in this sense, and their intricate relationship with the c.e. degrees.
  Joint work with George Barmpalias and Micheal McInerney.
  
  
• 16-20/09/2013, Asian Logic Conference 2013 in Guangzhou. Week 6. No logic seminar.
  
  
• 25/09/2013, 17:00 hrs, Recess Week, S17#04-05.
  Wong Tin Lok. The various faces of generic cuts.
  Generic objects are important in many areas of mathematical logic. Some examples are Cohen generics, Martin-Löf randoms and existentially closed models. Notions of genericity often turn out to be very robust. In the talk, I will demonstrate the robustness of genericity in the context of cuts of nonstandard models of arithmetic.
  
  
• 02/10/2013, 17:00 hrs, Week 7, S17#04-06.
  Zhang Jing. Weakly represented families in reverse mathematics.
  In this talk, we introduce the notion of a weakly represented family of sets and functions into principles in Second Order arithmetic in the context of reverse mathematics. This extends the existing notions about sequence of sets or functions which are uniformly recursive in a set of the model. With the help of weakly represented families of sets and functions, we are able to investigate a larger class of sets or functions, for example, the class of total recursive functions, the class of recursive sets etc. Specifically, we investigate the Cohesive Principle for weakly represented family (COHW) and separate COHW from Cohesive Principle COH. Further, other related principles using weakly represented family of sets/functions are also investigated, such as Domination Principle (DOM), Avoiding Principle (AVOID), Meeting Principle (MEET) and Hyperimmune Principle (HIM). Our results show that weakly represented families are a natural and robust notion to formalize principles in reverse mathematics.
  
  
• 06-09/10/2013, Algorithmic Learning Theory in Singapore. Week 8. No logic seminar.
  
  
• 16/10/2013, 17:00 hrs, Week 9, S17#04-06.
  Li Wei. TT¹ without Σ₂ Induction.
  TT¹ says that for any coloring of the binary tree with finitely many colors, there is a homogeneous perfect subtree. Classically, TT¹ is proved by Σ₂ Induction. In this talk, we will examine TT¹ without Σ₂ Induction and show that for some recursive coloring, no homogeneous perfect subtree is below 0".
  
  
• 23/10/2013, 17:00 hrs, Week 10, S17#04-06.
  Ng Keng Meng. Equivalence relations, categoricity and groups.
  Recently effective equivalence relations have been studied by various authors. Different aspects of equivalence relations have been investigated, such as the issue of completeness, reducibility and degree structures. This talk will consider the effective categoricity of equivalence relations and give an application to effective abelian group theory. This talk will be an expanded version of the talk I gave at the Asian Logic Conference.
  
  
• 30/10/2013, 17:00 hrs, Week 11, S17#04-06.
  Yang Yue. A real Turing machine.
  It is well-accepted that Turing program formalizes the concept "algorithm", as long as the domain is N. However working mathematicians deal with algorithm over R all the time. So the question for recursion theorists is: Are there "natural" computation models for real numbers? Naturalness here should at least include the following features: It should agree with the intuition of working mathematicians; the theory should be developed within arithmetic, at least not involving large cardinals nor determinacy; when restricted to natural numbers it should coincide with the standard Turing machine; it should be further generalized to computation on higher types; the computation should have steps which may or may not be a natural number, thus potentially lead to complexity theory; computation should be essentially finitary and discrete; relative computability can be defined on top of it, thus potentially lead to degree theory. No, this is not a philosophy talk.
  
  
• 06/11/2013, 17:00 hrs, Week 12, S17#04-06.
  Yang Yue. A real Turing machine.
  This is a continuation of the talk from the previous week providing more details.
  
  
• 13/11/2013, 17:00 hrs, Week 13, S17#04-06.
  Liu Yiqun. IΣ₁ and d.c.e. construction on isolation pairs.
  In this talk, I am working in any nonstandard model of P^- + IΣ₁ and construct a low d.c.e. set D which is upward isolated by the Turing complete set K in c.e. sense. I.e., K is the only c.e. set above D (which makes D proper d.c.e.).