Jun Le Goh

Assistant Professor, 

Department of Mathematics, National University of Singapore. 

Title of the talk:  Interior Operators in the Weihrauch Lattice

Abstract: The Weihrauch lattice offers a framework for classifying the uniform computational content of problems. Unlike many other degree structures in computability, it supports a wide variety of algebraic operations. These operations have intrinsic logical interest, but they also serve a technical purpose, by helping us characterize problems of interest in terms of other problems, or by separating problems of interest.

Examples of such operations include the well-studied closure operators of parallelization and diamond. On the other hand, interior operators have received less attention until the past few years, during which the following were discovered/first stated explicitly: the stashing operator (Brattka), the first-order part (Dzhafarov, Solomon, Yokoyama), and the deterministic part (Goh, Pauly, Valenti). We survey known results on these operators and pose some questions.

Time: 17.00 - 17.50 (Astana time, UTC+6).

Victor Selivanov

Chief researcher of the Laboratory of Theoretical Programming 

A.P. Ershov Institute of Informatics Systems, Siberian Branch of the Russian Academy of Sciences (IIS SB RAS).

Title of the talk: Natural Degrees and Natural Structures 

Abstract: Huge collections of structures considered in mathematics (say, of groups or of topological spaces) contain only a few naturally arising structures that are especially interesting and useful. Similarly, the degree structures considered in computability theory (say, the structures of Turing degrees and of many-one degrees) are very rich and complicated but only a few of their elements are needed to classify sets really interesting in mathematics (outside the computability theory). Accordingly, the degree structures contain much easier substructures of «natural» degrees which are especially important for applications.

In this talk, we discuss some natural degree structures considered earlier in the literature and initiate a discussion of algorithmic aspects of natural mathematical structures (like groups or topological spaces) which, in our opinion, deserve special study. Along with presenting some technical facts illustrating the idea of naturalness, we also compare two approaches to identifying the natural degrees: the intuitive one and the precise one which attempts to capture them formally. 

Time:  18.00 - 18.50 (Astana time, UTC+6).

Dino Rossegger

Marie Skłodowska Curie Fellow at UC Berkeley and TU Wien

Title of the talk: The Borel complexity of models of finitary first-order theories

Abstract: The Borel hierarchy gives a robust way to stratify the complexity of sets of countable structures and is intimately tied with definability in infinitary logic via the Lopez-Escobar theorem. However, what happens with sets axiomatizable in finitary first-order logic, such as the set of structures satisfying a given finitary first-order theory T? Is the complexity of the set of T's models in any way related to the quantifier complexity of the sentences axiomatizing it? In particular, if a theory T is not axiomatizable by a set of sentences of bounded quantifier complexity, can the set of models of T still be at a finite level of the Borel hierarchy?

In this talk, we will present results concerning these questions: 

In joint work with Andrews and Lempp, we show that the set of models of a theory T is \Pi^0_\omega-complete if and only if T does not have an axiomatization by sentences of bounded quantifier complexity, answering the last question in the negative. We also characterize the Borel complexity of the set of models of complete theories in terms of their finitary axiomatizations. Our results suggest that infinitary logic does not provide any efficacy when defining first-order properties, a phenomenon recently observed by Harrison-Trainor and Kretschmer.

Combining our results with recent results by Enayat and Visser, we obtain that a large class of theories studied in the foundations of mathematics, sequential theories, have a maximal complicated set of models.

Time:  19.00 - 19.50 (Astana time, UTC+6).