Contributed Talks 21
Chair: Ivan Di Liberti
Time allocation: 20 minutes per speaker; 5 minutes for each changeover
Talks in this session
16:30 
Kerkko Luosto, On the hierarchy of vectorizations of the Härtig quantifier 
A commonly used slogan in finite model theory is that the first order logic cannot count. A simple manifestation of this is that equicardinality, i.e., that two definable sets have the same power, is not definable in first order logic. A minimal way to overcome this shortcoming (simultaneously preserving the regularity of the logic) is to enhance first order logic by the equicardinality, or Härtig, quantifier \(\mathsf{I}\), with the assiocated semantic rule \(\mathfrak{M}\models \mathsf{I}xy\;(U(x),V(y)) \text{ if and only if } U^{\mathfrak{M}}=V^{\mathfrak{M}},\) introduced by Klaus Härtig in 1965 [1], leading to the logic \(\mathsf{FO(I)}\). However, being able to express equicardinality of sets does not result in being able to express equicardinality of \(n\)ary relations. Indeed, Risto Kaila showed in [2] that the \((n+1)^\mathrm{th}\) vectorization \(\mathsf{I}^{(n+1)}\) of the Härtig quantifier is not expressible in the logic \(\mathsf{FO}(\mathsf{I}^{(n)})\). Unfortunately, Kaila presented only the construction of the needed structures and left the tedious calculations for the reader. I shall revisit Kaila’s hierarchy result, presenting a novel proof. The construction is simplified, so that the cardinalities of definable relations will be polynomials of two integer parametres. Working in the polynomial ring \(\mathbb{Z}[x,y]\), I shall find values for the parametres that give the desired undefinability result. I expect that this kind of algebraic techniques can be applied in similar situations in quantifier definability theory in the future. Bibliography


16:55 
Tomáš Hons, Firstorder limits and rooted inverse problems 
Authors: David Hartman, Tomáš Hons and Jaroslav Nešetřil The field of graph convergence studies asymptotic properties of large graphs with the goal to define a wellbehaved notion of a limit structure for a convergent sequence of graphs. The two most prominent types of convergence are defined for sequences of dense and sparse graphs. These were recently unified by Nešetřil and Ossona de Mendez into a common framework called firstorder convergence using the expressive power of firstorder logic. Moreover, the flexibility of this framework has since led to studies of convergence for other structures, such as matroids and mappings. An important problem in the field is which objects can actually be approximated by finite structures, that is, to arise as a limit. This seems to be a very difficult problem (cf. AldousLyons conjecture). We thus restrict ourselves to a simplified problem to approximate vertices of the limit object, which we call rooted inverse problem. This can be viewed as an attempt to trace the origin of limit’s vertices to the finite structures. The rooted inverse problem was first defined by Nešetřil and Ossona de Mendez and answered negatively in general by Christofides and Král’. However, they also proved that almost all vertices of the limit can be approximated. Later, we proved that this includes algebraic vertices. Here we show that all vertices of the limit can be approximated given that the limit is sparse enough. We conjecture that all the vertices can be approximated if the limit is NIP. 

17:20 
Beibut Kulpeshov, On nonessential expansions of quite ominimal theories 
Authors: Beibut Kulpeshov and Sergey Sudoplatov The present lecture concerns the notion of weak ominimality originally studied by H.D. Macpherson, D. Marker and C. Steinhorn in [1]. A weakly ominimal structure is a linearly ordered structure \(M=\langle M,=,<,\ldots \rangle\) such that any definable (with parameters) subset of \(M\) is a finite union of convex sets in \(M\). Quite ominimal theories were introduced in [2]. Let \(T\) be a weakly ominimal theory, \(M\models T\), \(A\subseteq M\), \(p,q\in S_1(A)\) nonalgebraic. We say that \(p\) is quite orthogonal to \(q\) (\(p\perp^q q\)) if there is no \(A\)–definable bijection \(f: p(M)\to q(M)\). We say that a weakly ominimal theory is quite ominimal if the notions of weak and quite orthogonality coincide for 1types over arbitrary subsets of models of the given theory. Theorem. Let \(T\) be a quite ominimal Ehrenfeucht theory, \(M\) be a countable saturated model of \(T\). Then for every \(n<\omega\) and any \(\bar a=\langle a_1, \ldots, a_n\rangle \in M\) the theory \(T_1=Th(\langle M, \bar a\rangle)\) also is quite ominimal and Ehrenfeucht. Moreover: \((1)\) if each \(a_i\) is a realization of an isolated or quasirational 1type over \(\emptyset\) then \(I(T_1,\omega)=I(T, \omega)\); \((2)\) if there exist \(1\le s\le n\) and \(1\le i_1<i_2<\ldots <i_s\le n\) such that \(a_{i_t}\) is a realization of an irrational 1type \(p_{i_t}\) over \(\emptyset\) for each \(1\le t\le s\) and the remaining \(a_w\) (i.e. \(w\ne i_t\) for each \(1\le t\le s\)) are realizations of isolated or quasirational 1types over \(\emptyset\) then \(I(T_1, \omega)=6^{m_Tl}3^{k_T+2l}\), where \(l=\dim\{p_{i_1}, p_{i_2}, \ldots, p_{i_s}\}\). This research has been funded by Science Committee of Ministry of Science and Higher Education of the Republic of Kazakhstan (Grant No. AP19674850), and in the framework of the State Contract of the Sobolev Institute of Mathematics, Project No. FWNF20220012. Bibliography


17:45 
Dariusz Kalociński, Scott ranks and intended models 
Certain mathematical theories are about a single, socalled intended, structure (e.g., arithmetic is about natural numbers) while others investigate general properties of all structures they axiomatize (e.g., group theory). The former theories are known as nonalgebraic, while the latter as algebraic. One of the problems in the philosophy of mathematics concerns a systematic explanation of this phenomenon, ideally providing a theoretical notion that could explicate the concept of intendedness. I will briefly review some of the existing philosophical approaches regarding arithmetic, including the work of Halbach and Horsten [1], Button and Smith [2] and Walter Dean [3], among others. In the main part of my talk I will suggest a novel perspective on this problem, based on the measures of complexity of models, such as Scott ranks. I will try to explain basic technicalities involved in this notion and illustrate how it deals with the problem at hand with a few examples of algebraic as well as nonalgebraic theories, including PA (by leveraging results from [4]) and weaker systems like Robinson’s or Presburger’s arithmetic. Bibliography
