# Caltech logic seminars (2021-2022)

All times are in Pacific Time.

#### Slides

We introduce a framework for studying "reasonable" classifying invariants, more permitting than "classification by countable structures". This framework respects the intuitions and results about classifications by countable structures, and allows for equivalence relations such as $E_1$ and $E_1^+$ to be "reasonably classifiable" as well. In this framework we show that $E_1$ has classifying invariants which are $\kappa$-sequences of $E_0$-classes for $\kappa = \mathfrak{b}$, and it does not have such classifying invariants if $\kappa < \mathbf{add}(\mathcal{B})$.
The result relies on analysing the tail intersection model $\bigcap_{n < \omega} V[c_n, c_{n+1}, \ldots]$, where $\langle c_0, c_1, \ldots\rangle$ is a generic sequence of Cohen reals.

#### Slides

For every Polish permutation group $P \le \operatorname{Sym}(\mathbb{N})$, let $A \mapsto [A]_P$ be the assignment which maps every $A \subseteq \mathbb{N}$ to the set of all $k \in \mathbb{N}$ whose orbit under the action of the stabilizer $P_F$ of some finite $F \subseteq A$ is finite. Then $A \mapsto [A]_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 [A]_P$ satisfies additionally the exchange principle, that is, when $A \mapsto [A]_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 \mathbb{N}$, we will provide a Polish permutation group $P$ with $\dim(P) = n$ whose Bernoulli shift $P \curvearrowright \mathbb{R}^{\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.

#### Slides

Given an $L_{\omega_1\omega}$-sentence $\varphi$ in a countable language, we call an ergodic $S_\infty$-invariant probability measure on the Borel space of countable models of $\varphi$ (having fixed underlying set) an ergodic model of $\varphi$. I will discuss the number of ergodic models of such a sentence $\varphi$, including the case when $\varphi$ is a Scott sentence. This is joint work with N. Ackerman, C. Freer, A. Kruckman and A. Kwiatkowska.

#### Slides

A directed hypergraph $G$ consists of a vertex set $V$ along with a collection of directed hyperedges $(A, B)$, where $A$ and $B$ are finite subsets of $V$. Given a set of vertices $X$, we think of the edge $(A, B)$ as being on the boundary of $X$ if $X$ intersects $A$ and does not completely contain $B$.
We can generalize the notion of directed hypergraph as follows. A filter graph $G$ consists of an infinite vertex set $V$ along with a collection of edges $(F, G)$, where $F$ and $G$ are filters on $V$. Given a set of vertices $X$, we think of the edge $(F, G)$ as being on the boundary of $X$ if $X$ is $F$-positive and the complement of $X$ is $G$-positive.
Filter graphs seem to be surprisingly graph-like. We'll show that filter graphs satisfy the natural generalization of the max-flow/min-cut theorem, where point masses flowing along directed edges in the usual hypergraph setting are replaced by ultrafilters flowing along filter-edges.

#### Slides

One of the numerous strengthenings of Ramsey's theorem is due to Erdős and Rado, who analyzed what partition properties can be obtained on $m$-subsets of the naturals when colorings are not necessarily finite. Large monochromatic sets may not appear in that case, but there is a finite list of behaviors, called "canonical", to which every coloring reduces. The purpose of this talk will be to remind certain not so well-known analogous theorems of the same flavor that were obtained by Prömel in the eighties for various classes of structures (like graphs or hypergraphs), and to show how such theorems can in fact be deduced in the more general setting of Fraïssé classes.

#### Slides

The talk will be devoted to the isomorphism relations on Borel classes of locally compact Polish metric structures. Using continuous logic, one can prove that they are always Borel reducible to graph isomorphism, which implies, in particular, that isometry of locally compact Polish metric spaces is reducible to graph isomorphism. This answers a question of Gao and Kechris. As a matter of fact, locally compact Polish metric structures behave very much like countable ones. For example, Hjorth, Kechris and Louveau proved that isomorphism of countable structures that is potentially of rank $\alpha + 1$ multiplicative Borel class is reducible to equality on hereditarily countable sets of rank $\alpha$, and the same turns out to be true about locally compact Polish metric structures. Time permitting, I will also discuss certain variants of the Hjorth-isomorphism game, recently introduced by Lupini and Panagiotopoulos.

#### Slides

The point-to-set principle has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces $\mathbb{R}^n$. These are classical questions, meaning that their statements do not involve computation or related aspects of logic.
In this talk I will describe the extension of two algorithmic fractal dimensions --- computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions $\dim(x)$ and $\operatorname{Dim}(x)$ to individual points $x\in X$ --- to arbitrary separable metric spaces and to arbitrary gauge families. I will then discuss the extension of the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families. Finally, I will indicate how the extended point-to-set principle can be used to prove new theorems about classical fractal dimensions in hyperspaces.
This is joint work with Neil Lutz and Elvira Mayordomo.

#### Slides

Let $X$ and $Y$ be two topological spaces. Given a subset $A$ of $X$ and a subset $B$ of $Y$ we say that $A$ is Wadge-reducible (or sometimes continuously reducible) to $B$ if there is a continuous function $f$ from $X$ to $Y$ that satisfies $f^{-1}(B)=A$. Wadge reducibility is a particularly nice quasi-order on subsets of Polish zero-dimensional spaces: Wadge's Lemma guarantees indeed that its antichains are of size at most two, while Martin and Monk have proven that it is well-founded. This gives an ordinal ranking to every equivalence class for Wadge reducibility, thus generating various questions. I will talk about two of these questions.
First, given a Wadge equivalence class, can we build it using classes of lower ordinal rank, and how?
Second, given any Polish zero-dimensional space $X$, can we decide if there is an antichain of two classes or just one class of some specific ordinal rank of the Wadge quasi-order of $X$? For which ranks?

#### Slides

I will talk about an ongoing work in which new reasons of non-hypersmoothness are investigated. I will present an $F_\sigma$ equivalence relation, which is not hypersmooth because of a Ramsey-theoretic argument.

#### Slides

The talk is a meld of two papers, both joint with Douglas Ulrich.
We characterize which $\Phi \in \mathcal{L}_{\omega_1, \omega}$ have Borel complete expansions and give several sufficient conditions for a theory to have a Borel complete reduct, e.g., having uncountably many complete $1$-types.
We illustrate these general behaviors by considering a family $T_h$ of first-order theories, indexed by functions $h \colon \omega \rightarrow \omega \setminus \{0, 1\}$ in a language $L = \{E_n : n \in \omega\}$ asserting that each $E_n$ is an equivalence relation with $h(n)$ classes, and that the classes cross-cut. The key to showing that many theories have Borel complete reducts follows from the fact that $T_h$ is Borel complete whenever $h$ is unbounded. We deduce our equivalents of having a Borel complete expansion in order to show the converse: if $h$ is bounded, then $T_h$ is not Borel complete.

#### Slides

An orbit equivalence between Borel actions of Polish groups is a Borel bijection between phase spaces that preserves orbit partitions. We are interested in free $\mathbb{R}^m$-actions which are known as multidimensional flows. In this case, orbit equivalence is a coarse invariant collapsing all non-trivial flows into one class. Since any translation-invariant structure can be transferred from the acting group onto individual orbits, it is natural to consider strengthenings of orbit equivalence that respect these structures. Notable examples of such structures include measure, topology, and metric.
We will concentrate on two instances of this paradigm and discuss Borel versions of two ergodic-theoretical results: Katok's representation theorem and Rudolph's result on smooth orbit equivalence. The latter shows that any non-trivial free $\mathbb{R}^m$-flow can be transformed into any other $\mathbb{R}^m$-flow via an orbit equivalence that is a smooth orientation-preserving diffeomorphism on each orbit. Katok's theorem provides a multidimensional generalization of the suspension flow construction and shows that all free $\mathbb{R}^m$-flows emerge as special flows over $\mathbb{Z}^m$-actions.

#### Slides

We discuss a few new results concerning the descriptive combinatorics of bounded degree hyperfinite Borel graphs. In particular, we show that the Baire measurable edge chromatic number of $G$ is at most $\left\lceil\frac{3}{2}\Delta(G)\right\rceil+6$ when $G$ is a multigraph, and for bipartite graphs we improve this bound to $\Delta(G)+1$ and show that degree regular one-ended bipartite graphs have Borel perfect matchings generically. Similar results hold in the measure setting assuming some hyperfiniteness conditions. This talk is based on joint work with Kun and Sabok, Weilacher, and upcoming work with Poulin and Zomback.

#### Slides

According to the Connes-Feldman-Weiss theorem, measurable amenability is equivalent to measurable hyperfiniteness for countable group actions It is easy to see that Borel hyperfiniteness implies Borel amenability, but the opposite direction is a very hard open problem (Jackson-Kechris-Louveau).
The graph-theoretical analogue of amenability is clearly Property A. One can view the so-called uniform local amenability (ULA) property (or local Følner-property) as the graph-theoretical analogue of hyperfiniteness. Brodzky et al. proved that Property A implies ULA. Two years ago I was able to prove that, in fact, ULA is equivalent to Property A. This result has an interesting application in distributed computing.
We say that an action is Uniformly (measurably) Hyperfinite, if all the positive measure subgraphings of the graphing of the action is hyperfinite with the same structure constants. I recently proved that Uniform Hyperfiniteness is equivalent to Uniform Amenability (the measurable version of Property A). Note that UA $\implies$ UH is very similar to the Connes-Feldman-Weiss proof, UH $\implies$ UA requires some new ideas.

#### Slides

A family of infinite subsets of natural numbers is almost disjoint if for any two distinct members of the family, their intersection is finite. The classical theorem of Mathias from the 70s states that there is no infinite analytic maximal almost disjoint (mad) family. The original proof used forcing and it wasn't until almost four decades later that Asger Törnquist found a proof which used a derivative process on a tree.
In joint work with Asger Törnquist, we managed to simplify the derivative process so that it can be carried out (and it terminates) in $L_{\omega_1^{CK}}$, thus proving that for any infinite $\Sigma^1_1$ almost disjoint family, there is a $\Delta^1_1$ witness to non-maximality (where both classes are lightface). The ongoing work in progress attempts to generalise the result to the ideals $\mathrm{Fin}^\alpha$ for $\alpha < \omega_1^{CK}$.
This is joint work with Asger Törnquist.

#### Slides

Jens Mammen (Professor Emeritus of psychology at Aarhus and Aalborg University) has developed a theory in psychology, which aims to provide a model for the interface between a human being (and mind), and the real world.
This theory is formalized in a very mathematical way: Indeed, it is described through a mathematical axiom system. Realizations ("models") of this axiom system consist of a non-empty set $U$ (the universe of objects), as well as a perfect Hausdorff topology $S$ on $U$, and a family $C$ of subsets of $U$ which must satisfy certain axioms in relation to $S$. The topology $S$ is used to model broad categories that we sense in the world (e.g., all the stones on a beach) and the $C$ is used to model the process of selecting an object in a category that we sense (e.g., a specific stone on the beach that we pick up). The most desirable kind of model of Mammen's theory is one in which every subset of $U$ is the union of an open set in $S$ and a set in $C$. Such a model is called "complete".
The harder mathematical aspects of Mammen's theory were first studied in detail by J. Hoffmann-Joergensen in the 1990s. Hoffmann-Joergensen used the Axiom of Choice (AC) to show that a complete model of Mammen's axiom system, in which the universe $U$ is infinite, does exist. Hoffmann-Joergensen conjectured at the time that the existence of a complete model of Mammen's axioms would imply the Axiom of Choice.
I will discuss the set-theoretic aspects of complete Mammen models. First of all, the question of "how much" AC is needed to obtain a complete Mammen model; secondly, I will introduce some cardinal invariants related to complete Mammen models and establish elementary $\mathsf{ZFC}$ bounds for them, as well as some consistency results.
This is joint work with Jens Mammen.

#### Slides

In the 1920s, Lusin asked whether every Borel function on a Polish space is a union of countably many partial continuous functions (i.e. whether every Borel function is $\sigma$-continuous). This question has a negative answer; an example of a non-piecewise continuous Borel function is the Turing jump. A dichotomy of Solecki and Zapletal is that the Turing jump is the basis for every counterexample: every Borel function $f$ is either $\sigma$-continuous, or the Turing jump continuously reduces to $f$.
We generalize the Solecki-Zapletal dichotomy throughout the Borel hierarchy. Recall that a Borel function is Baire class $\alpha$ if and only if it is $\mathbf\Sigma^0_{\alpha+1}$-measurable. We show that every Borel function $f$ is either $\sigma$-Baire class $\alpha$, or a complete Baire class $\alpha+1$ function (an appropriate iterate of the Turing jump) continuously reduces to $f$. Our proof uses an adaptation of Montalbán's game metatheorem for priority arguments to boldface descriptive set theory.
This is joint work with Antonio Montalbán.

#### Slides

The correspondence between Ramsey theory, Fraïssé theory, and dynamics established in 2003 by Kechris, Pestov, and Todorčević has had far-reaching consequences in the study of automorphism groups of discrete first-order structures. The dual notion, projective Fraïssé theory (developed by Irwin and Solecki in 2006), considers classes of topological structures and in 2017, Panagiotopoulos proved that every compact, metrizable space can be obtained as a quotient of a projective Fraïssé limit. Therefore, projective Fraïssé theory provides an ideal framework to consider the homeomorphism groups of compact spaces. In this talk, for each Knaster continuum $K$, we will give a projective Fraïssé class of finite objects that approximates $K$ (up to homeomorphism) and use the dual of the KPT correspondence (proved by Bartošová and Kwiatkowska, 2018) to determine if the homeomorphism group of $K$ is extremely amenable.

#### Slides

The talk will consist of two parts. In the first one, we introduce a certain natural Polish space of all separable Banach spaces. We compare it with the recent different approach to topologizing the space of separable Banach spaces, by Godefroy and Saint-Raymond.
Our main interest will be in the descriptive complexity of classical Banach spaces with respect to this Polish topology. We show that the separable infinite-dimensional Hilbert space is characterized as the unique Banach space whose isometry class is closed, and also as the unique Banach space whose isomorphism class is $F_\sigma$, where the former employs the Dvoretzky theorem and the latter the solution to the homogeneous subspace problem. For $p$ in $[1,\infty)-\{2\}$, we mention that the isometry class of $L^p[0,1]$ is $G_\delta$-complete and the class of $\ell^p$ is $F_{\sigma, \delta}$-complete.
In the second part, we connect it with the recent study of Fraïssé Banach spaces, initiated by Ferenczi, López-Abad, Mbombo, and Todorčević. We show that a Banach space has a comeager isometry class in its closure if and only if it is the unique limit of a 'weak Fraïssé class' of finite-dimensional spaces. While it is open whether there are other Fraïssé Banach spaces besides the Gurariĭ space and the $L^p$'s, we show there are more examples of generic Banach spaces in the weaker sense above.
The first part will be based on joint work with M. Doležal, M. Cúth, and O. Kurka; the second is a work in progress jointly with M. Cúth and N. de Rancourt.

#### Slides

I will talk about my recent result joint with S. Shelah establishing that the Borel space of torsion-free abelian groups with domain $\omega$ is Borel complete, i.e., that the isomorphism relation on this Borel space is as complicated as possible, as an isomorphism relation. This solves a long-standing open problem in descriptive set theory, which dates back to the seminal paper on Borel reducibility of Friedman and Stanley from 1989. Time permitting, I will also talk about some recent results (also joint with S. Shelah) on the existence of uncountable Hopfian and co-Hopfian abelian groups and on anti-classification results for the countable co-Hopfian abelian and $2$-nilpotent groups. In particular, we will see that the countable co-Hopfian groups are complete co-analytic in the Borel space of $2$-nilpotent groups with domain $\omega$. This solves an open question of Thomas, who had posed the question for the space of all groups with domain $\omega$.

#### Slides

Which Borel quasi-orders are Borel reducible to Turing reducibility? In any such quasi-order, every element must have at most countably many predecessors (in which case we say the quasi-order is locally countable), but are there any other restrictions? It turns out that there are. It follows from recent work by Siskind and me that not every locally countable Borel quasi-order is Borel reducible to Turing reducibility. A more careful analysis shows that even fairly simple quasi-orders are not always reducible to Turing reducibility. I will discuss a few such examples as well as the broader context for this question. This talk contains joint work with Benjamin Siskind and Kojiro Higuchi.

#### Slides

Of the principles just slightly weaker than $\mathsf{ATR}$, the most well-known are the theories of hyperarithmetic analysis (THA). By definition, such principles hold in $HYP$. Motivated by the question of whether the Borel dual Ramsey theorem is a THA, we consider several theorems involving Borel sets and ask whether they hold in $HYP$. To make sense of Borel sets without $\mathsf{ATR}$, we formalize the theorems using completely determined Borel sets. We characterize the completely determined Borel subsets of $HYP$ as precisely the sets of reals which are $\Delta^1_1$ in $L_{\omega_1^{ck}}$. Using this, we show that in $HYP$, Borel sets behave quite differently than in reality. For example, in $HYP$, the Borel dual Ramsey theorem fails, every $n$-regular Borel acyclic graph has a Borel $2$-coloring, and the prisoners have a Borel winning strategy in the infinite prisoner hat game. Thus the negations of these statements are not THA. Joint work with Henry Towsner and Rose Weisshaar.

#### Slides

The axiom of real determinacy ($\mathsf{AD}_\mathbb{R}$) asserts the determinacy of every infinite two-player, perfect-information game with moves in the set of real numbers. By a theorem of Woodin, $\mathsf{ZF} + \mathsf{AD}_\mathbb{R}$ is consistent if and only if $\mathsf{ZFC}$ is consistent together with the existence of a cardinal $\lambda$ which is a limit of Woodin cardinals and ${<}\lambda$-strong cardinals.
In this talk, we explore the strength of $\mathsf{AD}_\mathbb{R}$ over the theory $\mathsf{KP} + \unicode{x201C}\textrm{$$\mathbb{R}$ exists}\unicode{x201D}$$ and observe that it is much weaker. Indeed, the theory $\mathsf{KP} + \mathsf{AD}_\mathbb{R} + \unicode{x201C}\textrm{$$\mathbb{R}$ exists}\unicode{x201D}$$ is weaker than $\mathsf{ZFC} + \unicode{x201C}\textrm{there are $$\omega^2$ Woodin cardinals}\unicode{x201D}$$. This is a consequence of the following theorem: over $\mathsf{ZFC}$, the existence of a transitive model of $\mathsf{KP} + \mathsf{AD}_\mathbb{R}$ containing the set of all real numbers is equivalent to the determinacy of all open games of length $\omega^3$.

#### Slides

We will describe how the perspectives of Recursion Theory and Set Theory suggest lines of investigation into Geometric Measure Theory. We will discuss the extent of capacitability for Hausdorff dimension and the question of existence of sets of strong gauge dimension, which is a property generalizing that of strong measure zero.

#### Slides

Every continuous action of a countable group on a Polish space induces a Borel equivalence relation. We are interested in the problem of realizing (i.e. finding a Borel isomorphic copy of) these equivalence relations as continuous actions on compact spaces. We provide a number of positive results on this problem, and we investigate the connection to subshifts. Joint with Joshua Frisch, Alexander Kechris and Zoltán Vidnyánszky.

#### Slides

There are several well-studied "jumps" on the class of Borel equivalence relations under Borel reducibility, namely, the Friedman-Stanley jump and the family of Louveau jumps. In joint work with John Clemens, we defined a new(ish) family of jumps called Bernoulli jumps. In this talk I will introduce and describe Bernoulli jumps, and present an application to the classification of countable scattered orders. I will conclude by summarizing some recent developments (due to Shani and Allison) on Bernoulli jumps.

#### Slides

For a given finite relational structure $\mathcal R$, the associated constraint satisfaction problem (or CSP) is the problem of testing when a structure admits a homomorphism into $\mathcal R$. The algebraic approach studies a CSP by considering its algebra of so-called polymorphisms, operations (of all arities) which preserve the relations in $\mathcal R$. This approach has led to many classification results. For instance, CSPs solvable by polynomial time algorithms, linear relaxation, and constraint propagation have all been classified. In this talk I will present partial results towards similar classifications of Borel CSPs with various descriptive set theoretic properties: those problems which are $\mathbf \Pi^1_1$ in the codes, effectivizable, or equivalent to their classical version.

#### Slides

Marks proved the existence of $d$-regular acyclic Borel graphs with Borel chromatic number $d+1$. It can be shown that such statements cannot be proved using measures or Baire category, and, indeed, the Borel determinacy theorem had to be invoked.
We discuss a generalization of Marks' method, which leads to an interesting new class of examples of $3$-regular acyclic Borel graphs, which we call homomorphism graphs.
This yields new proofs of a number of known results. As a new application, we show that it is hard to decide whether the Borel chromatic number of a Borel graph is $\le 3$, even for acyclic $3$-regular graphs (that is, such graphs form a $\mathbf\Sigma^1_2$-complete set).
Joint work with Jan Grebík.

#### Slides

We go through the history of measurable perfect matchings from the Banach-Tarski paradox via circle squaring and report on recent progress. We construct a $d$-regular treeing (for every $d > 2$) without a measurable perfect matching. We show that the Hall condition is essentially sufficient in the hyperfinite, one-ended, bipartite case. This allows us to characterize bipartite Cayley graphs with factor of i.i.d. perfect matchings extending the Lyons-Nazarov theorem. We apply these to Gardner's conjecture for uniformly distributed sets, to balanced orientations, and to get new, simple proofs of the measurable circle squaring. We prove the analogous theorems in the context of rounding flows, too. Partially joint work with Matt Bowen and Marcin Sabok.

## Other years

2023-2024 (current)
2022-2023
2021-2022
2020-2021
2019-2020
2018-2019
2017-2018
2016-2017
2015-2016
2014-2015
2013-2014
2012-2013
2011-2012
2010-2011
2009-2010
2008-2009
2007-2008
2006-2007