Logic Seminar in Semester II AY 2007/2008

• 15:00-16:00 hrs tutorial (either Frank Stephan oninductive inference or Wu Guohua on Π-0-1-classes);
• 16:00-17:00 hrs scientific talk.

1. 16/01/2008, Week 1
   16.15 hrs: Organizational Meeting.
   
   
2. 23/01/2008, Week 2
   15.00 hrs: Frank Stephan. Tutorial on inductive inference.
   16.00 hrs: Yang Yue. Computability over real numbers.
   
   
3. 30/01/2008, Week 3
   15.00 hrs: Frank Stephan. Tutorial on inductive inference.
   16.00 hrs: Chong Chitat. Undecidability of the theory of α-degrees.
   We report on the joint work with Ted Slaman on the undecidability of the theory of α-degrees for admissible ordinals α. A brief account of the proof will be given.
   
   
4. 06/02/2008, Week 4
   Happy Lunar New Year!
   
   
5. 13/02/2008, Week 5
   15.00 hrs: Frank Stephan. Tutorial on inductive inference.
   16.00 hrs: Feng Qi. A new characterization of supercompactness and its applications.
   We shall give some applications of a new characterization of supercompactness.
   
   
6. 20/02/2008, Week 6
   15.00 hrs: Frank Stephan. Tutorial on inductive inference.
   16:00 hrs: Wang Shenling. Foundations of Computable Model Theory.
   Computable model theory explores the effectiveness of constructions and theorems in model theory. Some fundamental concepts are introduced in my talk, and I will focus on the effective version of some classical model theoretic results, such as the Effective Completeness Theorem and the Omitting Type Theorem.
   
   
7. 05/03/2008, Week 7
   15.00 hrs: Wu Guohua. Tutorial on Π-0-1-classes.
   16.00 hrs: Li Yanfang. Glimm-Effros Dichotomy of Borel Equivalence Relations.
   I will talk about dichotomy of arbitrary Borel equivalence relations in Polish spaces.
   
   
8. 12/03/2008, Week 8
   15.00 hrs: Wu Guohua. Tutorial on Π-0-1-classes.
   16.00 hrs: Thomas Franklin Kent. The complexity of theories of mathematical structures.
   When working with a mathematical structure, it is natural to ask how complicated the first order theory of the structure is.
   In the case of structures that can be interpreted in first order arithmetic, this is equivalent to asking if the theory is as complex as possible, namely is it as complex as first order arithmetic. Restricting our attention to the language of partial orders, {≤}, there have been many results in this direction. For example, it has been shown that the first order theory of both the Turing degrees (Simpson, 1977) and the enumeration degrees (Slaman, Woodin, 1997) are as complex as second order arithmetic. In addition, it is known that the theory of each of the following structures is as complex as the theory true arithmetic (Th(N, +,×)):
   1. Turing degrees of Δ-0-2 sets (Shore, 1981),
   2. Turing degrees of c.e. sets (Nies, Shore, Slaman, 1998),
   3. many-one degrees of c.e. sets (Nies, 1994),
   4. truth-table degrees of c.e. sets (Nies, Shore, 1995) and
   5. weak truth-table degrees of c.e. sets (Nies, 2001).
   The same result holds for the lattice of c.e. sets under inclusion (Harrington, Nies, 1998).
   In this talk, we outline a proof that adds the Δ-0-2-enumeration degrees to this already lengthy list, and discuss what needs to be done to show the same result for the Σ-0-2-enumeration degrees.
   
   
9. 19/03/2008, Week 9
   15.00 hrs: Wu Guohua. Tutorial on Π-0-1-classes.
   16.00 hrs: Zhu Huiling. An Introduction to Shelah's pcf theory.
   At the beginning of set theory, many people worked on Cantor's Continuum Hypothesis, which turned out to be independent of ZFC. After Easton's theorem on regular cardinals, researchers studied the power of singular cardinals. Many results were obtained by building Inner Models (after Goedel's construction of L) and by forcing (after Cohen's idea). It is amazing that some theorems can even be proofed within ZFC, such as Silver's theorem. Shelah developed his pcf theory by considering the structure of ordinal functions module certain ideals. In this talk, I will introduce the basic ideas of pcf theory and try to present how it works to give a nice theorem in cardinal arithmetic.
   
   
10. 26/03/2008, Week 10.
    No seminar.
    
    
11. 02/04/2008, Week 11.
    No seminar.
    
    
12. 09/04/2008, Week 12
    15.00 hrs: Wu Guohua. Tutorial on Π-0-1-classes.
    16.00 hrs: Jin Chenyuan. Recursive Unsolvability and Second-Order Arithmetic.
    In the talk, I will introduce a famous theorem, first published in Annals of Mathematics, by S. G. Simpson in 1977, which shows that the first-order theory of the degrees of the recursive unsolvability is recursively isomorphic to the truth set of second-order arithmetic.
    
    
13. 16/04/2008, Week 13
    15.00 hrs: Liu Jiang. Infima and Branching of c.e. truth table degrees.
    We will first see that every truth table degree is branching (J. Mohrherr 1984) and, every incomplete c.e. truth table degree is branching in c.e. truth table degrees (P. Fejer and R. Shore 1999). Second, we consider the infima of c.e. truth table degrees (P. Fejer and R. Shore 1988).
    16.00 hrs: Shen Demin. Determinancy axioms and large cardinals.
    
    
14. 23/04/2008 - This time in Mathematics Conference Room.
    15:00 hrs: Noam Greenberg. The upward closure of a thin Π-0-1 class.
    In a paper with Joe Miller and Rod Downey, we showed that there is a perfect, thin effectively closed set (aka Π-0-1 class) whose upward closure in the Turing degrees is co-null. This answers a question about the Medvedev (weak) degrees of such classes. I will review this topic, which relates measure theory, computability and randomness. In particular I will discuss the "measure risking" method developed by Paris and Kurtz.
    16:00 hrs: Yu Liang. On Martin's proof of a conjecture of Friedman.
    In the 1970's Friedman raised a conjecture whether every uncountable hyperarithemtic set has a member of each hyperdegree ≥ O, the hyperdegree of Kleene's O. Martin gave a positive answer to this conjecture by a very tricky coding argument. We will discuss his proof and show how his argument can be changed to be a full approximation one.
    
    
15. 09/07/2008 - Colloquium Room B (S14#04-09).
    14:00 hrs: Jan Reimann. It is often pointed out that Martin-Loef randomness is an adequate formulation of randomness since it is robust with respect to different approaches to randomness: measure-theoretic typicality, unpredictability, incompressibility. However, this robustness appears rather fragile when one extends the study beyond Lebesgue measure to geometric outer measures, in particular Hausdorff measures. We study one of the central results of geometric measure theory, Frostman's Lemma, in the effective setting. We show that it yields an unexpected dichotomy of randomness notions which does not appear in the Lebesgue case. We further discuss how various characterizations of Hausdorff dimension give rise to an apparently linear hierarchy of randomness notions, and how these in turn can be used to derive results about computational properties of Martin-Loef random reals.
    
    
16. 16/07/2008 - Colloquium Room B (S14#04-09).
    14:00 hrs: Daisuke Ikegami. Forcing absoluteness and regularity properties.
    There is a close connection between forcing absolutenss and regularity properties, e.g., Sigma-1-3 Cohen forcing absoluteness holds if and only if every Delta-1-2 set of reals has the Baire property. It is known that the same kind of phenomena occur for random forcing and Lebesgue measurability, Mathias forcing and completely Ramseyness, Sacks forcing and Bernstein property etc. In this talk, I will introduce a class of forcing notions from which we can define the corresponding regularity properties and prove the equivalence as above for each forcing in the class in a uniform way. This class contains all the practical forcing notions connected to regularity properties and this result implies the unknown equivalence for some forcings (e.g. Silver forcing and Miller forcing). I will also talk about the connection between the regularity properties I define and the P-Baireness for a forcing P, which is essentially introduced in the paper "Universally Baire Sets of Reals" by Feng, Magidor and Woodin. If time permits, I will discuss some open problems in this topic.
    
    
17. 23/07/2008 - Colloquium Room B (S14#04-09).
    13:00 hrs: Keng Meng Ng. Traceability of the Jump and its Connection to Algorithmic Randomness.
    In this talk I will discuss various notions on the traceability of a set. Traceability allows us to obtain different guesses for the given set in some effective manner. Sets which are traceable also exhibit lowness properties, both in the classical sense and in connection with algorithmic randomness. In particular I will consider the interesting case of the jump traceable sets. This notion has been shown recently to be intricately linked with the K-trivial reals, which are reals exhibiting anti-random properties. I will also introduce a very strong variant of jump traceability, called the hyper jump traceable sets. These sets form the first known subclass of the K-trivial reals having no promptly simple members. Some other surprising properties of this class is also discussed.