Oberseminar mathematische Logik
Time and location
Monday 16.30-18.00 in room 0.011, Endenicher Allee 60.
The participants of the seminar are welcome for coffee and tea in the Hausdorff-Raum 1.012 at 16.00 before the talks.
Advanced talks on mathematical logic by guests and members of the logic group.
- 14 October Andre Nies (University of Auckland) Algorithmic randomness connects to set theory
- We discuss two connections between algorithmic randomness and set theory. The first direction replaces algorithmic tools such as test definitions by tools from effective descriptive set theory in order to obtain ``higher'' randomness notions. This goes back to Martin-Loef (1970) and was recently developed by Hjorth and Nies (2007), Chitat Chong and Yu Liang, and Greenberg and Monin. Their recent result is that the Borel complexity of the largest Pi-1-1 null set (first described by Kechris 1975) is exactly (boldface) Pi-0-3. The second direction finds analogs of cardinal invariants of the continuum in the realm of highness properties that indicate strength of a Turing oracle A. For instance, the bounding number corresponds to A computing a function that dominates all computable functions. This was first observed by N. Rupprecht (2010). Recent work of Brendle, Brooke-Taylor, Ng and Nies studied the full analog of the so-called Cichon diagram of cardinal invariants.
- 21 October Ralf Schindler (Universität Münster) Does Pi-1-1 determinacy yield 0#?
- It is unknown whether Pi-1-1 determinacy yields 0# in third order arithmetic. We show that third order arithmetic plus Harrington's principle "there is a real x such that every x-admissible is an L-cardinal" is equiconsistent with ZFC plus a remarkable cardinal, and we also discuss strengthenings of Harrington's principle. This is joint work with Cheng Yong.
- 28 October No talk. October 28-31 Workshop on homogeneous structures HIM, Poppelsdorfer Allee 45
- 04 November Dana Bartosova (HIM Bonn) Unique amenability of topological groups
- 18 November Thilo Weinert (Universität Bonn) Partition relations for linear orders in a non-choice context
- In "Partition Relations for eta_alpha-Sets", Erdös, Milner and Rado proved, using the Axiom of Choice, three partition relations which amount to the following: -It is possible to partition the triples of any linear order into two classes such that every set of order-type w* + w(the integers) contains a triple in the first class and every quadruple contains a triple in the second class. -It is possible to partition the triples of any linear order into two classes such that every set of order-type w+ w* contains a triple in the first class and every quadruple contains a triple in the second class. -It is possible to partition the triples of any linear order into two classes such that every set of order-type w* + w(the integers) contains a triple in the first class, every set of order-type w+ w* contains a triple in the first class, and every quintuple contains a triple in the second class. They could not tell whether one can replace "quintuple" by "quadruple" in the last statement. Using a structural analysis from " A Partition Theorem for Perfect Sets" by Blass it is possible to prove analogue statements for a choiceless context for 2x lexicographically ordered for some ordinal x replacing "triple" by "quadruple", "quadruple" by "quintuple", and "quintuple" by " septuple". This is going to be the topic of the talk.
- 25 November Luca Motto Ros (Universität Freiburg) Uniformly continuous and Lipschitz reducibilities on ultrametric Polish spaces
- We analyze the reducibilities induced by, respectively, uniformly continuous, Lipschitz, and nonexpansive functions on arbitrary ultrametric Polish spaces, and give sufficient and necessary (topological) conditions on such spaces for the corresponding degree-structures being well-behaved. This is joint work with Philipp Schlicht.
- 02 December Mati Rubin (Ben Gurion University) Locally moving groups and the reconstruction of structures from their automorphism groups
- 04 Dezember (Wednesday 16.30-18.00, Hausdorffraum) Nitin Saxena (Universität Bonn) Testing algebraic independence over finite fields
- The problem of algebraic independence is to test whether for given polynomials f1,...,fm (over a field k), there is a nontrivial annihilating polynomial A(y1,...,ym) such that A(f1,...,fm)=0. This is a fundamental problem with several known computational applications. There is an efficient randomized algorithm to solve this when k has characteristic zero. This is based on the Jacobian criterion. There is no efficient algorithm known when k is a general finite field. We will describe in this talk a new criterion to handle these cases -- the Witt-Jacobian criterion. This criterion is not yet efficient but is theoretically better than the brute-force method. We will sketch the proof, with the de Rham-Witt complex being the main tool. Based on: "Algebraic Independence in Positive Characteristic -- A p-adic Calculus", with Johannes Mittmann and Peter Scheiblechner. Trans. Amer. Math. Soc., 2013
- Canonical Ramsey theory on Polish spaces is a new research area (and book of the same name) initiated by Kanovei Sabok and Zapletal. It generalizes the classical Erdos-Rado canonical Ramsey theorem by considering Polish spaces equipped with sigma-ideals of the Borel algebra and definable equivalence relations on them instead of the set of natural numbers and arbitrary equivalence relations as in the classical case. It has connections to other areas of set theory, e.g. forcing, the theory of Borel equivalence relations, etc. I will give an introduction to this topic and present one of my results in this area (either related to the Silver ideal/forcing, Laver ideal/forcing, or related to the Carlson-Simpson Dual Ramsey theorem).
- 17 December (Tuesday 10.15-11.45, seminar room 0.006) Michael Pinsker (Wien) Reconstructing omega-categorical structures from their clones
- Any countable omega-categorical structure Delta can be
reconstructed up to first-order interdefinability from its
automorphism group, by the theorem of Ryll-Nardzewski. Even more
information about Delta is encoded into its polymorphism clone,
i.e., the set of all homomorphisms from finite powers of Delta into itself:
the polymorphism clone still ``knows'' Delta up to
primitive positive interdefinability (Bodirsky+Nesetril).
If we consider the automorphism group of Delta as an abstract topological group, then Delta can still be recovered from this information up to first-order biinterpretability (Ahlbrandt+Ziegler). Recently, Bodirsky+Pinsker have shown that if we see the polymorphism clone of Delta as an abstract topological and algebraic structure, then we still know Delta up to primitive positive biinterpretability.
It turns out that for many structures, in particular for some of the most prominent homogeneous structures, the topological structure of their automorphism group is determined by its algebraic structure; consequently, those structures can be recovered from the abstract group structure of their automorphism group up to first-order biinterpretability. This situation was discussed by Rubin in his seminar talk two weeks ago.
We investigate when we can recover the topological structure of polymorphism clones from the algebraic laws which hold in them. We also outline the very recent proof that this is possible for the polymorphism clone of the random graph.
- 06 January Philipp Schlicht (Bonn) The Hurewicz dichotomy for generalized Baire spaces
- 20 January Philipp Lücke (Bonn) Continuous images of closed sets in generalized Baire spaces
- 27 January Lorenz Halbeisen (Zürich) Konstruktion eines Permutationsmodells mit Hilfe eines Fraisse-Limes
- Nach einer kurzen Einführung in die Konstruktion von Permutationsmodellen für die Mengenlehre wird ein Permutationsmodell von Shelah vorgestellt, welches auf einem Fraisse-Limes basiert.
- 19 February Peter Holy (Bristol) Simplest Possible Locally Definable Wellorders
- I will present a forcing that, given an uncountable cardinal κ that satisfies κ<κ=κ, introduces a wellordering of H(κ+) that is definable over H(κ+) by a Σ1-formula with (or almost without) parameters, while preserving cofinalities up to 2κ and the value of 2κ.
In particular, this shows that one may have 2κ large in the presence of a Σ1-definable wellorder of H(κ+). As a consequence of Mansfield's Theorem, this is not the case if κ=ω.
This is joint work with Philipp Lücke.