## 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*

**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 computations. 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*

**12 January**Thursday 14.15-15.45, room 0.011 Benjamin Miller (Universität Münster)*Local rigidity, Glimm-Effros embeddings, and definable cardinals.*

- We employ local rigidity properties of the usual action of GL_2(Z) on the torus to rule out analogs of the Glimm-Effros dichotomy for non-measure-hyperfinite equivalence relations. As a consequence, we obtain the best possible bounds obtainable through measure-theoretic means concerning the region in which the definable cardinals become non-linear. I hope to make the talk accessible to a broad mathematical audience.

**20 January**Friday 10.15-11.45, room 1.012 (Hausdorffraum) Marcos Cramer (Universität Bonn)*Ackermann set theory and function theory*

- We present Ackermann set theory, a conservative extension of ZF with classes. Our motivation for considering this theory comes from a certain construction in mathematical texts - the implicit introduction of function - that we aim to capture formally. A function f can be introduced implicitly by a construct of the form: "For every x there is an f(x) such that R(x,f(x))." Implicit introduction of functions gives rise to a paradox similar to Russell's paradox. In order to avoid this paradox, we have developed a theory of functions that closely resembles Ackermann set theory. We show that this theory is equiconsistent to ZFC.

**24 January**Stefan Geschke (Universität Bonn)*There is no universal clopen graph on a compact metric space*

**31 January**Andreas Fackler (Universität München)*Topological Set Theory*

- The idea behind positive set theory is to weaken the naive comprehension principle by omitting all instances in which negation occurs. For example, the universal class V is a set while the Russell class is not. Surprisingly, this approach leads to a theory in which V is a topological space in a natural way.

Inspired by that fact, topological set theory TS instead of a comprehension principle has as its axioms several topological statements about V. Topological and positive set theory are closely related and in both of them there is an interesting interplay between the set theoretic and topological properties of V. Many basic theorems of TS remain true even without the axiom that the universal class V is a set, although one decisive statement about the ordinal numbers goes missing. Instead, a surprising connection to another familiar set theory arises ...

In my talk, I will present this family of axiom systems and give an overview of results about their implications, their consistency strengths, and their interrelations. We will also look briefly at their (known) models -- topological structures called hyperuniverses -- and at methods to construct such objects.

**17 February**Friday 15.15-16.45, room 1.007 Daisuke Ikegami (University of California, Berkeley)*Omega-logic and Boolean-valued second order logic*