Logic Seminar in Semester II AY 2011/2012

1. 18/01/2012, 17:00 hrs, Week 2.
   Ng Keng Meng. Jump Inversion and strong reducibilities.
   The study of strong reducibilities has been a major part of computability for a long time. As is well known, tabular reducibilies such as weak truth table (wtt-) and truth table (tt-) reduciblities place restrictions on oracle access. In recent times, truth table reducibility has become a central area of interest as it has been shown to be a natural reducibility to study in algorithmic randomness.
   Recent work by Anderson analyzing an old result of Mohrherr renewed interest in the variations of the classical jump inversion theorems, particularly their connection with the strong reducibilities. We prove that the analogs of Shoenfield's and Sacks' jump inversion results fail when considering tt- and wtt-reducibilities, and in fact they fail in more or less the strongest way that they can. One of our main results show that for any computable sequence of Δ⁰₂ sets V₀, V₁, ..., there exists a Δ⁰₂ set S truth-table above ∅' such that for every e, V_e' is not wtt-equivalent to S.
   We also examine the role of strong tabular reducibilities in the completion of pseudojump operators. We show that there is a pseudojump operator V such that V^X is Turing above X for every X, and there is no c.e. set A such that V^A is wtt-equivalent to ∅'.
   
   
2. 25/01/2012, 17:00 hrs, Week 3.
   Chinese New Year.
   
   
3. 01/02/2012, 17:00 hrs, Week 4.
   Chong Chitat. The strength of Ramsey's Theorem for Pairs.
   Abstract: We discuss the first order strength of Ramsey's Theorem foe pairs RT²₂ as well as some combinatorial principles weaker than RT²₂. We also consider SRT²₂ the stable Ramsey's Theorem for pairs and it's first order strength. We conclude with a theorem on the strength of SRT²₂ and give a very brief sketch of the proof.
   This is joint work with Ted Slaman and Yang Yue that began in July 2005.
   
   
4. 15/02/2012, 17:00 hrs, Week 6.
   Mars Yamaleev. Splitting properties and bubble pairs in n-c.e. Turing degrees.
   In the talk we will consider splitting properties of Turing degrees below 0'. 'Splitting' has two natural generalizations: 'splitting above' and 'splitting with avoiding cones'. Some of these properties are well known and have many applications in different levels of the Ershov hierarchy. We will pay attention to splitting properties in 2-c.e. degrees with avoiding cones and the corresponding sufficient conditions. Note that sometimes it's not possible to provide such a splitting (e.g., in the case of a bubble pair). A bubble pair was recently constructed by Arslanov, Kalimullin and Lempp in order to refute Downey's conjecture. However, their construction found out to be interesting and useful for other applications too. We will discuss these applications and links between splitting, bubble, and isolating properties.
   
   
5. 29/02/2012, 17:00 hrs, Week 7.
   Cheng Yong. Periodicity phenomenon on largest countable analytical set.
   The talk covers periodicity phenomenon on the existence of largest countable analytical sets under determinacy hypothesis.
   
   
6. 07/03/2012, 17:00 hrs, Week 8.
   Frank Stephan. Random Sets and Recursive Splittings.
   The starting point of this talk is the following: Given a set B, is there a random set A such that for each recursive set C either the intersection of A with C or the intersection of A with the complement of C is Turing above B? This question arises naturally from van Lambalgen's Theorem which permits to split many Martin-Loef random sets into halves which are computationally week. The affirmative answer to this question shows that some Martin-Loef random sets cannot be split into two computationally weak halves in a systematic way, but one half preserves always at least the computation power of B.
   For Schnorr randomness, a stronger result is obtained: Every high Turing degree contains a Schnorr random set A such that A is Turing equivalent to the intersection of A and B for any infinite recursive set B.
   If one looks at Turing degrees, one can show that every degree above the one of the halting problem is the join of two Turing incomplete Martin-Loef random sets.
   This is joint work with Ng Keng Meng and Andre Nies.
   
   
7. 14/03/2012, 17:00 hrs, Week 9.
   Alexander Melnikov. Computably isometric spaces.
   We say that an uncountable metric space is computably categorical if every two computable structures on this space are equivalent up to a computable isometry. Our interest is motivated by classical and recent results in computable (countable) model theory. We show that Cantor space, the Urysohn space, and every separable Hilbert space are computably categorical, but the space of continuous functions on the unit interval with the supremum metric is not. We also characterize computably categorical subspaces of Rⁿ, and give a sufficient condition for a space to be computably categorical.
   
   
8. 21/03/2012, 17:00 hrs, Week 10.
   Li Wei. Some minimal pairs in the α-r.e. degrees.
   Let α be an admissible ordinal. α is said to be refractory if p2α=gcα<tp2α. Lerman and Sacks (1972) proved there exists a minimal pairs of α-r.e. degrees if α is not refractory. This talk will be on their proof of this theorem.
   
   
9. 28/03/2012, 17:00 hrs, Week 11.
   Gao Ziyuan. Variants of Partial Learning in Inductive Inference.
   This talk reports on an ongoing investigation into several variants of partial learning in inductive inference. The talk will begin by outlining the general model of partial learning, and discuss how the imposition of learning constraints, such as confidence and consistency, introduces finer gradations of learning notions. Several results demonstrating how the choice of a learner's hypothesis space affects confident partial learnability, as well as a study of the additional learning power conferred by oracles, will be presented.
   This is joint work with Frank Stephan
   
   
10. 04/04/2012, 17:00hrs, Week 12.
    Russell Miller. Computable Fields and their Algebraic Closures.
    We present recent results about computable fields F and embeddings of F into its algebraic closure. We focus on fields which are algebraic over their prime subfields. The discussion begins with a review of Rabin's Theorem, and continues with more exact computability-theoretic comparisons of the set of irreducible polynomials in F[X], the set of polynomials there with roots in F, and the different ways F can sit within computable presentations of its algebraic closure. We also examine this issue for noncomputable fields, considering the spectrum of the field F and its spectrum as a relation on the algebraic closure. The recent results presented are the work of Frolov, Kalimullin, Steiner, and the speaker, in various combinations.
    
    
11. 11/04/2012, 17:00hrs, Week 13.
    Andre Nies. Complexity of equivalence relations.
    We study the complexity of equivalence relations, and in particular isomorphism relations, in a variety of settings: from descriptive set theory via computability theory to computational complexity theory.