Logic Seminar in Semester II AY 2018/2019

• Wednesday 16/01/2019, 17:00 hrs, Week 1, S17#04-06.
  Frank Stephan. Lamplighter Groups and Automata.
  This talk is about representing lamplighter groups using computational models from automata theory. It will be shown that if G can be presented such that the full group operation is recognised by a transducer, then the same is true for the lampgligher group G ≀ Z of G. Furthermore, Cayley presentations, where only multiplications with constants are recognised by transducers, are used to study generalised lampglighter groups of the form G ≀ Z^d and G ≀ F_d, where F is the free group over d generators. Additionally, Z_k ≀ Z² and Z_k ≀ F_d are shown to be Cayley tree automatic.
  This paper is joint work with Sanjay Jain, Birzhan Moldagaliyev and Tien Dat Tran. The paper is available on the speaker's homepage.
  
  
• Wednesday, 23/01/2019, 17:00 hrs, Week 2, S17#04-06.
  Yokoyama Keita. Ekeland's variational principle in reverse mathematics
  Ekeland's variational principle is a key theorem used in various areas of analysis such as continuous optimization, fixed point theory and functional analysis. It guarantees the existence of pseudo minimal solutions of optimization problems on complete metric spaces. Let f be a positive real valued continuous (or lower semi-continuous) function on a complete metric space (X,d). Then, a point x in X is said to be a pseudo minimum if f(x)=f(y)+d(x,y) implies x=y. Now, Ekeland's variational principle says that for any point a in X, there exists a pseudo minimum x such that f(x)≤f(a)-d(a,x). In reverse mathematics, it is observed that many theorems for continuous optimization problems are provable within the system of arithmetical comprehension (ACA₀), and thus most such problems have arithmetical solutions. However, this is not the case for pseudo minima. We will see that Ekeland's variational principle or its restriction to the space of continuous functions C([0,1]) are both equivalent to Π¹₁-comprehension.
  This is a joint work with Paul Shafer and David Fernandez-Duque.
  
  
• Wednesday 30/01/2019, 17:00 hrs, Week 3, S17#04-06.
  Feng Qi. On investigation of some foundational problems of economics.
  I shall present some of my toughts regarding some foundational problems of economics from mathematical logic point of view.
  
  
• Wednesday 06/02/2019, 17:00 hrs, Week 4, S17#04-06.
  No Seminar, Lunar New Year.
  
  
• Wednesday 13/02/2019, 17:00 hrs, Week 5, S17#04-06.
  Matthias Baaz. On the benefit of unsound rules: Henkin quantifiers and beyond.
  We give examples of analytic sequent calculi LK+ and LK++ that extend Gentzen's sequent calculus LK by unsound quantifier rules in such a way that (i) derivations lead only to true sequents (ii) cut free proofs may be non-elementary shorter than cut free LK proofs. This research is based on properties of Hilbert's epsilon calculus and is part of efforts to complement Hilber's stepwise concept of proof by useful global concepts.
  We use these ideas to provide analytic calculi for Henkin quantifiers and demonstrate soundness, (cut free) completeness and cut elimination. Furthermore, we show, that in the case of quantifier macros such as Henkin quantifiers for a partial semantics global calculi are the only option to preserve analyticity.
  
  
• Wednesday 20/02/2019, 17:00 hrs, Week 6, S17#04-06.
  Liu Yong. There is no strong minimal pair.
  A strong minimal pair in r.e. degrees is defined to be a pair of A and B such that they are incomparable and for any non-recursive r.e. set W below A, B+W computes A. Historically, this was a difficult problem. Slaman showed a weaker version of this, that is, B+W computes a third set C instead of A. This is called Slaman-Triple nowadays. Only recently, people showed that there is a strong minimal pair. However, we realized that there is a problem in that paper. Then we turned the problem into a proof that there is no strong minimal pair. In this talk, we will sketch the proof.
  
  
• Wednesday 06/03/2019, 17:00 hrs, Week 7, S17#04-06.
  Dilip Raghavan. A small ultrafilter number.
  It is proved to be consistent relative to a measurable cardinal that there is a uniform ultrafilter on the real numbers which is generated by fewer than the maximum possible number of sets. It is also shown to be consistent relative to a supercompact cardinal that there is a uniform ultrafilter on ℵ_ω+1 which is generated by fewer than 2^ℵ_ω+1 sets.
  This is joint work with Saharon Shelah.
  
  
• Wednesday 13/03/2019, 17:00 hrs, Week 8, S17#04-06.
  Wong Tin Lok. End extensions and subsystems of second-order arithmetic.
  Investigations in reverse mathematics reveal that most naturally occurring theorems in mathematics are equivalent to one of five arithmetic axioms nowadays known as the Big Five. These provide strong empirical evidence for the importance of the Big Five. In the talk, I will attempt to explain their importance mathematically in terms of the characteristics of their models.
  The work to be presented is joint with Stephen G. Simpson (Vanderbilt).
  
  
• Wednesday 20/03/2019, 16:00 hrs, Week 9, S17#04-06.
  David Vogan. Coxeter groups and regular polyhedra.
  Department's 90th Anniversary Lecture; no separate logic seminar.
  
  
• Wednesday 27/03/2019, 17:00 hrs, Week 10, S17#04-06.
  Ashutosh Kumar. Order dimension of Turing degrees.
  The order dimension of a partially ordered set (P, <) is the smallest size of a family F of linear orders, each extending <, such that the intersection of F is the given ordering <. Higuchi, Lempp, Raghavan and Stephan asked if the order dimension of Turing degrees could be decided in ZFC. We show that the answer is no.
  This is joint work with Dilip Raghavan.
  
  
• Wednesday 03/04/2019, 17:00 hrs, Week 11, S17#04-06.
  Wu Guohua. wtt-degrees of dre sets. In this talk, I will present some recent work on wtt-degrees of dre sets. In particular, I will give a rough idea of showing the densitiy of this structure. I will also give a few projects into this direction.
  
  
• Wednesday 10/04/2019, 17:00 hrs, Week 12, S17#04-06.
  Gao Ziyuan. Finitely distinguishable erasing pattern languages with bounded variable frequency.
  A pattern is a nonempty string made up of symbols from two disjoint sets, an alphabet Σ of constant symbols and a countably infinite set X of variables. The erasing pattern language L(π) generated by a pattern π is the set of all words over Σ obtained by replacing all the variables of π with arbitrary words over Σ, with the proviso that identical variables be replaced with the same string. In particular, patterns allow for repetitions of variable substrings, a feature known as backreferencing in programming languages. A distinguishing set for any pattern π w.r.t. a class Π of patterns containing π is a set D of words over Σ that distinguishes π from every other pattern τ in Π with L(τ) ≠ L(π), that is, D ∩ L(π) ≠ D ∩ L(τ) whenever L(τ) ≠ L(π).
  Two basic types of counting problems will be discussed: first, given any pattern π belonging to a class Π of patterns, does π have a finite distinguishing set w.r.t. Π; second, what is the minimum size of a distinguishing set for π w.r.t. Π? The latter quantity gives a measure of the information complexity of π w.r.t. Π, and it is known as the (classical) teaching dimension of π w.r.t. Π in computational learning theory. We also consider the problem of determining, for any given strict partial order < on Π (up to equivalence of patterns) and any pattern π belonging to Π, the minimum size of a distinguishing set for π w.r.t. the subclass of all τ in Π such that τ≮π; this quantity is known as the preference-based teaching dimension of π w.r.t. (Π,<). We study how the classical and preference-based teaching dimensions of patterns w.r.t. various "naturally" defined classes of patterns and strict partial orders depend on the alphabet size and the maximum number of variable repetitions in any single pattern belonging to the class.
  
  
• Wednesday 17/04/2019, 17:00 hrs, Week 13, S17#04-06.
  Liu Tianyu. Arithmetic algorithms of surreal numbers.
  The surreal number system is a totally ordered proper class containing the real numbers as well as infinite and infinitesimal numbers. A surreal number is sometimes defined as a function from an initial segment of the ordinals into the set {+,-}, usually leads to an infinite sign sequence. It can also be expressed uniquely in a normal form, as ∑_i<α ω^a_ir_i . In this talk I will present some algorithms for addition, multiplication and division on the real field. Besides, we will cover the normal form and sign sequence of surreal numbers, which will be crucial for arithmetic algorithm of surreal numbers of length strictly greater than ω. The anstract is also available as a pdf-file.
  
  
• Wednesday 24/04/2019, 17:00 hrs, S17#04-05.
  Juris Steprans. Talk cancelled.
  
  
• Wednesday 08/05/2019, 17:00 hrs, S17#04-05.
  Borisa Kuzeljevic. Matrices of countable elementary submodels.
  We present an application of the forcing notion of finite matrices whose rows consist of isomorphic countable elementary submodels of a given structure of the form H_θ. We will explain how forcing with this poset adds a Kurepa tree. If a minor modification of the poset is considered, then the tree added is actually an almost Souslin Kurepa tree.
  This is a joint work with Stevo Todorcevic.
  
  
• Thursday 11/07/2019, 16:15 hrs, S17#04-06.
  Andre Nies. The remarkable expressivity of first-order logic in profinite groups.
  Profinite groups are the inverse limits of finite groups, or equivalently, the compact totally disconnected groups. First-order logic in the signature of groups can directly talk only about their algebraic structure.
  We address the question whether a profinite group G can be determined by a single first-order sentence: is there a sentence φ such that each profinite model of φ is topologoically isomorphic to G?
  Let p be an odd prime. We show that this property holds for for the groups SL_p(Z_p) and PSL_p(Z_p) where Z_p is the ring of p-adic integers. If we restrict the reference class to the inverse limit of p-groups, we obtain many further examples, for example all groups with a bound on the dimension of closed subgroups (such as the Abelian groups Z_p).
  This is joint work with Dan Segal and Katrin Tent. The paper can be found on the internet at http://arxiv.org/abs/1907.02262.
  
  
• Tuesday 16/07/2019, 16:00 hrs, S17#04-06.
  Andre Nies. Random sequences of quantum bits.
  Martin-Loef formalised in 1966 the intuitive notion of randomness of infinite sequences of bits via algorithmic tests. In this talk, we investigate what happens if we replace classical bits by quantum bits.
  We first provide a framework to formalise infinite sequences of quantum bits as states of a suitable C^* algebra. Thereafter we introduce an analog of Martin-Loef's notion. We show that for classical bit sequences the two notions coincide. We also discuss quantum Kolmogorov complexity for finite sequences of quantum bits and its relationship to quantum Martin-Loef randomness. Finally, we consider an effective version of the Shannan-McMillan-Breiman theorem in the quantum setting.
  This is joint work with Volkher Scholz. The paper is available at http://arxiv.org./abs/1709.08422.