Logic Seminar in Semester II AY 2009/2010

Talks are Wednesday afternoon in Seminar Room S17#06-11
The general scheme of the seminar is Here an overview over the topics.
  1. 13/01/2010, Week 1
    16:30 hrs: Organizational meeting.

  2. 20/01/2010, Week 2
    15:30 hrs: Frank Stephan. Tutorial Complexity theory.
    16:45 hrs: Wu Guohua. Talk Doing cupping in the Ershov Hierarchy.
    Abstract: In this talk, I will give a brief survey of cupping recursively enumerable degrees to 0' in the Ershov hierarchy. In particular, I will focus on the construction of almost universal cupping degrees (a recent joint work with Liu Jiang), and the related topics.

  3. 27/01/2010, Week 3
    15:30 hrs: Frank Stephan. Tutorial Complexity theory.
    16:45 hrs: Chong Chi Tat. Talk Π11-conservation of combinatorial principles weaker than Ramsey's Theorem for Pairs.
    Abstract: We report on recent joint work with Yang Yue and Theodore A Slaman. Arising from the earlier investigations of Cholak, Jockusch and Slaman (2001) and Hirschfeldt and Shore (2007), the relative strengths of Ramsey's Theorem for pairs with respect to combinatorial principles such as COH and CAC have been clarified and, in some cases, understood. Π11-conservation of these principles over weaker theories, however, have been restricted to strong induction schema such as Σ02. In this talk we will discuss the new ideas that lead to the proof of Π11-conservation of principles such as COH and CAC over Σ02-bounding, in the absence of Σ02-induction. It had been observed previously that this was the best possible.

  4. 03/02/2010, Week 4
    15:30 hrs: Frank Stephan. Tutorial Complexity theory.
    16:45 hrs: Fang Chengling. Talk Nonhemimaximal degrees and high/low hierarchy.
    Abstract: In the study of the structure C, the lattice of c.e. sets, an important program is the classification of the orbits under Aut(C), the automorphism group of C. Soare proved that maximal sets form an orbit in 1974; Downey and Stob proved that hemimaximal sets form an orbit in 1992, where an incomputable c.e. set H is a hemimaximal set if there is an incomputable c.e. set A disjoint from H such that the union of H and A is maximal. At the same time, Downey and Stob proved several relative results: (1) Every high degree contains a hemimaximal set; (2) There exists a nonhemimaximal degree; (3) Nonhemimaximal degree is dense in the low c.e. degrees. So any nonhemimaximal degree is not high. Downey, Lempp and Shore proved that there is a high2 nonhemimaximal degree in 1993. Downey and Stob showed that there is a low2 but not low nonhemimaximal degree. In their proof, they made use of the fact that m-topped degree is low2 but not low. In this talk, we give another approach to this result by a direct construction of low2 but not low degrees. Here, we will see that the combination of many strategies is another important part of the construction, but not a simple pile of basic strategies. Our construction provides us an easy way to understand the low2 but not low nonhemimaximal degrees.

  5. 10/02/2010, Week 5
    15:30 hrs: Frank Stephan. Tutorial Complexity theory.
    16:45 hrs: John Case. Talk A medley of three computability theory topics: 1. Machine self-reference and the theater of consciousness, 2. Learning secrets interactively, and 3. Cautious virus detection: bad news and, then, good news.
    Abstract: I will present, back to back, three 20 minute topics I hope will interest my NUS Math Logic colleagues and which are, also, typical of my research interests. The connecting thread, such as it is, pertains to machine self-reference techniques. In the first Topic I provide an elementary example and discuss what, I believe, machine self-reference has to do with the reflective component of consciousness. The second is within computational learning theory, my main research focus, and is joint work with Timo Kötzing, my most recent and 14th finished Ph.D. student. The third is a theoretical exploration of an unpleasant kind of computer virus and is joint work with Samuel E. Moelius, my 13th finished Ph.D. student. I'll argue (with theorems) that this kind of virus is, happily, not likely to be found in the real world. Some of the theorems of the 2nd and 3rd topic are proven (but not in my talk) by infinitary machine self-reference techniques of mine. I'll also provide a slide on these tools between Topics One and Two.

  6. 24/02/2010, Week 6
    15:30 hrs: Benjamin Miller. Talk A generalization of Silver's dichotomy theorem.
    Abstract: We will establish the generalization of Silver's dichotomy theorem to co-κ-Souslin, ω-universally Baire equivalence relations. The only prerequisite knowledge is a basic understanding of point-set topology and Baire category.
    16:45 hrs: Zhu Huiling. Talk Borel's conjecture.
    Abstract: Consider ideals on the set of reals. The ideal of Lebesgue measure zero sets contains the ideal of countable sets, and the ideal of strong measure zero sets lies between them. Borel conjectured that every set with strong measure zero is countable, which is false under the assumption of continuum hypothesis. Laver proved Borel's conjecture is consistent (with ZFC). This proof made use of iterated forcing with countable support, and initiated the study of Axiom A forcing and proper forcing. In the talk, I'll show an alternative proof of consistency of Borel's conjucture (by Baumgartner).

  7. 03/03/2010, Week 7
    15:30 hrs: Yang Yue. Tutorial Cut elimination and applications.
    16:45 hrs: Shao Dongxu. Talk Closed Game Representation.
    Abstract: In my talk, I will first introduce some basic properties of scales, which is a very important concept in descriptive set theory. Then I will proof that every set of reals admitting a closed game representation admits a scale. In the proof, there are some interesting methods to transfer scales between pointclasses using games. This work is due to Moschovakis.

  8. 10/03/2010, Week 8
    15:30 hrs: Yang Yue. Tutorial Cut elimination and applications.
    16:45 hrs: Peng Yinhe. Talk Partition relations in ZFC.
    Abstract: An r-partition of X into γ colours is a function f: [X]r → γ. The partition relations are relations between |X|, r, γ and |Y|. It all starts from Ramsey theorem which describes the countable case. When |X| is countable, the relations are easy and clear, but when |X| becomes larger, the relations will be complicated and interesting.

  9. 17/03/2010, Week 9
    15:30 hrs: Yang Yue. Tutorial Cut elimination and applications.
    16:45 hrs: Li Wei. Talk Infinite chains and antichains in computable partial orderings.
    Abstract: For an infinite partial ordering, it has either an infinite chain or an infinite antichain. In this talk, we will discuss some results about computable partial ordering on N by Herrmann. Firstly, it will be shown that every computable partial ordering has either a Δ2 chain or a Π2 antichain. In the second part of the talk, we will prove it is the best estimation by constructing a computable partial ordering without any Δ2 chain or Δ2 antichain.

  10. 24/03/2010, Week 10
    15:30 hrs: Shi Xianghui. Tutorial Posner-Robinson type theorems.
    16:45 hrs: Li Yanfang. Talk Bqo theory and Fraisse's conjecture.
    Abstract: Fraisse's conjecture about countable linear ordered set is the set of all countable linearly ordered sets contains no infinite descending sequence and no infinite antichain. Laver proved this conjecure is true using better quasiordering theory (Bqo theory). I will give some introduction of bqo theory and a sketch of Laver's proof.

  11. 31/03/2010, Week 11
    15:30 hrs: Shi Xianghui. Tutorial Posner-Robinson type theorems.
    16:45 hrs: Cheng Yong. Talk Borel determinacy and its metamathematics.
    Abstract: Topic in this talk is Harvey Friedman's result on Borel Determinacy (BD): ZC can not prove BD. We will introduce the problem, background and a general picture of the proof. Also we will have a quick review of Martin's proof of BD in ZFC and some metamathematical property of BD will be discussed.

  12. 07/04/2010, Week 12
    15:30 hrs: Shi Xianghui. Tutorial Posner-Robinson type theorems.
    16:45 hrs: Frank Stephan. Talk Learnability of co-r.e. classes.
    Abstract: Angluin gave a characterisation for the learnability of uniformly recursive classes in terms of a condition with tell-tale sets. In the present talk, it is shown that this condition can be generalised to characterise which classes of co-r.e. sets have a conservative learner. Further comparisons and relations between the learnability notions for uniformly recursive, r.e. and co-r.e. classes are given.
    This is joint work with Gao Ziyuan.

  13. 14/04/2010, Week 13
    15:30 hrs: Shi Xianghui. Tutorial Posner-Robinson type theorems.
    16:45 hrs: Wang Shenling. Talk The structure of quasi-degrees.
    Abstract: In 1944, Post asked a question: Does there exists an r.e. set which is neither recursive nor T-complete? To attack Post's Problem, a natural way is to try first with simpler versions of it and, once a solution is found for them, proceed to more difficult cases, in the hope of finally reaching the solution of the original problem.
    In this talk, First, we will follow the path of solving Post's problem to introduce some basic facts about Quasi-reducibility. Then, we will focus on some important results on the c.e. sets and Quasi-reducibility done by Downey, LaForte, and Nies in 1998. In their paper, they proved that there exists a single Turing degree containing a branching of 0 in the c.e. Q-degrees. And they also showed that the existence of nonbranching c.e. Q-degrees and the c.e. Q-degrees form a dense partial order. We will discuss their construction of nonbranching c.e. Q-degrees. Finally, we will introduce some results done by Arslanov and Omanadze recently, they proved that noncappable c.e. degree exists and properly n-c.e. Q-degrees are dense in the c.e. Q-degrees.

Talks from the last semester.