Oberseminar mathematische Logik

Organizers

• Prof. Dr. Stefan Geschke
• Prof. Dr. Peter Koepke
• Dr. Philipp Schlicht

Time and location

Monday 16.30-18.00 at room 1.007, Endenicher Allee 60, beginning April 16.

The participants of the seminar are welcome for coffee and tea in the Hausdorff-Raum 1.012 at 16.00 before the talks.

Contents

Advanced talks on mathematical logic by guests and members of the logic group.

Plan

16 April Philipp Schlicht (Universität Bonn) Continuous reducibility and dimension

Borel sets and Borel structures such as graphs or equivalence relations can be compared using Borel measurable, Lebesgue measurable, or continuous reducibility. We will look at a construction of an uncountable family of Borel subsets of an arbitrary metric space of positive dimension with the property: No set in the family is a preimage under a continuous map on the space of another set in the family. Together with known results this implies that dimension forms a dividing line for continuous reducibility.

23 April  Andrey Morozov (Novosibirsk State University and Sobolev Institute of Mathematics) On Sigma-presentability over HF(R)

In the talk we consider structures Sigma-definable over HF(R) (the superstructure of hereditarily finite sets over the ordered field of reals). If we replace omega with HF(R), the notion of computable enumerability will naturally change to Sigma-definability over HF(R), and the concept of structure Sigma-definable over HF(R) will be a natural replacement to the concept of computable structure. We will present some general properties of the structures and a characterization of at most countable structures in this class. Special attention will be paid to the question if it is possible to define essentially different isomorphic copies of the reals and to the problem on the number of non-Sigma-isomorphic Sigma-presentations of structures over HF(R).

30 April  no seminar

07 May  Peter Scheiblechner (Hausdorff Center) Effective de Rham Cohomology

A long standing open problem in computational algebraic geometry is to find an algorithm which computes the topological Betti numbers of a semialgebraic set in single exponential time. There has been recent progress on the corresponding problem over the complex numbers. A fundamental Theorem of Grothendieck states that the Betti numbers of a smooth complex variety can be computed via its algebraic de Rham cohomology, which is defined in terms of algebraic differential forms on the variety. In this talk we discuss degree bounds on these differential forms and their importance for the algorithmic computation of Betti numbers. We will start with a moderate introduction to algebraic geometry, and finish with the latest of these results, which is a single exponential degree bound in the case of any smooth affine variety.

Slides

14 May  John Clemens (Universität Münster) Treeable equivalence relations and descriptive complexity

The property of treeability has been well-studied in the context of countable Borel equivalence relations, but has been little studied up to now in the uncountable case. I will discuss a family of treeable equivalence relations which provides new insights into this area as well as the area of potential descriptive complexity. In particular, we show that the collection of treeable Borel equivalence relations is unbounded in the Borel-reducibility hierarchy. Additionally, a generalization of the Kechris-Louveau dichotomoy for E_1 allows us to show that for every Borel equivalence relation which is not essentially hyperfinite we may find equivalence relations of arbitrarily high descriptive complexity with which it is incomparable under Borel reducibility. This is joint work with Dominique Lecomte and Ben Miller.

21 May  Victor Selivanov (Ershov Institute of Informatics Systems) Some variations on the Wadge reducibility

The classical Wadge reducibility provides a nice tool to calibrate the topological complexity of subsets of the Baire space. Since many applications need more complicated spaces than the Baire space and more complicated objects than subsets, it is natural and instructive to search for possible extensions and modifications of the Wadge theory. Several such variations on the Wadge reducibility are known, for example people consider: other natural classes of reducing functions in place of the continuous functions, more complicated spaces than the Baire space, reducibility between functions rather than reducibility between sets, more complicated reductions than the many-one reductions by continuous functions.

In this talk, we review several such variations on the Wadge reducibility including recent results (which are obtained in a joint work with Luca Motto Ros and Philipp Schlicht) on the reductions between subsets of the so called quasi-Polish spaces, and a recent extension of the Wagner hierarchy from the omega-regular languages to the omega-regular k-partitions of the Cantor space (for each natural k>1).

22 May Tuesday 12.15-14.00, Zeichensaal, Wegelerstr. 10 (1. Stock) Robert Lubarsky (Florida Atlantic University) Varieties of the Fan Theorem

24 May Thursday 16.15-18.00, Hausdorffraum 1.012 Andrey Morozov (Novosibirsk State University and Sobolev Institute of Mathematics) Computability and Symmetry

The talk is a survey of results related to symmetries arising in the study of the concept of computability. In particular, we will be speaking about groups of relatively computable permutations, groups of computable automorphisms of computable structures, and Turing degrees of automorphisms and of groups of computable automorphisms of computable structures.

29 May  no seminar

04 June  no seminar

11 June  Matteo Viale (University of Torino) Forcing and absoluteness as means to prove theorems

The forcing method has been introduced by Cohen in the early sixties to prove the independence of the continuum problem. Forcing can be presented as an "algorithm" which takes as inputs a model M of ZFC and a boolean algebra B in M and produces a boolean valued model M^B of ZFC. The first order theory of M^B depends on the first order theory of M and on the combinatorial properties of B. Since its introduction forcing has been the most powerful tool to prove independence results in set theory. In this talk we shall take a dIfferent attitude and show that forcing is a powerful tool to prove theorems in ZFC.

The talk aims to be accessible to a general audience of logicians. In particular we try to make the most part of it accessible to an audience who does not have much acquaintance with forcing.

Those interested in the argument of this seminar can consult the preprint Martin's maximum revisited available at my web-page: http://www2.dm.unito.it/paginepersonali/viale/Martinmaximumrevisited.pdf.

If time permits I shall also sketch a proof of the main result I will present.

18 June no tea and coffee, talk begins at 16.15 Meeri Kesälä (University of Helsinki) Introduction to non-elementary model theory and applications

Classically model theory studies classes of infinite structures, which are the models of a theory in first order logic. These are called elementary classes. Powerful machinery, such as the tools from geometric stability theory, have been developed to analyze elementary classes. Furthermore, the tools have been applied to solve questions from many fields of mathematics, for example algebraic geometry and number theory.

In this talk we give some motivation and examples why and how this machinery has been generalized beyond first-order definable classes, to so called non-elementary classes. We focus on examples by Zilber and Kirby motivated by the study of the field of complex numbers with the exponent function.

If time is left, we discuss some connections of non-elementary model theory to set-theoretical combinatorics. No prequisities in model theory are needed for the talk.

20 June Wednesday 10.15-12.00, Seminarraum 0.011 Clinton Conley The Paulsen simplex via Fraisse theory

The Paulsen simplex is a reappearing object throughout the theory of integral representations, notable for its homogeneity and universality properties. We discuss a new approach to the construction of the simplex as a sort of Fraisse limit. This is joint work with Asger Törnquist.

25 June  Merlin Carl (Universität Konstanz) Real Closed Exponential Fields and Models of Peano Arithmetic

A real closed field (RCF) is a first-order structure which is elementary equivalent to the real numbers. An integer part (IP) of a real closed field K is a discretely ordered subring R with smallest element 1 such that, for every x in K, there is a unique k in R such that k≤x<k+1. By a theorem of Shepherdson, integer parts of real closed fields are exactly the models of open induction, which is Peano Arithmetic with induction restricted to quantifier-free formulas. We consider the question when an RCF can have an IP that is a model of full PA. By a recent result of D'Aquino, Knight and Starchenko, this is the case for a countable real closed field K iff K is recursively saturated. We will demonstrate that this characterization fails in the uncountable case. In particular, we will prove that no field of formal power series can admit an IP modeling PA.

02 July  Philipp Lücke (Universität Bonn) The influence of closed maximality principles on Sigma-1-1 subsets of generalized Baire spaces

Abstract

09 July  no seminar