Virtual Gathering, Joint Mathematics Meeting, January 8–9, 2021

The 2021 Winter Meeting of the Association of Symbolic Logic was held online on January 7–8, 2020 in conjunction with the annual Joint Mathematics Meetings. The members of the Program Committee were Chris Laskowski, Antonio Montalbán (Chair) and Anush Tserunyan. The program consisted of seven invited 50-minute talks and two contributed talks. There was a co-sponsored AMS–ASL Special Session Computability Theory and Effective Mathematics organized by Jun Le Goh, Joe Miller, and Mariya Soskova on Thursday, January 7th.

The 50-minute invited addresses at the ASL meeting were as follows:

Dana Bartosova (University of Florida), Interactions between dynamics and algebraic operation.

Anton Bernshteyn (Georgia Institute of Technology), Descriptive combinatorics and distributed algorithms.

Barbara Csima (University of Waterloo), Understanding frameworks for priority arguments in computability theory.

Gabriel Conant (University of Cambridge), Model theoretic tameness in multiplicative combinatorics.

Russell Miller (Queens College and CUNY Graduate Center), Computable structure theory with noncomputable structures.

Christian Rosendal (University of Illinois at Chicago), Groups with bounded geometry.

Charles Steinhorn (Vassar College), Asymptotic and multidimensional asymptotic classes of finite structures.

Abstracts of the invited talks and contributed talks given by members of the Association for Symbolic Logic follow.

For the Program Committee

Antonio Montalbán

Abstracts of invited talks

▸DANA BARTOŠOVÁ Non-metrizable universal minimal flows.

University of Florida, USA.

E-mail: dbartosova@ufl.edu.

For a topological group G, a continuous action of G on a compact Hausdorff space is called a G-flow. A G-flow is minimal if every orbit is dense. The universal minimal G-flow has every minimal G-flow as a quotient and it is unique up to an isomorphism of flows. Universal minimal flows of infinite-dimensional groups have received considerable attention in the past 15 years due to their connection with finite combinatorics. On the other hand, locally compact, non-compact groups have non-metrizable universal minimal flows, which means the failure of the finitary combinatorial principles. However, other methods are available for locally compact groups and we encounter interesting connections with set theory in our investigation of discrete groups and their products.

This is in part a joint work with Aleksandra Kwiatkowska.

▸ ANTON BERNSHTEYN, Descriptive combinatorics and distributed algorithms.

School of Mathematics, Georgia Institute of Technology, Atlanta, GA, USA.

E-mail: bahtoh@gatech.edu

Descriptive combinatorics is the study of combinatorial problems (such as graph coloring) under additional topological or measure-theoretic regularity restrictions. It turns out that there is a close relationship between descriptive combinatorics and distributed computing, i.e., the area of computer science concerned with problems that can be solved efficiently by a decentralized network of processors. In this talk, I will outline this relationship and present a number of applications.

▸GABRIEL CONANT, Model theoretic tameness in multiplicative combinatorics.

University of Cambridge, Cambridge, UK.

E-mail: gconant@maths.cam.ac.uk

In combinatorics, an “inverse theorem” is a result inwhichmathematical objects exhibiting approximate structure are proved to be close to objects that are perfectly structured. A celebrated example is the structure theorem for approximate subgroups due to Breuillard et al. [1], which built on work of Hrushovski [4].

This talk is about related results in the context of model-theoretic tameness. For example, Martin-Pizarro et al. [5] showed that under a local stability assumption, a finite approximate subgroup can be approximated by a bounded number of cosets of a finite subgroup, up to error ε > 0. Their proof combines local stability theory with the stable arithmetic regularity lemma for finite groups due to Conant et al. [2], but gives ineffective bounds. I will first discuss a new proof of this result, which yields polynomial bounds in 1/ε. This also provides the first quantitative account of stable arithmetic regularity for arbitrary finite groups, and improves the previous exponential bound in the abelian case (due to Terry and Wolf [6,7]). I will then describe joint work with Pillay on analogous qualitative results in the setting of bounded VC-dimension, which is motivated by previous work on NIP arithmetic regularity [3].

[1] Emmanuel Breuillard, Ben Green, and Terence Tao, The structure of approximate groups, PublicationsMathématiques. Institut de Hautes Études Scientifiques, vol. 116 (2012), pp. 115–221.

[2] G. Conant, A. Pillay, and C. Terry, A group version of stable regularity, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 168 (2020), no. 2, pp. 405–413.

[3]____, Structure and regularity for subsets of groups with finite VC-dimension, Journal of the European Mathematical Society, to appear.

[4] Ehud Hrushovski, Stable group theory and approximate subgroups, Journal of the American Mathematical Society , vol. 25 (2012), no. 1, pp. 189–243.

[5] Amador Martin-Pizarro, Daniel Palacín, and Julia Wolf, A model-theoretic note on the Freiman-Ruzsa theorem, Preprint, 2019. arXiv:1912.02883

[6] C. Terry and J. Wolf, Stable arithmetic regularity in the finite field model, Bulletin of the London Mathematical Society , vol. 51 (2019), no. 1, pp. 70–88.

[7]____,Quantitative structure of stable sets in finite abelian groups, Transactions of the American Mathematical Society , vol. 373 (2020), no. 6, pp. 3885–3903.

▸ BARBARA CSIMA, Understanding frameworks for priority arguments in Computability Theory.

Department of Pure Mathematics, University of Waterloo, Waterloo, ON N2L 3G1, Canada.

E-mail: csima@uwaterloo.ca

Priority arguments are a common proof technique used in Computability Theory. A theorem is broken down to being equivalent to a list of requirements. These requirements are given a priority order, and a strategy is devised to meet all the requirements, making use of the priority order.

Those who know a Computability Theorist know that we love our priority arguments! In this talk, we will discuss why Computability Theory lends itself so well to this proof technique, and discuss at a high level the types of strategies used in priority arguments.

As soon as one first learns of priority arguments, one asks, can we save repeating ourselves, and have a framework for this? In this talk, we will discuss, again at a high level, existing frameworks for priority arguments, with a particular focus on Ash’s $\alpha$ -systems and Montalban’s $\eta$ -systems. We discuss the general idea of how the frameworks work, their power, and their limitations.

▸RUSSELL MILLER, Computable structure theory with noncomputable structures.

Department of Mathematics, Queens College, 65-30 Kissena Blvd., Queens, NY 11367. CUNY Graduate Center, 365 Fifth Avenue, New York, NY 10016, USA.

E-mail: Russell.Miller@qc.cuny.edu

From its inception, computable model theory has been based on the notion of a computable structure: a structure with domain $\omega$ (or a computable subset of $\omega$ ) whose functions, relations, and constants can all be computed effectively by Turing machines. This notion, which arose in both the Western and Russian schools, enables a logician to focus on the complexity of various aspects of these structures—new relations on them, isomorphisms between them, interpretations of one structure in another—without allowing distractions from complexities that could be baked into the structure, such as an unorthodox choice of domain or a deliberate obfuscation of a symbol in the signature.

However, there is another means of achieving the same end: one can treat the atomic diagram of the structure as an oracle, via a Gödel coding that turns it into a subset of. (The structure is still required to have domain $\omega$ .) Perhaps this oracle is not itself computable, but if it is provided this way, one can then ask which aspects of the structure can be computed by a Turing functional endowed with such an oracle. On its face, this distinction seems unlikely to yield results much different from those using traditional computable structures. Surprisingly, though, many properties that were quite complex under the traditional approach become far more tractable and recognizable when oracles for noncomputable structures are considered this way. If anything, the presence of noncomputable structures makes life easier! We will provide several examples of this phenomenon, due to many researchers, illustrating them so that they will be accessible even to logicians with no background in this area.

▸CHRISTIAN ROSENDAL, Groups with bounded geometry.

Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, 851 S. Morgan St., Chicago, IL 60607, USA.

E-mail: rosendal.math@gmail.com

Topological and, in particular, Polish groups with bounded geometry form a near perfect geometric generalization of the locally compact second countable groups. With outset in the recently developed framework for geometric group theory for general topological groups, we shall present a number of results about this specific subclass of Polish groups with a particular focus on coarse embeddings, equivalences and topological couplings.

▸CHARLES STEINHORN, Asymptotic and multidimensional asymptotic classes of finite structures.

Department of Mathematics and Statistics, Vassar College, 124 Raymond Ave., Poughkeepsie, NY 12604, USA.

E-mail: steinhorn@vassar.edu

Asymptotic classes of finite structures and measurable structures were introduced by Macpherson and the speaker in an effort to develop a model theory for classes of finite structures that reflects contemporary infinite model theoretic themes. This talk surveys work on that topic, including contributions of several others, and on current research that generalizes those concepts to what are called multidimensional asymptotic classes and generalized measurable structures. This most recent work is joint with Macpherson, Anscombe and Wolf.

Abstracts of contributed talks

▸KATALIN BIMBÓ AND J. MICHAEL DUNN, Entailment and (restricted) mingle.

Department of Philosophy, University of Alberta, 2–40 Assiniboia Hall, Edmonton, AB T6G2E7, Canada.

E-mail: bimbo@ualberta.ca

URL: www.ualberta.ca/~bimbo

Luddy School of Informatics, Computing and Engineering, and Department of Philosophy, Indiana University, 901 East Tenth Street, Bloomington, IN 47408, USA.

E-mail: dunn@indiana.edu

The logic of entailment ( ${E}_{\to }$ ) was formulated as a sequent calculus by Kripke [3]. $RM$ , the (full) logic of relevant implication with ( $M$ ), the mingle axiom $A\to \left(A\to A\right)$ has been thoroughly investigated in the literature. ${E}_{\to }$ can be (non-equivalently) extended with ( $M$ ) or ( $\overrightarrow{M}$ ), the restricted mingle axiom $\left(A\to B\right)\to \left(\left(A\to B\right)\to \left(A\to B\right)\right)$ . Anderson and Belnap [1, p. 94] posed the question (attributing it to S. McCall) whether ${E}_{\to }={R}_{\to}\cap E{\overrightarrow{M}}_{\to }$ . We use a modal extension of ${M}_0$ [1, p. 253] along the lines of [2], and following the ideas of Meyer, we show that ${E}_{\to}\ne {R}_{\to}\cap E{\overrightarrow{M}}_{\to }$ . We also consider a version of the problem with ( $M$ ), and we use a counter example to prove that ${E}_{\to}\ne {R}_{\to}\cap {EM}_{\to }$ .

[1] A. R. Anderson and N. D. Belnap, Entailment. The Logic of Relevance and Necessity , Princeton University Press, Princeton, NJ, 1975.

[2] J. M. Dunn, The algebra of intensional logics , PhD Thesis, University of Pittsburgh, 1966, (Logic PhDs, v. 2, College Publications, London, 2019).

[3] S. A. Kripke, The problem of entailment (abstract), The Journal of Symbolic Logic , vol. 24 (1959), p. 324.

▸JOACHIM MUELLER-THEYS, Named Model Theory.

Kurpfalzstr. 53, 69 226 Heidelberg, Germany.

E-mail: mueller-theys@gmx.de

Let $L$ be any first-order language. We call an $L$ -structure $\mathrm{\mathcal{M}}$ with domain $M\ne \emptyset$ (completely) named :iff for all $a\in M$ there is a closed $L$ -term $t$ such that $a={t}^{\mathrm{\mathcal{M}}}$ , where ${t}^{\mathrm{\mathcal{M}}}$ is the usual $\mathrm{\mathcal{M}}$ -interpretation of $t$ .

$\mathrm{\mathcal{M}}{\sqsubseteq}_{id}\mathcal{N}$ :iff $\mathrm{\mathcal{M}}\models t\doteq s$ implies $\mathcal{N}\models t\doteq s$ for all closed $t$ , $s$ . If $\mathrm{\mathcal{M}}$ is named and $\mathrm{\mathcal{M}}{\sqsubseteq}_{\mathrm{id}}\mathcal{N}$ , then for all $a\in M$ there is one and only one $\beta \left[a\right]:= b\in N$ such that $a={t}^{\mathrm{\mathcal{M}}}$ and $b={t}^{\mathcal{N}}$ for some closed $t$ . If $\mathcal{N}$ is named as well, $\beta:M\to N$ is surjective. If $\mathrm{\mathcal{M}}$ is named and $\mathrm{\mathcal{M}}{\equiv}_{\mathrm{id}}\mathcal{N}$ , $\beta$ is injective. If $\mathrm{\mathcal{M}}$ , $\mathcal{N}$ are named both and $\mathrm{\mathcal{M}}{\equiv}_{\mathrm{id}}\mathcal{N}$ , $\beta$ is bijective.

$\mathrm{\mathcal{M}}{\sqsubseteq}_{at}\mathcal{N}$ :iff $\mathrm{\mathcal{M}}\models \alpha$ implies $\mathcal{N}\models \alpha$ for all atomic sentences. If $\mathrm{\mathcal{M}}$ is homomorphic to $\mathcal{N}$ , $\mathrm{\mathcal{M}}{\sqsubseteq}_{\mathrm{at}}\mathcal{N}$ . Conversely, if $\mathrm{\mathcal{M}}$ is named and $\mathrm{\mathcal{M}}{\sqsubseteq}_{\mathrm{at}}\mathcal{N}$ , then $\mathrm{\mathcal{M}}{\simeq}_{\beta}\mathcal{N}$ . If $\mathcal{N}$ is named as well, $\beta$ is an epimorphism. Epimorphy maintains namedness. If $\mathrm{\mathcal{M}}$ is named and $\mathrm{\mathcal{M}}{\equiv}_{\mathrm{at}}\mathcal{N}$ , $\beta$ will be a monomorphism. Eventually, if $\mathrm{\mathcal{M}}$ , $\mathcal{N}$ are named both and $\mathrm{\mathcal{M}}{\equiv}_{\mathrm{at}}\mathcal{N}$ , $\mathrm{\mathcal{M}}{\cong}_{\beta}\mathcal{N}$ . In particular, named algebras are isomorphic if they satisfy the same closed equations.

Consider, e.g., some arithmetical language ${L}_{\mathrm{ar}}$ with the standard model ${\mathcal{N}}_{\mathrm{ar}}$ named. If $\mathcal{N}$ is any named ${L}_{\mathrm{ar}}$ -structure having the same atomic theory as ${\mathcal{N}}_{ar}$ , then $\mathcal{N}\cong {\mathcal{N}}_{ar}$ .

Let $\lambda$ range over atomic and negated-atomic sentences. $\mathrm{\mathcal{M}}{\sqsubseteq}_{bas}\mathcal{N}$ :iff $\mathrm{\mathcal{M}}\models \lambda$ implies $\mathcal{N}\models \lambda$ for all $\lambda$ . $\mathrm{\mathcal{M}}{\sqsubseteq}_{\mathrm{bas}}\mathcal{N}$ implies $\mathrm{\mathcal{M}}{\equiv}_{\mathrm{at}}\mathcal{N}$ . ${\Lambda}_{\mathrm{\mathcal{M}}}:= \left\{\lambda:\mathrm{\mathcal{M}}\models \lambda \right\}$ is called the basic theory of $\mathrm{\mathcal{M}}$ . $\mathcal{N}\models {\Lambda}_{\mathrm{\mathcal{M}}}$ implies $\mathrm{\mathcal{M}}{\sqsubseteq}_{\mathrm{bas}}\mathcal{N}$ . $\mathrm{\mathcal{M}}\kern0.5em \mid \equiv \sigma$ :iff $\mathrm{\mathcal{M}}$ is named and $\mathrm{\mathcal{M}}\models \sigma$ (named satisfaction). Now $\mathcal{N}\kern0.5em \mid \equiv {\Lambda}_{\mathrm{\mathcal{M}}}$ implies $\mathcal{N}\cong \mathrm{\mathcal{M}}$ provided that $\mathrm{\mathcal{M}}$ is named.

$\Sigma \kern0.5em \mid \equiv \sigma$ :iff $\mathrm{\mathcal{M}}\kern0.5em \mid \equiv \Sigma$ implies $\mathrm{\mathcal{M}}\kern0.5em \mid \equiv \sigma$ for all $\mathrm{\mathcal{M}}$ (named consequence). $\mathrm{\mathcal{M}}\kern0.5em \mid \equiv \sigma$ implies ${\Lambda}_{\mathrm{\mathcal{M}}}\kern0.5em \mid \equiv \sigma$ . If $\mathrm{\mathcal{M}}$ is named, ${\Lambda}_{\mathrm{\mathcal{M}}}\kern0.5em \mid \equiv \sigma$ iff $\mathrm{\mathcal{M}}\models \sigma$ . As a corollary, ${\Lambda}_{\mathrm{ar}}\kern0.5em \mid \equiv \sigma$ iff ${\mathcal{N}}_{\mathrm{ar}}\models \sigma$ , where ${\Lambda}_{ar}:= {\Lambda}_{{\mathcal{N}}_{\mathrm{ar}}}$ is the basic arithmetical theory.

A detailed elaboration of these results with proofs is found in the paper “Named Model Theory.” One of the further topics: reduction to propositional logics, has been already indicated in the abstract: “The idea of Named Logic” (2020 ASL Annual Meeting, (Long) Program, pp. 32–33) (to appear in The Bulletin of Symbolic Logic ).

Recently, Peter Maier-Borst uttered the idea to generalise the approach. Indeed, $L$ -structures $\mathrm{\mathcal{M}}$ that are not completely named can be identified with certain named $\hat{L}$ -expansions $\hat{\mathrm{\mathcal{M}}}$ of them. Thence $\mathcal{N}\cong \mathrm{\mathcal{M}}$ if $\mathcal{N}$ has a named $\hat{L}$ -expansion $\hat{\mathcal{N}}$ such that $\hat{\mathcal{N}}{\equiv}_{\mathrm{at}}\hat{\mathrm{\mathcal{M}}}$ . Moreover, the basic theory of $\hat{\mathrm{\mathcal{M}}}$ axiomatizes the theory of $\mathrm{\mathcal{M}}$ .

Named semantics may be canonized, as any named structure will be isomorphic to some term interpretation.

Let $L$ be such that ${\mathrm{CT}}_L\ne \emptyset$ and the number of relation symbols are finite. We call named $L$ -structures finitary then. Finitary structures describe a huge class of data structures. $\mid \kern0em {\equiv}_{fin}\sigma$ :iff $\mathrm{\mathcal{M}}\mid \equiv \sigma$ for all $L$ -structures $\mathrm{\mathcal{M}}$ . Unlike finite first-order validity (Trachtenbrot’s Theorem), finitary validity will even be decidable.