## Oberseminar mathematische Logik

### Time and location

Mondays 16.30-18.00 in room 0.008, Endenicher Allee 60.

The participants of the seminar are welcome for coffee and tea in the Plückerraum 1.012 at 16.00 before the talks.

### Talks

• 24 April: Frank Stephan (Singapore) - Deciding parity games in quasipolynomial time

Parity games are games on finite graphs where each node has a value. Two players, Anke and Boris, move alternately a marker through the graph and plays between the two players have infinite duration. One determines the winner of such an infinite play by taking the largest value of a node which is visited infinite often; if this value is odd then the first player Anke wins else the second player Boris wins. An important question is to determine the player who has a winning strategy in such games.
One often evaluates such algorithms with respect to the run time in terms of the number n of nodes and number m of colours and other possible parameters. Prior work has given algorithms with runtime nm/3+O(1) and nO(Sqrt(n)). The talk will present an improved quasipolynomial algorithm with runtime O(nlog(m)+8) which determines the winner and the winning strategy. Furthermore, if m < log(n), one can determine the winner in time O(n5); thus the problem is fixed-parameter tractable and the algorithm brings it from the prior known complexity class XP into FPT.
This is joint work of Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Li Wei and Frank Stephan.

• 01 May: no seminar

• 08 May: Chris Lambie-Hanson (Bar-Ilan) - Constructions from square and diamond, with an application to super-Souslin trees

In 1982, Shelah and Stanley proved that, if $\kappa$ is a regular, infinite cardinal, $2^\kappa = \kappa^+$, and there is a $(\kappa^+, 1)$-morass, then there is a $\kappa^{++}$-super-Souslin tree, which is a type of normal $\kappa^{++}$-tree that necessarily has a $\kappa^{++}$-Souslin subtree and continues to do so in any outer model in which $\kappa^{++}$ is preserved and no new subsets of $\kappa$ are present. This result establishes a lower bound of an inaccessible cardinal for the consistency strength of the conjunction of $2^\kappa = \kappa^+$ and Souslin's Hypothesis at $\kappa^{++}$. In this talk, we will present a method for constructing objects of size $\lambda^+$ from $\square_\lambda + \diamondsuit_\lambda$, where $\lambda$ is a regular, uncountable cardinal. As an application, we will use $\square_{\kappa^+} + \diamondsuit_{\kappa^+}$ to construct a $\kappa^{++}$-super-Souslin tree. For uncountable $\kappa$, this increases Shelah and Stanley's lower bound from an inaccessible cardinal to a Mahlo cardinal. This is joint work with Assaf Rinot.

• 15 May: Andrey Morozov (Novosibirsk, Sobolev Institute of mathematics) - Infinite time Blum-Shub-Smale machines for computability in analysis

We continue the study of the computational strength of infinite time Blum-Shub-Smale machines (ITBM) performing computations over the reals in ordinal time started by P. Koepke and B. Seyfferth. We give a characterization of ITBM-computable functions via iterated Turing jumps and discuss the adequacy of this approach to our intuitive imaginations of computability used in analysis. This is joint work with Peter Koepke.

• 22 May: no seminar

• 29 May: Ana Njegomir (Bonn) A forcing characterization of $\lambda$-ineffable cardinals

In this talk, we will introduce corrected proofs of theorems of Christoph Weiß on the relationship between $\lambda$-ineffable cardinals and certain list properties, in particular showing that those large cardinals can be characterized by certain types of forcing. This is joint work with Peter Holy and Philipp Lücke.

• 05 June: no seminar

• 12 June: Yizheng Zhu (Münster) Iterates of $M_1$

Assume $\boldsymbol{\Delta}^1_{3}$-determinacy. Let $L_{\kappa_3}[T_2]$ be the admissible closure of the Martin-Solovay tree and let $M_{1,\infty}$ be the direct limit of $M_1$ via countable trees. We show that $L_{\kappa_3}[T_2]\cap V_{u_{\omega}} = M_{1,\infty} | u_{\omega}$.

• 19 June: Stefan Hoffelner (Vienna) NS saturated and $\Delta_1$-definable

Questions which investigate the interplay of the saturation of the nonstationary ideal on $\omega_1$, NS, and definability properties of the surrounding universe can yield surprising and deep results. Woodins theorem that in a model with a measurable cardinal where NS is saturated, CH must definably fail is the paradigmatic example. It is another remarkable theorem of H. Woodin that given $\omega$-many Woodin cardinals there is a model in which NS is saturated and $\omega_1$-dense, which in particular implies that NS is (boldface) $\Delta_1$-definable. S.D. Friedman and L. Wu asked whether the large cardinal assumption can be lowered while keeping NS $\Delta_1$-definable and saturated. In this talk I will outline a proof that this is indeed the case: given the existence of $M_1^{\#}$, there is a model of ZFC in which the nonstationary ideal on $\omega_1$ is saturated and $\Delta_1$-definable with parameter $K_{\omega_2^K}$ (note that $\omega_2^K$ is of size $\aleph_1$ in that model). In the course of the proof I will present a new coding technique which seems to be quite suitable to obtain definability results in the presence of iterated forcing constructions over inner models for large cardinals.

• 26 June: no seminar

• 03 July: no seminar

• 10 July: Yair Hayut (Jerusalem) Special Aronszajn trees

For a regular cardinal $\kappa$ and a $\kappa$-Aronszajn Tree, T, one may look for a reason T to have no cofinal branch. One possible reason (which is upwards absolute for models that preserve the regularity of $\kappa$) is that T have a specialization function (in this case we say that T is special). Baumgarthner constructed a forcing notion that enables one to add a specialization function to a given $\omega_1$-Aronszajn tree. This can be iterated in order to make all Aronszajn tree special, thus showing that it is consistent that being special is not only sufficient but also necessary for being Aronszajn tree (at $\aleph_1$). Laver and Shelah proved, in 1981, that it is consistent (starting from weakly compact) that CH holds and every $\omega_2$-Aronszajn tree is special. In a joint work with Mohammad Golshani, we showed that one can combine those two results and prove the consistency (relative to much stronger large cardinal assumption) of the statement "For every regular $\kappa$, there are Aronszajn trees of $\kappa^{+}$ and all of them are special". I will discuss the definitions and the theorems and I will indicate the main interesting features in the proof of Laver-Shelah and how they translate to the global case.

• 17 July: Itay Kaplan (Jerusalem) On dense subgroups of permutation groups

I will present a criterion that ensures that Aut(M) has a 2-generated dense subgroup when M is a countable structure (which holds in many natural examples), and then show how expanding an omega categorical structure might help in getting a finitely generated dense subgroup. Joint work with Pierre Simon.

• 24 July: Philipp Lücke (Bonn) Partition properties for simply definable colourings