Talks of the fall term 2024

Wed 18.09.2024 12 -14, C124

Ilkka Törmä: Multidimensional subshifts defined by MSO logic

Consider a coloring of the infinite $d$-dimensional grid $\Z^d$ using finitely many colors. A certain monadic second order (MSO) logic can be used to define classes of such colorings that are always translation invariant. In addition, a certain natural fragment of this logic only defines topologically closed sets, i.e. subshifts. I present old and new results concerning the structure and computability of the sets definable by these formulas. Some quantifier alternation hierarchies collapse, while others are infinite. Many natural decision problems lie on higher levels of the analytical hierarchy. Contrast this to the special case $d = 1$, where MSO formulas define exactly the $\omega$-regular languages and many nontrivial properties are decidable.

Wed 25​​​​.09.2024 15-16, Zoom (note unusual time and place!)

Nicholas Ramsey: Measures on bounded perfect PAC fields

A Keisler measure is a finitely additive probability measure on definable sets in a structure. Keisler measures are an important model-theoretic tool in a variety of contexts, but are especially significant for the analysis of definable groups. We will describe a construction for producing Keisler measures on bounded perfect PAC fields, an important class of algebraic examples within model theory. We will explain how the existence of these measures entails that all groups definable in bounded perfect PAC fields, and even in unbounded Frobenius fields, are definably amenable. This work builds on our earlier constructions of measures for e-free PAC fields and a related construction due to Will Johnson. This is joint work with Zoé Chatzidakis.

Wed 02.10.2024, no seminar

Wed 09​​​​.10.2024 12 -14, C124

Jouko Väänänen: Second order logic and inner models

I consider inner models arising from extended logics, as in my joint paper with Kennedy and Magidor. I introduce a new inner model of this kind, denoted C2(omega), based on the second order logic in which second order variables range over countable subsets of the domain. I give some results about large cardinals in C2(omega) and also about its relationship with C(aa). I also discuss the inner model HOD1 arising from existential second order logic. This is joint work with Menachem Magidor.

Wed 16.10.2024 12-14, C124

Davide Quadrellaro: On the Model Theory of Open Incidence Structures of Rank 2

Abstract: Recently, Hyttinen and Paolini proved that the theory of open projective planes is complete, stable, but not superstable. Even more recently, Ammer and Tent extended this result to cover all generalised n-gons, thus proving that the theory of open generalised n-gons is complete, stable, but not superstable. These results have the important consequence that all the free projective planes (resp. all the free generalised n-gons) are elementary equivalent, independently on the number of their generators. Inspired by these previous results, I will present a uniform treatment of the model theory of open incidence structures in two dimensions, e.g. projective and affine planes, generalised n-gons, Steiner systems, k-nets and Benz planes. This treatment is based on a mix of the methods from Hyttinen-Paolini and Ammer-Tent, and crucially involves both Hrushovski constructions and so-called HF-orders. Using these techniques I will present a general proof that, for all these examples of geometries, the theory of their open infinite models is complete, stable, but not superstable. This generalises the previous results from the literature to all (reasonable) examples of two-dimensional incidence geometries and thus shows that their free structures are all elementary equivalent. This is joint work with Gianluca Paolini.

Wed 23.10.2024, Exam week (no seminar)

Wed 30.10.2024 12-14, C124

Manon Blanc: Computing with real numbers: Robustness in computability and complexity over the reals.

Abstract: Many recent papers have studied how analogue models of computation work. By "analogue", we mean computing over continuous quantities, while digital models work on discrete structures like bits.
It led to a broader use of Ordinary Differential Equations (ODEs) in computability. In this context, the field of implicit complexity has also been widely studied, using computable analysis.
In the presentation, we will first present algebraic characterisations of PTIME and PSPACE over the reals, using "robust" ODEs. Then, we will see that, with the proper notion of robustness, we can prove that the reachability relation of (real) dynamical systems is computable and even have some complexity results. Eventually, we will extend robustness to computability in tiling theory. 

Wed 06.11.2024, C124

Joni Puljujärvi: Some model-theoretic results on complete existential second-order theories

Abstract: As a loose continuation to my talk last year about model theory of team semantics, I discuss results on complete existential second-order theories (or complete theories in dependence logic). Even though existential second-order logic is not closed under negation, there still exists a meaningful definition of being complete, and such complete theories seem to be somewhat interesting. As the main theorems of the work, I present two categoricity transfer results, making use of some elementary stability theory. This is joint work with Tapani Hyttinen and Davide Quadrellaro.

Wed 13.11.2024,  C124

Tapio Saarinen: The spectra of second-order logic

Abstract: The spectrum of a sentence of some logic is the set or class of cardinalities in which the sentence has a model. Second-order logic has quite a lot of set theoretic expressiveness, which puts it beyond many of the tools of model theory: for example, the Löwenheim-Skolem number of second-order logic is the first supercompact cardinal, if it exists. (The Löwenheim-Skolem number is the least cardinal K such that for any structure M satisfying a sentence phi, there is a substructure of M of cardinality less than K satisfying the same sentence phi.)

As such, the structure of the spectra of second-order logic can be quite complex. We discuss some closure properties of the collection of second-order spectra (and the spectra of some related logics). We also introduce iterated Löwenheim and Hanf numbers, and investigate their relation on the spectra of second-order logic and related logics.

Wed 20.11.2024, 12-14, C124

Siiri Kivimäki: Trees without cofinal branches

Abstract: I will discuss the motivation behind the study of trees without cofinal branches and address the question of existence of a universal such tree.

Wed 27.11.2024, C124

Matilda Häggblom: (Non)-axiomatizability results for extended inclusion atoms

Abstract: We consider implication problems for inclusion atoms with different syntactical restrictions. We also recall the axiomatizations for exclusion atoms and their approximate variant, highlighting the importance of carefully considering syntactical restrictions on, e.g., repetitions of variables.

We recall positive axiomatization results for inclusion atoms and present an alternative completeness proof, such that the result in the propositional setting is immediate. We discuss that this can not always be expected, since any potential complete system for propositional exclusion atoms necessarily extends their first-order system. We then define variants of extended inclusion atoms by relaxing the syntax and prove that a finite axiomatization can no longer exist. 

Wed 04.12.2024, 12-14, C124

Sylvain Cabanacq: Several theories for a same concept: the categorical approach to semantic contents

Whether we think of a group as an L-structure, with L = < . , -1 >, or as an L‘-structure, with L’ = < . , / , e >, we have the same concept in mind in both cases. Behind the infinite diversity of signatures thus appears the unity of the structural concept, and the limits of formal language in characterising mathematical concepts are revealed. But is it possible to define a concept without introducing, as model theory does, the arbitrariness of the choice of signature?

Since 1963 and Bill Lawvere's thesis, category theory has taken up this question and proposed different forms of invariants for formal presentations. The aim of this talk is to present these different notions derived from categorical logic and the work of Lawvere, Makkai and Ehresmann, the main results that are connected to them and the epistemological implications of such an approach, concerning for example the distinction between syntax and semantics.

Wed 11.12.2024, 12-14, C124

Boban Velickovic: Magidor Malitz quantifier 

In 1977 Magidor and Malitz introduced a quantifier Q^n, for n < \omega, and studied the logic obtained by adding these quantifiers to first order logic. The standard interpretation is the following: Q^n x_1,\ldots, x_n \phi(x_1,…,x_n) holds iff there is an uncountable set X such that for all n-tuples of distinct elements a_1,…,a_n \in X the formula \phi (a_1,…,a_n) holds.  They show that the logic L(Q^{</omega}) obtained by adding all the Q^n’s to first order logic satisfied the countable compactness theorem assuming the set theoretic principle \Diamond.  We give a set theoretic presentation of this and some related results by using an iterated ultra power construction. 

Wed 18.12.2024, Exam week (no seminar)