Logic Seminar in Semester I AY 2015/2016

• 12/08/2015, 17:00 hrs, Week 1, S17#04-05.
  Borisa Kuzeljevic. Isomorphic Substructures of Fraïssé Limits.
  We will present some results on embedding linear orders into the posets of isomorphic substructures of Fraïssé limits. For a relational structure X we denote this poset by P(X). Because each chain in a poset can be extended to a maximal one, it is enough to characterize the class M(X) of order types of all maximal chains in P(X). For example, if the structure X is either the rational line, the random k-uniform hypergraph, the random poset or some of the Henson graphs, then a linear order belongs to the class M(X) if and only if it is isomorphic to the order type of a compact set of reals whose minimum is not isolated. We will also show that our construction is applicable to any Fraïssé structure whose age satisfies the strong amalgamation property.
  This is a joint work with Milos Kurilic.
  
  
• 19/08/2015, 17:00 hrs, Week 2, S17#04-06.
  Ding Longyun. On equivalence relations generated by Schauder bases.
  In this talk, a notion of Schauder equivalence relation R^N/L is introduced, where L is a linear subspace of R^N and the unit vectors e_n form a Schauder basis of L, where each vector in R^N can be written as Σ_n a_n×e_n. The main theorem shows that the following conditions are equivalent:
  (1) The unit vector basis is boundedly complete;
  (2) L is F_σ in R^N;
  (3) R^N/L is Borel reducible to R^N/Ɩ_∞.
  We show that a Schauder equivalence relation generalised by any basis of R^N/Ɩ₂ itself, but it is not true for bases of c₀ or Ɩ₁. Furthermore, among all Schauder equivalence relations generated by sequences in c₀, we find the minimum and the maximum elements with respect to Borel reducibility.
  We also schow that R^N/Ɩ_p is Borel reducible to R^N/J iff p≤2 where J is James' space.
  A pdf abstract is also available.
  
  
• 26/08/2015, 17:00 hrs, Week 3, S17#04-06.
  Gao Su. Borel complete sections in Bernoulli shifts.
  In this talk I will present some results about Borel complete sections in Bernoulli shifts which are proved by a forcing construction. These results reveal regularity properties of Borel complete sections for countable group actions, and at the same time rule out certain Borel constructions that turn out to be too regular to exist.
  This is joint work with Steve Jackson, Brandon Seward and Edward Krohne.
  
  
• 02/09/2015, 17:00 hrs, Week 4, S17#04-06.
  Alexander Kreuzer. On the Uniform Computational Content of Computability Theory.
  We demonstrate that the Weihrauch lattice can be used to study the uniform computational content of computability theoretic properties and theorems in one common setting. The properties that we study include diagonal non-computability, hyperimmunity, complete extensions of Peano arithmetic, 1-genericity, Martin-Löf randomness and cohesiveness. The theorems that we include in our case study are the Low Basis Theorem of Jockusch and Soare, the Kleene-Post Theorem and Friedman's Jump Inversion Theorem. It turns out that all the aforementioned properties and many theorems in computability theory, including all theorems that claim the existence of some Turing degree, have very little uniform computational content. They are all located outside of the upper cone of binary choice (also known as LLPO) and we call problems with this property indiscriminative. Since practically all theorems from classical analysis whose computational content has been classified are discriminative, our observation could yield an explanation for why theorems and results in computability theory typically have very little direct consequences in other disciplines such as analysis.
  Two notable exceptions to this are the Low Basis Theorem which is discriminative, this is perhaps why it is considered to be one of the most applicable theorems in computability theory, and the Baire category theorem (or to be precise certain formulations of it) which is an indiscriminative principle occurring in mathematical analysis. We will see that the Baire category theorem is related to 1-genericity.
  In some cases a bridge between the indiscriminative world and the discriminative world of classical mathematics can be established via a suitable residual operation and we demonstrate this in case of the cohesiveness problem, which turns out to be the quotient of two discriminative problems, namely the limit operation and the jump of Weak König's Lemma.
  This is joint work with Vasco Brattka and Matthew Hendtlass.
  
  
• 09/09/2015, 17:00 hrs, Week 5, S17#04-06.
  David Belanger. New conservation theorems for COH.
  We prove a series of conservation results for COH over various axiom systems, extending earlier results of Cholak-Jockusch-Slaman and of Chong-Slaman-Yue. Our method is new, however, and carries a number of advantages. Along the way we revisit and formalize several well-known theorems from recursion theory, including some from Post, from Friedberg and from Jockusch-Stephan.
  
  
• 16/09/2015, 17:00 hrs, Week 6, S17#04-06.
  Dilip Raghavan. Real games and strategically selective coideals, Part 1.
  A classical theorem of Mathias says that the Axiom of Determinacy for Real games (AD_R) implies that there are no tall selective coideals on omega. Farah introduced the notion of a semiselective coideal and proved in ZF that these are precisely those ideals on omega whose quotient adds a selective ultrafilter. It is unkown whether AD_R implies the non-existence of tall semiselective coideals. We introduce the notion of strategically selective coideal, and show that tall strategically selective coideals do not exist under AD_R. The Axiom of Choice implies that the notions of semiselective and strategically selective coideal coincide.
  This is joint work with Paul Larson.
  
  
• 23/09/2015, 17:00 hrs, Recess Week, S17#04-06.
  No Talk.
  
  
• 30/09/2015, 17:00 hrs, Week 7, S17#04-06.
  Chong Chi Tat. Ramsey's Theorem on Trees.
  Ramsey's theorem on trees concerns the existence of a monochromatic tree isomorphic to the full binary tree, for a given finite colouring of the latter. The existence of a monochromatic perfect tree is immediate in the system of Peano arithmetic. The interesting question is to identify the weakest system that is sufficient for it. We will give a progress report of our study.
  This is joint work with Li Wei and Wang Wei.
  
  
• 07/10/2015, 17:00 hrs, Week 8, S17#04-06.
  Dilip Raghavan. Real games and strategically selective coideals, Part 2.
  A classical theorem of Mathias says that the Axiom of Determinacy for Real games (AD_R) implies that there are no tall selective coideals on omega. Farah introduced the notion of a semiselective coideal and proved in ZF that these are precisely those ideals on omega whose quotient adds a selective ultrafilter. It is unkown whether AD_R implies the non-existence of tall semiselective coideals. We introduce the notion of strategically selective coideal, and show that tall strategically selective coideals do not exist under AD_R. The Axiom of Choice implies that the notions of semiselective and strategically selective coideal coincide.
  This talk is a continuation of the talk from 16/09/2015 and will provide more mathematical details and selected proofs.
  This is joint work with Paul Larson.
  
  
• 14/10/2015, 17:00 hrs, Week 9, S17#04-06.
  Frank Stephan. Covering the recursive sets.
  The talk gives an overview of recent work which solves two problems of Brendle, Brooke-Taylor, Ng and Nies. One construction is based on a construction of Khan and Miller from 2014, the other construction is a direct construction utilising martingales. Furthermore, the talk introduces the notions of infinitely often subuniform families and shows first results for these; these concepts also permit to get some result towards the solution of the third problem of Brendle, Brooke-Taylor, Ng and Nies.
  This talk is based on joint work with Bjørn Kjos-Hanssen and Sebastiaan A. Terwijn.
  The current version of the paper is available on the homepage of Frank Stephan and had been presented at CiE 2015; the paper of Brendle, Brooke-Taylor, Ng and Nies is on http://arxiv.org/abs/1404.2839.
  
  
• 21/10/2015, 17:00 hrs, Week 10, S17#04-06.
  Frank Stephan. The complexity of semiautomatic structures.
  This talk extends previous work on semiautomatic structures and in particular investigates complexity issues with groups and semigroups; furthermore, results from recursion theory are used to show that one specific structure is not semiautomatic while a related one can be shown to be semiautomatic.
  This is joint work with Sanjay Jain, Bakhadyr Khoussainov, Dan Teng and Siyuan Zou.
  
  
• 28/10/2015, 17:00 hrs, Week 11, S17#04-06.
  Jason Teutsch. When cryptocurrencies mine their own business.
  Bitcoin and hundreds of other cryptocurrencies employ a consensus protocol called Nakamoto consensus which reward miners for maintaining a public blockchain. In this talk, we study the security of this protocol with respect to rational miners and show how a minority of the computation power can incentivize the rest of the network to accept a blockchain of the minority's choice. By deviating from the mining protocol, a mining pool which controls at least 38.2% of the network's total computational power can, with modest financial capacity, gain mining advantage over honest mining. Such an attack creates a longer valid blockchain by forking the honest blockchain, and the attacker's blockchain need not disrupt any "legitimate" non-mining transactions present on the honest blockchain. By subverting the consensus protocol, the attacking pool can double-spend money or simply create a blockchain that pays mining rewards to the attacker's pool. We show that our attacks are easy to encode in any Nakamoto-consensus-based cryptocurrency which supports a scripting language that is sufficiently expressive to encode its own mining puzzles.
  This is joint work with Sanjay Jain and Prateek Saxena.
  The current version of the paper is available from the homepage of Jason Teutsch.
  
  
• 04/11/2015, 17:00 hrs, Week 12, S17#04-06.
  Peng Cheng. The properties of d.r.e. degrees.
  In this talk, we will present some classical important properties about n-r.e. degrees, especially in the d.r.e. cases.
  We will present some main ideas about the proof in these theorems, also we will give some open problems about d.r.e. degress which we are considering.
  
  
• 11/11/2015, 17:00 hrs, Week 13, S17#04-06.
  Liu Yong. Maximal d.r.e. degrees and avoiding the upper cone.
  We will review briefly the strategy for avoiding the upper cone of a given nonrecursive r.e. set, and the strategy for building a maximal d.r.e. set. And explain how to combine these two strategies. Therefore we can build a maximal d.r.e. set avoiding the upper cone of a given nonrecursive r.e. set.
  
  
• 02/12/2015, 17:00 hrs, S17#04-06.
  Slawomir Solecki. Menger compacta as projective Fraïssé limits with emphasis on dimension one.
  In each dimension d, there exists a canonical compact, second countable space, called the d-dimensional Menger space, with certain universality and homogeneity properties. For d = 0, it is the Cantor set, for d = ∞, it is the Hilbert cube. I will concentrate on the 1-dimensional Menger space. I will prove that it is a quotient of a projective Fraïssé limit. I will describe how a property of projective Fraïssé limits coming from Logic, called the projective extension property, can be used to prove high homogeneity of the 1-dimensional Menger space.