Logic Seminar in Semester I AY 2014/2015

• 13/08/2014, 17:00 hrs, Week 1, S17#04-04.
  Frank Stephan. The complexity of verbal and pattern languages over groups.
  The talk presents the complexity of verbal languages and pattern languages of Thurston automatic groups in terms of the Chomsky hierarchy. Here the language generated by a pattern is taken as the set of representatives of all strings obtained when chosing values for the various variables. For noncommutative free groups, it is shown that the complexity of the verbal and pattern languages (in terms of level on the Chomsky hierarchy) does not depend on the Thurston automatic representation, that verbal languages cannot be context-free (unless they are either the empty word or the full group) and that pattern languages cannot be regular (unless they are either a singleton or the full group). Verbal languages and pattern languages can, however, be indexed languages. Furthermore, it is shown that in the general case, it might depend on the exactly chosen Thurston automatic representation which level a verbal language takes in the Chomsky hierarchy. There are examples of groups where, in an appropriate representation, all pattern languages are regular or context-free, respectively.
  This is joint work with Sanjay Jain and Alexei Miasnikov; the talk builds on and extends work presented at LICS 2012.
  
  
• 20/08/2014, 17:00 hrs, Week 2, S17#04-04.
  Dilip Raghavan. On embedding certain partial orders into the P-points under Tukey and RK reducibility.
  The study of the global structure of the P-points was initiated mainly by Blass in 1970s. In a paper in 1973 he asked what partially ordered sets can be embedded into the P-points under the ordering of Rudin-Keisler reducibility. This question is of most interest under some hypothesis that guarantees the existence of many P-points, such as Martin's axiom for σ-centered posets. In the 1973 paper he showed under this assumption that both ω₁ and the reals can be embedded. This result was later generalized to the coarser notion Tukey reducibility. We will prove that under Martin's axiom for σ-centered posets P(ω)/FIN can be embedded into the P-points both under Rudin-Keisler and Tukey reducibilities. Since P(ω)/FIN is universal for partial orders of size at most continuum, this a good step towards giving a complete answer to Blass' original question.
  This is joint work with Saharon Shelah.
  
  
• 27/08/2014, 17:00 hrs, Week 3, S17#04-04.
  Four talks at the Department of Mathematics within the framework of the I.C.M. Day; no logic seminar on this day. A logic-related talk at the I.C.M. Day is the following.
  Vladimir Voevodsky. Computer proof assistants - the future of mathematics.
  I will tell about the movement to create new foundations of mathematics, new common language and new commonly accepted methods of inference, to be used to express mathematics in forms that can be verified by computer proof assistants. Almost miraculously the new ideas that were required to resolve some of the outstanding problems that stalled the development of such foundations came from homotopy theory. There is now a growing new synthesis of constructive mathematics with Grothendieck style pure mathematics that can be effectively developed using existing proof assistants such as Coq.
  
  
• 03/09/2014, 17:00 hrs, Week 4, S17#04-04.
  No talk. There is the IMS-JSPS Joint Workshop in Mathematical Logic and Foundations of Mathematics; see the IMS page for talks at the IMS in that week.
  
  
• 10/09/2014, 17:00 hrs, Week 5, S17#04-04.
  Liu Yiqun. Another decomposition of c.e. degrees.
  It's known that R is a disjoint union of Prompt Simple degrees (simply as P.S. degrees) and Cappable degrees (denoted as M, namely all degrees which are parts of c.e. minimal pair or 0).
  We specify another decomposition of c.e. degrees R as (disjoint) union of P.S. degrees and the degrees of the base sets for all Slaman Triples (simply as BSLT degrees). Slaman Triple is a triple of nontrivial c.e. degrees, say (a,b,c), such that c is not strictly below b and for any c.e. W_e < a, c < b + W_e or W_e is computable. In such triple, a is defined to be the base set for Slaman triple. BSLT degree is also Cappable degree since (a,b) is a minimal pair.
  As a corollary of two decompositions, Cappable degree is also a BSLT degree. Thus, base for SLT is equivalent to Cappable as set property in Turing degree structure.
  
  
• 17/09/2014, 17:00 hrs, Week 6, S17#04-04.
  Yang Yue. On a question of Cholak and Downey.
  In a paper entitled "On the Cantor-Bendixon rank of recursively enumerable sets" (JSL 1993), Cholak and Downey showed that for every recursive ordinal &alpha and every nonrecursive r.e. degree d, there is an r.e. set of rank α and degree d. They also asked if one can generalize the result to Δ⁰₂ degrees, i.e., for every recursive ordinal α and every nonrecursive Δ⁰₂ degree d there is a Δ⁰₂ set of rank α and degree d. I will show the answer is positive.
  This is a joint work with Rod Downey and Guohua Wu.
  
  
• 24/09/2014, 17:00 hrs, Recess Week, S17#04-04.
  No Talk.
  
  
• 01/10/2014, 17:00 hrs, Week 7, S17#04-04.
  Ng Keng Meng. Constructing minimal pairs.
  We show how to use the determinacy of finite games to construct minimal pairs in the truth-table degrees.
  
  
• 08/10/2014, 17:00 hrs, Week 8, S17#04-04.
  Peng Ningning. Defining a randomness notion via another.
  In this talk, we ask whether a given randomness notion can be defined via another randomness notion. If so, How can we define it? We will formalize this questions using the concept relativization of randomness. And, give some solutions to our formalized questions.
  
  
• 15/10/2014, 17:00 hrs, Week 9, S17#04-04.
  Wu Guohua. Nonhemimaximal sets and degrees.
  In this talk, I will present a recent work with Mustafa and Yamaleev on the Turing degrees of nonhemimaximal sets, proving that the nonhemimaximal degrees are nowhere dense in the low₂ c.e. degrees. This answers a question of Downey and Stob.
  
  
• 22/10/2014, 17:00 hrs, Week 10, S17#04-04.
  Deepawali, no talk.
  
  
• 29/10/2014, 17:00 hrs, Week 11, S17#04-04.
  Chong Chi Tat. Lowness of reals in higher randomness.
  This talk will discuss the problem of the existence of nontrivial reals which are low for various notions of higher randomness, reporting on the works of several authors.
  
  
• 05/11/2014, 17:00 hrs, Week 12, S17#04-04.
  Rupert Hölzl. Universality, optimality, and randomness deficiency.
  A Martin-Löf test U is universal if it captures all sequences which are not Martin-Löf random. A test is optimal if for every Martin Löf test V there is a c ∈ ω such that ∀n ( V_n+c ⊆ U_n). We study the computational differences between universal and optimal Martin-Löf tests as well as the effects that these differences have on both the notion of layerwise computability and the Weihrauch degree of LAY, the function that produces a bound for a given Martin-Löf random sequence’s randomness deficiency. We prove several robustness results concerning the Weihrauch degree of LAY. Along similar lines we also study the principle RD, a variant of LAY outputting the precise randomness deficiency of sequences instead of only an upper bound as LAY.
  This is joint work with Paul Shafer.
  
  
• 12/11/2014, 17:00 hrs, Week 13, S17#04-04.
  Liu Yong. The strength of Carlson-Simpson Lemma VW(k,l).
  It is known that the Carlson-Simpson Lemma (VW(k,l)) is the combinatorial core of the Dual Ramsey Theorem. This talk is an introduction to the combinatorial principles VW(k,l) and OVW(k,l) from the perspective of reverse mathematics. For example, WKL₀ does not prove VW(k,l) and VW(k,l+1) is equivalent to VW(k,l).
  
  
• 19/11/2014, 17:00 hrs, S17#04-04.
  Teng Dan. Semiautomatic structures.
  Semiautomatic structures generalise automatic structures in the sense that for some of the relations and functions in the structure one only requires the derived relations and structures are automatic when all but one input are filled with constants. One can also permit that this applies to equality in the structure so that only the sets of representatives equal to a given element of the structure are regular while equality itself is not an automatic relation on the domain of representatives. It is shown that one can find semiautomatic representations for the field of rationals and also for finite algebraic field extensions of it. Furthermore, it is shown that there are semiautomatic ordered rings consisting of the integers augmented by the multiples of the square-root of a non-square integer; here the order is the same as the corresponding order on the real numbers.
  
  
• 26/11/2014, 17:30 hrs, S17#04-05.
  Kihara Takayuki. Recursion theoretic methods in topological dimension theory.
  By introducing the notion of generalized Turing degrees in any admissibly represented space (represented second-countable T₀-quotient space), we provide a refinement of Roman Pol's solution to Pavel Alexandrov's old problem in infinite dimensional topology. Formally, we show that there is an embedding of an uncountable partial ordering into the σ-embeddability ordering of weakly infinite dimensional metrizable compacta (indeed, metrizable C-compacta, also known as selectively screenable compacta Sc(O,O) in set theoretic topology).
  This is a joint work with Arno Pauly.