# Caltech–UCLA Logic Seminar

## (Aka Cabal Seminar)

The Logic seminar generally meets on Fridays, 2–3:30p.m., at Caltech or UCLA. Contact Alexander Kechris or Itay Neeman if you wish to give a talk.

Schedule of talks, going back to Fall 2015, in reverse chronological order:

# Logic Seminar: 02/27/2017 - 02/27/2018

 Friday Jun 02 2017 14:00-15:30 (MS 6221) Anush Tserunyan (UIUC) Friday May 19 2017 14:00-15:30 (MS 6221) Wai Yan Pong (CSUDH)

# Logic Seminar: 09/1/2015 - 02/26/2017

 Friday Feb 10 2017 14:00-15:30 (MS 6221) Vassilis Gregoriades (U. Turin) The problem of HYP-isomorphism between recursive Polish spaces Abstract. It is a fundamental fact of descriptive set theory that every uncountable Polish space is Borel-isomorphic to the Baire space. The effective version of the latter is true as long as the given (recursive) Polish space has no isolated points. Given the importance of this fact in the development of effective descriptive set theory, it is natural to ask if this is also true in general. This however turns out to be false; in fact not only there are recursive uncountable Polish spaces, which are not effectively Borel-isomorphic to the Baire space, but the natural notion of effective Borel reduction carries a rich structure. In this talk we present some central results about these spaces and we describe the main techniques for proving them.Hide Friday Jan 27 2017 14:00-15:30 (MS 6221) Zoltán Vidnyánszky (York U. and U. Toronto) Characterization of order types representable by Baire class 1 functions Abstract. Let $\mathcal{F}$ be a family of real valued functions on a Polish space $X$. A natural partial ordering on $\mathcal{F}$ is the pointwise ordering, $\leq_p$. The description of linearly ordered subsets of $(\mathcal{F},\leq_p)$ reveals a lot of information about the poset itself. It turns out that the first interesting family of functions to consider is the family of Baire class 1 functions, $\mathcal{B}_1(X)$. Answering a question of Laczkovich, we give a complete combinatorial characterization of the linearly ordered subsets of $(\mathcal{B}_1(X),\leq_p)$.Hide Friday Jan 20 2017 14:00-15:30 (MS 6221) Minh Tran (UIUC) Tame structures via multiplicative character sums over constructible subsets of finite fields Abstract. We study the model theory of the structure $(\mathbb{F}; <)$ where $\mathbb{F}$ is the algebraic closure of the field of $p$ elements and $<$ is an ordering on $\mathbb{F}^\times$ induced by an injective group homomorphism $\chi: \mathbb{F}^\times \to \mathbb{C}^\times$. Various notions of model theoretic tameness of the structure turn out to be consequences of number theoretic behaviors of the character map $\chi$. The results obtained are attempts to bring number theoretic phenomena of this type into model theory, following a suggestion by van den Dries, Hrushovski and Kowalski.Hide Friday Jan 13 2017 14:00-15:30 (MS 6221) Spencer Unger (UCLA) Borel circle squaring Abstract. We give a completely constructive solution to Tarski's circle squaring problem. More generally, we prove a Borel version of a general equidecomposition theorem due to Laczkovich. This answers a question of Wagon. Our proof uses ideas from the study of flows in networks, and a recent result of Gao, Jackson, Khrone, and Seward on special types of witnesses to the hyperfiniteness of free Borel actions of $\mathbb{Z}^d$. This is joint work with Andrew Marks.Hide Friday Nov 18 2016 14:00-15:30 (MS 6221) Anton Bernshteyn (UIUC) Measurable graph colorings and the Lovasz Local Lemma Abstract. The Lovasz Local Lemma, or the LLL for short, is an immensely important tool in probabilistic combinatorics. It is typically used to demonstrate the existence of a function $f \colon X \to Y$ satisfying certain local'' combinatorial constraints, where $X$ is an underlying combinatorial structure (e.g. a graph) and $Y$ is a (usually finite) set (e.g. a set of colors). Since its first appearance in 1975, the LLL found numerous applications in combinatorics, some of them straightforward, and some highly technical and sophisticated. In this talk, we will consider the following question: Assume $X$ is equipped with a standard Borel structure and a probability Borel measure $\mu$. Can the function $f$, whose existence is asserted by the LLL, be $\mu$-measurable? Most of our attention will be focused on the situation when the combinatorial structure on $X$ is in some sense induced'' by a measure-preserving action of a countable group $\Gamma$. We will see that for some actions the answer is positive (which yields measurable analogs of various combinatorial consequences of the LLL for such actions). On the other hand, for some actions the measurable version of the LLL fails; in fact, if $\Gamma$ is amenable, then a probability measure-preserving action of $\Gamma$ satisfies a measurable analog of the LLL if and only if it has infinite entropy.Hide Friday Oct 28 2016 15:00-15:50 (MS 6221) Alessandro Achille (UCLA CS Dept.) A Vietoris-Smale mapping theorem for the homotopy of hyperdefinable sets Abstract. Classical results of Vietoris (1927), Begle (1950), Smale (1950) and Dugundji (1969) allow to compare the homotopy of two topological spaces $X$ and $Y$ whenever a map $f : X \rightarrow Y$ with sufficiently trivial fibers is given (acyclic, contractible, etc.). We apply similar techniques in o-minimal expansions of fields to compare the (o-minimal) homotopy of a definable set $X$ with the homotopy of some of its bounded hyperdefinable quotients $X/E$. As a special case we obtain some homotopy comparison results due to Delfs-Knebush (semialgebraic case) and Baro-Otero and we strengthen previous results on the higher homotopy groups of $G/G^{00}$, where $G$ is a definably compact group and $G^{00}$ is the infinitesimal subgroup. Under suitable assumptions on $E$ we show that $\dim(X) = \dim_R(X/E)$. In particular we obtain a new proof of Pillay's group conjecture $\dim(G) = \dim_R(G/G^{00})$ largely independent of the group structure of $G$. Joint work with Alessandro Berarducci. (Note unusual starting time, 3pm.)Hide Friday Oct 14 2016 14:00-15:30 (MS 6221) Ronnie Chen (Caltech) Structurability by locally finite contractible simplicial complexes Abstract. By a result of Jackson, Kechris, and Louveau, every treeable compressible countable Borel equivalence relation (CBER) admits a treeing where each vertex has degree at most 3. We generalize this to show that every compressible CBER structurable by $n$-dimensional contractible simplicial complexes is structurable by $n$-dimensional contractible simplicial complexes in which each vertex is contained in at most $c_n$ simplices, where $c_n$ depends only on the dimension $n$. The proof is based on a classical result of Whitehead in algebraic topology.Hide Friday Sep 16 2016 14:00-15:30 (MS 6221) Haim Horowitz (Hebrew U) On the non-existence and definability of mad families Abstract. By an old result of Mathias, there are no mad families in the Solovay model constructed by the Levy collapse of a Mahlo cardinal. By a recent result of Törnquist, the same is true in the classical model of Solovay as well. In a recent paper, we show that ZF+DC+"there are no mad families" is actually equiconsistent with ZFC. I'll present the ideas behind the proof in the first part of the talk. In the second part of the talk, I'll discuss the definability of maximal eventually different families and maximal cofinitary groups. In sharp contrast with mad families, it turns out that Borel MED families and MCGs can be constructed in ZF. Finally, I'll present a general problem in Borel combinatorics whose solution should explain the above difference between mad and maximal eventually different families, and I'll show how large cardinals must be involved in such a solution. This is joint work with Saharon Shelah.Hide Friday Jun 03 2016 15:00-15:50 (MS 6221) Andrew Marks (UCLA) Measurable matchings and quasitilings Abstract. It was recently shown by Downarowicz, Huczek, and Zhang that if $G$ is a finitely generated amenable group, and $\epsilon > 0$, then $G$ admits a partition into $\epsilon$-Folner sets such that up to translation, only finitely many distinct parts appear. We establish a strengthening of this result for measurable quasitilings of free measure preserving actions of amenable groups. Our proof uses a measurable matching lemma of Lyons and Nazarov that we adapt to an asymmetric context. This is joint work with Conley, Jackson, Kerr, Seward, and Tucker-Drob. (Note unusual time, 3pm.)Hide Friday May 20 2016 13:00-13:50 (MS 3915A) Anton Bobkov (UCLA) VC-density in an additive reduct of p-adic numbers. Abstract. I will introduce basic techniques and results for working with p-adic numbers in model theory, define an additive reduct of p-adic numbers and compute its VC-density function. (Note unusual time, 1pm, and place.)Hide Friday May 13 2016 15:00-15:50 (MS 3915A) Anton Bobkov (UCLA) VC-density in partial order trees. Abstract. I will define notion of VC-density, introduce basic techniques for its computation and show an application to partial order trees. (Note unusual time, 3pm, and place.)Hide Friday Apr 29 2016 15:00-15:50 (MS 6221) Omer Ben Neria (UCLA) The distance between HOD and V Abstract. The pursuit of better understanding the universe of set theory V motivated an extensive study of definable inner models M whose goal is to serve as good approximations to V. A common property of these inner models is that they are contained in HOD, the universe of hereditarily ordinal definable sets. Motivated by the question of how ?close? HOD is to V, we consider various related forcing methods and survey known and new results. This is a joint work with Spencer Unger. (Note unusual time, 3pm.)Hide Friday Apr 15 2016 15:00-15:50 (MS 6221) Spencer Unger (UCLA) Compactness in graphs Abstract. We survey various constants related to colorings of graphs and their compactness properties. We are particularly interested in successors of singulars where we extend techniques for the chromatic number from countable to uncountable cofinalities. (Note unusual time, 3pm.)Hide Friday Apr 01 2016 13:00-13:50 (MS 6221) James Freitag (UCLA) Elimination of imaginaries in ACVF Abstract. We will continue to follow Johnson's exposition of elimination of imaginaries in algebraically closed valued fields. (Note unusual time, 1pm.)Hide Friday Mar 11 2016 14:00-15:30 (MS 6221) Javier de la Nuez (U. Muenster) Bounding the Shelah rank of varieties over the free group Abstract. We report on joint work in progress with Chloé Perin and Rizos Sklinios, where we deduce lower bounds for the Shelah rank of certain definable sets in the free group. In the proof some results from geometric group theory concerning the action of the mapping class group of a surface on its complex of curves come into play.Hide Wednesday Mar 09 2016 16:00-17:30 (MS 5118) Andre Nies (University of Auckland) The complexity of isomorphism between profinite groups Abstract. A topological group $G$ is profinite if it is compact and totally disconnected. Equivalently, $G$ is the inverse limit of a surjective system of finite groups carrying the discrete topology. An example is the additive group of 2-adic integers. We discuss how to represent a countably based profinite group as a point in a Polish space. Thereafter, we study the complexity of their isomorphism using the theory of Borel reducibility in descriptive set theory. For topologically finitely generated groups this complexity is the same as the one of identity for reals. In general, it is the same as the complexity of isomorphism for countable graphs. Note unusual time (4pm), day (Wednesday), and room (MS 5118).Hide Friday Mar 04 2016 14:00-15:30 (MS 6221) James Freitag (UCLA) Elimination of imaginaries for ACVF. Abstract. We will continue working on Johnson's exposition of elimination of imaginaries in ACVF.Hide Friday Feb 19 2016 14:00-15:30 (MS 6221) Noah Schweber (UC Berkeley) Uncountable computable structure theory Abstract. We will examine an approach to studying uncountable structures from a computability-theoretic viewpoint, by looking at generic extensions where those structures become countable. We will prove some basic and general results, and then turn to specific examples, especially of structures which compute every real. We will finally turn to an application of this approach to classical computable structure theory: the Medvedev degrees of countable ordinals.Hide Friday Feb 05 2016 14:00-15:30 (MS 6221) James Freitag (UCLA) Elimination of imaginaries for ACVF: definable types Abstract. We are in the middle of a series of seminars working towards Johnson's exposition of the proof of elimination of imaginaries in algebraically closed valued fields (ACVF). This seminar will be self-contained, and will introduce some general notions around definable types which are used later in the proof.Hide Friday Jan 29 2016 14:00-15:30 (MS 6221) Martino Lupini (Caltech) Nonstandard analysis and a sumset conjecture of Erdos Abstract. It is an open problem to formulate and prove a density version of Hindman's theorem on sets of finite products. I will discuss some results in this direction, which can be naturally presented and proved using the language of nonstandard analysis. This is joint work with Mauro Di Nasso, Isaac Golbring, Renling Jin, Steven Leth, and Karl Mahlburg.Hide Friday Jan 22 2016 14:00-15:30 (MS 6221) Katrin Tent (Universitaet Muenster) Profinite groups with NIP theory and $p$-adic analytic groups Abstract. We consider profinite groups as $2$-sorted structures reflecting the profinite topology. It is shown that if the basis consists of all open subgroups, then the first order theory of such a structure is NIP (that is, does not have the independence property) precisely if the group has a normal subgroup of finite index which is a direct product of finitely many compact $p$-adic analytic groups, for distinct primes $p$. In fact, the condition NIP can here be weakened to NTP${}_2$. We also show that any NIP profinite group, presented as a $2$-sorted structure, has an open prosoluble normal subgroup. (Joint work with D. Machperson.)Hide Friday Jan 15 2016 14:00-15:30 (MS 6221) Alex Kruckman (UC Berkeley) Properly Ergodic Structures Abstract. One natural notion of "random L-structure" is a probability measure on the space of L-structures with domain $\omega$ which is invariant and ergodic for the natural action of $S_\infty$ on this space. We call such measures "ergodic structures." Ergodic structures arise as limits of sequences of finite structures which are convergent in the appropriate sense, generalizing the graph limits (or "graphons") of Lovász and Szegedy. In this talk, I will address the properly ergodic case, in which no isomorphism class of countable structures is given measure 1. In joint work with Ackerman, Freer, and Patel, we give a characterization of those theories (in any countable fragment of $L_{\omega_1,\omega})$ which admit properly ergodic models. The main tools are a Morley-Scott analysis of an ergodic structure, the Aldous-Hoover representation theorem, and an "AFP construction" - a method of producing ergodic structures via inverse limits of discrete probability measures on finite structures.Hide Friday Jan 08 2016 14:00-15:30 (MS 6221) Dima Sinapova (UIC) The tree property at successive cardinals Abstract. The tree property is a reflection type combinatorial principle. It holds at $\omega$ (Konig's infinity lemma), fails at $\omega_1$ (Aronszajn) and can consistently hold at $\omega_2$ (Mitchell). A long standing project in set theory is to obtain the tree property at every regular cardinal greater than $\omega_1$. We will start by introducing some classical results. Then I will show that assuming large cardinals, one can consistently get the tree property at the first and double successor of a singular strong limit cardinal.Hide Friday Dec 04 2015 14:00-15:30 (MS 6221) Artem Chernikov (UCLA) Elimination of imaginaries in algebraically closed valued fields, IV Abstract. This is the 4th in a series of lectures on Johnson's exposition of Hrushovski's simplified proof of elimination of imaginaries for algebraically closed valued fields (ACVF). This time we start working towards the proof and discuss geometric sorts, definable valued vector spaces and submodules, and definable types in ACVF.Hide Friday Nov 20 2015 14:00-15:30 (MS 6221) Peter Burton (Caltech) Completely positive entropy actions of sofic groups with $\mathbb{Z}$ in their center Abstract. Let $\Gamma$ be a sofic group with a copy of $\mathbb{Z}$ in its center. We construct an uncountable family of pairwise nonisomorphic measure-preserving $\Gamma$ actions with completely positive entropy, none of which is a factor of a Bernoulli shift. Our construction shows that the relation of isomorphism among completely positive entropy $\Gamma$ actions is not smooth, in contrast with the relation of isomorphism among Bernoulli shifts.Hide Friday Nov 13 2015 16:00-17:00 (MS 6627) Nick Ramsey (UC Berkeley) Trees and the global combinatorics of first-order theories Abstract. (Note unusual time and place: 4pm in MS 6627.) Model-theoretic tree properties - the tree property (TP), the tree property of the first kind (TP_1), and the tree property of the second kind (TP_2) - provide a way of distinguishing theories based on the complexity of patterns of forking that occur in some formula. These properties have emerged as markers of important dividing lines within model theory. They were introduced by Shelah as the local versions of a family of cardinal invariants quantifying the complexity of forking for a theory, possibly among families of different formulas. Shelah proved a family of results about these tree properties and asked whether certain global analogues of these results might also hold for the cardinal invariants. We will describe how two unexpected tools from infinitary combinatorics - strong colorings studied by Galvin and later Shelah, as well as finite square principles studied by Kennedy and Shelah - can be applied to understand what relationships that hold between the local' tree properties also holds for the global' cardinal invariants.Hide 14:00-15:30 (MS 6221) Jesse Han; Artem Chernikov (UCLA) Basic model theory of algebraically closed valued fields, III Abstract. This is the 3rd in a series of lectures on Johnson's exposition of Hrushovski's simplified proof of elimination of imaginaries for algebraically closed valued fields (ACVF). We will finish the overview of the basic theory of imaginaries, and start setting up the scene for the analysis of ACVF (some combinatorial properties of definable sets, geometric sorts, definable valued vector spaces and modules).Hide Friday Nov 06 2015 14:00-15:30 (MS 6221) Artem Chernikov (UCLA) Regularity lemmas for definable graphs Abstract. Szemeredi regularity lemma is a fundamental result in graph combinatorics with numerous applications in additive number theory, computer science and other fields. Roughly speaking, it asserts that every large enough graph can be partitioned into boundedly many sets so that on almost all pairs of those sets the edges are approximately uniformly distributed at random. It was demonstrated by Gowers that in general the size of the required partition grows as an exponential tower in terms of the allowed error. Recently several improved regularity lemmas giving much better bounds were obtained for restricted families of graphs: algebraic graphs of bounded complexity in large finite fields (Tao), semialgebraic graphs of bounded complexity (Fox, Gromov, Lafforgue, Naor, Pach), graphs of bounded VC-dimension (Lovasz, Szegedy), graphs without arbitrary large half-graphs (i.e. stable graphs, Malliaris, Shelah). It turns out that these results are closely related to the model-theoretic classification theory, Shelah's stability and its generalizations. I will give a survey of the area stressing this point and present some recent joint work with Sergei Starchenko on generalizations of the semialgebraic and stable cases to general NIP structures.Hide Friday Oct 30 2015 14:00-15:30 (MS 6221) Matthias Aschenbrenner, Jesse Han (UCLA) Basic model theory of algebraically closed valued fields, II; imaginaries Abstract. This is the second in a series of lectures on Johnson's exposition of Hrushovski's simplified proof of elimination of imaginaries for algebraically closed valued fields. We will finish the proof of quantifier elimination for algebraically closed valued fields, and then introduce the definition and basic facts concerning imaginaries.Hide Friday Oct 23 2015 14:00-15:30 (MS 6221) James Freitag (UCLA) Around Jouanolou-type theorems Abstract. In the late 1970s, Jouanolou proved that a codimension one holomorphic foliation on a complex manifold (satisfying some technical conditions) has infinitely many hypersurface solutions if and only if it has a meromorphic first integral. This notation will be explained at the beginning of the talk. Around 20 years ago, Hrushovski built on a theorem of Jouanolou concerning hypersurface solutions to Pfaffian equations in order to prove that any differential variety with constant coefficients has either finitely many co-order one subvarieties or admits a nontrivial differential rational map to the constant field. Hrushovski's generaliation of Jouanolou's theorem allowed for a strong characterization of the possible algebraic relations between solutions of any order one ODE. In model theoretic terms, Hrushovski showed that any strongly minimal order one ODE is either nonorthogonal to the constants or has a trivial countably categorical forking geometry. In this talk, I will explain several generalizations of Hrushovski's theorem. The first direction removes the assumption of constant coefficients, while the second generalizes the work to the case of several derivations. I will also explain how these generalizations allow one to answer a question of Hrushovski and Scanlon regarding Lascar rank and Morley rank in differential fields.Hide Friday Oct 16 2015 14:00-15:30 (MS 6221) Matthias Aschenbrenner (UCLA) Basic model theory of algebraically closed valued fields Abstract. This is the first in a series of lectures on Johnson's exposition of Hrushovski's simplified proof of elimination of imaginaries for algebraically closed valued fields. In this introductory talk I will give a crash course in basic valuation theory and prove quantifier elimination for algebraically closed valued fields. No previous knowledge of valuations will be assumed.Hide Friday Oct 09 2015 14:00-15:30 (MS 6221) Martino Lupini (Caltech) Fraisse theory and the noncommutative Poulsen simplex Abstract. The Poulsen simplex is the unique Choquet simplex with dense extreme boundary. It was first realized by Conley and Tornquist that the Poulsen simplex can be obtained via a Fraisse-theoretical construction from a suitable class of linear spaces. In my talk I will recall such a construction, and explain how one can adapt these ideas to define the `quantum analog' of the Poulsen simplex. In conclusion, I will explain how the known equivalent characterizations of the Poulsen simplex can be recovered in the quantum setting.Hide