2022 NORTH AMERICAN ANNUAL MEETING OF THE ASSOCIATION FOR SYMBOLIC LOGIC Cornell University Ithaca, NY, USA April 7–10, 2022

The 2022 North American Annual Meeting of the Association for Symbolic Logic was held at Cornell University in Ithaca, New York, April 7–10, 2022. There were eight plenary talks, one tutorial, the Retiring Presidential Address, six special sessions, four sessions of contributed talks, and two panel discussions. A welcoming reception was held on the evening of Thursday, April 7.

The program committee consisted of Wesley Calvert, Valentine Kabanets, Justin Moore, Rehana Patel, Sanford Shieh, and Jindrich Zapletal (chair). The local organizing committee consisted of Bob Constable, Harold Hodes, Alexander Kocurek, Dexter Kozen, Justin Moore (chair), Anil Nerode, and Slawomir Solecki.

There were 113 registered participants at the meeting, of which 46 were graduate students. Generous financial support was provided by the Association for Symbolic Logic, the National Science Foundation, and Cornell University.

There were eight plenary addresses at the meeting.

• Will Boney (Texas State University), Compactness of strong logics and large cardinals.

• Juliet Floyd (Boston University), Turing and Wittgenstein.

• Meng-Che (Turbo) Ho (California State University, Northridge), Small cancellation groups in logic.

• Michael Hrušák (Universidad Nacional Autónoma de México), Ultrafilters, MAD families, and the Katětov order.

• Jerome Keisler (University of Wisconsin), Model theory for non-metric structures.

• Alexander Razborov (University of Chicago), Continuous combinatorics.

• Robin Tucker-Drob (University of Florida), Treeability and planarity in measured group theory.

• Avi Wigderson (Institute for Advanced Studies), The value of errors in proofs (a fascinating journey from Turing’s 1936 seminal R  $\ne$  RE to the 2020 breakthrough of MIP ${}^{\ast }$  = RE).

There was one tutorial, consisting of three 1-hour sessions.

• Isaac Goldbring (University of California, Irvine), The Connes Embedding Problem, $\kern0.1em {MIP}^{\ast}= RE\!$ , and model theory.

The Retiring Presidential Address was given by Julia Knight.

• Julia Knight (University of Notre Dame), Generalizing a question of Gromov.

The program included two panel discussions on Mathematical logic in the pandemic era, organized by Johanna Franklin and Deirdre Haskell. The speakers in the first panel were Hélène Barcelo, Tomek Bartoszynski, and Elvira Mayordomo, and the speakers in the second panel were Philipp Hieronymi, Joel Ronnie Nagloo, Christopher Porter, and Caroline Terry. A description of the panel is given below in the abstracts section.

The program included six special sessions held in parallel (with the organizers listed in parentheses): Computability Theory (Antonio Montalbán), History, and Philosophy of Logic (Lydia Patton), Homotopy Type Theory (Emily Riehl), Logic and Machine Learning (James Freitag and Valentina Harizanov), Models of Peano Arithmetic (Roman Kossak), and Set Theory (Slawomir Solecki). There were 12 contributed talks delivered at the meeting.

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

For the Program Committee

Jindrich Zapletal

Abstract of the Retiring Presidential Address

▸ JOHANNA FRANKLIN, MENG-CHE (TURBO) HO, AND JULIA F. KNIGHT, Generalizing a question of Gromov.

Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556, USA.

E-mail: [email protected].

Gromov asked “What is a typical group?” He was thinking of finitely presented groups. He proposed an approach involving limiting density. In 2013, the third author conjectured that for elementary first order sentences $\varphi$ , and for groups with $n$ generators ( $n\ge 2$ ) and a single relator, the limiting density of the groups satisfying $\varphi$ always exists, with value $0$ or $1$ , and the value is $1$ iff $\varphi$ is true in the non-abelian free groups. The conjecture is still open, but there are partial results by Kharlampovich and Sklinos and by Coulon, Ho, and Logan. We ask about structures in other equational classes. What sentences are true in the typical structure? We give examples illustrating different possible behaviors. In particular, for abelian groups given by presentations with a single generator and a single relator, the analogue of the conjecture fails—we find sentences for which the limiting density does not exist, and sentences for which the limiting density has value strictly between $0$ and $1$ . Focusing on languages with just finitely many unary function symbols, we prove a result with conditions sufficient to guarantee that the analogue of the conjecture holds. The proof uses a version of Gaifman’s Locality Theorem, plus ideas from random group theory and probability.

Abstract of invited tutorial

▸ ISAAC GOLDBRING, The Connes Embedding Problem, ${MIP}^{\ast}= RE\!$ , and model theory.

Department of Mathematics, University of California, Irvine, 340 Rowland Hall, Irvine, CA 92697, USA.

E-mail: [email protected].

URL Address: https://www.math.uci.edu/isaac/.

The Connes Embedding Problem is one of the most famous open problems in the theory of von Neumann algebras and can be stated in purely model-theoretic terms: do all II ${}_1$ factors have the same universal theory? Here, a II ${}_1$ factor is an infinite-dimensional von Neumann algebra that admits a trace and has trivial center. Since its formulation in Alain Connes’ seminal paper [1], the Connes Embedding Problem’s notoriety has increased through a plethora of nontrivial reformulations spanning a wide variety of areas of mathematics, including C*-algebras, quantum information theory, free probability, noncommutative real algebraic geometry, group theory, and, more recently, continuous model theory.

In early 2020, a group of computer scientists announced a groundbreaking result in the field of quantum complexity known as ${MIP}^{\ast}= RE$ [5], asserting that the collection of languages (in the sense of complexity theory) that can be reliably verified by a verifier interacting with a pair of provers sharing an entangled quantum state coincides with the class of recursively enumerable languages. Besides being intrinsically fascinating, this result yields, as a corollary, a negative solution to the Connes Embedding Problem! However, the path from ${MIP}^{\ast}= RE$ to the resolution of the Connes Embedding Problem is quite difficult and involves deep detours in C*-algebra theory and quantum information theory.

In these tutorials, I will carefully describe the statements of the Connes Embedding Problem and ${MIP}^{\ast}= RE$ and briefly describe the “standard” derivation of the negative solution of the former using the latter. I will then describe a more elementary derivation of this implication using methods from continuous model theory; this part of the tutorial represents joint work with Bradd Hart [3, 4]. The key tools from continuous model theory being used here are a continuous version of the Completeness Theorem as well as the theory of definable sets in continuous model theory. I will also describe how the model theoretic approach offers extra information, including a Gödelian style refutation of the Connes Embedding Problem as well as the existence of infinitely many distinct universal theories of II ${}_1$ factors.

Time permitting, I will also discuss the basic outline of the proof of ${\mathrm{MIP}}^{\ast}=\mathrm{RE}$ as well as a model-theoretic variant of the Connes Embedding Problem, namely the existence of the enforceable II ${}_1$ factor, which still remains open.

I will not presuppose any knowledge of operator algebras or complexity theory in these tutorials. Most if not all of the material to be presented can be found in the survey article [2].

[1] A. Connes, Classification of injective factors. Cases ${\mathrm{II}}_1$ , ${\mathrm{II}}_{\infty }$ , ${\mathrm{III}}_{\lambda }$ , $\lambda \ne 1$ . Annals of Mathematics , vol. 74 (1976), pp. 73–115.

[2] I. Goldbring, The connes embedding problem: a guided tour, preprint, 2021, arXiv:2109.12682 .

[3] I. Goldbring and B. Hart, A computability-theoretic reformulation of the Connes Embedding Problem, this Journal, vol. 22 (2016), pp. 238–248.

[4] ———, The universal theory of the hyperfinite II ${}_1$ factor is not computable, preprint, 2021, arXiv:2006.05629.

[5] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen, ${\mathrm{MIP}}^{\ast}=\mathrm{RE}$ , preprint, 2020, arXiv:2001.04383.

Abstracts of invited plenary lectures

▸ WILL BONEY, Compactness of strong logics and large cardinals.

Department of Mathematics, Texas State University, 601 University Drive, San Marcos, TX, USA.

E-mail: [email protected].

URL Address: https://wboney.wp.txstate.edu/.

Connections between large cardinals in set theory and compactness principles of strong logics in model theory have a long history, going back to Tarski (compact cardinals), Magidor (extendibles), and Benda (supercompacts). We discuss several recent advances, including connecting omitting types and normal ultrafilters; sort logic and ${C}^{(n)}$ -cardinals; abstract Henkin models and Woodin cardinals; and virtual logic and virtual large cardinals. Additionally, this work has connections to category theory.

This draws from joint work with Dimopoulos, Gitman, and Magidor and with Brooke-Taylor.

▸ JULIET FLOYD, Turing and Wittgenstein.

Department of Philosophy, Boston University, 745 Commonwealth Avenue, Boston, MA 02215, USA.

E-mail: [email protected].

A philosophical reconstruction of the mutual impact of Wittgenstein and Turing upon one another. Wittgensteinian features of Turing’s diagonal argumentation and machine-model of human computation in [2] may be discerned, especially when conjoined with Turing’s reference to Hobson’s Cambridge textbook on analysis [1]. This interplay of Cambridge traditions and ideas illuminates the path toward Turing’s machine-model of computation, deepens our understanding of Wittgenstein’s later philosophy of logic, and highlights the anti-psychologistic, yet pragmatist sides of Turing’s conception of the foundations of logic, including the Turing Test [3]. Some of Turing’s later work on types [5] was explicitly indebted to his having attended Wittgenstein’s Cambridge lectures in 1939 [6]. Wittgenstein in turn responded to Turing in his later philosophy, surrendering the ideal of a “gap free” presentation of logic to admit partial functions as basic, and incorporating into his mature philosophy of logic the ideas of forms of life and technique. These concepts are strikingly consonant with certain aspects of Turing’s subsequent writings about AI [4].

[1] E. W. Hobson, The Theory of Functions of a Real Variable and the Theory of Fourier’s Series, vol. I , Revised second ed., Cambridge University Press, 1921 .

[2] A. M. Turing, On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society , vol. 2 (1936/1937), no. 42, pp. 230–265.

[3] ———, Computing machinery and intelligence. Mind , vol. 59 (1950), pp. 433–460.

[4] ———, Intelligent Machinery (1948), Alan Turing: His Work and Impact (B. S. Cooper and J. van Leeuven, editors), North Holland/Elsevier Science, Amsterdam, 2013, pp. 107–128.

[5] ———, The Reform of Mathematical Notation and Phraseology (1944/45), Alan Turing: His Work and Impact (B. S. Cooper and J. van Leeuven, editors), North Holland/Elsevier Science, Amsterdam, 2013, pp. 245–249.

[6] L. Wittgenstein, Wittgenstein’s 1939 Lectures on the Foundations of Mathematics: Cambridge 1939 (C. Diamond, editor), University of Chicago Press, 1989.

▸ MENG-CHE “TURBO” HO, Small cancellation groups in logic.

Department of Mathematics, California State University, Northridge, Northridge, CA 91330, USA.

E-mail: [email protected].

Small cancellation theory is developed by Greendlinger and later refined and generalized by Lyndon, Schupp, Olshanskii, and others. One of the first main results in small cancellation theory is Greendlinger’s lemma, which says the word problem of a small cancellation group can be solved by Dehn’s algorithm. Small cancellation theory is also used to construct many special groups, for instance, the Burnside groups and the Tarski’s monsters.

In this talk, we will start by introducing the definition and basic properties of a small cancellation group and some classical results. We will then discuss how they can be used to code computability information in groups. We will also discuss equations in small cancellation groups and their connection to the model theory of free groups.

▸ MICHAEL HRUŠÁK, Ultrafilters, MAD families and the Katětov order.

Centro de Ciencias Matemáticas, Universidad Nacional Autónoma de México, Campus Morelia, Mexico.

E-mail: [email protected].

We shall review recent results on the Katětov order on Borel ideals and its applications to classification of ultrafilters and maximal almost disjoint families on countable sets concentrating on open problems.

▸ H. JEROME KEISLER, Model theory for non-metric structures.

Department of Mathematics, University of Wisconsin–Madison, Madison, WI, USA.

E-mail: [email protected].

In the seminal paper “Model Theory for Metric Structures,” Ben Yaacov, Berenstein, Henson, and Usvyatsev, London Math. Society Lecture Note Series, vol. 350 (2008), pp. 315–427, introduced the modern version of continuous model theory, which has led to an explosion of research with many applications to analysis. In that paper, a metric signature is a set of constant, function, and predicate symbols including a binary predicate d for distance, and a bound of uniform continuity for each function and predicate symbol. A metric structure has a metric signature, a universe set M, and interpretations of the symbols that respect the uniform continuity bounds, where d is a complete metric and the predicates take values in the real unit interval [0,1].

Continuous model theory is often used to study objects that are not quite metric structures in the above sense. They may have predicates with unbounded values, fail to satisfy uniform continuity requirements, and so on. In some cases it is easy to convert the original object to a metric structure in a way that clarifies properties of the original object. But in other cases such a conversion will be very complicated or will obscure the original object too much.

A notion with less baggage than a metric structure is a [0,1]-valued structure, which has no distinguished metric and no continuity requirement on the functions and predicates. In the author’s paper “Model theory for real-valued structures,” to appear in “Beyond Second Order Model Theory,” CRC Press, edited by Jose Iovino (arXiv:2005.11851), it is shown (using a result called the expansion theorem) that almost all of the model theory of metric structures can be carried over in a systematic way to arbitrary [0,1]-valued structures.

The above paper was in part motivated by the idea that in some applications it will be easier to usefully convert an object to a [0,1]-valued structure than to a metric structure. The model theory of [0,1]-valued structures would be appropriate for such applications. It may happen that the [0,1]-valued structure is easily described, but any corresponding metric structure will have a complicated or unnatural metric. This lecture will expand on that idea and give some illustrative examples.

▸ ALEXANDER RAZBOROV, Continuous combinatorics.

Andrew McLeish Distinguished Service Professor, University of Chicago, Chicago, IL 60637, USA.

E-mail: [email protected].

Any increasing sequence of finite models of an universal theory in a relational signature contains a subsequence converging in a strictly defined sense to an analytical object. It turns out that these objects possess a rich and very helpful structure; in particular, they can be alternately described in many different ways using analytical, logical, algebraic, or statistical languages.

In this talk we will describe this theory using examples from combinatorics, logic, and other fields. Most of the talk will be devoted to the so-called “dense regime” in which the density of elementary predicates is assumed to be a constant in (0,1). Then, time permitting, we will also discuss recent applications, including the theory of quasi-randomness and connections to infinite Ramsey combinatorics via stability theory.

▸ ROBIN TUCKER-DROB, Treeability and planarity in measured group theory.

Department of Mathematics, University of Florida, Gainesville, FL 32611, USA.

E-mail: [email protected].

We show that several new classes of groups are measure strongly treeable, i.e., all of their free quasi-pmp actions are treeable. This includes all finitely generated groups admitting planar Cayley graphs, all finitely generated elementarily free groups, and more generally all groups arising as the fundamental group of an “IFL tower” over these groups. Our techniques also lead to new measure strong free factors of groups, i.e., group elements which generate a primitive subrelation in every free quasi-pmp action. This is based on joint work with Clinton Conley, Damien Gaboriau, and Andrew Marks.

▸ AVI WIGDERSON, The value of errors in proofs (a fascinating journey from Turing’s 1936 seminal R  $\ne$  RE to the 2020 breakthrough of MIP ${}^{\ast }$  = RE).

School of Mathematics, Institute for Advanced Study, Princeton, NJ, USA.

E-mail: [email protected].

Last year, a group of theoretical computer scientists posted a paper on the arXiv with the strange-looking title “MIP ${}^{\ast }$  = RE,” impacting and surprising not only complexity theory but also some areas of math and physics. Specifically, it resolved, in the negative, the “Connes’ embedding conjecture” in the area of von-Neumann algebras, and the “Tsirelson problem” in quantum information theory. You can find the paper here: https://arxiv.org/abs/2001.04383.

As it happens, both acronyms MIP ${}^{\ast }$ and RE represent proof systems, of a very different nature. To explain them, we’ll take a meandering journey through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modeling and classification (both problems and proofs) by algorithmic efficiency, naturally leads to the generation of new such notions and results. A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties.

The talk does not assume any special mathematical background.

Abstract of the Panel Discussions by the Organizers

▸ JOHANNA FRANKLIN AND DEIRDRE HASKELL, Mathematical logic in the pandemic era.

Department of Mathematics, Hofstra University, Hempstead, NY 11549, USA.

E-mail: [email protected].

Department of Mathematics, McMaster University, Hamilton, ON, Canada.

E-mail: [email protected].

The pandemic has affected all of us, but not affected us all equally. For some, it has been wonderful to hide away in a comfortable place at home with no distractions and really get some work done. But for others, that hide-away at home is filled with children, working spouses, caregiving responsibilities, and pivoting to online teaching. This panel is an opportunity for senior and junior logicians to air their concerns and to listen to each other’s experience. For the first session, we have three senior logicians with administrative responsibilities who can talk about how they assess quality in the current environment and how they see the pandemic affecting the future of the discipline. In the second session, four more junior logicians will share their experiences of job hunting, starting new jobs online, and maintaining their research programs.

Abstracts of invited talks in the Special Session on Computability Theory

▸ DAMIR D. DZHAFAROV, Some questions and observations about the structure of the Weihrauch degrees.

Department of Mathematics, University of Connecticut, Storrs, CT 06269, USA.

E-mail: [email protected].

The Weihrauch degrees, and their non-uniform analogue, the computable degrees, have seen much interest in computable analysis. More recently, they have also played a prominent role in computable combinatorics and reverse mathematics. Each class of degrees forms a lattice, and a number of papers have focused on their algebraic properties. In this talk, I will survey some known facts about these structures, and mention a few open questions. I will also present some new results concerning the density of the Weihrauch and computable lattices, which contrast with the situation in the related Medvedev/Muchnik lattices. This is joint work with Lerman, Patey, and Solomon.

▸ JUN LE GOH, Extensions of embeddings in the ${\Sigma}_2^0$ enumeration degrees.

Department of Mathematics, University of Wisconsin–Madison, 480 Lincoln Drive, Madison, WI 53706, USA.

E-mail: [email protected].

In order to measure the algorithmic content of partial functions, or the positive information content of subsets of the natural numbers, one can use the notion of enumeration reducibility. The associated degree structure, known as the enumeration degrees (e-degrees), forms a superstructure of the Turing degrees. We present ongoing work with Steffen Lempp, Keng Meng Ng, and Mariya Soskova on the algebraic properties of a countable substructure of the e-degrees, namely the ${\Sigma}_2^0$ e-degrees. The ${\Sigma}_2^0$ e-degrees are analogous to the computably enumerable (c.e.) Turing degrees but these structures are not elementarily equivalent as partial orders. Indeed, Ahmad [1] showed that there are incomparable ${\Sigma}_2^0$ e-degrees $\mathbf{a}$ and $\mathbf{b}$ such that if $\mathbf{c}<\mathbf{a}$ , then $\mathbf{c}<\mathbf{b}$ , implying that $\mathbf{a}$ cannot be expressed as the join of two degrees below it. This stands in contrast to Sacks’s splitting theorem for the c.e. Turing degrees.

One can view Ahmad’s result as a two-quantifier sentence in the language of partial orders which holds in the ${\Sigma}_2^0$ e-degrees. While it is easy to compute whether a given one-quantifier sentence is true in the ${\Sigma}_2^0$ e-degrees (because all finite partial orders embed), the corresponding task for two-quantifier sentences (which corresponds to an extension of embeddings problem) is not known to be algorithmically decidable. Towards solving this problem, we investigate the extent to which Ahmad’s result can be generalized. For instance, we [2] show that a natural generalization of Ahmad’s result to triples of ${\Sigma}_2^0$ e-degrees fails to hold: For any incomparable ${\Sigma}_2^0$ e-degrees $\mathbf{a}$ , $\mathbf{b}$ , and $\mathbf{c}$ , either there is some $\mathbf{d}$ such that $\mathbf{d}<\mathbf{a}$ and, or there is some $\mathbf{d}$ such that $\mathbf{d}<\mathbf{b}$ and.

[1] S. Ahmad and A. Lachlan, Some special pairs of ${\Sigma}_2$ e-degrees. Mathematical Logic Quarterly , vol. 44 (1998), no. 4, pp. 431–449.

[2] J. L. Goh, S. Lempp, K. M. Ng, and M. Soskova, Extensions of two constructions of Ahmad, to appear .

▸ MATTHEW HARRISON-TRAINOR, How hard is it to find an atlas for a surface?.

Department of Mathematics, University of Michigan, Ann Arbor, MI 48109, USA.

E-mail: [email protected].

A (topological) manifold is a topological space which is locally Euclidean, i.e., there is an atlas of coordinate charts covering the surface. While the manifold does not come equipped with any particular atlas, nearly every proof begins by fixing an atlas. So it is natural to ask, how hard is it to recover an atlas from the purely topological structure of the manifold? We consider the case of surfaces, represented as the completion of a countable metric space. We show that there is always an atlas which is arithmetic in the surface. One can view this as saying that the locally Euclidean structure is not too hidden within the topological structure, and can be recovered in a first-order way. This is joint work with Alexander Melnikov.

▸ RUSSELL MILLER, Universal properties of differentially closed fields.

Mathematics Department, Queens College, City University of New York, 65-30 Kissena Boulevard, Queens, NY 11355, USA.

E-mail: [email protected].

Various classes of structures are known to be universal (or complete) for standard computable-model-theoretic properties, as described in [2]. These classes include graphs, partial orders, groups, and fields, but exclude linear orders, Boolean algebras, and trees. Here we build on results in [3], joint with Marker, that showed that differentially closed fields of characteristic $0$ are not universal for Turing degree spectra.

We begin by adjoining a unary predicate $A$ to the signature of differential fields, defined to hold of those elements algebraic over a specific computable differential subfield $K$ of the differential closure of $\mathrm{\mathbb{Q}}$ . Universality of the class ${\mathcal{D}}^A$ of all countable models of DCF ${}_0$ (in the signature with $A$ ) can now be considered “on a cone,” i.e., relative to an oracle set. We use the set $T$ of those formulas with parameters from $K$ that are complete for DCF ${}_0$ . This set $T$ is ${\Pi}_1^0$ , but its decidability is an open question. We show that on the cone above $T$ , the class ${\mathcal{D}}^A$ is universal for Turing degree spectra, and also for categoricity spectra and other computable-categoricity properties. Of course, if $T$ is decidable, then this universality holds without restriction. If $T$ is undecidable, then it gives some of the first natural examples of the notion of “universality on a cone.”

We also note that this construction fails to prove universality of ${\mathcal{D}}^A$ for automorphism groups, and hence does not yield a bi-interpretation between ${\mathcal{D}}^A$ and the class of graphs, even in the broad sense of interpretations from [1]. This failure raises intriguing model-theoretic questions about the models of DCF ${}_0$ .

[1] M. Harrison-Trainor, R. Miller, and A. Montalbán, Borel functors and infinitary interpretations. The Journal of Symbolic Logic , vol. 83 (2018), no. 4, pp. 1434–1456.

[2] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, and A.M. Slinko, Degree spectra and computable dimensions in algebraic structures. Annals of Pure and Applied Logic , vol. 115 (2002), pp. 71–113.

[3] D. Marker and R. Miller, Turing degree spectra of differentially closed fields. The Journal of Symbolic Logic , vol. 82 (2017), no. 1, pp. 1–25.

▸ ANTONIO MONTALBÁN AND DINO ROSSEGGER_, The structural complexity of models of arithmetic.

Department of Mathematics, University of California, Berkeley, Berkeley, CA, USA.

E-mail: [email protected].

Department of Mathematics, University of California, Berkeley, Berkeley, CA, USA, and Institute of Discrete Mathematics and Geometry, Technische Universität Wien, Wien, Austria.

E-mail: [email protected].

The Scott rank of a countable structure is the least ordinal $\alpha$ such that all automorphism orbits of the structure are definable by infinitary ${\Sigma}_{\alpha }$ formulas. Montalbán showed that the Scott rank of a structure is a robust measure of the structural and computational complexity of a structure showing that various different measures are equivalent. For example, a structure has Scott rank $\alpha$ if and only if it has a ${\Pi}_{\alpha +1}$ Scott sentence if and only if it is uniformly ${\mathtt{D}}_{\alpha}^0$ categorical.

One of the objectives of computable structure theory is to obtain measures of the complexity of structures in common classes. In this talk we present results on the Scott rank of non-standard models of Peano arithmetic. We show that non-standard models of PA have Scott rank at least $\omega$ , but, other than that, there are no limits to their complexity. Given a completion $T$ of $PA$ we give a reduction via bi-interpretability of the class of linear orders to the models of $T$ . This allows us to exhibit models of $T$ of Scott rank $\alpha$ for every $\omega \le \alpha \le {\omega}_1$ . In particular, every completion of $T$ has models of high Scott rank.

▸ JAMES S. BARNES, JUN LE GOH, AND RICHARD A. SHORE_, Theorems of hyperarithmetic analysis and almost theorems of hyperarithmetic analysis.

Department of Mathematics, Yale University, New Haven, CT, USA.

Department of Mathematics, University of Wisconsin–Madison, Madison, WI, USA.

Department of Mathematics, Cornell University, Ithaca, NY, USA.

E-mail: [email protected]

This talk is based on [1] which will appear in the BSL and reports on work in [2–4].

Theorems of hyperarithmetic analysis (THAs) occupy an unusual neighborhood in the realms of reverse mathematics and recursion theoretic complexity. They lie above all the fixed (recursive) iterations of the Turing jump but below ATR ${}_0$ (and so ${\Pi}_1^1$ -CA ${}_0$ or the hyperjump). There is a long history of proof theoretic principles which are THAs. There was only one mathematical example until [2]. There we analyze an array of ubiquity theorems in graph theory descended from Halin’s 1965 work on rays in graphs. They seem to be typical applications of ACA ${}_0$ but are actually THAs. These results answer Question 30 of Montalban’s Open Questions in Reverse Mathematics and supply several other natural principles of different and unusual levels of complexity.

This work led in [4] to a new neighborhood of the reverse mathematical zoo: almost theorems of hyperarithmetic analysis (ATHAs). When combined with ACA ${}_0$ they are THAs but on their own are very weak. Denizens both mathematical and logical are provided. Generalizations of several conservativity classes ( ${\Pi}_1^1$ , r- ${\Pi}_2^1$ , and Tanaka) are defined and these ATHAs as well as many other principles are shown to be conservative over RCA ${}_0$ in all these senses and weak in other recursion theoretic ways as well. These results answer a question raised by Hirschfeldt and reported in Montalbán’s Open Questions in Reverse Mathematics by providing a long list of pairs of principles one of which is very weak over RCA ${}_0$ but over ACA ${}_0$ is equivalent to the other which may be strong (THA) or very strong going up a standard hierarchy and at the end being stronger than full second order arithmetic.

[1] J. S. Barnes, J. L. Goh, and R. A. Shore, Theorems of hyperarithmetic analysis and almost theorems of hyperarithmetic analysis, this Journal, to appear .

[2] ———, Halin’s Infinite Ray Theorems: Complexity and Reverse Mathematics, to appear.

[3] J. L. Goh, The strength of an axiom of finite choice for branches in trees, to appear.

[4] R. A. Shore, Almost theorems of hyperarithmetic analysis, to appear.

▸ MARIYA SOSKOVA, Enumeration pointed trees.

Department of Mathematics, University of Wisconsin–Madison, 480 Lincoln Drive, Madison, WI 53706, USA.

E-mail: [email protected].

An enumeration pointed tree (e-pointed tree) is a tree $T$ with no dead ends such that every path in $T$ can enumerate $T$ . This notion arises in work by Montalbán [3]: he showed that a degree spectrum of a structure is never the upward closure of an ${F}_{\sigma }$ set in Cantor space or Baire space unless it is the set of Turing oracles that can enumerate an e-pointed tree in Cantor space or Baire space respectively. McCarthy [2] characterized the class of enumeration degrees of e-pointed trees in Cantor space. It turned out to be the well-studied class of cototal degrees [1]: degrees of sets $A$ such that $A{\le}_e\overline{A}$ . McCarthy also showed that this class is fairly robust: for instance, the degrees of e-pointed trees in Cantor space are the degrees of e-pointed trees with dead ends. We investigate the similar class of e-pointed trees in Baire space and the related class of enumeration degrees of introenumerable sets: a set $A$ is introenumerable if it is enumeration reducible to each of its infinite subsets. We prove that the cototal degrees are a strict subclass of the introenumerable degrees, which is in turn strictly contained in the enumeration degrees of e-pointed trees in Baire space. We further characterize the class of e-pointed trees in Baire space with dead ends using the notion of hyperenumeration reducibility, introduced by Sanchis [4]. We show that they strictly extend the degrees of e-pointed trees in Baire space (with no dead ends). This work is joint with Goh, Jacobsen-Groccott, and J. Miller.

[1] U. Andrews, H. Ganchev, R. Kuyper, S. Lempp, J. Miller, A. Soskova, and M. Soskova, On cototality and the skip operator in the enumeration degrees. Transactions of the American Mathematical Society , vol. 372 (2019), no. 3, pp. 1631–1670.

[2] E. McCarthy, Cototal enumeration degrees and their applications to effective mathematics. Proceedings of the American Mathematical Society , vol. 146 (2018), no. 8, pp. 3541–3552.

[3] A. Montalbán, Computable structure theory—within the arithmetic , Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Ithaca, 2021.

[4] L. Sanchis, Hyperenumeration reducibility. Notre Dame Journal of Formal Logic , vol. 19 (1978), no. 3, pp. 405–415.

▸ LINDA WESTRICK, Borel sets in reverse mathematics.

Department of Mathematics, The Pennsylvania State University, McAllister Building, University Park, PA 16802, USA.

E-mail: [email protected].

The principles “Every Borel set has the property of Baire” and “Every Borel set is measurable” are incomparable and strictly weaker than ${\mathrm{ATR}}_0$ . Yet these principles suffice to prove many theorems of Borel combinatorics. We examine the implications among these theorems.

Abstracts of invited talks in the Special Session on History and Philosophy of Logic

▸ JUSTIN CAVITT, The evidence for large cardinal axioms and the curious case of supercompactness.

Department of Philosophy, Harvard University, 25 Quincy Street, Cambridge, MA, USA.

E-mail: [email protected].

The independence phenomenon motivates the study of new axioms to be added to ZFC and raises the philosophical question of what considerations can serve as evidence for those axioms. Large cardinal axioms, which assert the existence of large transfinite cardinals, are the most widely accepted new axioms. In this talk, we will give an overview of the study and use of various kinds of large cardinals, discuss how it is that this research can constitute evidence for the corresponding large cardinal axioms, and articulate what that evidence amounts to. Of particular concern will be the case of supercompact cardinals. We shall compare the evidence for their consistency and existence with that for other large cardinals and identify some features of supercompacts that complicate this case.

▸ ALEXANDER W. KOCUREK, Axiomatizing hyperlogic.

Sage School of Philosophy, Cornell University, Ithaca, NY, USA.

E-mail: [email protected].

Hyperlogic is a hyperintensional modal logic developed in [5] to regiment and interpret metalogical claims (e.g., “Intuitionistic logic is correct” or “The law of noncontradiction fails”) directly in the object language, even within embedded environments such as in attitude reports (“Inej believes intuitionistic logic is correct”) and counterfactuals (e.g., “If the Liar were true and not true, the law of noncontradiction would fail”). This is achieved by extending the basic propositional modal language with propositional quantifiers (see [3, 4]), a multigrade entailment operator, and modified versions of the standard hybrid logical operators (see [1, 2]), which can shift the interpretation of logical connectives. Formulas in this language are interpreted relative to an interpretation of the basic connectives and operators (including the entailment operator). This paper motivates hyperlogic as an approach to the semantics of metalogical claims and presents a series of axiomatizability results for the logic of hyperlogic in various languages (including ones with propositional quantifiers and counterfactuals) and over a variety of classes of models. These axiomatizations involve two interdependently defined proof systems, each representing different notions of consequence and each containing rules for moving back and forth between these systems. The result is an elegant and nontrivial logic for hyperlogic.

[1] C. Areces and B. ten Cate, Hybrid logics, Handbook of Modal Logic (P. Blackburn, F. Wolter, and J. van Benthem, editors), Elsevier, 2007, pp. 821–868.

[2] T. Braüner, Hybrid logic, The Stanford Encyclopedia of Philosophy (E. N. Zalta, editor), Metaphysics Research Lab, Stanford University, 2017. Available at https://plato.stanford.edu/archives/sum2017/entries/logic-hybrid/.

[3] K. Fine, Propositional quantifiers in modal logic. Theoria , vol. 36 (1970), pp. 336–346.

[4] D. Kaplan, S5 with quantifiable propositional variables. The Journal of Symbolic Logic , vol. 35 (1970), no. 2, p. 355.

[5] A. W. Kocurek, Logic talk. Synthese , vol. 199 (2021), nos. 5–6, pp. 13661–13688.

▸ SUN-JOO SHIN, Peirce’s triadic logic: extension or deviation?

Department of Philosophy, Yale University, New Haven, CT 06520, USA.

E-mail: [email protected].

The talk has two goals: (i) to suggest a new way to understand Peirce’s triadic logic and (ii) to raise the question of whether Peirce’s triadic logic is an extension of or a deviation from classical logic. I classify Peirce’s six binary connectives, based on the dominance among three values, V, F, and L. Then, they may be grouped into three, depending on how the third value L is placed in the dominance hierarchy. (My visual representation makes the issue clearer.) Where is Peirce’s triadic logic located in a bigger picture, an extended standard logic or a non-standard logic? Traditionally, many-valued logic is non-standard, hence a deviation from classical logic. While examining passages which seem to support the deviation view of Peirce’s new logic, I beg you to resist the temptation to rush to that conclusion. Peirce’s discussion on the third value L is rather nuanced. He says dyadic logic is defective (which is different from being incorrect) because dyadic logic “takes no heed of the limit between two realms.” Obviously, his new logic aims to cover the limit which traditional logic neglects to represent. Peirce draws our attention to the existence of “an intermediate ground” between both ends, i.e., “positive assertion and positive negation,” and wants to represent that middle area. According to this interpretation, Peirce’s triadic logic is an extension of classical logic, unlike other many-valued logics.

▸ VALÉRIE LYNN THERRIEN, The evolution of Cantor’s proof of the non-denumerability of $\mathrm{\mathbb{R}}$ .

Department of Philosophy, McGill University, 855 Sherbrooke Street West Montréal, QC H3A 2T7, Canada.

E-mail: [email protected].

URL Address: www.valerielynntherrien.com.

Cantor gave three distinct proofs of the non-denumerability of $\mathrm{\mathbb{R}}$ : (1) the first one in 1874 [1]; (2) the second one in 1879 [3]; and (3) the third and final one in 1891 [4]—after a protracted absence from public mathematics. The third one is the canonical one, and is also known as the diagonal argument. Notably, Cantor’s diagonal argument makes use of an infinite array of infinite sequences, from which a sequence that isn’t an element of the array is constructed. Yet, the published versions of his first two proofs did not involve such an array. Interestingly, the first unpublished version of the first proof did involve an infinite array of infinite sequences, out of which a potentially infinite sequence of nested intervals was constructed. As well, Cantor’s 1878 proof of the equipollence of $\mathrm{\mathbb{R}}$ and ${\mathrm{\mathbb{R}}}^n$ [2] involved a finite array of infinite sequences, out of which a sequence that is itself not an element of the array is also constructed.

The primary aim of this paper is to track the evolution of Cantor’s proofs of the non-denumerability of $\mathrm{\mathbb{R}}$ —which culminates in the famous diagonal argument and Cantor’s Theorem. Why did Cantor revisit his proof three times? The secondary aim of this paper is to explore the role of arrays in his proofs of the non-denumerability of $\mathrm{\mathbb{R}}$ . Why did Cantor return to the infinite array he had abandoned for his first two versions of the proof? I will conclude that Cantor likely had the means to arrive at the diagonal argument by 1878, but that the ways in which he had been using arrays up until then would have involved arbitrarily constructing an irrational number simply by manipulating numbers as if they were mere symbols. While this may seem natural to us now, this would not have been an acceptable way to construct an irrational number to his peers. Cantor’s lengthy absence from public mathematics likely provided him with the time required to distill the essence of the diagonal argument, and to produce a proof that did not require the construction of an irrational number at all.

[1] G. Cantor, Sur une propriété de tous les nombres algébriques réels. Acta Mathematica , vol. 2 (1874/1883), no. 1, pp. 305–310.

[2] ———, Une contribution à la théorie des ensembles. Acta Mathematica , vol. 2 (1878/1883), no. 1, pp. 311–328.

[3] ———, Sur les ensembles infinis et linéaires de points, I. Acta Mathematica , vol. 2 (1879/1883), no. 1, pp. 349–346.

[4] ———, On an Elementary Question in the Theory of Manifolds, From Kant to Hilbert: A Source Book in the Foundations of Mathematics (W. Ewald, editor), Clarendon Press, Oxford, 1891/2005, pp. 920–922.

Abstracts of invited talks in the Special Session on Homotopy Type Theory

▸ STEVE AWODEY, Kripke–Joyal semantics for type theory.

Departments of Philosophy and Mathematics, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213, USA.

E-mail: [email protected].

Recent joint work with Nicola Gambino and Sina Hazratpour is presented. Kripke–Joyal semantics extends basic Kripke semantics for intuitionistic propositional logic (IPL) and first-order logic (IFOL) to the higher-order logic used in topos theory (IHOL). It provides a systematic way to interpret propositions in IHOL into any Grothendieck topos and test them for validity under the interpretation. We extend the interpretation to the dependent type theory of Martin-Löf (MLTT), using the formalism of natural models [1]. Prior cases are subsumed, including the completeness theorem for MLTT from [2]. Presheaf models of homotopy type theory (HoTT) occurring in the work of Voevodsky et al. [4] and Coquand et al. [3] can be recovered as special cases of our semantics, as will be presented in a subsequent talk by Hazratpour.

[1] S. Awodey, Natural models of homotopy type theory. Mathematical Structures in Computer Science , vol. 28 (2016), no. 2, pp. 241–286.

[2] S. Awodey and F. Rabe, Kripke semantics for Martin–Löf’s extensional type theory. Logical Methods in Computer Science , vol. 7 (2011), no. 3, pp. 1–25.

[3] C. Cohen, T. Coquand, S. Huber, and A. Mörtberg, Cubical type theory: A constructive interpretation of the univalence axiom, 21st International Conference on Types for Proofs and Programs (TYPES 2015), (T. Uustalu, editor), Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, 2016, pp. 5:1–5:34.

[4] C. Kapulkin and P. LeFanu Lumsdaine, The simplicial model of univalent foundations (after Voevodsky). Journal of the European Mathematical Society , preprint, arXiv:1211.2851, to appear .

▸ JONAS FREY, An introduction to cohesive homotopy type theory.

Department of Philosophy, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213, USA.

E-mail: [email protected].

Cohesive homotopy type theory was devised by Schreiber and Shulman [2, 3] as a combination of Lawvere’s cohesive topos theory [1] with ideas from homotopy type theory [4], to provide a framework that allows to reason about mathematical objects which have both a homotopical and a continuous/geometric (“cohesive”) aspect. Formally this is achieved by extending type theory with an adjoint sequence ∬ ⊣ ♭ ⊣ # of modal operators that relate geometry and homotopy by associating with a space $X$ , e.g., its homotopy type $\int\!X$ and its set of points $\flat X$ .

After reviewing basic concepts of homotopy type theory this talk will present the category theoretic motivation and type theoretic formalization of cohesive homotopy type theory, and will conclude by discussing applications to geometry and higher category theory.

[1] W. Lawvere, Axiomatic cohesion. Theory and Applications of Categories , vol. 19 (2007) no. 3, pp. 41–49.

[2] U. Schreiber and M. Shulman, Quantum gauge field theory in cohesive homotopy type theory, 9th Workshop on Quantum Physics and Logic (Brussels, Belgium), vol. 158 (R. Duncan and P. Panangaden, editors), 2014, pp. 109–126, preprint, arXiv:1408.0054.

[3] M. Shulman, Brouwer’s fixed-point theorem in real-cohesive homotopy type theory. Mathematical Structures in Computer Science , vol. 28 (2018) no. 6, pp. 856–941.

[4] The Univalent Foundations Program, Homotopy Type Theory: Univalent Foundations of Mathematics , Institute for Advanced Study, 2013. Available at https://homotopytypetheory.org/book.

▸ SINA HAZRATPOUR, Kripke–Joyal semantics for homotopy type theory.

Department of Mathematics, Johns Hopkins University, 3400 North Charles Street, Baltimore, MD 21218, USA.

E-mail: [email protected].

URL Address: https://sinhp.github.io.

This talk is a continuation of Awodey’s talk earlier today and it uses our extended Kripke–Joyal Semantics to find new proofs of some results in Homotopy Type Theory. The presented material is based on joint work [2] with Steve Awodey and Nicola Gambino.

Uniform fibrations are central to constructing Quillen model structures in order to study categorical models of Homotopy Type Theory. They were introduced in [3, 4] to provide a constructive model of the Univalence Axiom. However, working with uniform fibrations diagrammatically can be very complex, since the algebraic structure on a map is in general not unique, and thus needs to be carried around explicitly. As a result, the construction of the object of fibration structures on a given map using only diagrams can be a daunting task.

An alternative approach is provided by the internal type theory of a presheaf category, which is a highly expressive extensional dependent type theory, in which it is possible to handle not only the basic categorical structure, but also locally Cartesian closed structure. Following on the suggestion of Thierry Coquand, in [7], Orton and Pitts successfully used this internal type theory to develop parts of the theory of uniform fibrations entirely in a type-theoretic fashion. In this approach one can feasibly write down the type of fibration structures on a map and reason about it formally.

This talk demonstrates a few applications of our forcing semantics in proving certain important properties of uniform fibrations crucial to their role in the constructive models of Homotopy Type Theory. In particular, using our forcing semantics, we show that the category-theoretic and type-theoretic descriptions of uniform fibrations considered in [1, 3–5, 7–9] coincide.

[1] S. Awodey, A cubical model of homotopy type theory. Annals of Pure and Applied Logic , vol. 169, no. 12, pp. 1270–1294.

[2] S. Awodey, N. Gambino, and S. Hazratpour, Kripke–Joyal forcing for type theory and uniform fibrations, preprint, 2021, arXiv:2110.14576 .

[3] M. Bezem, T. Coquand, and S. Huber, A model of type theory in cubical sets, 19th International Conference on Types for Proofs and Programs (Dagstuhl, Germany), (R. Matthes and A. Schubert, editors), Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2015, pp. 107–128.

[4] C. Cohen, T. Coquand, S. Huber, and A. Mörtberg, Cubical type theory: a constructive interpretation of the univalence axiom, 21st International Conference on Types for Proofs and Programs (TYPES 2015) (Wadern, Germany), (T. Uustalu, editor), Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, 2018, pp. 5:1–5:34.

[5] N. Gambino and C. Sattler, The Frobenius condition, right properness, and uniform fibrations. Journal of Pure and Applied Algebra , vol. 221 (2015), no. 12, pp. 3027–3068.

[6] S. Mac Lane and I. Moerdijk, Sheaves in Geometry and Logic. A First Introduction to Topos Theory , Universitext, Springer, 1994 .

[7] I. Orton and A. M. Pitts, Axioms for modelling cubical type theory in a topos. Logical Methods in Computer Science , vol. 14 (2017), no. 4, pp. 1–33.

[8] C. Sattler, The equivalence extension property and model structures, preprint, 2017, arXiv:1704.06911.

[9] A. Swan, An algebraic weak factorisation system on 01-substitution sets: A constructive proof. Journal of Logic & Analysis , vol. 8 (2016), no. 1, pp. 1–35.

▸ SIMON HENRY, Homotopy invariant languages.

Department of Mathematics and Statistics, University of Ottawa, Ottawa, ON, Canada.

E-mail: [email protected].

One of the nice properties of homotopy type theory is that it allows to talk about homotopy theoretic properties in a “homotopy invariant” and “model invariant way.” For example, if one consider a statement in HoTT that involves some spaces or maps as parameters and we replace these by homotopy equivalent ones, then the validity of the statement is unchanged.

Something similar was also observed a long time ago in category theory: if you write a first order formula (with parameters) in the language of category theory that do not involve equality between objects then the validity of this formula is preserved if you replace each object appearing in the formula by isomorphic ones, or if you replace the category to which it applies by an equivalent category.

The common point between these two observations is that both correspond to theories where the use of equality has been restricted, but which relies on a notion of dependent type to maintain enough expressivity despite the lack of equality. And while equality destroys homotopy invariance (or homotopy invariance), the use of dependent types is compatible with it.

In this talk I will explain how, more generally, to each Quillen model category, one can associate a similar “homotopy language,” which can be seen as first order logic without equality over a dependently typed algebraic theory. This language is automatically “homotopy invariant” in three different senses (invariant under homotopies, under weak equivalence, and under Quillen equivalences) that I will explain.

This construction is strongly inspired from Makkai’s FOLDS and in some sense is a generalization of it.

▸ CHRIS KAPULKIN, Equivalences of dependent type theories.

Department of Mathematics, University of Western Ontario, 1151 Richmond Street, London, ON, Canada.

E-mail: [email protected].

The goal of this talk is to answer the question: what does it mean for two dependent type theories to be equivalent?

The category of models of a fixed dependent type theory carries the canonical structure of a left semi-model category, previously studied in categorical homotopy theory. It is in particular well-understood in homotopy theory when two left semi-model categories are equivalent; namely, when they are Quillen equivalent. We thus propose the notion of a Morita equivalence between dependent type theories, amounting to the existence of a Quillen equivalence between their categories of models.

We will introduce the notion of Morita equivalence and discuss what kind of logical information about the theories is preserved under it.

▸ PAIGE RANDALL NORTH, The univalence principle.

Departments of Mathematics and Electrical and Systems Engineering, University of Pennsylvania, 209 South 33rd Street, Philadelphia, PA, USA.

E-mail: [email protected].

URL Address: https://paigenorth.github.io.

The Equivalence Principle is an informal principle asserting that equivalent mathematical objects have the same properties. For example, group theory has been developed so that isomorphic groups have the same group-theoretic properties, and category theory has been developed so that equivalent categories have the same category-theoretic properties (though sometimes other, “evil” properties are considered). Vladimir Voevodsky established Univalent Foundations as a foundation of mathematics (based on dependent type theory) in which the Equivalence Principle for types (the basic objects of type theory) is a theorem [5]. Later, versions of the Equivalence Principle for set-based structures such as groups [3] and categories [1] were shown to be theorems in Univalent Foundations.

In [2] we formulate and prove versions of the Equivalence Principle for a large class of categorical and higher categorical structures in Univalent Foundations. Our work encompasses bicategories, dagger categories, opetopic categories, and more. Some of the notions used in our work were inspired by Makkai’s First-order logic with dependent sorts [4].

[1] B. Ahrens, K. Kapulkin, and M. Shulman, Univalent categories and the Rezk completion. Mathematical Structures in Computer Science , vol. 25 (2015), no. 5, pp. 1010–1039.

[2] B. Ahrens, P. R. North, M. Shulman, and D. Tsementzis, The univalence principle, preprint, 2021, arXiv:2102.06275 .

[3] T. Coquand and N. A. Danielsson, Isomorphism is equality. Indagationes Mathematicae , vol. 24 (2013), no. 4, pp. 1105–1120.

[4] M. Makkai, First order logic with dependent sorts, with applications to category theory, 1995 .

[5] V. Voevodsky, A very short note on homotopy $\lambda$ -calculus, 2009.

Abstracts of invited talks in the Special Session on Logic and Machine Learning

▸ HUNTER CHASE, No-clash teaching of some infinite classes.

Department of Mathematics, University of Maryland, College Park, 4176 Campus Drive, College Park, MD 20742, USA.

E-mail: [email protected].

No-clash teaching dimension is a generalization of recursive teaching dimension and other notions of machine teaching that seek to encode sets in a set system using a small number of labeled examples [1]. While work conducted around machine teaching has primarily focused on the case where the set system is finite, it is possible to consider infinite classes as well. In particular, several properties that result in good bounds on the size of a teaching function correspond with model-theoretic dividing lines. We present bounds on the size of a no-clash teacher for certain infinite classes, including classes with finite Littlestone dimension and countable classes with VC-dimension 1. We also observe that many infinite classes do not admit a no-clash teacher, even some with properties that lead to good results in the finite case.

This is joint work with Chris Laskowski.

[1] D. Kirkpatrick, H. U. Simon, and S. Zilles, Optimal collusion-free teaching, Algorithmic Learning Theory (A. Garivier and S. Kale, editors), Proceedings of Machine Learning Research, vol. 98, 2019, pp. 506–528 .

▸ VINCENT GUINGONA, Model theory and differential privacy.

Department of Mathematics, Towson University, 8000 York Road, Towson, MD 21252, USA.

E-mail: [email protected].

URL Address: https://tigerweb.towson.edu/vguingona/.

In this talk, we explore the connections between model theory and a notion from theoretical machine learning called differential privacy. We survey how to employ model theoretic techniques, specifically ideas from stability theory, to obtain results about differential privacy. Finally, I discuss some recent work towards classifying various notions of differential privacy. This work comes from an REU at Towson University; it is joint with Alexei Kolesnikov and two undergraduate researchers, Julie Nierwinski and Avery Schweitzer.

▸ MATTHEW HARRISON-TRAINOR, Lowness notions in computer science.

Department of Mathematics, University of Michigan, Ann Arbor, MI 48109, USA.

E-mail: [email protected].

Some oracles are very weak in the sense that they have no power for solving problems from a particular class of problems: any problem of that kind that could be solved with the oracle could already be solved without the oracle. The classic example is that of an oracle being low, which means that anything that is limit computable in the oracle was already limit computable. There are many other lowness properties; in this talk I will talk about two of them. (1) An oracle is low-for-speed if it does not speed up any computations: any decision problem that is computable in time $t(x)$ using the oracle was already computable in time only polynomially slower than $t(x)$ . (2) An oracle is low-for-learning if any computable function which can be learned with oracle $A$ can be learned without $A$ .

▸ HUNTER JOHNSON, Binary strings of finite VC dimension.

Department of Mathematics and Computer Science, John Jay College, CUNY, 524 West 59th Street, New York, NY 10019, USA.

E-mail: [email protected].

The complexity of a string can be measured by the richness of its substrings. For example in genetics a region of DNA is considered to be highly informative if many of the possible substrings of a certain length actually occur. Abstractly this kind of complexity is captured by the standard string complexity function. When dealing with binary strings, we have the additional feature that substrings can be viewed as subsets of an index set. This allows us to apply measures of subset complexity such as VC dimension. In this talk we define a notion of VC dimension for binary strings and investigate the structure of strings of finite VC dimension.

▸ MICHAEL C. LASKOWSKI, The more we talk together, the happier we’ll be.

Department of Mathematics, University of Maryland, College Park, MD 20742, USA.

E-mail: [email protected].

Since it was first observed that a uniformly definable family of sets $\left\{\phi \left(M,a\right):a\in M\right\}$ is a Vapnik-Chervonenkis (VC) class if and only if the formula $\phi \left(x,y\right)$ is NIP (does not have the Independence Property) the three fields of model theory, combinatorics, and machine learning have become deeply intertwined. This talk will survey how the original connection was discovered by way of a question of Stengle and Yukich in real algebraic geometry, and trace through the subsequent connections between these fields. Via this connection, examples from model theory give rise to many interesting VC classes, which are PAC-learnable. With Johnson, we noted the connection between definability of types and compression schemes. Working backwards from this led to the formulation of the UDTFS conjecture, which was extensively studied by Guingona. We discuss how this conjecture was solved, highlighting the roles played by non-trivial results from both combinatorics (the $\left(p,q\right)$ -theorem) and machine learning (the fundamental theorem of Recursive Teaching Dimension). Also working backwards, the original proof given by Vapnik and Chervonenkis has led to the model theoretic VC-theorem, which has become central to how model theorists’ understanding of Keisler measures of types in NIP theories. Over the past few years, Chase and Freitag have noted how other models of machine learning are connected to other properties of uniformly definable sets and we speculate as to how machine learning tools may further advance our understanding of these families.

▸ D. GIHANEE SENADHEERA, Effective concept classes of PAC and PACi incomparable degrees and jump structure.

School of Mathematics and Statistical Sciences, Southern Illinois University, 1245 Lincoln Drive, Mail Code 4408, Carbondale, IL, USA.

E-mail: [email protected].

The Probably Approximately Correct (PAC) learning model is one of the machine learning models and it is introduced by Leslie Valiant in 1984. There is a reducibility to this learning model which is similar to Turing reducibility. The PACi means a less restricted version of this reducibility. Here i refers to the independence of the size and time computation of the PAC reducibility definition. The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples. We can throw in equivalence relationships to these PACi and PAC reducibilities and form the respective degrees. We recursively construct two c.e. effective concept classes of incomparable PACi degrees to show that there exist incomparable PACi degrees. Similarly we can construct for PAC degrees which is analogous to incomparable Turing degrees. The priority construction method is used to construct the two concept classes, which was used by Friedburg and Muchnik in their proof of incomparable Turing degrees. It was necessary to deal with the size of an effective concept class; thus we propose a method to compute the size of the effective concept class using Kolmogorov complexity. Furthermore, we explore the jump structure of effective concept classes similar to the Turing jump.

[1] W. Calvert, PAC learning, VC dimensions, and the arithmetic hierarchy. Archive for Mathematical Logic , vol. 54, nos. 7–8, pp. 871–883 .

[2] ———, Mathematical Logic and Probability , preprint, 2021.

[3] W. Calvert, M. J. Kearns, and U. Vazirani, An Introduction to Computational Learning Theory , MIT Press, 1994.

[4] M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications , Springer, Cham, 2019.

[5] R. Soare, Recursively Enumerable Sets and Degrees , Springer, New York, 1987.

▸ MADELEINE UDELL, Automating machine learning.

School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853, USA.

E-mail: [email protected].

How should practitioners choose a machine learning model? What kind of model (linear, tree ensemble, or deep neural network) will work best? Will the default hyperparameters work, or should you tweak them? How valuable is the dataset, and has the algorithm chosen realized that value? In this talk we’ll survey some interesting strategies for automated machine learning that aim to answer these questions automatically.

We will focus in particular on understanding how AutoML can teach us about the structure of data and about the relations between datasets and between algorithms.

▸ KEVIN ZHOU, Query learning of automata.

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

E-mail: [email protected].

Query learning of various forms of automata is a long-studied area of problems, with applications in automatic verification of security protocols as well as in the study of hardware and software systems. In this setting, a learner attempts to identify an unknown target automata by submitting queries to an oracle. Most commonly, the learner is allowed to ask two types of queries: (1) whether the target is equivalent to a particular hypothesis automata and (2) whether the target automata accepts a particular string. Prior work on developing query learning algorithms for automata began with work of Angluin [1] on learning deterministic finite automata, and was followed by many other authors extending Angluin’s algorithm to generalizations of DFAs.

More recently, Chase and Freitag [3] used ideas from model theory to prove general bounds on the complexity of query learning in terms of certain combinatorial invariants of concept classes (namely, Littlestone dimension and consistency dimension). Applying this approach to the setting of DFAs, they obtain results that are qualitatively different than previous results. In our work, we extend this approach to prove new bounds on the complexity of query learning for two variants of DFAs. The first is that of DFAs with advice [4], where classical DFAs are augmented with a fixed infinite “advice tape” that is read in parallel to the input tape. In this setting, no prior query learning results are known. The second variant is that of nominal DFAs [2], a generalization of DFAs to infinite alphabets and state sets. Prior query learning results exist for this setting [5], but our work gives significant improvements over these results.

[1] D. Angluin, Learning regular sets from queries and counterexamples. Information and Computation , vol. 75 (1987), no. 2, pp. 87–106.

[2] M. Bojańczyk, B. Klin, and S. Lasota, Automata theory in nominal sets. Logical Methods in Computer Science , vol. 10 (2014), no. 3 .

[3] H. Chase and J. Freitag, Bounds in query learning, Proceedings of the Thirty Third Conference on Learning Theory (J. Abernethy and S. Agarwal, editors), PMLR, 2020, pp. 1142–1160 .

[4] A. Kruckman, S. Rubin, J. Sheridan, and B. Zax, A Myhill–Nerode theorem for automata with advice, Proceedings of the Third International Symposium on Games, Automata, Logics and Formal Verification (M. Faella and A. Murano, editors), EPTCS, 2012, pp. 238–246.

[5] J. Moerman, M. Sammartino, A. Silva, B. Klin, and M. Szynwelski, Learning nominal automata, Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (G. Castagna and A. D. Gordon, editors), Association for Computing Machinery, 2017, pp. 613–625.

Abstracts of invited talks in the Special Session on Models of Peano Arithmetic

▸ ATHAR ABDUL-QUADER, Generic subsets of models of PA.

School of Natural and Social Sciences, SUNY Purchase College, 735 Anderson Hill Road, Purchase, NY 10577, USA.

E-mail: [email protected].

We study notions of genericity in models of $\mathrm{PA}$ , inspired by lines of inquiry initiated by Chatzidakis and Pillay [2] and continued by Dolich, Miller, and Steinhorn [3, 4] in general model-theoretic contexts. In [2], Chatzidakis and Pillay axiomatized the theories obtained by adding a “random” predicate to a class of structures. We look at subsets of models of $\mathrm{PA}$ satisfying the axiomatization given by Chatzidakis and Pillay; we refer to these sets as CP-generics. In this talk, we use an arithmetic version of Cohen forcing to construct CP-generics with various properties, including ones in which every element of the model is definable in the expansion, and, on the other extreme, ones in which the definable closure relation is unchanged. This shows a chasm between the generic subsets of tame theories and generic subsets of models of $\mathrm{PA}$ , answering a question raised by Kossak and the author in [1]. This is joint work with James Schmerl.

[1] A. Abdul-Quader and R. Kossak, Neutrally expandable models of arithmetic. Mathematical Logic Quarterly , vol. 65 (2019), no. 2, pp. 212–217.

[2] Z. Chatzidakis and A. Pillay, Generic structures and simple theories. Annals of Pure and Applied Logic , vol. 95 (1998), nos. 1–3, pp. 71–92.

[3] A. Dolich, C. Miller, and C. Steinhorn, Extensions of ordered theories by generic predicates. The Journal of Symbolic Logic , vol. 78 (2013), no. 2, pp. 369–387.

[4] ———, Expansions of o-minimal structures by dense independent sets. Annals of Pure and Applied Logic , vol. 167 (2016), no. 8, pp. 684–706.

▸ ALI ENAYAT, Surrounding the solidity of $\mathrm{PA}$ and ${\mathrm{Z}}_2$ .

Department of Philosophy, Linguistics, and Theory of Science, University of Gothenburg, Renströmsgatan 6, 41255 Gothenburg, Sweden.

E-mail: [email protected].

URL Address: https://www.gu.se/en/about/find-staff/alienayat.

Let ${\trianglerighteq}_{\mathrm{par}}$ denote the relation of parametric interpretability among structures. A first order theory $T$ is said to be solid iff the following property $\left(\nabla \right)$ holds for all models $\mathrm{\mathcal{M}}$ , ${\mathrm{\mathcal{M}}}^{\ast }$ , and $\mathcal{N}$ of $T$ :

$\left(\nabla \right)$ If $\mathrm{\mathcal{M}}{\trianglerighteq}_{\mathrm{par}}\mathcal{N}{\trianglerighteq}_{\mathrm{par}}{\mathrm{\mathcal{M}}}^{\ast }$ and there is a parametrically $\mathrm{\mathcal{M}}$ -definable isomorphism ${i}_0:\mathrm{\mathcal{M}}\to {\mathrm{\mathcal{M}}}^{\ast }$ , then there is a parametrically $\mathrm{\mathcal{M}}$ -definable isomorphism $i:\mathrm{\mathcal{M}}\to \mathcal{N}$ .

Note that if $T$ is solid, then no two distinct deductively closed extensions of $T$ (in the same language) are bi-interpretable. The solidity of $\mathrm{PA}$ was established by Visser [2]. Visser’s result inspired the author [1] to establish the solidity of certain other foundational theories, including ${\mathrm{Z}}_2$ (second order arithmetic). This talk presents evidence in support of the conjecture that the aforementioned results of Visser and the author about $\mathrm{PA}$ and ${\mathrm{Z}}_2$ are optimal.

[1] A. Enayat, Variations on a Visserian theme, Liber Amicorum Alberti. A Tribute to Albert Visser (J. van Eijk, R. Iemhoff, and J. J. Joosten, editors), College Publications, London, 2016, pp. 284–341.

[2] A. Visser, Categories of theories and interpretations, Logic in Tehran (A. Enayat, I. Kalantari, and M. Moniri, editors), Lecture Notes in Logic, vol. 26, Association for Symbolic Logic, La Jolla, 2006, pp. 284–341.

▸ HAIM GAIFMAN, The conflict between mathematical beauty and realism in the foundations of mathematics.

Department of Philosophy, Columbia University, New York, NY 10027, USA.

E-mail: [email protected].

Usually mathematicians appreciate the so-called beauty of certain mathematical proofs, or certain mathematical constructions. This beauty is associated with new ways of organizing the familiar items of a given problem, which result in new clarity; something complicated and foggy becomes illuminated from a new angle, thereby leading to a solution. For the sake of simplicity I shall use a well-known simple tiling problem as an example. Yet this kind of beauty is exemplified in frameworks whose development took years of intensive efforts. It resulted in new disciplines (new ways of organizing the mathematical material) such as algebraic topology, and its subdiscipline of homology theory. Arguably set theory is beautiful, at least Hilbert thought so. Andre Weil and Michael Atiyah—among the top of influential mathematicians at the turn of this century—certainly did not.

What is common to all the cases of mathematical beauty is that they are based on epistemology, that is, human ways of getting to know. Truth, however, or the facts, may resist attempts at reorganization that make for easier, ore transparent proofs. In this talk I shall use Apéry’s proof of the irrationality of $\zeta (3)$ (where $\zeta$ is Riemann’s $\zeta$ function) as an example of a valid proof that is definitely not beautiful. There will also be a short discussion of Riemann’s conjecture and Perlman’s proof of Poincare’s conjecture.

I shall then apply the beauty-versus-truth distinction to set theory. Here Woodin can be taken as the proponent of beauty, that is, epistemic clarity. Shelah, on the other hand, was well aware of the danger of using considerations of epistemic nature as a guide for choosing new set-theoretic axioms. In a paper from 2000 he criticizes Woodin and provides a truer, down to earth picture of the use of axiomatic set theories.

At the end of the talk I plan to discuss the most extreme cases when beauty has to be sacrificed for the sake of truth: the need to use computers in order to prove mathematical results. The two obvious cases are the Appel–Haken proof of the four-color theorem and the dramatic story of Tom Hales’ solution of the Kepler problem.

▸ LAURENCE KIRBY, Models of arithmetic: forty years on (again).

Department of Mathematics, Baruch College, New York, NY 10010, USA.

E-mail: [email protected].

The 1970s were a transitional period in the model theory of arithmetic. Some four and a half decades have now elapsed since then: roughly the same amount of time that elapsed from the foundational results of Skolem and Gödel to the 1970s. This talk will give some personal and historical reflections on what we knew, what we didn’t know, and what we ought to have known.

▸ LESZEK KOŁODZIEJCZYK, An isomorphism theorem for models of Weak König’s Lemma without ${\Sigma}_1^0$ induction.

Institute of Mathematics, University of Warsaw, Warsaw, Poland.

E-mail: [email protected].

${\mathrm{RCA}}_0^{\ast }$ is the fragment of second-order arithmetic axiomatized by ${\Delta}_1^0$ -comprehension, ${\Delta}_1^0$ -induction, and the statement that exponentiation is a total function. ${\mathrm{WKL}}_0^{\ast }$ is ${\mathrm{RCA}}_0^{\ast }$ extended by Weak König’s Lemma. These theories were first considered in the mid-1980s by Simpson and Smith, who proved among other things that ${\mathrm{WKL}}_0^{\ast }$ is ${\Pi}_1^1$ -conservative over ${\mathrm{RCA}}_0^{\ast }$ .

We prove that if $\left(M,\mathcal{X}\right)$ and $\left(M,\mathcal{Y}\right)$ are two countable models of ${\mathrm{WKL}}_0^{\ast }$ , with the same first-order universe $M$ , such that $\mathcal{X}\cap \mathcal{Y}$ contains a set relative to which ${\Sigma}_1^0$ induction fails, then $\left(M,\mathcal{X}\right)$ and $\left(M,\mathcal{Y}\right)$ are isomorphic. This result makes it possible to reprove some earlier theorems in first-order arithmetic (due to Kossak and to Kaye) saying that each countable model of ${\Sigma}_n^0$ collection but not ${\Sigma}_n^0$ induction has many automorphisms. However, it also has a number of consequences for theories of second-order arithmetic. For instance, it implies that Weak König’s Lemma is the strongest ${\Pi}_2^1$ statement that is ${\Pi}_1^1$ -conservative over ${\mathrm{RCA}}_0^{\ast }$ plus negated ${\Sigma}_1^0$ induction, and it means that there are some serious restrictions on the methods available for proving ${\Pi}_1^1$ -conservation over collection principles.

Joint work with Marta Fiori Carones, Tin Lok Wong, and Keita Yokoyama.

▸ MATEUSZ ŁEŁYK, The Tarski Boundary: a cartographic report.

Faculty of Philosophy, University of Warsaw, Warsaw, Poland.

E-mail: [email protected].

The talk surveys the recent results that revolve around the question: Which properties make the notion of truth strong? We shall focus on the extensions of the canonical compositional truth theory, usually denoted with ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]$ . The theory extends Peano Arithmetic $\left(\mathrm{PA}\right)$ with the following characteristic axioms for the notion of truth:

• • $\forall s,t\left[T\left(s\dot{=}t\right)\equiv val(s)= val(t)\right],$

• • $\forall \phi, \psi \left[T\left(\phi \dot{\vee}\psi \right)\equiv \left(T\left(\phi \right)\vee T\left(\psi \right)\right)\right],$

• • $\forall \phi \left[T\left(\dot{\neg}\phi \right)\equiv \neg T\left(\phi \right)\right],$

• • $\forall \phi (v)\left[T\left(\dot{\exists} v\phi (v)\right)\equiv \exists xT\left(\phi \left[\dot{x}/v\right]\right)\right).$

In the above $s,t$ range over (codes of) terms, $\phi$ , $\psi$ range over codes of sentences of the arithmetical language ( ${\mathrm{\mathcal{L}}}_{PA}$ ), and $\phi (v)$ ranges over (codes of) formulae of ${\mathrm{\mathcal{L}}}_{PA}$ . The extension of $T$ in each model of ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]$ is essentially a full satisfaction class.

${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]$ is well known to be a conservative extension of $\mathrm{PA}$ [3]. However, as observed already in the cited paper, it admits very pathological interpretations. In particular, there are models of ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]$ in which, for some nonstandard $a$ , the sentence ${\left(0=1\right)}^a$ is in the extension of the $T$ predicate, where ${\left(0=1\right)}^0=\left(0=1\right)$ and ${\left(0=1\right)}^{n+1}={\left(0=1\right)}^n\vee {\left(0=1\right)}^n$ . It is another classical fact, that after adding full induction scheme for the extended language the resulting theory (usually denoted with $\mathrm{CT}$ ) eliminates such pathologies. However, such a theory is a non-conservative extension of $\mathrm{PA}$ . The Tarski Boundary project seeks to establish which principles can ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]$ be extended with, so that the resulting theory remains conservative over $\mathrm{PA}$ .

In the first part of the talk we shall look at the non-conservative side of the Tarski Boundary. We shall start from an obviously non-conservative principle of Global Reflection for $\mathrm{PA}$ (GR), which asserts “All theorems of $\mathrm{PA}$ are true” and provide some recently discovered truth-theoretic principles which are equivalent to it (from [1, 4]). The main message here is that ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]+$ GR is a robust theory, which admits many, apparently very different, axiomatizations. Additionally, it turns out to be mutually $\omega$ -interpretable with the subsystem of second order arithmetic $\mathrm{AC}{\mathrm{A}}_0^{\prime }$ . Then we shall enter the realm of non-conservative theories of truth provable in ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]$  + GR. We explain that each such theory shares arithmetical consequences with an extension of ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]$ by a sentence “All sentences from $\delta$ are true,” where $\delta$ is proof-theoretically reducible to the standard axiomatization of $\mathrm{PA}$ (we denote such sentences with $T\left[\delta \right]$ ) [2].

In the second part we look at the conservative side of the boundary. We give some examples of proper extensions of ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]$ which occupy this territory. Last but not least, we provide some insights into the structure of the fragment of the Lindenbaum algebra of ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]$ consisting of those sentences of the form $T\left[\delta \right]$ (as defined above) for which ${\mathrm{CT}}^{-}\left[\mathrm{PA}\right]+T\left[\delta \right]$ remains on the conservative side of the boundary.

[1] C. Cieśliński, M. Łełyk, and B. Wcisło, The two halves of disjunctive correctness, preprint, 2021, arXiv:2108.13718 .

[2] A. Enayat and M. Łełyk, Axiomatizations of PA: A truth theoretic study, part I, submitted.

[3] H. Kotlarski, S. Krajewski, and A. Lachlan, Construction of satisfaction classes for nonstandard models. Canadian Mathematical Bulletin , vol. 24 (1981), no. 3, pp. 283–293.

[4] M. Łełyk, Model theory and proof theory of the global reflection principle, submitted.

▸ KEN MCALOON, Models of arithmetic–its long, slow development.

Department of Computer and Information Science, Brooklyn College, Brooklyn, NY 11210, USA, and Graduate Center, City University of New York, New York, NY 10016, USA.

E-mail: [email protected].

Many currents converged to give rise to Models of Arithmetic as a full-fledged field of research of its own within Mathematical Logic. We will discuss how the subject was built up on contributions from people working in recursion theory, proof theory, set theory, model theory, and miscellaneous topics over a long period of time.

▸ BARTOSZ WCISŁO, Properties characterising truth and satisfaction.

Instytut Filozofii, University of Gdańsk, Wydział Nauk Społecznych ul. Jana Bażyńskiego 4, 80-309 Gdańsk, Poland.

E-mail: [email protected].

Satisfaction and truth classes are subsets of models of arithmetic which satisfy certain truth-like axioms. One of the basic such axioms is compositionality. For instance, (a Gödel code of) a sentence $\phi \wedge \psi$ is supposed to be a member of a compositional truth class $T$ iff both $\phi \in T$ and $\psi \in T$ .

It turns out that the presence of truth or satisfaction classes in a model of Peano Arithmetic ( $\mathrm{PA}$ ) imposes a number of model-theoretic properties on the underlying arithmetical structure. For instance, by results of [1], any model of Peano Arithmetic containing a full satisfaction class is recursively saturated. Another example is that if we take any extension of models $\left(M,S\right)\subseteq \left({M}^{\prime },{S}^{\prime}\right)$ such that $S,{S}^{\prime }$ are (full or partial) satisfaction classes and $\left(M,S\right)$ is a substructure of $\left({M}^{\prime },{S}^{\prime}\right)$ in the expanded language with a predicate denoting the satisfaction class, then $M$ , the arithmetical reduct of $\left(M,S\right)$ , is an elementary submodel of ${M}^{\prime }$ .

Satisfaction and truth classes can be characterised axiomatically, as subsets satisfying certain first-order clauses, like induction or compositionality. We can therefore consider in a more abstract manner an arbitrary theory $\mathrm{U}$ which guarantees that the underlying arithmetical structure satisfies such truth-related properties. For instance, a theory $\mathrm{U}$ imposes recursive saturation if any model of $\mathrm{PA}$ which can be expanded to a model of $\mathrm{U}$ is recursively saturated.

It turns out that in many cases theories with such truth-like model-theoretic consequences can be conversely shown to define a certain form of truth predicate. For instance, it can be shown that if a theory $\mathrm{U}$ imposes recursive saturation on models of $\mathrm{PA}$ , then in every model one can define a (noninductive) satisfaction predicate which is compositional on a cut of formulae, possibly the standard cut. Consequently, if $M\subseteq {M}^{\prime }$ is a submodel in the sense of a theory $\mathrm{U}$ , then the arithmetical reduct of $M$ is an elementary submodel of the arithmetical reduct of ${M}^{\prime }$ .

In our talk, we will discuss certain model-theoretic properties imposed by the presence of satisfaction and truth predicates and we will present certain results showing how to define truth and satisfaction predicates in theories which impose some truth-related conditions on models of $\mathrm{PA}$ .

The results discussed in this talk are a joint work with Mateusz Łełyk.

[1] A. Lachlan, Full satisfaction classes and recursive saturation. Canadian Mathematical Bulletin vol. 24 (1981), pp. 295–297.

Abstracts of invited talks in the Special Session on Set Theory

▸ DANA BARTOŠOVÁ, MIRNA DŽAMONJA, REHANA PATEL, AND LYNN SCOW, Ramsey theory in ultraproducts of finite structures.

Department of Mathematics, University of Florida, 1400 Stadium Road, Gainesville, FL, USA.

E-mail: [email protected].

IRIF, Université de Paris, Bâtiment Sophie Germain, Case courrier 7014, 8 Place Aurélie Nemours, 75205 Paris Cedex 13, France.

AIMS-Senegal , 92RR+VMQ, Mbour, Senegal, and Bentley University, 175 Forest Street, Waltham, MA 02452, USA.

California State University, San Bernardino, 5500 University Parkway, San Bernardino, CA 92407, USA.

Ramsey theory of classes of finite structures has been studied since the 1960s and in the past two decades it has seen rapid progress. We show that countable ultraproducts of classes of finite structures with finite Ramsey degrees have analogous Ramsey theoretic behaviour to the class itself with respect to internal colourings. In particular, let $\mathcal{K}$ be a class of finite structures with a cofinal sequence ${\left({K}_i\right)}_{i\in \omega }$ and suppose that $A\in \mathcal{K}$ has Ramsey degree $d$ in $\mathcal{K}$ . Let $\mathcal{U}$ be a non-principal ultrafilter on $\omega$ . Then, for any internal colouring $c$ of copies of $A$ in ${\Pi}_{i\in \omega }{K}_i/\mathcal{U}$ by finitely many colours, there is a copy of any countable structure whose finite substructures are in $\mathcal{K}$ that takes on at most $d$ colours on copies of $A$ .

▸ FILIPPO CALDERONI, Descriptive set theoretic rigidity and countable Borel equivalence relations.

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

E-mail: [email protected].

URL Address: https://filippoc.people.uic.edu.

Descriptive set theoretic rigidity asserts that the Borel cardinality of the orbit space of certain actions of groups “remembers” a lot about the acting group. For example, Adams and Kechris [1] proved that if one considers the canonical action of ${\mathrm{GL}}_n\left(\mathrm{\mathbb{Z}}\right)$ on ${\mathbb{T}}^n$ , then ${\mathbb{T}}^n/{\mathrm{GL}}_n\left(\mathrm{\mathbb{Z}}\right)$ has the same Borel cardinality as ${\mathbb{T}}^m/{\mathrm{GL}}_m\left(\mathrm{\mathbb{Z}}\right)$ if and only if $m=n$ . In this talk we discuss some new results of descriptive set theoretic rigidity for the action of the groups of rational rotations over the Euclidean spheres [2].

[1] S. Adams and A. S. Kechris, Linear algebraic groups and countable Borel equivalence relations. Journal of the American Mathematical Society , vol. 13 (2000), no. 4, pp. 909–943.

[2] F. Calderoni, Rotation equivalence and cocycle superrigidity for compact actions, preprint, 2022. arXiv:2203.05135 .

▸ RUIYUAN CHEN, A representation theorem for cardinal algebras.

Department of Mathematics and Statistics, CRM/McGill University, 805 Sherbrooke Street West, Montréal, QC H3A 0B9, Canada.

E-mail: [email protected].

Tarski’s 1949 theory of cardinal algebras seeks to axiomatize key features of cardinal arithmetic without assuming the axiom of choice, and has recently found several applications to Borel equivalence relations. The theory is remarkable in its efficiency: from a few simple axioms, Tarski (and later authors) derive seemingly all conceivable “natural” properties of countable addition in familiar algebras such as $\left[0,\infty \right]$ . This talk will present a result partially explaining this phenomenon: every cardinal algebra $A$ embeds into an algebra of Borel $\left[0,\infty \right]$ -valued functions (on a standard Borel space when $A$ is countably presented, and more generally on a locale). The result is proved for a more general universally Horn-axiomatizable class of “countably additive posets” that includes all cardinal algebras, and extends analogous results of Wehrung in the finitely additive setting as well as of Tix in the setting of continuous domains.

▸ ARISTOTELIS PANAGIOTOPOULOS, Strong ergodicity phenomena for Bernoulli shifts of bounded algebraic dimension.

Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA.

E-mail: [email protected].

For every Polish permutation group $P\le \mathrm{Sym}\left(\mathrm{\mathbb{N}}\right)$ let $A\mapsto {\left[A\right]}_P$ be the assignment which maps every $A\subseteq \mathrm{\mathbb{N}}$ to the set of all $k\in \mathrm{\mathbb{N}}$ whose orbit under the action of the stabilizer ${P}_A$ of $A$ is finite. Then $A\mapsto {\left[A\right]}_P$ is a closure operator and hence it endows $P$ with a natural notion of dimension $\dim (P)$ . This notion of dimension has been extensively studied in model theory when $A\mapsto {\left[A\right]}_P$ satisfies additionally the exchange principle; that is, when $A\mapsto {\left[A\right]}_P$ forms a pregeometry. However, under the exchange principle, every Polish permutation group $P$ with $\dim (P)<\infty$ is locally compact and therefore unable to generate any “wild” dynamics. In this talk we will discuss the relationship between $\dim (P)$ and certain strong ergodicity phenomena in the absence of the exchange principle. In particular, for every $n\in \mathrm{\mathbb{N}}$ we will provide a Polish permutation group $P$ , with $\dim (P)=n$ , whose Bernoulli shift $P\curvearrowright {\mathrm{\mathbb{R}}}^{\mathrm{\mathbb{N}}}$ is generically ergodic relative to the injective part of the Bernoulli shift of any permutation group $Q$ with $\dim (Q)<n$ . We will use this to exhibit an equivalence relation of pinned cardinal ${\aleph}_1^{+}$ which strongly resembles Zapletal’s counterexample to a question of Kechris, but which does not Borel reduce to the latter. Our proofs rely on the theory of symmetric models of choiceless set-theory and in the process we establish that a vast collection of symmetric models admit a theory of supports similar to the basic Cohen model.

This is joint work with Assaf Shani.

▸ DIMA SINAPOVA, Combinatorial principles and singular cardinals.

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

E-mail: [email protected].

Combinatorial properties at infinite cardinals are used to address ZFC constraints versus what can be obtained by the method of forcing. We will focus on two key principles: the tree property and stationary reflection. Both are compactness type principles with deep connection to large cardinals. In this talk we will go over recent results on how these principles interact with cardinal arithmetic, especially at the level of singular cardinals.

▸ KONSTANTIN SLUTSKY, ${\mathrm{L}}^1$ full groups of flows.

Department of Mathematics, Iowa State University, 411 Morrill Road, Ames, IA 50011, USA.

E-mail: [email protected].

URL Address: https://kslutsky.com.

It has been proved by Foreman, Rudolph, and Weiss [4] that classification of measure-preserving transformations up to conjugation is an infeasible task. Long before the descriptive set theoretical viewpoint allowed for estimating the complexity of this classification problem, ergodic theorists shifted their attention to weaker forms of equivalence. The paramount idea here belongs to Dye [2, 3], who introduced the concept of a full group of an action, which became an important algebraic invariant encoding the orbit partition. The scope of applicability of these ideas grew in a multitude of directions, two of which are most relevant to our talk. First, the concept of a full group was generalized to Borel measure-preserving actions of Polish groups by Carderi and Le Maître [1] and second, various subgroups of full groups were found to correspond to stronger types of equivalence than the orbit equivalence of actions. The latter phenomena first appeared prominently in Cantor dynamics in the work of Giordano, Putnam, and Skau [5], who showed that the so-called topological full groups encode flip-conjugacy of minimal homeomorphisms of the Cantor set. Motivated by this correspondence, Le Maître [6] introduced ${\mathrm{L}}^1$ full groups of discrete group actions as the analog of topological full groups within the framework of ergodic theory.

In this talk we will discuss our recent work with Le Maître [7] on the ${\mathrm{L}}^1$ full groups of general Polish group actions. We show that under minor assumptions on the actions, topological derived subgroups of ${\mathrm{L}}^1$ full groups are topologically simple and—when the acting group is locally compact and amenable—are whirly amenable and generically two-generated. For measure-preserving actions of the real line (also known as measure-preserving flows), the topological derived subgroup of an ${\mathrm{L}}^1$ full group coincides with the kernel of the index map, which implies that ${\mathrm{L}}^1$ full groups of free measure-preserving flows are topologically finitely generated if and only if the flow admits finitely many ergodic components. The latter is in a striking contrast to the case of ergodic $\mathrm{\mathbb{Z}}$ -actions, where finite topological rank is equivalent to finiteness of the entropy of the action.

[1] A. Carderi and F. Le Matre, More Polish full groups. Topology and Its Applications , vol. 202 (2016), pp. 80–105.

[2] H. A. Dye, On groups of measure preserving transformations I. American Journal of Mathematics , vol. 81 (1959), pp. 119–159.

[3] ———, On groups of measure preserving transformations II. American Journal of Mathematics , vol. 85 (1963), pp. 551–576.

[4] M. Foreman, D. J. Rudolph, and B. Weiss, The conjugacy problem in ergodic theory. Annals of Mathematics. Second Series , vol. 173 (2011), no. 3, pp. 1529–1586.

[5] T. Giordano, I. F. Putnam, and C. F. Skau, Full groups of Cantor minimal systems. Israel Journal of Mathematics , vol. 111 (1999), pp. 285–320.

[6] F. Le Maître, On a measurable analogue of small topological full groups. Advances in Mathematics , vol. 332 (2018), pp. 235–286.

[7] F. Le Matre and K. Slutsky, ${\mathrm{L}}^1$ full groups of flows, preprint, 2021, arXiv:2108.09009 .

▸ JENNA ZOMBACK, Pointwise ergodic theorems for semigroup actions.

Department of Mathematics, University of Illinois, Champaign, IL, USA.

E-mail: [email protected].

We discuss new pointwise ergodic theorems for free semigroup actions, where the averages are taken over trees. This is joint work with Anush Tserunyan.

Abstracts of contributed talks

▸ MATTHEW DEVILBISS AND JAMES FREITAG, Strong minimality of generic differential equations.

Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, IL, USA.

E-mail: [email protected].

Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, Chicago, IL, USA.

E-mail: [email protected].

In this talk, I will outline a new technique for showing that non-linear algebraic differential equations are strongly minimal. This is used to prove the strong minimality of generic differential equations with sufficiently large degree, answering a question of Poizat (1980). Time permitting, I will also discuss ongoing work in applying this method to differential equations of interest whose coefficients are not generic.

▸ VERA FISCHER AND MICHAŁ TOMASZ GODZISZEWSKI, Spectra of maximal almost orthogonal families of projections in the Calkin algebra.

Institute of Philosophy, University of Warsaw, Warsaw, Poland, and University of Łódź, Łódź, Poland.

E-mail: [email protected].

Institute of Mathematics, University of Vienna, Vienna, Austria.

E-mail: [email protected].

Let $H$ be an infinite dimensional separable complex Hilbert space with inner product $\left\langle \cdot |\cdot \right\rangle$ . Let $\mathrm{\mathcal{B}}(H)$ be a Banach space of bounded linear operators on $H$ with the operator norm. In case when $H={\mathrm{\ell}}^2\left(\omega \right)$ , we can distinguish a particular subalgebra of the Banach space $\mathrm{\mathcal{B}}(H)$ : we define $\mathcal{K}(H)$ as the smallest Banach subalgebra of $\mathrm{\mathcal{B}}(H)$ containing all finite-dimensional operators, and we call its elements compact operators. So, $T\in \mathrm{\mathcal{B}}(H)$ is compact if it is a limit of finite-rank operators. (Equivalently, an operator $T\in \mathrm{\mathcal{B}}(H)$ is compact if the image of the closed unit ball $B\subset H$ under $T$ is precompact, which in turn is equivalent to $T$ being weak-norm continuous when restricted to $B$ .) The collection $\mathcal{K}(H)$ has the structure of a ${\mathrm{C}}^{\ast }$ -algebra and is a ring-theoretical ideal in $\mathrm{\mathcal{B}}(H)$ .

The Calkin algebra is the quotient ${\mathrm{C}}^{\ast }$ -algebra $\mathcal{C}(H)=\mathrm{\mathcal{B}}(H)/\mathcal{K}(H),$ where the quotient mapping is denoted by $\pi :\mathrm{\mathcal{B}}(H)\to \mathcal{C}(H).$ Every separable ${\mathrm{C}}^{\ast }$ -algebra is isomorphic to a ${\mathrm{C}}^{\ast }$ -subalgebra of the Calkin algebra. We are interested in the set of projections in the Calkin algebra, i.e., in the set: $P\left(\mathcal{C}(H)\right)=\{p\in \mathcal{C}(H):p={p}^{\ast}={p}^2\}.$ For a set $A\subseteq \omega$ , let ${P}_A$ be the projection onto ${\mathrm{\ell}}^2(A)\subseteq {\mathrm{\ell}}^2\left(\omega \right)$ . The map $A\mapsto {P}_A$ embeds the Boolean algebra $\mathcal{P}\left(\omega \right)$ into the space of projections $P(H)$ . The map $A\mapsto \pi \left({P}_A\right)$ defines an embedding of $\mathcal{P}\left(\omega \right)/\mathrm{fin}$ into $P\left(\mathcal{C}(H)\right)$ . This map is called the diagonal embedding. A family of projections $A\subseteq P\left(\mathcal{C}(H)\right)$ is almost orthogonal if the product of any two elements $p,q\in A$ is the zero of the algebra $\mathcal{C}(H)$ . In this paper we investigate the possible spectra of maximal almost orthogonal families of projections in the Calkin algebra. The collection of projections $P\left(\mathcal{C}(H)\right)$ is a natural object to study, as it can be identified with the lattice of projections on $\mathrm{\mathcal{B}}(H)$ modulo a natural equivalence relation, so we can identify elements of $P\left(\mathcal{C}(H)\right)$ with closed subspaces of $\mathrm{\mathcal{B}}(H)$ .

An important result by Wofsey is:

Theorem (Wofsey, 2007). Let $A$ be a family of disjoint uncountable sets. Then

$$\begin{align*}{\mathrm{\mathbb{P}}}_A\Vdash \forall X\in A\exists Y\left(|Y|=|X|\&Y\;\mathrm{is}\;\mathrm{a}\;\mathrm{m}.\mathrm{a}.\mathrm{o}.\mathrm{f}.\right).\end{align*}$$

In other words, for any family of cardinals $C$ there is a forcing notion such that $C$ is included in the spectrum of m.a.o.f.’s. Wofsey’s result is an operator-theoretic counterpart of the (positive) result of Hechler concerning spectra of maximal almost disjoint families of sets. We have been searching for an operator-theoretic counterpart of the (negative) strengthening of Hechler’s result on spectra of mad families given by Blass. Thus, our main question in this paper is: can we isolate conditions, under which a specific set of cardinals $C$ can be not only included, but actually equal to the spectrum of maximal almost orthogonal family of projections in a given model of set theory?

Theorem. Assume $GCH$ . Let $C$ be a set of cardinals satisfying the following conditions:

• • $\forall \kappa \in C\kern0.24em \kappa$ is uncountable,

• • $C$ is closed,

• • $\forall \kappa \in \left[{\aleph}_1,|C|\right]\kern0.24em \kappa \in C,$

• • $\forall \kappa \in C\;\mathrm{cf}\left(\kappa \right)=\omega \Rightarrow {\kappa}^{+}\in C.$

Then there exists a forcing notion $\mathrm{\mathbb{P}}$ such that it satisfies the countable chain condition and forces the spectrum of maximal almost orthogonal families to be exactly $C$ .

▸ JARL G. TAXERÅS FLATEN, Internal injectivity of modules in higher toposes.

Department of Mathematics, Western University, 1151 Richmond Street, London, ON, Canada.

E-mail: [email protected].

Any “internal” property in a (higher) topos ought to be stable by pullback. While this is automatically the case for properties coming from an internal language, such properties are often unwieldy and one seeks simpler characterizations. Our present interest is in comparing the notion of injectivity of a module coming from HoTT, to the preexisting notion of internal injectivity. This is part of joint, ongoing work with Dan Christensen on the interpretation of homological algebra from HoTT into higher toposes.

In the 80s, Roswitha Harting proved that internal injectivity of abelian groups in an elementary topos $\mathrm{\mathcal{E}}$ is pullback-stable. Central is her construction [1] of a left-exact left adjoint to pullback of abelian groups, called the internal coproduct:

$$\begin{align*}{\oplus}_X:\mathrm{Ab}\left(\mathrm{\mathcal{E}}/X\right)\leftrightarrows \mathrm{Ab}\left(\mathrm{\mathcal{E}}\right):{X}^{\ast }.\end{align*}$$

In 2017, Ingo Blechschmidt remarked in his thesis that Harting’s construction works for modules as well, and further proves that internal injectivity of modules corresponds to injectivity in the “Stacks semantics” of an elementary topos.

We prove that for higher toposes satisfying the external axiom that “sets cover,” internal injectivity of modules coincides with the notion of injectivity coming from HoTT. Thus the notions coincide for $\infty$ -sheaves on a $1$ -site. In general, we show that internal injectivity is stable by pullback over $0$ -truncated objects as well as pointed, connected objects. When pulling back over untruncated objects, the analog of the internal coproduct is an internal colimit. We give a novel construction of this internal colimit in HoTT, and produce examples demonstrating that it may fail to be left-exact.

[1] R. Harting, Internal coproduct of abelian groups in an elementary topos. Communications in Algebra , vol. 10 (1982), no. 11, pp. 1173–1237.

▸ OMER BEN-NERIA AND THOMAS GILTON, Club Stationary Reflection and the Special Aronszajn Tree Property.

Department of Mathematics. The Dietrich School of Arts and Sciences, 301 Thackeray Hall, Pittsburgh, PA 15260, USA.

Einstein Institute of Mathematics, Hebrew University of Jerusalem, Jerusalem, Israel.

E-mail: [email protected].

E-mail: [email protected].

A fruitful line of research in set theory investigates the tension between compactness and incompactness principles. Given this tension, it is of interest when principles in these categories are in fact jointly consistent. In a recent result with Omer Ben-Neria, we have established such a joint consistency result, showing that Club Stationary Reflection [2] is consistent with the Special Aronszajn Tree property [1] on the cardinal ${\omega}_2$ .

The tension between these two principles shows up in the very different properties of our posets (specializing, and club adding) which we must maintain throughout the course of our construction. To build the desired posets, we first introduce the idea of an $\mathrm{\mathcal{F}}$ -Strongly Proper poset ( $\mathrm{\mathcal{F}}$ is the filter on $\kappa$ dual to the ineffability ideal). These posets use systems of continuous residue functions to witness strong genericity. We then show how to specialize trees on ${\omega}_2$ following an $\mathrm{\mathcal{F}}$ -strongly proper forcing, generalizing the classic result of Laver and Shelah. We also show that the composition of Levy collapsing an ineffable cardinal followed by our club adding is $\mathrm{\mathcal{F}}$ -strongly proper.

Additionally, we develop new ideas for preserving Aronszajn trees and for stationary sets which do not make use of the usual closure assumptions. For instance, we show that our club adding posets don’t add branches to Aronszajn trees of interest and that quotients of the specializing forcing preserve stationary sets of countable cofinality.

In this talk we will survey these two classes of posets and sketch our proof of specializing, as well as our preservation theorems.

[1] R. Laver and S. Shelah, The ${\aleph}_2$ -Souslin hypothesis. Transactions of the American Mathematical Society , vol. 264 (1981), no. 2, pp. 411–417.

[2] M. Magidor, Reflecting stationary sets. The Journal of Symbolic Logic , vol. 47 (1983), no. 4, pp. 755–771.

▸ VICTORIA GITMAN, MICHAŁ TOMASZ GODZISZEWSKI, TOBY MEADOWS, AND KAMERYN WILLIAMS, On axioms for multiverses of set theory .

Department of Mathematics and Statistics, Sam Houston State University, Huntsville, TX 77340, USA.

E-mail: [email protected].

Graduate Center, City University of New York, New York, NY 10017, USA.

E-mail: [email protected].

Institute of Philosophy, University of Lódź, Łódź, Poland, and University of Warsaw, Warsaw, Poland.

E-mail: [email protected].

Department of Logic and Philosophy of Science, University of California, Irvine, Irvine, CA 92697, USA.

E-mail: [email protected].

Recursive saturation, introduced by Barwise and Schlipf, is a robust notion, one which has proved to be important for the study of nonstandard models. In particular, it is ubiquitous in the model theory of axiomatic theories of truth, e.g., in the topic of satisfaction classes (one can show that if $M\models ZFC$ is a countable $\omega$ -nonstandard model, then $M$ admits a satisfaction class iff $M$ is recursively saturated). V. Gitman and J. Hamkins showed in A Natural Model of the Multiverse Axioms that the collection of countable, recursively saturated models of set theory satisfy the so-called Hamkins’s Multiverse Axioms. The property that forces all the models in the Multiverse to be recursively saturated is the so-called Well-Foundedness Mirage axiom which asserts that every universe is $\omega$ -nonstandard from the perspective of some larger universe, or to be more precise, that: if a model $M$ is in the multiverse then there is a model $N$ in the multiverse such that $M$ is a set in $N$ and $N\models$ “ $M$ is $\omega$ -nonstandard.” Inspection of the proof led to a question if the recursive saturation could be avoided in the Multiverse by weakening the Well-Foundedness Mirage axiom. Our main results answer this in the positive. We give two different versions of the Well-Foundedness Mirage axiom—what we call Weak Well-Foundedness Mirage (saying that if $M$ is a model in the Multiverse then there is a model $N$ in the Multiverse such that $M\in N$ and $N\models$ “ $M$ is nonstandard”) and Covering Well-Foundedness Mirage (saying that if $M$ is a model in the Multiverse then there is a model $N$ in the Multiverse with $K\in N$ such that $K$ is an end-extension of $M$ and $N\models$ “ $K$ is $\omega$ -nonstandard”). I will present constructions of two different Multiverses satisfying these two weakened axioms. This is joint work with V. Gitman. T. Meadows, and K. Williams.

▸ SAMSON LEUNG, Axiomatizing AECs and applications.

Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213, USA.

E-mail: [email protected].

URL Address: http://www.math.cmu.edu/~wangchil/.

Let $\mathbf{K}$ be an abstract elementary class and $\lambda =\mathrm{LS}\left(\mathbf{K}\right)$ . $K$ can be axiomatized by a sentence in ${L}_{{\left({2}^{\lambda}\right)}^{+},\, {\lambda}^{+}}$ , allowing game quantification. This extends Kueker’s result which assumes finite character and countable $\mathrm{LS}\left(\mathbf{K}\right)$ . It is also a parallel to Shelah–Villaveces result which demands a much higher complexity of junctions but without game quantification. Shelah’s presentation theorem gives $K= PC\left(T,\Gamma, \mathrm{L}\left(\mathbf{K}\right)\right)$ where $T$ is a first-order theory in an expansion of $\mathrm{L}\left(\mathbf{K}\right)$ and $\Gamma$ is a set of $T$ -types. We provide a better bound of $\mid \Gamma \mid$ in terms of ${I}_2\left(\lambda, \mathbf{K}\right)$ . We also give conditions under which the categoricity in two successive cardinals implies the existence of models in the next cardinal. This improves the result of Shelah and as a corollary we extend Shelah–Vasey’s result.

▸ SHAY ALLEN LOGAN, Easy proofs of strong variable sharing theorems.

Department of Philosophy, Kansas State University, 201 Dickens Hall, Manhattan, KS 66506, USA.

E-mail: [email protected].

Formal symptoms of relevance concern propositional variables shared between antecedent and consequent of provable conditionals. The earliest such result is in [1]. In [2], Brady showed that for weak enough logics, very strong variable sharing results are available. In [3], I proved a strengthening of Brady’s result. Both Brady’s proof and mine use a method that I find to be fairly philosophically opaque. In this talk I will give more illuminating proofs of weak versions of these results.

The depth of an occurrence of an atom is the number of entailments it is nested under. So the occurrence of $p$ in $p$ is a depth 0 occurrence; the occurrence of $p$ in $\left(p\to q\right)\to r$ is a depth 2 occurrence. Depth substitutions are functions that replace each atom at a given depth with a formula. Depth substitutions are not uniform—they may replace an atom at one depth with one formula and replace the same atom at a different depth with a different formula.

The logic $L$ is closed under depth substitutions when applying a depth substitution to a theorem always produces another theorem. In this talk I show that many weak relevant logics are closed under depth substitutions. I then use this fact to give illuminating proofs of both Brady’s result and my recent strengthening of it.

[1] N. D. Belnap, Entailment and relevance. The Journal of Symbolic Logic , vol. 25 (1960), no. 2, pp. 144–146.

[2] R. T. Brady, Depth relevance of some paraconsistent logics. Studia Logica , vol. 43 (1984), no. 1, pp. 67–73.

[3] S. A. Logan, Strong depth relevance. Australasian Journal of Logic , vol. 18 (2021), no. 6, pp. 645–656.

▸ JUAN AGUILERA, ROBERT S. LUBARSKY, AND CONNOR WATSON, On winning strategies in ${\Sigma}_2^0$ games.

Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Vienna, Austria, and Department of Mathematics, Ghent University, Ghent, Belgium.

E-mail: [email protected].

Department of Mathematical Sciences, Florida Atlantic University, 777 Glades Road, Boca Raton, FL 33431, USA.

E-mail: [email protected].

Department of Mathematical Sciences, Florida Atlantic University, 777 Glades Road, Boca Raton, FL 33431, USA.

E-mail: [email protected].

It is known where winning strategies for player I in ${\Sigma}_2^0$ games appear (and for that matter also for games in the standard Boolean difference hierarchy over ${\Sigma}_2^0$ ). But where are strategies for player II? The answer is not quite so straightforward as one might think.

[1] C. Heinatsch and M. Möllerfeld, The determinacy strength of ${\Pi}_2^1$ -comprehension. Annals of Pure and Applied Logic , vol. 161 (2010), pp. 1462–1470.

[2] Y. Moschovakis, Descriptive Set Theory , second ed., American Mathematical Society, 2009 .

[3] P. Wolfe, The strict determinateness of certain infinite games. Pacific Journal of Mathematics , vol. 5 (1955), pp. 841–847.

▸ DIEGO A. ROJAS, Effective vague convergence of measures on the real line.

Department of Mathematics, Iowa State University, 396 Carver Hall, 411 Morrill Road, Ames, IA 50011, USA.

E-mail: [email protected].

Recently, McNicholl and Rojas [1] developed a framework to study the effective theory of weak convergence of measures on $\mathrm{\mathbb{R}}$ . In this talk, we introduce a similar framework to study the effective theory of vague convergence of measures on $\mathrm{\mathbb{R}}$ . In particular, we define two effective notions of vague convergence of measures in $\mathrm{\mathbb{R}}$ and show that they are equivalent. However, unlike effective weak convergence, we show that an effectively vaguely convergence sequence need not have a computable limit. Nevertheless, we show that for a computable sequence ${\left\{{\mu}_n\right\}}_{n\in \mathrm{\mathbb{N}}}$ of measures in $\mathrm{\mathbb{R}}$ , effective weak and vague convergence of measures coincide whenever ${\left\{{\mu}_n\left(\mathrm{\mathbb{R}}\right)\right\}}_{n\in \mathrm{\mathbb{N}}}$ has a computable modulus of convergence.

[1] T. H. McNicholl and D. A. Rojas, Effective notions of weak convergence of measures on the real line, preprint, 2021, arXiv:2106.00086 .

▸ DAVID J. WEBB, Reducibilities between $\mathrm{MLR}$ and $\mathrm{Either}\left(\mathrm{MLR}\right)$ .

Department of Mathematics, University of Hawaii at Manoa, 2565 McCarthy Mall, Honolulu, HI 96822, USA.

E-mail: [email protected].

We investigate which reducibility notions suffice to output a (Martin-Löf) random real given a pair of input oracles, an unknown member of which is itself random. We demonstrate that truth-table reducibility suffices, showing that the classes of Kolmogorov–Loveland random reals and Martin-Löf random reals are truth-table Medvedev equivalent, answering a question of Miyabe. We also investigate whether even stronger reducibilities can be used, showing that positive, linear, and bounded truth-table reductions can fail to output randomness given such oracles.

▸ YUXIN ZHOU, Distinguish chromatic numbers for isosceles triangles in choiceless set theory.

Department of Mathematics, University of Florida, 1400 Stadium Road, Gainesville, FL 32601, USA.

E-mail: [email protected].

URL Address: https://people.clas.ufl.edu/yuxinzhou/.

For $n$ a positive natural number, let ${\Gamma}_n$ be the hypergraph of isosceles triangles on ${\mathrm{\mathbb{R}}}^n$ . Under the axiom of choice, the existence of a countable coloring for ${\Gamma}_n$ holds for every $n$ . Without the axiom of choice, the chromatic numbers may or may not be countable. With an inaccessible cardinal assumption, there is a model of ZF + DC in which ${\Gamma}_2$ has countable chromatic number while ${\Gamma}_3$ has uncountable chromatic number. This result is obtained by a balanced forcing over the symmetric Solovay model.

Abstracts of talks presented by title

▸ ALEXANDR BESSONOV, Gödel’s first incompleteness theorem is numerically dependent.

Institute of Philosophy and Law, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia, and Institute of Philosophy and Law, Novosibirsk State University, Novosibirsk, Russia.

E-mail: [email protected].

In proving the first incompleteness theorem, Gödel constructs a formula with one free variable (up to notation) $\Phi (x)=\forall y\neg \mathrm{Prov}\left(x,y\right)$ , numeralwise expressing the fact that a formula with number $x$ is unprovable. If the Gödel number of $\Phi (x)$ is $n$ , then an unsolvable Gödel formula (we denote it by $G$ ) is obtained from $\Phi (x)$ by substituting the numeral $\mathbf{n}$ for the variable $x$ .

It is generally accepted that the first theorem establishes the unsolvability of $G$ in Dedekind–Peano (PA) formal arithmetic as such. In fact, Gödel proved only the unsolvability of $G$ in a very specific fixed numbering of the PA syntax. However, the definition of the unsolvability of a formula in arithmetic is numerically independent: there is no mention whatsoever of any numbering. The Gödel’s proof of the unsolvability of $G$ is valid only if a numbering was fixed by Gödel himself and the Gödel number of $\Phi (x)$ equals $n$ . A numbering other than Gödel’s will have another formula $\forall y\neg {\mathrm{Prov}}_{\mathrm{new}}\left(x,y\right)$ with a different number ${n}_{\mathrm{new}}$ , and another unsolvable (in this numbering) formula ${G}_{\mathrm{new}}$ . And each numbering will have its own formula. In order to establish the incompleteness of PA, however, we must prove the unsolvability of $G$ outside some numbering, at least its unsolvability inside any other numbering. What will happen to the old formula $G$ in the new numbering? What happens if the formula $\Phi (x)$ is assigned a different number, or if $n$ is the number of some other formula, or if it is not at all a Gödel number? Can we prove the unsolvability of $G$ in the new numbering?

Here is an example of the formula constructed (as $G$ ) by substituting into the same formula of PA the Gödel number of the same arithmetic formula, which is unsolvable in one numbering and solvable in another. Consider a formula with one free variable

(*) $$\begin{align}G\&\left(x=\mathbf{n}\right).\end{align}$$

Substituting $\mathbf{n}$ into $\left(\ast \right)$ , we obtain the formula $G\&\left(\mathbf{n}=\mathbf{n}\right)$ , which is obviously equivalent to $G$ and is therefore unsolvable if $G$ is unsolvable.

Let’s move on to another numbering, in which $G$ has a number $l$ other than $n$ . Substituting $\mathbf{l}$ in $\left(\ast \right)$ yields the formula $G\&\left(\mathbf{l}=\mathbf{n}\right)$ , the second conjunct of which is refutable in PA since ${\vdash}_{\mathrm{PA}}\neg \left(\mathbf{l}=\mathbf{n}\right)$ for $l\ne n$ , yielding ${\vdash}_{\mathrm{PA}}\neg \left(G\&\left(\mathbf{l}=\mathbf{n}\right)\right)$ .

Thus, the formula obtained by substituting in $\left(\ast \right)$ the number of $G$ for $x$ is unsolvable in Gödel’s own numbering and is solvable (refutable) in some other numbering. Hence, it is possible that a formula constructed in the same way as $G$ is unsolvable in one numbering and solvable in another. Therefore, until we prove that the Gödel formula $G$ remains unsolvable in any other numbering, we have no sufficient grounds to assert that the incompleteness of PA is established in Gödel’s first theorem.

▸ JOACHIM MUELLER-THEYS, Equivalence.

Heidelberg, Germany.

E-mail: [email protected].

We legitimate and categorize the different approaches to equivalence, leading to a natural nomenclature.

0. Let $M\ne \varnothing$ be any domain, $a,b,\dots \in M$ , $P\subseteq M$ , $P(a)$ : iff $a\in P$ , $\mathcal{P}\subseteq \wp (M)$ . We specified similarity and equality by $a{\sim}_Pb$ : iff $P(a)\&P(b)$ , $a{\sim}_{\mathcal{P}}b$ : iff $\exists P\in \mathcal{P}$ $a{\sim}_Pb$ , and $a{\equiv}_Pb$ : iff $P(a)\iff P(b)$ , $a{\equiv}_{\mathcal{P}}b$ : iff $\forall P\in \mathcal{P}$ $a{\equiv}_Pb$ . Among many other things, $a{\sim}_{\mathcal{P}}b$ iff $\exists P\in \mathcal{P}$ $a,b\in P$ , $a{\equiv}_{\mathcal{P}}b$ iff $\forall P\in \mathcal{P}$ : $a\in P\iff b\in P$ ; $a{\equiv}_{\wp (M)}b$ iff $a=b$ .

I. Original Equivalence. Literally, equivalent means to have the same value. This presupposes a valuation $\omega :M\to V$ , where $V\ne \varnothing$ . From the abstract point of view, a valuation is nothing else than a function or a mapping. Now

$$\begin{align*}a{\simeq}_{\omega }b:\mathrm{iff}\kern0.22em \omega (a)=\omega (b)\end{align*}$$

defines the unique equivalence of $\omega$ in the well-known manner.

II. Axiomatic Equivalence. Let $E\subseteq M\times M$ be RST, viz. $E$ is reflexive, symmetrical, and transitive. As usual, $M/E:= \left\{a/E:a\in M\right\}$ , where $a/E:= \left\{b\in M:b\kern0.1em E\kern0.1em a\right\}$ .

For all $\omega$ , ${\simeq}_{\omega }$ is RST. Conversely, one can link various i(n)dentifications to $E$ . In particular, the canonical mapping ${\kappa}_E$ with $a\kern0.1em E\kern0.1em b$ $\iff$ $a/E=b/E$ $\iff$ ${\kappa}_E(a)={\kappa}_E(b)$ $\iff$ $a{\simeq}_{\kappa_E}b$ shows $E$ to be an original equivalence. Hence RST-relations and original equivalences may be identified. This justifies the term (axiomatic) equivalence.

III. Partitional Equivalence. Let $\mathcal{P}$ be any partition (of $M$ ), viz. $M=\cup \mathcal{P}$ , $P\ne \varnothing$ for all $P\in \mathcal{P}$ . $M/E$ is a partition.

We then call ${\sim}_{\mathcal{P}}$ (cf. 0) the partitional similarity induced by $\mathcal{P}$ . ${\sim}_{\mathcal{P}}$ is STR. Since, moreover, as is generally known, $\mathcal{P}$   $=$   $M/{\sim}_{\mathcal{P}}$ and $E$   $=$   ${\sim}_{M/E}$ , as well quotient sets and partitions as partitional similarities and axiomatic equivalences may be identified.

We call ${\equiv}_{\mathcal{P}}$ the partitional equality of $\mathcal{P}$ . $a{\equiv}_{\mathcal{P}}b$ means that $a$ , $b$ correspond with respect to all $P\in \mathcal{P}$ . By the Buchholz Theorem, partitional equality and similarity coincide, i.e., ${\equiv}_{\mathcal{P}}$   $=$   ${\sim}_{\mathcal{P}}$ .

All in all, we may now call ${\cong}_{\mathcal{P}}$   $:\in$   $\left\{{\sim}_{\mathcal{P}},{\equiv}_{\mathcal{P}}\right\}$ the partitional equivalence of $\mathcal{P}$ . We suggest $\simeq$ as a general equivalence symbol.

The following abstracts are referenced: “Similarity and Equality” (2021 ASL Annual Meeting), “Mathematical Theorems on Equality and Unequality” (abstract, LC 2021, by-title; comprising the proven Dichotomy Theorem: All $P$ are $Q$ -equal ( $\forall a,b\in P\;a{\equiv}_Qb$ ) if (and only if) $P\subseteq Q$ or $P\cap Q=\varnothing$ ), and “On the Relations Induced by Partitions” (2022 ASL-JMM, abstracts). Thanks to Fritz Paepcke, “Peana Pesen,” Andreas Haltenhoff, P. Maier-Borst, Wernher Bornemann-von Loeben, Reed David Solomon, and Shannon Miller. Joint work with Wilfried Buchholz.