Logic Seminar in Semester II AY 2022/2023

• Wednesday 11/01/2023, 17:00 hrs, Week 1.
  No Talk.
  
  
• Wednesday 18/01/2023, 17:00 hrs, Week 2, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Bakhadyr Khoussainov. Definability of algorithmically presented structures.
  We aim to describe the isomorphism types of algorithmically presented structures in the language of the first order logic. This is one of the key research topics related to the expressive power of the first order logic. The focus is on two classes of structures. The first class is the class of structures for which the positive atomic diagrams are computably enumerable. We call these structures positive structures. The second class is the class of structures for which the negative atomic diagrams are computably enumerable. We call these structures negative structures. We investigate definability of positive and negative structures by sets of sentences quantified with ∃, ∀, ∃∀ and ∀∃ using expansions of languages.
  
  
• Wednesday 25/01/2023, 17:00 hrs, Week 3, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Leonardo Mainardi. Regressive Versions of Hindman's Theorem.
  When the Canonical Ramsey's Theorem by Erdös and Rado is applied to regressive functions, one obtains the Regressive Ramsey's Theorem by Kanamori and McAloon. Taylor proved a ``canonical'' version of Hindman's Theorem, analogous to the Canonical Ramsey's Theorem. We introduce the restriction of Taylor's Canonical Hindman's Theorem to a subclass of the regressive functions, the λ-regressive functions, relative to an adequate version of min-homogeneity and prove some results about the Reverse Mathematics of this Regressive Hindman's Theorem and of natural restrictions of it. In particular we prove that the first non-trivial restriction of the principle is equivalent to Arithmetical Comprehension. We furthermore prove that this same principle reduces the well-ordering-preservation principle for base-ω exponentiation by a uniform reduction.
  The slides are available here and there is also a technical report available on http://arxiv.org/abs/2207.08554 of the paper. This is joint work with Lorenzo Carlucci.
  
  
• Wednesday 01/02/2023, 17:00 hrs, Week 4, Department of Mathematics, Room S17#05-11.
  Yu Liang. Some applications of recursion theory to set theory.
  I shall present some recent results in set theory which are based on proof methods and results from recursion theory.
  
  
• Wednesday 08/02/2023, 17:00 hrs, Week 5, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Will Johnson. NIP integral domains and Henselianity.
  Is every NIP integral domain a Henselian local ring? In this talk, I will give evidence for this conjecture, sketching why it holds in the positive characteristic case and the finite dp-rank case. I will also discuss how this ``generalized Henselianity conjecture'' is related to the standard conjectures on NIP fields and valued fields. For example, the Henselianity conjecture for NIP valued fields implies the generalized Henselianity conjecture for Noetherian NIP integral domains. Lastly I will discuss how this conjecture fits into the general problem of classifying NIP fields and NIP commutative rings. For example, it implies that NIP fields with definable field topologies must be ample/large in the sense of Pop, and NIP commutative rings must be finite products of Henselian local rings.
  
  
• Wednesday 15/02/2023, 17:00 hrs, Week 6, Department of Mathematics, Room S17#05-11.
  David Belanger. A system of functionals-of-finite-type for BSigma_n models.
  We present a system of functionals that can serve as Skolem functions, so that any arithmetical formula can be rewritten in terms of them, in a model of BSigma_n + not ISigma_n. A distinguishing feature of our construction is that each functional is coded as a natural number within the model, and there is an upper bound on the codes. The method has a number of interesting applications.
  This is joint work with Chong, Li, Wong, and Yang.
  
  
• Wednesday 01/03/2023, 17:00 hrs, Week 7, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Linus Richter. Co-analytic counterexamples to Marstrand's Projection Theorem.
  A recent "point-to-set principle" of Jack Lutz and Neil Lutz characterises the Hausdorff dimension of any subset of Euclidean space in terms of the Kolmogorov complexity of its individual points. Sets with particular fractal properties can now be constructed point-by-point, by coding "enough" information into each point, bit-by-bit. After introducing the point-to-set principle, I will present a new result in fractal geometry: under V=L (the axiom of constructiblity), I will outline the construction of co-analytic sets of Euclidean space which fail Marstrand's Projection Theorem, a classical result in fractal geometry concerning the dimension of orthogonal projections of analytic plane sets onto lines.
  
  
• Wednesday 08/03/2023, 17:00 hrs, Week 8, Department of Mathematics, Room S17#05-11.
  Chong Chi Tat. Proof-theoreitic strength of the Halpern-Läuchli Theorem.
  Let T be the full infinite binary tree (i.e. the Cantor space). An infinite subtree S of T is a strong subtree if (i) S is isomorphic to T, (ii) if σ is a node in S, and σ₀,σ₁ are its immediate successors in S, then σ₀ and σ₁ have the same length in T and furthermore (iii) the intersection σ₀ ∩ σ₁ is σ.
  The Halpern-Läuchli Theorem is a theorem in combinatorial mathematics which states that for any finite number of infinite full binary trees T₁,T₂,...,T_d and any finite coloring of the d-row vectors in T₁ × T₂ × ... × T_d there exist strong subtrees S_i ⊆ T_i with i=1,2,...,d for which all d-row verctors in S₁ × S₂ × ... × S_d have the same color. This Ramsey type theorem is yet another striking demonstration of the existence of order within chaotic disorder. There is no known simple proof of this theorem in the published literature.
  In this talk we discuss the proof-theoretic strength of the Halpern-Läuchli theorem from the reverse mathematics point of view. In particular, we give a characterisation of the inductive strength of this theorem as well as its conservation strength over a base theory weaker than Σ₂-induction.
  This is joint work with Li Wei and Yang Yue.
  
  
• Wednesday 15/03/2023, 17:00 hrs, Week 9, Department of Mathematics, Room S17#05-11.
  Liu Shixiao Forcing with density requirements.
  In the first half of the talk I shall be proving the properness of Mathias forcing with lower density requirement. In the second half of the talk I shall demonstrate the difficulty in applying this method (and some other commonly used methods) to Silver forcing with lower density requirement.
  
  
• Wednesday 22/03/2023, 17:00 hrs, Week 10, Department of Mathematics, Room S17#05-11.
  Kihara Takayuki. Topos-theoretic aspect of the degrees of unsolvability.
  In this talk, we examine the topos-theoretic aspect of the degrees of (computable) unsolvability. One of the main interpretations of constructive mathematics is Kleene's realizability interpretation, which, as is well known, can be relativized by an oracle. In this sense, an oracle can be a factor that causes a change in a model of constructive mathematics.
  Let us review this observation from another point of view: there is a topos, called the effective topos, based on Kleene's realizability interpretation. And relativizing the realizability interpretation to an oracle yields a subtopos of the effective topos. Thus, the structure of oracles, i.e., the structure of the degrees of unsolvability, is expected to be closely related to the structure of the subtoposes of the effective topos. In this talk, we give a complete correspondence, in a strict sense, between the structure of the degrees of unsolvability and the structure of subtoposes of the effective topos (or its relatives).
  
  
• Wednesday 29/03/2023, 17:00 hrs, Week 11, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Xie Ruofei. Majorising the optimal c.e. supermartingale.
  In the article Highness properties close to PA-completeness, Greenberg, Miller and Nies left the following two questions open:
  (1) Is there a finite collection of functionals {Γ_i:i<N} such that for every martingale M majorizing the optimal c.e. supermartingale m, Γ_i(M) is a DNC_k function for some i<N?
  (2) Is there a uniform way to compute a DNC_k function from a martingale M majorizing m whose initial capital is bounded by 1?
  In the talk, I will try to answer these questions.
  
  
• Wednesday 05/04/2023, 17:00 hrs, Week 12, Department of Mathematics, Room S17#05-11.
  Frank Stephan. Languages given by finite automata over the unary alphabet.
  Languages over the unary alphabet have been studied in computer science for a long time. The present work investigates regular languages over the unary alphabet and one investigates the various forms of representing them by finite automata. Here three types of automata are studied:
  (a) Deterministic finite automata where the finite automaton has exactly one run per word which is accepting iff the word is in the given language.
  (b) Nondeterministic finite automata where there are choices in the states on how to procede with a run on various symbols, a word is in the language iff there is some run which is accepting.
  (c) Unambiguous finite automata which are a special case of nondeterministic finite automata and which either reject a word or which have exactly one accepting run for a word.
  The results presented are from the following three areas:
  (1) This paper improves the upper bound of the equality problem of unary nondeterministic automata from an exponential in the second root to an exponential in the third root of the number of states. This almost matches a known lower bound based on the exponential time hypothesis by Fernau and Krebs.
  (2) It is established that the standard regular operations of union, intersection, complementation and Kleene star cause either only a polynomial or a quasipolynomial blow-up. Concatenation of two n-state ufas, in worst case, causes a blow-up from n to a function with an exponent of sixth root of n. Decision problems of finite formulas using regular operations and comparing languages given by n-state unambiguous automata, in worst case, require an exponential-type of time under the Exponential Time hypothesis and this complexity goes down to quasipolynomial time in the case that the concatenation of languages is not used in the formula. Merely comparing two languages given by n-state ufas in Chrobak Normal Form is in LOGSPACE.
  (3) Starting from this research, membership of the infinite word given by a unary alphabet language in a fixed regular language of infinite words is shown to be approximately as difficult as constructing the dfa of that language from the given automaton.
  This talk is joint work with Gordon Hoi, Sanjay Jain and Christopher Tan. More details are found in the technical report on https://arxiv.org/abs/2302.06435.
  
  
• Wednesday 12/04/2023, 17:00 hrs, Week 13, Zoom 830 4925 8042, Passcode z=x3+y3, replace z as indicated above.
  Daniel Hoffmann. Model completeness of SL(2,R).
  I will present some results from my joint project with Chieu Minh Tran and Jinhe Ye. Model completeness is a weakening of quantifier elimination. The main task here is to define a field in the structure of the pure group, but in such a way that this definition transfers over some group extensions. I will recall basic facts from the model theory needed here and similar recent results in the field, then - hopefully - I will be able to sketch the idea of the proof, which is quite geometric.
  
  
• Wednesday 10/05/2023, 17:00 hrs, Department of Mathematics, Room S17#04-05.
  Jan Baars. Generalisations of a result by Gulko on spaces of continuous functions.
  Click here for an abstract and the slides of the talk.