Oberseminar mathematische Logik

Organized by

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

Time and location

Tuesdays 16.30-18.00 at room 0.003, Endenicher Allee 60. The participants of the seminar are welcome for coffee and tea at Peter Koepke's office 4.005 at 16.00 before the talks.

Contents

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

Plan

18 October  Dominique Lecomte (Université Paris 6) Baire class xi colorings

The G_0-dichotomy due to Kechris, Solecki and Todorcevic characterizes the analytic relations having a Borel measurable countable coloring. Our goal is to find a version of the G_0-dichotomy for xi-measurable countable colorings. We give a positive solution for the first three levels, as well as some recent progress for the general case.

25 October No seminar

02 November Wednesday 16.30-18.00, room N0.008 Philipp Lücke (Universität Münster) The automorphism tower problem

Abstract

08 November  Nitin Saxena (Universität Bonn) Algebraic Independence and Applications

Algebraic independence is a basic notion in advanced commutative algebra that generalizes linear independence of linear polynomials to higher degree. Polynomials f_1,...,f_m are called *algebraically independent* if there is no non-zero polynomial F such that F(f_1,...,f_m)=0. Based on this we could also define a notion of rank for a set of polynomials - transcendence degree (short, trdeg). Being a fundamental concept, trdeg appears in many contexts in algebraic computation. In this talk I will describe algorithms for computing trdeg efficiently in practice, and then mention various situations where the concept is useful. To name a few - circuit lower bounds, constructions of algebraic extractors, and polynomial identity testing.

This is based on a joint work with Malte Beecken and Johannes Mittmann (ICALP 2011).

17 November Thursday 16.30-18.00, Hausdorffraum Hannes Diener (Universität Siegen) Variations on a theme by Ishihara

This will be a talk in two halves. The first will consist of a gentle introduction to constructive analysis. In constructive mathematics one is interested in objects that one cannot only rule out the non-existence of, but those that one can (at least in theory) actually construct. The easiest way to achieve this, is to limit oneself to intuitionistic instead of classical logic, that is not to make any use of the law of excluded middle.

In the second half of the talk we will present results by Hajime Ishihara of 1991, which became known as ``Ishihara's tricks''. These results are about decisions that, on first and maybe even second glance, seem algorithmically impossible to make. We will present new results, which extend Ishihara's ideas. Lastly, we will show how all of this can be used to give an axiomatic, concise, and clear proof of the well known phenomenon that in many constructive settings every real-valued function on the unit interval is continuos (``computability implies continuity'').

22 November Wolfgang Wohofsky (TU Wien) Small subsets of the real line and variants of the Borel Conjecture

I will first give a short overview of (the history of) the notions "strong measure zero" and "strongly meager", and of the consistency proofs of the Borel Conjecture (by Laver) and the dual Borel Conjecture (by Carlson).

Then I will talk about our recent result that it is consistent that the Borel Conjecture and the dual Borel Conjecture hold simultaneously. This is joint work with Martin Goldstern, Jakob Kellner, and Saharon Shelah. I will try to present at least some of the ideas involved in the proof.

Finally, I will talk about another variant of the Borel Conjecture, which I call "Marczewski Borel Conjecture" (MBC). It is the analogue of the (dual) Borel Conjecture when the ideal of meager (measure zero) sets in its definition is replaced by the ideal of Marczewski null sets. I still do not know whether it is consistent; to investigate this question, I introduced the notion of "Sacks dense ideal": I will discuss its relation to MBC and outline several results (and open problems) about Sacks dense ideals.

29 November Benjamin Seyfferth (Universität Bonn) Tree representations via ordinal machines

We study sets of reals computable by ordinal Turing machines with a tape of length the ordinals that are steered by a standard Turing program. The machines halt at some ordinal time or diverge. We construct tree representations for ordinal semi-decidable sets of reals from ordinal compu- tations. The aim is to generalize uniformization results to classes of ordinal semi-decidable sets defined by bounds on the halting times of computations. We further briefly examine the jump structure and nondeterminism.

06 December Charles Morgan (Universidade de Lisboa) Extent : density

Extent and density are two classical properties of topological spaces. I shall discuss how their relationship is affected by (set theoretic) combinatorics for certain classes of spaces, and highlight the set theoretic problems brought into focus by the investigation. (No background in the relevant topological notions will be assumed.)

13 December No seminar. At 14.15 Tomás Silveira Salles will speak about Extreme amenability of topological groups in the master students seminar.

20 December no seminar

Christmas break

12 January Thursday 14.15-15.45, room 0.011 Benjamin Miller (Universität Münster) tba

17 January Marcos Cramer (Universität Bonn) tba

24 January tba

31 January tba

17 February  (tentative) Friday 14.15-15.45, room 1.007 Daisuke Ikegami (Berkeley) tba