Logic Seminar in Semester II AY 2013/2014

• 15/01/2014, 17:00 hrs, Week 1, S17#04-05.
  Frank Stephan. Closed left-r.e. sets.
  A set A is called many-one closed left-r.e. iff every set many-one reducible to A is a left-r.e. set. Similarly one can define the notions of ascending closed left-r.e. sets, conjunctive closed left-r.e. sets, disjunctive closed left-r.e. sets and positive closed left-r.e. sets. The implications r.e. ⇒ positive closed left-r.e. ⇒ many-one closed left-r.e. ⇒ ascending closed left-r.e. ⇒ left-r.e. hold and no arrow can be reversed. Cohesive, r-cohesive and weakly 1-generic sets are not r.e. but can be many-one closed left-r.e.; furthermore there is an ascending closed left-r.e. set which is cohesive and not many-one closed left-r.e.; however every cohesive left-r.e. set is also an ascending closed left-r.e. set. The initial segment complexity of ascending closed left-r.e. sets is sublinear and can be kept near to linear; for many-one closed left-r.e. sets, one can obtain such bounds infinitely often; for conjunctive / disjunctive / positive closed left-r.e. sets the bound is logarithmic.
  This talk reports on joint work with Sanjay Jain and Jason Teutsch and has been presented at CCR 2013; the results extend those presented on 24 August 2011 in the logic seminar.
  
  
• 22/01/2014, 17:00 hrs, Week 2, S17#04-05.
  Dilip Raghavan. Constructing special almost disjoint families.
  We will survey some recent progress in constructing almost disjoint families with strong combinatorial properties. The recent constructions are based on ideas introduced by Shelah in 2011. The use of cardinal invariants plays an important role in these constructions.
  
  
• 29/01/2014, 17:00 hrs, Week 3, S17#04-05.
  Ding Longyun. Actions by Sequence Spaces.
  We investigate the Borel reducibility between equivalence relations of the form as ℝ^ω/G where G is a Borel subgroup of ℝ^ω. We are mainly interested on special cases in which G is a Borel linear subspace. This kind of research begin from Dougherty and Hjorth, while G is one of the classical sequence spaces: ℓp (p≥1) or c₀
  In this talk, we will recall some old results and introduce some new results on this topic.
  
  
• 05/02/2014, 17:00 hrs, Week 4, S17#04-05.
  Peng Ningning. The Query Complexity of Read-once Boolean Functions.
  We study the query complexity of algorithms with randomness. We consider the deterministic and the randomized decision tree complexities for Boolean functions, denoted D(f) and R(f), respectively. A major open problem is how small R(f) can be with respect to D(f). The well-known Saks-Wigderson's Conjecture is the statement that for any Boolean function f, R(f) = Ω(n^0.753), where n is the number of inputs. In this talk, we will show some positive evidences of this conjecture. We also introduce the latest results on this topic.
  
  
• 12/02/2014, 17:00 hrs, Week 5, S17#04-05.
  Chong Chi Tat. TT¹, Part II.
  In the previous part I, Li Wei gave the following talk: TT¹ says that for any colouring of the binary tree with finitely many colours, there is a homogeneous perfect subtree. Classically, TT¹ is proved by Σ₂ Induction. In this talk, we will examine TT¹ without Σ₂ Induction and show that for some recursive colouring, no homogeneous perfect subtree is below 0".
  This is now the second part of this series of talks on TT¹.
  
  
• 19/02/2014, 17:00 hrs, Week 6, S17#04-05.
  Omori Hitoshi. A dialetheic approach to Russell's paradox.
  Dialetheism is the metaphysical view which claims that there are true contradictions. And Russell's paradox together with the liar's paradox has been one of the main motivations for defending dialetheism.
  Now, the aim of the talk is twofold. First, we try to explain why the dialetheic approach to Russell's paradox might be interesting. Here, we consider some of the discussions given by Graham Priest who is the modern founder and defender of dialetheism. Second, we outline how one may take an approach towards a dialetheic set theory. To this end, we present a system of non-classical logic that replaces classical logic, and then develop a set theory based on the newly introduced system.
  
  
• 26/02/2014, 17:00 hrs, Recess Week, S17#04-05.
  No Talk.
  
  
• 05/03/2014, 17:00 hrs, Week 7, S17#04-05.
  Rupert Hölzl. Randomness in the Weihrauch degrees.
  The Weihrauch degrees are a degree structure that can be used to classify how complex it is to find solutions to certain mathematical tasks, that typically arise from classical mathematical theorems, for example in analysis. We will give an overview over recent work about interactions between these degrees and the field of algorithmic randomness. In particular we will discuss where two different models of randomized computation are located in this lattice: computation with access to a Martin-Löf random oracles and computation with a Las Vegas algorithm. We will see that these two models can be separated in the Weihrauch degree, which is in contrast to results in the related field of reverse maths, where they are known to coincide. After briefly discussing some other results relating the two subjects mentioned above, we present some open questions.
  
  
• 12/03/2014, 17:00 hrs, Week 8, S17#04-05.
  Ian Herbert. Weak Lowness Notions and Weak Reducibilities.
  The prefix-free Kolmogorov complexity of a finite binary string is the length of the shortest description of the string, according to some universal decoding machine. This gives rise to some `standard' lowness notions for reals: A is K-trivial if its initial segments have the lowest possible complexity and A is low for K if using A as an oracle does not decrease the complexity of strings by more than a constant factor. We discuss various ways of weakening these notions and the relations among these weakenings and between them and standard notions. We also discuss how these notions behave under reducibilities that are based on Kolmogorov complexity and are weaker than Turing reducibility.
  
  
• 19/03/2014, 17:00 hrs, Week 9, S17#04-05.
  Alexander Kreuzer. Non-principal ultrafilters, program extraction and higher order reverse mathematics.
  We investigate the strength of the existence of a non-principal ultrafilters over fragments of higher order arithmetic.
  Let (U) be the statement that a non-principal ultrafilter on N exists and let ACA₀^w be the higher order extension of ACA₀ (arithmetical comprehension).
  We show that ACA₀^w is Π¹₂-conservative over ACA₀^w and thus ACA₀^w+(U) is conservative over PA.
  Moreover, we provide a program extraction method and show that from a proof that a strictly Π¹₂ statement ∀ f ∃ g [A_qf(f,g)] is in ACA₀^w+(U), one can extract a realizing term in Gödel's system T. This means that one can extract a term t, such that ∀ f [A_qf(f,t(f))].
  
  
• 26/03/2014, 17:00 hrs, Week 10, S17#04-05.
  Massoud Pourmahdian. Some generalizations of metric model theory.
  In this talk, first of all, I will explain how to generalize metric theory to get a new logic, called ultrametric logic. Secondly, I will explain how to extend the notion of metric structures so that the uniformizable structures are included.
  
  
• 02/04/2014, 17:00 hrs, Week 11, S17#04-05.
  Liu Yiqun. IΣ₃ and Universal Cupping degrees In this talk, we use the typical 0'''-Injury method to re-tackle the Universal Cupping degree theorem which asserts there exists a ω-c.e. degree d < 0' such that for any nonzero c.e. w, the join of w and d is 0'. Based on this, we claim P- + IΣ₃ proves the existence of the universal cupping degree.
  
  
• 09/04/2014, 17:00 hrs, Week 12, S17#04-05.
  Wu Guohua. On a theorem of Seetapun.
  In this talk, we will consider local noncappability property of recursively enumerable degrees, which was proposed by Seetapun in his thesis in 1991. We will give an improvement of this theorem, which will have several known results as direct corollaries. This talk is based on joint work with Frank Stephan.
  
  
• 16/04/2014, 17:00 hrs, Week 13, S17#04-05.
  Bakhadyr Khoussainov. Algorithmically random algebraic structures.
  In this talk we introduce the concept of algorithmically random algebraic structure. In particular, we construct algorithmically random structures in the classes of graphs, trees, universal algebras, and monoids. We prove that there exist computably enumerable algorithmically random trees. We also build algorithmically random universal algebras and graphs computable in the halting set.