Archives of: Bonn Logic Seminar

André Nies: Topological isomorphism for classes of closed subgroups of the group of permutations of N

Tuesday, November 20, 2018, 10:30
Seminar room N0.003, Mathematical Institute, University of Bonn

Speaker: André Nies (Auckland)

Title: Topological isomorphism for classes of closed subgroups of the group of permutations of N

Abstract:

The closed subgroups of the group of permutations of $\mathbb{N}$ coincide with the automorphism groups of structures with domain $\mathbb{N}$. We consider natural Borel classes of such groups, such as being profinite (each orbit is finite), or being oligomorphic (for each $k$ there are only finitely many $k$-orbits). We work towards classifying the complexity of their isomorphism relation in the sense of Borel reducibility.

For each class, work with A. Kechris and K. Tent (J. Symb. Logic, in press) shows that the topological isomorphism relation is Borel below the isomorphism relation among countable graphs. For the class of profinite groups, we show that this bound is sharp. On the other hand, for oligomorphic groups, work with Schlicht and Tent from this year shows that the isomorphism relation is below a Borel equivalence relation with only countable classes, and hence much lower than graph isomorphism. A lower bound, other than the identity relation on the set of reals, remains unknown.

Robert Passmann: The de Jongh Property for a Subtheory of CZF

Tuesday, November 6, 2018, 10:30
Seminar room N0.003, Mathematical Institute, University of Bonn

Speaker: Robert Passmann (Amsterdam)

Title: The de Jongh Property for a Subtheory of CZF

Abstract:

After recalling intuitionistic logic, Kripke semantic, and (Heyting) algebra-valued models for set theory, we will introduce the notions of loyalty and faithfulness: An algebra-valued model is called loyal if its propositional logic is the propositional logic of its underlying algebra; it is called faithful if all elements of the underlying algebra are truth values of sentences in the language of set theory in the model. We will then analyse the loyalty and faithfulness of a particular construction of Kripke models of set theory due to Iemhoff, and, by using classical models of ZFC set theory and the forcing technique, prove the de Jongh property for the constructive set theory CZF${}^*$ satisfied by Iemhoff’s models, i.e., for any propositional formula $\phi(p_0,…,p_{n-1})$ with propositional letters $p_0,…,p_{n-1}$, it holds that intuitionistic logic IPC proves $\phi(p_0,…,p_{n-1})$ if and only if CZF${}^*$ proves $\phi(\psi_0,…,\psi_{n-1})$ for all set theoretical sentences $\psi_0,…,\psi_{n-1}$. More precisely, we show that CZF${}^*$ has the de Jongh property with respect to every logic that can be characterised by a class of Kripke frames.

Aleksandra Kwiatkowska: Infinite permutation groups

Tuesday, October 30, 2018, 10.00
Seminar room N0.003, Mathematical Institute, University of Bonn

Speaker: Aleksandra Kwiatkowska (Münster)

Title: Infinite permutation groups

Abstract:

We discuss several results on infinite permutation groups, that is, closed subgroups of the symmetric group on a countable set, or equivalently, automorphism groups of countable structures. We will focus on ample genericity, where a topological group G has ample generics if for every n, the diagonal conjugacy action of G on Gn has a comeager orbit, on similarity classes, and on topological generators of permutation groups. For example, we show that for a permutation group G, under mild assumptions, for every n and an n-tuple f in G, the countable group generated by f is discrete, or precompact, or the conjugacy class of f is meager. Finally, we will focus on automorphism groups of structures equipped with a definable linear order, such as the ordered random graph, the ordered rational Urysohn metric space, the ordered random poset, the ordered random boron tree, and many other extremely amenable permutation groups. In particular, we give new examples of such groups which have a comeager conjugacy class. This is joint work with Maciej Malicki.

Dan Nielsen : Mapping the Ramsey-like cardinals

Monday, December 18, 2017, 16.30
Seminar room 0.008, Mathematical Institute, University of Bonn

Speaker: Dan Nielsen (University of Bristol)

Title: Mapping the Ramsey-like cardinals

Abstract:

Ramsey-like cardinals were introduced in Gitman (2011) and Gitman & Welch (2011), broadly speaking being cardinals k that are critical points of elementary embeddings from a size k ZFC^- model. Recently, Holy & Schlicht (2017) have introduced a new large cardinal into the Ramsey-like family, called (strategic) alpha-Ramsey cardinals, whose distinctive feature is that they admit a game-theoretic characterisation. I will present some new results concerning how these Ramsey-like cardinals fit into the large cardinal hierarchy and how they interact with the core model K. This is joint work with Philip Welch.

Merlin Carl: Complexity theory for ordinal Turing machines

Monday, November 27, 2017, 16.30
Seminar room 0.008, Mathematical Institute, University of Bonn

Speaker: Merlin Carl (Universität Konstanz)

Title: Complexity theory for ordinal Turing machines

Abstract:

Ordinal Turing Machines (OTMs) generalize Turing machines to transfinite working time and space. We consider analogues of theorems from complexity theory for OTMs, among them the Cook-Levin theorem, the P vs. NP problem and Ladner’s theorem. This is joint work with Benedikt Löwe and Benjamin Rin.

Philipp Schlicht: The Hurewicz dichotomy for definable subsets of generalized Baire spaces

Monday, November 20, 2017, 16.30
Seminar room 0.008, Mathematical Institute, University of Bonn

Speaker: Philipp Schlicht (Universitat Bonn)

Title: The Hurewicz dichotomy for definable subsets of generalized Baire spaces

Philipp Lücke: Squares, chain conditions, and products

Monday, November 13, 2017, 16.30
Seminar room 0.008, Mathematical Institute, University of Bonn

Speaker: Philipp Lücke (Universität Bonn)

Title: Squares, chain conditions, and products

Abstract:

With the help of square principles, we obtain results concerning the consistency strength of several statements about strong chain conditions and their productivity. In particular, we show that if the κ-Knaster property is countably productive for some uncountable regular cardinal κ, then κ is weakly compact in L. The proof of this result relies on a new construction that shows that Todorcevic’s principle □(κ) implies an indexed version of the principle □(κ,λ). This is joint work with Chris Lambie-Hanson (Bar-Ilan).

Peter Holy: The exact strength of the class forcing theorem

Monday, October 23, 2017, 16.30
Seminar room 0.008, Mathematical Institute, University of Bonn

Speaker: Peter Holy (Universität Bonn)

Title: The exact strength of the class forcing theorem

Abstract:

We consider second order set theories, that have as objects both sets and classes, and the role of the class forcing theorem, that is the forcing theorem for all notions of class forcing, within this range of theories. While Kelley-Morse class theory (KM) proves the class forcing theorem, its failure is consistent with the axioms of Gödel-Bernays set theory (GBC). We show that the class forcing theorem is equivalent, over GBC, to the principle of elementary transfinite (class) recursions of length Ord, and to the existence of various kinds of truth predicates. This is joint work with Victoria Gitman, Joel Hamkins, Philipp Schlicht and Kameryn Williams.

Stefan Hoffelner: NS saturated and Delta_1-definable

Monday, June 19, 2017, 16.30
Seminar room 0.011, Mathematical Institute, University of Bonn

Speaker: Stefan Hoffelner (University of Vienna)

Title: NS saturated and Delta_1-definable

Abstract:

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.

Yizheng Zhu: Iterates of M_1

Monday, June 12, 2017, 16.30
Seminar room 0.011, Mathematical Institute, University of Bonn

Speaker: Yizheng Zhu (University of Münster)

Title: Iterates of M_1

Abstract:

Assume 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}.