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

1. Klaus H{ä}rtig,{"U}ber eine Quantifikator mit zwei Wirkungsbereiche, Colloquiumon the foundations of Mathematics, Mathematical Machinesand their Applications (1965), 31–36, Akad. Kiad'{o}, Budapest.
2. Risto Kaila,On probabilistic elimination of generalized quantifiers,Random Structures Algorithms 19 (2001), no. 1,pp. 1–36.

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 well-behaved 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 first-order convergence using the expressive power of first-order 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. Aldous-Lyons 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.

Authors: Beibut Kulpeshov and Sergey Sudoplatov

The present lecture concerns the notion of weak o-minimality originally studied by H.D. Macpherson, D. Marker and C. Steinhorn in [1]. A weakly o-minimal 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 o-minimal theories were introduced in [2]. Let \(T\) be a weakly o-minimal theory, \(M\models T\), \(A\subseteq M\), \(p,q\in S_1(A)\) non-algebraic. 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 o-minimal theory is quite o-minimal if the notions of weak and quite orthogonality coincide for 1-types over arbitrary subsets of models of the given theory.

Theorem. Let \(T\) be a quite o-minimal 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 o-minimal and Ehrenfeucht. Moreover:

\((1)\) if each \(a_i\) is a realization of an isolated or quasirational 1-type 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 1-type \(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 1-types over \(\emptyset\) then \(I(T_1, \omega)=6^{m_T-l}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. FWNF-2022-0012.

Bibliography

1. H.D. Macpherson, D. Marker, and C. Steinhorn,shape Weaklyo-minimal structures and real closed fields, shape Transactionsof the American Mathematical Society, Vol. 352, No. 12 (2000), pp. 5435–5483.
2. B.Sh. Kulpeshov, shape Convexity rank and orthogonality in weakly o-minimaltheories, shape News of the National Academy of Sciences of the Republic of Kazakhstan,physical and mathematical series, Vol. 227 (2003), pp. 26–31.

Certain mathematical theories are about a single, so-called 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 non-algebraic, 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 non-algebraic theories, including PA (by leveraging results from [4]) and weaker systems like Robinson’s or Presburger’s arithmetic.

Bibliography

1. Volker Halbach and Leon Horsten,Computational Structuralism,Philosophia Mathematica,vol. 13 (2005), no. 2, pp. 174–186.
2. Tim Button and Peter Smith,The philosophical significance of {Tennenbaum}’s theorem,Philosophia Mathematica,vol. 20 (2012), no. 1, pp. 114–121.
3. Walter Dean,Models and computability,Philosophia Mathematica,vol. 22 (2014), no. 2, pp. 143–166.
4. Antonio Montalbán and Dino Rossegger,The structural complexity of models of arithmetic,The Journal of Symbolic Logic,(2023), pp. 1–17.