Logic Seminar in Semester I AY 2009/2010

• 15:30 hrs: first hour tutorial;
• 16:45 hrs: second hour scientific talk.

1. 12/08/2009, Week 1
   15:30 hrs: Organizational meeting.
   
   
2. 19/08/2009, Week 2
   15:30 hrs: Frank Stephan. Tutorial Algorithmic Randomness.
   16:45 hrs: Wu Guohua. Talk Construct a high minimal pair of enumeration degrees.
   Abstract: In this talk, I will first give a brief introduction of the main results of enumeration degrees. Then I will talk on the construction of a high minimal pair of enumeration degrees, a recent result of Sorbi, Yang and Wu.
   
   
3. 26/08/2009, Week 3
   15:30 hrs: Frank Stephan. Tutorial Algorithmic Randomness.
   16:45 hrs: Wang Shenling. Talk O-minimal structures.
   Abstract: In the early 1980s, A. Pillay and C. Steinhorn introduced the notion of o-minimal structures, and explored some important properties of this well-behaved class of linearly ordered structures. L.van den Dries also noticed that many propertities of semialgebraic sets and maps could be derived from a few simple axioms, essentially the axioms defining "o-minimal structures". In this talk, I will first introduce some elementary results of o-minimal structures, and provide characterizations of o-minimal ordered groups and rings. Then I will talk on some essential results in the subject of o-minimal structures.
   
   
4. 02/09/2009, Week 4
   15:30 hrs: Frank Stephan. Tutorial Algorithmic Randomness.
   16:45 hrs: Peng Yinhe. Talk pcf theory and applications.
   Abstract: pcf(A) collect all possible cofinality of partial order of functions on A. Shelah usd it to prove many beautiful theorems, such as

           aleph_omega ^ aleph_0 <= 2 ^ aleph_0 + aleph_omega_4

   on the top of his page at http://shelah.logic.at. In the talk we may introduce some theorems and to show the idea of pcf theory.
   
   
5. 09/09/2009, Week 5
   15:30 hrs: Frank Stephan. Tutorial Algorithmic Randomness.
   16:45 hrs: Zhu Yizheng. Talk Mouse Sets.
   Abstract: A mouse set is the set of reals in a mouse. Investigation of mouse sets lie in the heart of applications of inner model theoretic ideas to descriptive set theory. In this talk I will introduce mouse sets of L, M_n, etc, which also have descriptive set theoretic meanings themselves. The ultimate goal will be discussed, including Steel-Woodin's mouse set conjecture.
   
   
6. 16/09/2009, Week 6
   15:30 hrs: Pavel Semukhin. Tutorial Computable Model Theory.
   16:45 hrs: Wu Liuzhen. Talk.
   
   
7. 30/09/2009, Week 7
   15:30 hrs: Pavel Semukhin. Tutorial Computable Model Theory.
   16:45 hrs: Zhu Huiling. Talk Playing on Boolean Algebras.
   Abstract: Motivated by games played on reals, it is natural to consider games played on Boolean algebras. Jech considered the descending chain game first. It turns out that the determinacy of the game is closely related to the distributivity of the Boolean algebra. Several other games were studied later, focusing on the relationship with some weak forms of distributivity.
   
   
8. 07/10/2009, Week 8
   15:30 hrs: Wu Guohua. Tutorial Numberings.
   16:45 hrs: Li Wei. Talk Effective versions of Cantor-Bernstein Theorem.
   
   
9. 14/10/2009, Week 9
   15:30 hrs: Wu Guohua. Tutorial Numberings.
   16:45 hrs: Chong Chitat. Talk Martin's conjecture in the projective hierarchy.
   
   
10. 21/10/2009, Week 10
    15:30 hrs: Pavel Semukhin. Tutorial Computable Model Theory.
    16:45 hrs: Shao Dongxu. Talk Introduction to AD_R.
    Abstract: AD_R is a generalization of AD and it is much stronger. In my talk I will use Wadge degrees to get a reasonable candidate for inner models of AD_R, together with some other consequences. This work is due to Solovay.
    
    
11. 28/10/2009, Week 11
    15:30 hrs: Wu Guohua. Tutorial Numberings.
    16:45 hrs: Li Yanfang. Talk A cofinal family of Borel equivalence relations.
    Abstract: Given a Borel ideal J in Polish space X, it can induce a Borel equivalence relation E_J in a canonical way, i.e., x E_J y iff symmetric difference of x and y is in J. Not every Borel equivalence relation is induced by some Borel ideal, however, by Rosendal's result, equivalence relations induced by Borel ideal are cofinal in the structure of Borel reducibility.
    
    
12. 04/11/2009, Week 12
    15:30 hrs: Pavel Semukhin. Tutorial Computable Model Theory.
    16:45 hrs: Frank Stephan. Talk Automatic Structures and Model Theory.
    Abstract: Khoussainov and Nerode posed various open questions on automatic structures and model theory. Pavel Semukhin and Frank Stephan were able to solve some of these and showed the following: (1) There are automatic structures with exactly n automatic models where n in {3,4,5,...}; these models are then also the only countable models. (2) There are automatic structures where the prime model is automatic and there are countably many further nonautomatic countable models. (3) If LOGSPACE = P then there is a aleph₁-categorical but not aleph₀-categorical theory which has countably many model of which all but the prime model are automatic. (4) There is a theory with countably many countable models including a countable prime model and countable saturated model such that the saturated model but not the prime model is automatic.
    
    
13. 11/11/2009, Week 13
    15:30 hrs: Wu Guohua. Tutorial Numberings.
    16:45 hrs: Sanjay Jain. Talk Hypothesis spaces for learning.
    In this talk we will survey some results in inductive inference showing how learnability of a class of languages may depend on the hypothesis space chosen. Additionally, optimal hypothesis spaces, using which every learnable class is learnable, is considered. We also discuss results which consider how learnability is effected if one requires learning with respect to every suitable hypothesis space.