Bonn Mathematical Logic Group

Oberseminar mathematische Logik

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

Organized by

Time and location

Mondays 16:30-18:00 at room 1.007, Endenicher Allee 60.
The participants of the seminar are welcome for coffee and tea at the Hausdorff-Raum 1.012 from 16:00-16:30 before the talks.

Programme

18 October Stefan Geschke (Universität Bonn) 2-dimensional convexity and P_4-free graphs

The convexity number of a set S in R^n is the least size of a family of convex sets with union S. A subset C of S is an m-clique if the convex hull of no m-element subset of C is contained in S. We show that there is essentially just one way to construct a closed planar set S that has an uncountable convexity number but does not contain an uncountable 3-clique. In particular, any two such sets have the same convexity number. This result follows from an analysis of the convex structure of closed planar sets without uncountable 3-cliques in terms of clopen, P_4-free graphs on Polish spaces. slides

25 October Peter Koepke (Universität Bonn) Singularizing Successor Cardinals by Forcing

Namba forcing singularizes the successor of κ=ω1 without collapsong κ. In my talk I study the case κ>ω1. Let μ be a measurable cardinal and let κ be a regular cardinal such that ω1<κ<μ. Then there are successive forcing extensions V⊆M⊆N such that κ∈CardN, κ>ω1, and cofN(κ+M)=ω. The construction combines Prikry forcing for μ with Levy collapsing μ to κ+. Conversely, standard covering arguments show that singularizing larger successor cardinals indeed requires the strength of measurable cardinals. This work is currently being extended to uncountable cofinalities together with Dominik adolf at Münster. pdf

08 November Philipp Schlicht (Universität Bonn) The Wadge order for the real line

We consider the Borel subsets of the real line quasiordered via preimages of continuous functions, corresponding to the Wadge order for Baire space. We show that the quasiorder is universal for partial orders of size omega_1 on the level just above open and closed sets and below the set of rationals. We also construct a minimal proper F_sigma set. This is joint work with Daisuke Ikegami.

15 November Christine Gaßner (Universität Greifswald) Komplexitätsbetrachtungen über beliebigen Strukturen

1989 führten L. Blum, M. Shub und S. Smale ein uniformes Berechnungsmodell für Berechnungen über dem Ring R der reellen Zahlen ein. Dieses Modell ähnelt einer "reellen" Turingmaschine, in deren Zellen jeweils eine reelle Zahl gespeichert werden kann und mit deren Hilfe reelle Zahlen als einheitliches Ganzes betrachtet und verarbeitet werden können. Überraschenderweise blieb das PR -NPR -Problem für dieses Modell bisher, ebenso wie das klassische P-NP-Problem für die Turingmaschine, offen. Andererseits konnte für gewisse andere algebraische Strukturen S relativ schnell PS ≠ NPS gezeigt werden. Unklar war lange Zeit, ob es auch Strukturen S gibt, für die PS = NPS bezüglich der uniformen Berechenbarkeit über S gilt.

In dem Vortrag wird ein uniformes Berechnungsmodell über beliebigen Strukturen S eingeführt. Es werden deterministische, nichtdeterministische und digital (binär) nichtdeterministische Maschinen über S eingeführt, eine Zusammenfassung von Ergebnissen bezüglich der resultierenden Klasse PS, DNPS und NPS gegeben und eine Idee zur Konstruktion von Strukturen S mit PS = NPS vorgestellt. abstract slides

22 November Heike Mildenberger (Universität Freiburg) The minimal cofinality of an ultrapower of omega and the cofinality of the symmetric group can be larger than the successor of the bounding number

In the talk we will look at a kind of c.c.c. iteration that works with particular combinatorics on the names present at a given iteration length that is used to define the next iterand. We establish the consistency result stated in the title. This is joint work with Shelah.

29 November (Monday 18:15, Seminarraum Diskrete Mathematik, Lennéstr. 2) Stefan Geschke (Universität Bonn) 2-dimensional convexity and P4-free graphs

The convexity number of a set S in R^n is the least size of a family of convex sets with union S. A subset C of S is an m-clique if the convex hull of no m-element subset of C is contained in S. We show that there is essentially just one way to construct a closed planar set S that has an uncountable convexity number but does not contain an uncountable 3-clique. In particular, any two such sets have the same convexity number. This result follows from an analysis of the convex structure of closed planar sets without uncountable 3-cliques in terms of clopen, P_4-free graphs on Polish spaces. slides

01 December (Wednesday 16:30-18:00, Seminarraum 0.006) Frank Stephan (National University of Singapore) Automatic structures and model theory

In the field of Automatic structures, the functions, relations and domains of automatic models have all to be recognisable by finite automata. In the recent years, various approaches from computable model theory have been transferred to the field of automatic structures and questions parallel to those in computable model theory were investigated; in particular one is interested in the questions which of the countable models of a theory can be automatic. Khoussainov and Nerode posed various open questions on automatic structures and model theory. Recently, we made the following progress on the problems of Khoussainov and Nerode.

1. There is an uncountably categorical but not countably categorical complete theory for which only the prime model is automatic.
2. There are complete theories with exactly 3,4,5,... countable models, respectively, and every countable model has an automatic presentation.
3. There is a complete theory for which exactly 2 countable models have an automatic presentation.
4. If LOGSPACE = P then there is an uncountably categorical but not countably categorical complete theory for which the prime model is not automatic but all other models have an automatic presentation.
5. There is a complete theory with countably many countable models including a countable prime model and countable saturated model such that the saturated model has an automatic presentation and the prime model does not have one.

This is joint work with Pavel Semukhin. slides paper

06 December Salma Kuhlmann (Universität Konstanz) Valued differential fields of exponential logarithmic series

Consider the valued field R((Γ)) of generalised series, with real coefficients and monomials in a totally ordered multiplicative group Γ. In a series of papers, we investigated how to endow this formal algebraic object with the analogous of classical analytic structures, such as exponential and logarithmic maps, derivation, integration and difference operators. In this talk, we shall discuss series derivations and series logarithms on R((Γ)) (that is, derivations that commute with infinite sums and satisfy an infinite version of Leibniz rule, and logarithms that commute with infinite products of monomials), and investigate compatibility conditions between the logarithm and the derivation, i.e. when the logarithmic derivative is the derivative of the logarithm. pdf

13 December Philipp Lücke (Universität Münster) Descriptive set theory at uncountable cardinals - Delta11 subsets of kappa^kappa

Let κ be an uncountable regular cardinal with κ=κ<κ. A subset of (κκ)n is a Σ11 subset if it is the projection of all cofinal branches through a κ-tree T on κn+1. We define Σ1k, Π1k and Δ1k subsets as usual. Given an arbitrary subset A of κκ, I showed that there is a <κ-closed forcing P that satisfies the &kappa+-chain condition and forces A to be a Δ11 subset of κκ in every P-generic extension of V. This result allows us to construct a forcing with the above properties that forces the existence of a well-ordering of κκ whose graph is a Δ12 subset of (κκ)2. In my talk, I want to present the central ideas behind the proofs of these results, focusing on coding subsets of κκ by κ-Kurepa trees in forcing extensions and the strong absoluteness properties of this coding. pdf

20 December Alexey Ostrovsky (Unibw München) Neue Lösungen zu klassischen Problemen von Hausdorff, Luzin und Novikov

Hausdorff bewies: wenn f: X -> Y eine offene stetige Funktion und X vollständig metrisierbar ist, dann ist Y auch vollständig metrisierbar. Er beschäftigte sich auch mit der Frage der möglichen Übertragung dieses Satzes auf Borelmengen und andere Klassen von Funktionen. Wir verallgemeinern den Satz auf Borelmengen X unter folgenden Bedingungen: (1) f ist stetig und das Urbild jedes Punktes ist kompakt und (2) f bildet jede offene Teilmenge auf die Vereinigung von n Mengen ab, die jeweils endliche Durchschnitte von offenen und abgeschlossenen Teilmengen sind. Die Methode liefert erstmals positive Ergebnisse zu Problemen von Lusin und Novikov für separable metrische Räume. Diese Probleme beinhalten die Zerlegung von Borelmessbaren Funktionen in abzählbar viele stetige Funktionen und haben im Allgemeinen negative Lösungen für Funktionen der ersten Baire-Klasse.

17 January Arthur Apter (CUNY) Strong Compactness and Strong Unfoldability

We construct a model in which there is a characterization of the strongly compact cardinals in terms of the strongly unfoldable cardinals. In this model, kappa is strongly compact iff kappa is both measurable and strongly unfoldable.

21 January Friday 14.15-15.45 at room 1.007 Andreas Weiermann (Ghent University) A quick proof-theoretic analysis of ID1

Modifying an exposition of Buchholz, we provide a smooth ordinal analysis of ID1 using abstract operator controlled derivations which in case of PA are developed in our paper 'Classifying the provably total functions of PA'.

24 January Joan Bagaria (ICREA and Universitat de Barcelona) Structural Reflection and Large Cardinals

Beginning in the mid-20th century, a number of prominent set theorists and philosophers have repeatedly argued that any intrinsic justification of new set-theoretic axioms, beyond ZFC, and especially the axioms of large cardinals, should be based on generalizations to strong logics of the classical Levy-Montague Reflection Theorem. However, some results of W. Tait, and more recently of P. Koellner, have definitely established the essential limitations of this approach. In this talk we will consider a new form of reflection, Structural Reflection (SR), and will present some results showing that various natural forms of SR are exactly equivalent to well-known large cardinal axioms, ranging from the existence of supercompact cardinals to Vopenka's Principle. We will also show how these reformulations of large cardinal axioms in terms of SR can be applied to prove new results in category theory and algebraic topology, such as the existence of cohomological localizations of simplicial sets.

31 January No seminar

Last changed: 16 January 2011