Logic Seminar in Semester I AY 2007/2008

1. 15/08/2007, Week 1, 16.30 hrs: Organizational Meeting
   
   
2. 22/08/2007, Week 2, 15.00 hrs: Frank Stephan (joint work with Sanjay Jain)
   Learning in Friedberg Numberings
   The topic of this talk is learnability in some special numberings, such as Friedberg numberings, which contain all the recursively enumerable languages, but have simpler grammar equivalence problem compared to acceptable numberings. While every explanatorily learnable class can be learnt in some Friedberg numbering, there are finitely learnable classes which cannot be learnt finitely in Friedberg numberings. Furthermore, for Friedberg numberings, behaviourally correct learning collapses to explanatory learning. Some Friedberg numberings are so restrictive that all classes which can be explanatorily learnt in such Friedberg numberings have only finitely many infinite languages. Smilar questions are studied for several properties of learners such as consistency, conservativeness, prudence, iterativeness and non U-shaped learning. A generalization of Frieberg numberings are KE-numberings which have a K-recursive equality problem. Every vacillatorily learnable class is behaviourally correct learnable in some KE-numbering although it remains open whether this result can be extended to behaviourally correct learning itself. In general, KE-numberings have a better learnability properties than Friedberg numberings although there are still some limitations.
   
   
3. 29/08/2007, Week 3, 15:00 hrs: Wu Guohua
   Cuppable degrees and noncuppable pairs
   In this talk, we will outline the proof on the following result: There is a minimal pair a, b such that both are cuppable and no incomplete computably enumerable degree cups both of them to 0'. Several possible projects will be proposed. We will also show that the dual of Lempp's conjecture is true: Given a, b with b not above a, if a is not complete, then there is an incomplete cuppable computably enumerable degree c above b, but not above a.
   
   
4. 05/09/2007, Week 4, 15:00 hrs: Johanna Franklin
   Schnorr triviality and genericity
   The Turing degrees of Schnorr trivial reals seem to have no simple characterization. Therefore, we may examine other properties in connection with Schnorr triviality to determine the extent to which they are compatible in the Turing degrees. In this talk, we will discuss the relationship between Schnorr trviality and genericity. We find that no Schnorr trivial real is Turing equivalent to a 2-generic real. However, we also show that while no Schnorr trivial real is truth-table equivalent to a 1-generic real, such reals may be Turing equivalent.
   
   
5. 12/09/2007, Week 5, 14:00 hrs: Yang Sen
   A combinatorial principle introduced by Moore: Mapping Reflection Principle
   Mapping Reflection Principle (MRP) is a new combinatorial principle introduced by Justin T. Moore in [1]. It is a consequence of well known forcing axiom PFA. Whilemean is a tool to decide questions from PFA. All results in this talk are due to Justin T. Moore [1] and Matteo Viale [2].
   [1] Justin Tatch Moore. Set mapping reflection. Journal of Mathematical Logic, volume 5, number 1, pages 87-97, 2005.
   [2] Matteo Viale. The proper forcing axiom and the singular cardinal hypothesis. The Journal of Symbolic Logic, volume 71, number 2, pages 473-479, June 2006.
   
   
6. 19/09/2007, Week 6, 15:00 hrs: Wang Wei
   Upper Bounds of Arithmetic Turing Degrees
   In this talk I will present two theorems. They are quite technical. But what led me to these theorems is interesting. It is about recursion and degree theoretic analysis of a certain initial segment of Goedel's constructive universe. So I will talk a little on these and also the techniques and proofs of the two theorems.
   
   
7. 03/10/2007, Week 7, 15:00 hrs: Pong Wai Yan
   Homogeneous Graphs of Finite Degree
   We identify the class of infinite graphs of finite degree whose theory in the language of distance predicates admits quantifier elimination. Various notions of homogeneity processed by these graphs will be discussed. This is a joint work with Shawn Hedman.
   
   
8. 10/10/2007, Week 8, 14:00 hrs: Wu Liuzhen
   Five Element Basis for Uncountable Linear Order
   After a careful analysis in the structure of uncountable linear order, Shelah raised a conjecture that under the proper forcing axiom, five order structures including omega₁, omega₁^*, C, C^*, X are sufficient to serve as the base for uncountable linear order. Recently, J. Moore showed the conjecture is true via his new reflection principal. In my talk, I will focus on some basic linear order analysis and then sketch the proof given by Moore.
   
   
9. 17/10/2007, Week 9, 15:00 hrs: Shen Demin
   Silver's work on Singular Cardinal Problem
   This talk presents the following theorem of Silver: If k is a singular cardinal with uncountable cofinality and if the generalized continuum hypothesis holds for all cardinals l < k then the generalized continuum hypothesis also holds for k itself.
   
   
10. 24/10/2007, Week 10, 15:00 hrs: Rod Downey, Victoria University of Wellington
    Strong Jump Traceability and Variations
    This talk concerns part of the recent evolving programme devoted to understanding notions of low computational complexity and their relationship with low levels of algorithmic randomness. I will attempt to explain the "little boxes" technique.
    
    
11. 31/10/2007, Week 11, 14:00 hrs: Shi Niandong, East Stroutsburg University
    Decidable Pseudo O-minimal Stone Algebra
    In this talk, we will investigate the pseudo O-minimality of Stone algebras. We will prove that the pseudo O-minimality holds for a large class of Stone algebras. We will also prove that the theory of these Stone algebras is decidable, and the exchange principle does not hold.
    
12. 31/10/2007, Week 11, 15:00 hrs: Liu Jiang, Nanyang Technological University
    Isolation, Infima and Diamond Embeddings
    In (1993, Annals of Pure and Applied Logic, 62, 207-263), Kaddah pointed out that there are two d.c.e. degrees a; b forming a minimal pair in the d.c.e. degrees, but not in the Delta⁰₂ degrees. Kaddah's result shows that Lachlan's theorem, stating that the infima of two c.e. degrees in the c.e. degrees and in the Delta⁰₂ degrees coincide, cannot be generalized to the d.c.e. degrees.
    In this article, we apply Kaddah's idea to show that there are two d.c.e. degrees c; d such that c cups d to 0', and caps d to 0 in the d.c.e. degrees, but not in the Delta⁰₂ degrees. As a consequence, the diamond embedding {0, c, d, 0'} is different from the one first constructed by Downey in 1989. To obtain this, we will construct c.e. degrees a, b, and d.c.e. degrees c > a; d > b and a non-zero omega-c.e. degree e ≤ c, d such that (i) a; b form a minimal pair, (ii) a isolates c, and (iii) b isolates d. From this, we can have that c; d form a minimal pair in the d.c.e. degrees, and Kaddah's result follows immediately. In our construction, we apply Kaddah's original idea to make e below both c and d. Our construction allows us to separate the minimal pair argument (a meet b is 0), the splitting of 0' (c join d is 0'), and the non-minimal pair of c; d (in the Delta⁰₂ degrees), into several parts, to avoid direct conflicts that could be involved if only c; d and e are constructed. We also point out that our construction allows us to make a; b above (and hence c; d) high.
    This is a joint work with Wu Guohua.
    
    
13. 07/11/2007, Week 12, 14:00 hrs: Li Yanfang
    Martin's Axiom
    Martin's Axiom arose from the consistency problem for Souslin's Hypothesis and it relates closely with iterated forcing. Souslin's Hypothesis (SH) states that there are no "Souslin trees". The consistency proof was given by Solovay and Tennenbaum by the method of iterated forcing, i.e., they built a model of ZF in which no Souslin tree exists. After that, Martin's Axiom was introduced in the paper of Martin and Solovay, "Internal Cohen Extensions", which captures the combinatorial content of the above model and it leads to many interesting results. I will talk about the motivation of introducing this "axiom" and some of its applications.
    
    
14. 14/11/2007, Week 13, 14:00 hrs: Minh Chieu Tran
    Should the universe of sets be constructible?
    The Constructible Universe L was introduced by Goedel in 1937 as a model of ZFC+GCH. The question "V = L ?" is undecidable within ZFC. Modern set theoretic view, however, is that "not V=L". By analyzing the relationship between truth and language in mathematics, I will try to make clear the nature of undecidable questions. Based on that, I will discuss how the modern picture of set theory answers the question "V = L ?", as well as the philosophical issues involved.
    
15. 14/11/2007, Week 13, 15:00 hrs: Jin Chenyuan
    Sacks Density Theorem
    Let (R,<) be the lattice of recursively enumerable Turing degrees ordered by Turing reduction, so a < b iff the sets in the Turing degree a are Turing reducible to those in the Turing degree b but not vice versa. Sacks density theorem says that for all a and b in R with a < b there is a c in R with a < c < b.