# UCLA Logic Colloquium

The UCLA Logic Colloquium meets on alternate Fridays, at 4 p.m., in MS 6221.
The Logic Colloquium is organized by Patrick Lutz and Forte Shinko.
Here are links to the UCLA Logic Center, the Caltech-UCLA Logic Seminar, and the Philosophy Colloquium.

Talks are listed here in reverse chronological order.

# Logic Colloquium: 09/1/2018 - 12/8/2022

 Friday Dec 02 2022 16:00-16:50 (MS 6221) Don Stull Pinned distance sets using effective dimension Abstract. Recent work has shown that effective techniques can be used to understand problems in (classical) geometric measure theory. An important open problem in geometric measure theory is to prove strong lower bounds on the Hausdorff dimension of pinned distance sets. Given a set E in the plane, and a point x, the pinned distance set of E with respect to x is the set of all distances between x and the points in E. In this talk, I will discuss how we can use effective methods to improve the bounds on the dimension of pinned distance sets. Link to zoom recording: https://ucla.zoom.us/rec/share/LmBXTATfUKdSl8AOAI42wWMVbSo6f0zIJk0yMvCA3FcpWzoVo_of5CuuvtDfIuU.0F60PEwV_6gy53n3Hide Friday Nov 18 2022 16:00-16:50 (MS 6221) Scott Mutchnik NSOP_2 Theories Abstract. Model theory has been described as a "geography of tame mathematics," creating a map of the universe of first-order theories according to various dividing lines, such as tree properties or order properties. While some regions of this map, such as the stable theories or simple theories, are well-understood to varying degrees, as we progress outward it even becomes open whether some regions are empty or not. Extending the NSOP_n hierarchy of Shelah [1995] defining an ascending chain of strong order properties for n > 2, Dzamonja and Shelah [2004] introduce two further tree properties, NSOP_1 and NSOP_2, and ask whether the implications between NSOP_1 and NSOP_2 and between NSOP_2 and NSOP_3 are strict. We have answered the first of these questions, showing that the class NSOP_1 coincides with NSOP_2. We discuss this result and some aspects of its proof, which incorporates ideas from various other regions of the model-theoretic map such as the NSOP_1, NSOP_3 and NTP_2 theories. Link to zoom recording: https://ucla.zoom.us/rec/share/rv7VXHYenMBhMPywHR5LMCtS5BGgROu_crVkM5ztjpIp2GGdEATREVQJrfnDYNqX.kq0JF3CF2D3gdbnfHide Friday Nov 04 2022 16:00-16:50 (MS 6221) Garrett Ervin Decomposing the real line into everywhere isomorphic suborders Abstract. We show that it is impossible to decompose the real line (R, <) into two suborders that are everywhere isomorphic. That is, if R = A U B is a partition of R, then there is an open interval I such that A's restriction to I is not order-isomorphic to B's restriction to I. The proof depends on the completeness of R, and it turns out that in contrast there does exist a partition of the irrationals R - Q = A U B such that A and B are isomorphic on every open interval. I do not know whether it is possible to decompose R into three suborders that are everywhere isomorphic.Hide Wednesday Oct 26 2022 16:00-16:50 (MS 6221) Mariana Vicaria Elimination of imaginaries in ordered abelian groups Abstract. I will present the current picture of the model theoretic study of ordered abelian groups. Their classification from a combinatorial point of view, results on quantifier elimination and model completeness. I aim to explain two main results on elimination of imaginaries in ordered abelian groups with finite spines, a class including the strongly dependent, dp-minimal and definably complete OAG. No prior knowledge of advanced model theory will be assumed and everyone is very welcome to join. The zoom recording can be found here: https://ucla.zoom.us/rec/share/5s6qv99lKCX2zUbOSTOBPOKFtEuqftMig7zuAgmlwJiDGedNvCcM6HxxVJvywG4P.fdl3ep1qOp3ku4-CHide Friday Oct 07 2022 16:00-16:50 (MS 6221) Meng-Che "Turbo" Ho Torsion-free abelian groups of finite rank and fields of finite transcendence degree Abstract. In descriptive set theory, Borel reducibility is used to study the complexities of classes of countable structures. A classical example is the isomorphism problem on the class $TFAb_r$ of torsion-free abelian groups of rank r. Baer gave a simple invariant for $TFAb_1$, i.e., when two torsion-free abelian groups of rank 1 are isomorphic. On the other hand, Hjorth showed that $TFAb_1 <_B TFAb_2$ and Thomas generalized this to show that $TFAb_r <_B TFAb_{r+1}$. Recently, Paolini and Shelah, and independently Laskowski and Ulrich, showed that the class of torsion-free abelian group with domain $\omega$ is Borel complete. The class $FD_r$ of fields over $\mathbb{Q}$ of finite transcendence degree r shares many features with $TFAb_r$. For instance, there is an r-tuple over which every element in the field is algebraic (definable in the case of groups). We compare the class of torsion-free abelian groups and the class of fields using the notion of Turing computable embedding defined by Knight, Miller, and Vanden Boom, and computable functors defined by Miller, Poonen, Schoutens, and Shlapentokh. In particular, we show that there are functorial Turing computable embeddings from $TFAb_r$ to $FD_r$ and from $FD_r$ to $FD_{r+1}$. Unlike in the results by Hjorth and Thomas, we do not know if these embeddings are strict. However, we show that under the computable countable reduction, these classes are all bi-reducible. This is joint work with Julia Knight and Russell Miller. The zoom recording can be found here: https://ucla.zoom.us/rec/share/JyqV-DI4Uyf2dFFSw43R5RTwPNZOWIEDQYgzvHIlbW2FLZ4CmUgDdU7cY98L_F9T.nT_v3Jbog7-3h7SoHide Friday May 22 2020 15:00-15:50 (https://ucla.zoom.us/j/672060601) Henry Towsner (University of Pennsylvania) Removal and Amalgamation Abstract. (https://ucla.zoom.us/j/672060601) The key step in the proof of the triangle removal lemma can be viewed as saying that we can identify a small number of edges in a graph as being the "exceptional" edges, and the remaining edges are sufficiently "representative of the neighborhood around them" that, if there are any triangles left, there must have been many triangles. This can be viewed as a amalgamation problem in the sense of model-theory: given types p(x,y), q(x,z), and r(y,z), each of which indicates that there is an edge between the vertices, when are the types p,q,r "large" in a way which guarantees that there are many (x,y,z) extending each of these types? The exceptional types can be characterized as the non-Lebesgue points - that is, the points which fail to satisfy the Lebesgue density theorem in the right measure space. We give a way to generalize this to types of higher arity and use this to prove a new generalization, an "ordered hypergraph removal lemma", extending the recent ordered graph removal lemma of Alon, Ben-Eliezer, and Fischer.Hide Friday Apr 10 2020 16:00-16:50 (https://zoom.us/j/8244003061) Matthew Foreman (UC Irvine) Attacking Classical Problems in Dynamical Systems with Descriptive Set Theory Abstract. In his classical 1932 paper, von Neumann asked 3 questions: Can you classify the statistical behavior of differentiable systems? Are there systems where time-forward is not isomorphic to time-backward? Is every abstract statistical system isomorphic to a differentiable system? These questions can be addressed with some surprising consequences by embedding them in Polish Spaces. Indeed the tools answer other questions from the 60's and 70's such as the existence of diffeomorphisms with arbitrary Choquet simplexes of invariant measures. Moreover there are surprising analogues to Hilbert's 10th problem. In a different category, building on work of Poincar\{e}, Smale proposed classifying the \emph{qualitative} behavior of differentiable systems on compact manifolds. His 1967 paper explicitly argued that the equivalence relation of conjugacy up to homeomorphism" captures this notion and he proposes classifying it. Call this notion \emph{topological equivalence}. Very recent joint results with A. Gorodetski show: - The equivalence relation $E_0$ is Borel reducible to topological equivalence of diffeomorphisms of any smooth 2-manifold. - The equivalent relation of \emph{Graph Isomorphism} is Borel reducible to topological equivalence of diffeomorphisms of any smooth manifold of dimension 5 or above. As corollaries, none of the classical numerical invariants such as entropy, rates of growth of periodic points and so forth, can classify diffeomorphisms of 2-manifolds, and there is no Borel classification at all of diffeomorphisms of 5-manifolds. In the same 1967 paper Smale asks (in different language) whether there is a generic class that can be classified. This is still an open problem. Link to the talk: https://zoom.us/j/8244003061Hide Friday Mar 13 2020 16:00-16:50 (MS 6221) Anand Pillay (University of Notre Dame) CANCELLED Friday Feb 21 2020 16:00-16:50 (MS 6221) Jose G. Mijares (CalState LA) Metrically Baire sets and the Ramsey Property Abstract. There exist topological Ramsey spaces admitting metric projections where every Baire set has the Ramsey property. Jointly with N. Dobrinen, we gave a characterization of such spaces, answering a question of S. Todocervic. In this talk, we will discuss the characterization and present some examples (see https://drive.google.com/open?id=1l35j19JP9B6-fskoSc4I91VLnV-XABxw for the references).Hide Friday Feb 14 2020 16:00-16:50 (MS 6221) Katrin Tent (University of Muenster) Automorphism groups of order and tournament expansions Abstract. Introducing the notion of a stationary independence relation, Tent and Ziegler developed a framework for proving abstract simplicity of automorphism groups of a broad range of mathematical structures. In current work with Calderoni and Kwiatkowska we are extending this to cover in particular order and tournament expansions of such structures and show that their automorphism groups are again simple groups.Hide Friday Feb 07 2020 16:00-16:50 (MS 6221) Natasha Dobrinen (University of Denver) Strong coding trees and Ramsey theory on ultrahomogeneous structures Abstract. Strong coding trees were invented in order to solve the problem of whether or not the triangle-free Henson graph has analogues of Ramsey's theorem for colorings of finite triangle-free graphs. Since then, the method has been extended to handle all k-clique-free Henson graphs. Further, it has been useful for extending Ellentuck's infinite dimensional Ramsey theory to the rationals, and for extending the Galvin-Prikry theorem to the Rado graph. We will present some of the main ideas in these results, the history of the area, and some future directions.Hide Friday Jan 24 2020 16:00-16:50 (MS 6221) Aristotelis Panagiotopoulos (Caltech) Definable (co)homology and classification of solenoids Abstract. We will develop a framework for enriching various classical invariants from algebraic topology with descriptive set-theoretic information. Applying these ideas to Steenrod homology theory we get a new invariant for compact metrizable spaces up to homotopy equivalence which we call definable homology.'' Similarly we get a dual notion of definable cohomology'' for locally compact metrizable spaces by enriching the classical \v{C}ech cohomology theory. Our invariants are strictly finer than the original ones. In particular, we will show that $n$-dimensional (co)solenoids are completely classified up to homeomorphism by their definable (co)homology. In the process, we will generalize Veli\v{c}kovi\'c's rigidity theorem for definable automorphisms of $\mathcal{P}(\omega)/\mathrm{fin}$, to the arbitrary quotient $G/N$, where $G$ is a locally pro-finite abelian group and $N$ is a countable dense subgroup of $G$, and we will develop some basic definable homological algebra. This is a joint work with J. Bergfalk and M. Lupini.Hide Friday Jan 10 2020 16:00-16:50 (MS 6221) Rizos Sklinos (Stevens Institute of Technology) Fields definable in the theory of nonabelian free groups Abstract. In this talk I will show that only finite fields are definable in the theory of nonabelian free groups. This is joint work with Ayala Byron.Hide Friday Nov 15 2019 16:00-16:50 (MS 6221) Isaac Goldbring (UC Irvine) The almost sure theory of finite metric spaces Abstract. In this talk, we show that the class of finite metric spaces (of diameter at most 1) has an almost sure theory in the following sense: for each sentence $\sigma$ in the language of metric spaces, there is a real number $r$ such that, for any $\epsilon>0$, for large enough finite metric spaces $X$, with high probability, the value of $\sigma$ in $X$ differs from $r$ by at most $\epsilon$. This almost-sure theory is in fact the theory of a particular metric space, which we call the almost-sure metric space AS, and which can be defined as the Fraisse limit of the class of all finite metric spaces with nontrivial distances in the interval [1/2,1]. This is joint work with Bradd Hart.Hide Friday Nov 01 2019 16:00-16:50 (MS 6221) Pieter Spaas (UCLA) Almost invariant sets and stable equivalence relations Abstract. We are interested in structural properties of countable ergodic, but non-strongly ergodic, equivalence relations. Firstly, we will discuss a question posed by Jones and Schmidt in the 80s. In particular, we will provide examples and non-examples of equivalence relations all of whose almost invariant sets come from a single hyperfinite quotient. Secondly, we will study stable equivalence relations, i.e. those that can be written as a direct product of some equivalence relation with the hyperfinite one. We will then show that the stabilization of any strongly ergodic equivalence relation admits a unique stable decomposition in a precise sense.Hide Friday Oct 18 2019 16:00-16:50 (MS 6221) Mate Szabo (Université Paris 1 - Panthéon-Sorbonne) Pepis' and Kalmár's Arguments Against Church's Thesis Abstract. In his famous paper, "An Unsolvable Problem of Elementary Number Theory," Alonzo Church (1936) identified the intuitive notion of effective calculability with the mathematically precise notion of recursiveness. This proposal, known as Church's Thesis, has been widely accepted. In this talk I consider two early arguments against it. Pepis criticized Church's Thesis already in 1937 in his dissertation and in a letter written to Church. I will display recently found documents showing Pepis's stance. The main focus of the talk will be László Kalmár's famous "An Argument Against the Plausibility of Church's Thesis" from 1959. As this paper is quite short, my aim will be to present Kalmár's argument and to fill in missing details based on his general philosophical thoughts on mathematics and his writings published on these issues in Hungarian.Hide Friday Oct 04 2019 16:00-16:50 (MS 6221) Erik Walsberg (UC Irvine) Expansions of $(\mathbb{R},<,+)$ Abstract. I will survey recent work on first order expansions of $(\mathbb{R},<,+)$. Time permitting, I will discuss connections to automata theory and $\mathrm{NIP}$.Hide Friday May 31 2019 16:00-16:50 (MS 6221) Joshua Wiscons (Sacramento State) Status of the classification of finite Morley rank actions with a high degree of generic transitivity Abstract. It became clear through work of Borovik and Cherlin in 2008 that the classification theory for groups of finite Morley rank (fMr) is sufficiently developed that general questions about permutation groups of fMr can be settled even though the classification itself remains incomplete. This is a particularly salient direction since the study of uncountably categorical theories is intertwined with binding groups of fMr (acting on realizations of types). Borovik and Cherlin posed several motivating problems, many of which are centered around the notion of generic $n$-transitivity''. In this talk, we will discuss the status and implications of their conjecture that the only transitive and generically $(n+2)$-transitive group of fMr acting on a set of rank $n$ is $operatorname{PGL}_{n+1}$ acting naturally on projective $n$-space. Among other things, we will highlight a general approach to constructing a projective geometry in this context, and we will also illustrate how this conjecture is intertwined with minimal fMr representations of the finite symmetric groups. The talk will begin with a brief overview of the fMr landscape---knowledge of the advanced theory of groups of fMr will be not be required.Hide Friday May 17 2019 16:00-16:50 (MS 6221) Rachid Atmai (Mira Costa College, Oceanside) The search for definable counterexamples to the CH Abstract. We will talk about some partial results and methods which point in the direction of more definable counterexamples of the continuum hypothesis. The goal is to try to identify a canonical generic extension of L(R) in which Theta^L(R)>aleph_3, the axiom of choice holds and whose theory is set-forcing invariant in the presence of large cardinals. From the point of view of Woodin's Omega-logic, the idea behind this work is to identify axioms which mirror forcing axioms and which settle Sigma_2 truth of initial segments of V but under which there are definable counterexamples to CH. We will first review the context and motivation of this investigation and previous results.Hide Friday May 03 2019 16:00-16:50 (MS 6221) Aristotelis Panagiotopoulos (Caltech) Bernoulli shifts for Polish groups and a question of Kechris Abstract. The orbit equivalence relation of any continuous action of a Polish group $G$ has trivial Borel complexity if $G$ is compact. Similarly it is a theorem of A.S. Kechris that whenever a locally--compact Polish group acts continuously on a Polish space, the orbit equivalence relation of the action is essentially countable ---that is, Borel reducible to the orbit equivalence relation of an action of a countable group. A.S. Kechris asked for `inverses'' to these results: (1) does every non--compact Polish group admit a continuous action that is not concretely classifiable? (2) does every non--locally--compact Polish group admit a continuous action that is not essentially countable? Question (1) was positively answered by S. Solecki in a paper where he also answered question (2) for the special case where $G$ is the additive group of a separable Banach space. It is also resolved for the case where $G$ is an Abelian pro--countable group, by results of M. Malicki. In this talk I will present recent work on this problem, including a new dynamical proof of question (1) and a positive solution of question (2) in the case of non--Archimedean Polish groups. This is in joint work with J. Zielinski.Hide Friday Apr 19 2019 16:00-16:50 (MS 6221) Todor Tsankov (University Paris 7) A model-theoretic approach to ergodic theory Abstract. The main object of study of ergodic theory are the measure-preserving actions of (countable) groups on probability spaces. I will discuss a formalization of this setup in the framework of continuous logic and explain how some important notions studied in ergodic theory have a natural model-theoretic interpretation. This allows for some quick proofs of known results as well as a new rigidity theorem for strongly ergodic, distal actions. This is joint work with Tomas Ibarlucia.Hide Friday Mar 08 2019 16:00-16:50 (MS 6221) Nadja Hempel (UCLA) N-dependent groups and fields Abstract. NIP theories are the first class of the hierarchy of n-dependent structures. The random n-hypergraph is the canonical object which is n-dependent but not (n-1)-dependent. Thus the hierarchy is strict. But one might ask if there are any algebraic objects (groups, rings, fields) which are strictly n-dependent for every n? We will start by introducing the n-dependent hierarchy and present all known results on n-dependent groups and fields.Hide Friday Feb 22 2019 16:00-16:50 (MS 6221) Omer Mermelstein (University of Wisconsin - Madison) Generic flat pregeometries Abstract. The property of "flatness" of a pregeometry (matroid) is best known in model theory as the device with which Hrushovski showed that his example refuting Zilber's conjecture does not interpret an infinite group. I will dedicate the first part of this talk to explaining what flatness is, how it should be thought of, and how closely it relates to hypergraphs and Hrushovski's construction method. In the second part, I will conjecture that the family of flat pregeometries associated to strongly minimal sets is model theoretically nice, and share some intermediate results.Hide Friday Feb 08 2019 16:00-16:50 (MS 6221) Adam Day (Victoria University of Wellington) Computability Theoretic Hierarchies of Real-valued Functions Abstract. In this talk I will review some fundamental concepts in computability theory and show how they can be applied to analyze the relative complexity of real-valued functions. I will review some old results that come from this analysis, in particular, the continuous degrees of Miller. Then I will introduce some new hierarchies that results from joint work with Downey and Westrick. One of these new hierarchies refines the Bourgain rank for Baire class 1 functions and allows a new way to extend this rank to all Baire measurable functions.Hide Friday Jan 25 2019 16:00-16:50 (MS 6221) Lynn Scow (California State University, San Bernardino) Transfer of the Ramsey property Abstract. For $L$-structures $B$, $C$ we use the notation ${C choose B}$ to denote the set of all substructures of $C$ isomorphic to $B$. We say that a countable, locally finite structure $I$ ordered by a relation $<$ has RP (the Ramsey property) if for all $A_0, B_0 in textrm{age}(I)$ and integers $k geq 1$ there is some $C_0 in textrm{age}(I)$ such that $C_0 rightarrow (B_0)^{A_0}_k$. In other words, for all functions $c: {C_0 choose A_0} rightarrow k$ there is some $B' subseteq C_0$, $B' cong B_0$ such that $c$ restricted to ${B' choose A_0}$ is a constant function. We will approach the question of when RP transfers from one countable structure to another, where these structures are in possibly different languages. We will look at universal algebraic and model theoretic criteria.Hide Friday Jan 11 2019 16:00-16:50 (MS 6221) Szymon Torunczyk (University of Warsaw) Some applications of model theory in computer science Abstract. I will present a few basic applications of model theory in theoretical computer science, e.g. in verification, databases, and algorithms. I will also discuss some initial ideas employing (ideas from) stability theory to solve algorithmic problems concerning graphs.Hide Friday Nov 30 2018 16:00-16:50 (MS 6221) Nick Ramsey (UCLA) Kim-independence and NSOP1 theories Abstract. Shelah's work on saturation spectra, Hrushovski on PAC structures, and Cherlin-Hrushovski on quasi-finite structures gave the initial impetus for the development of simple theories. A general theory, which unified and explained these different lines of research, was developed by Kim and Pillay using the notion of non-forking independence, which in turn spawned a remarkably rich line of model-theoretic research. In my talk, we will describe a parallel theory for the broader class of NSOP1 theories centered around the notion of Kim-independence and the applications that this theory made possible. We will survey results in a series of papers joint with Artem Chernikov, Itay Kaplan, Alex Kruckman, and Saharon Shelah (though not all at once).Hide Friday Nov 16 2018 16:00-16:50 (MS 6221) Lynn Scow (California State University, San Bernardino) Transfer of the Ramsey property - CANCELLED Abstract. For $L$-structures $B$, $C$ we use the notation ${C choose B}$ to denote the set of all substructures of $C$ isomorphic to $B$. We say that a countable, locally finite structure $I$ ordered by a relation $<$ has RP (the Ramsey property) if for all $A_0, B_0$ in age$(I)$ and integers $k geq 1$ there is some $C_0$ in age$(I)$ such that $C_0 rightarrow (B_0)^{A_0}_k$. In other words, for all functions $c: {C_0 choose A_0} rightarrow k$ there is some $B' subseteq C_0$, $B' cong B_0$ such that $c$ restricted to ${B' choose A_0}$ is a constant function. We will approach the question of when RP transfers from one countable structure to another, where these structures are in possibly different languages. We will look at universal algebraic and model theoretic criteria.Hide Friday Nov 02 2018 16:00-16:50 (MS 6221) Douglas Ulrich (UC Irvine) Generalized Amalgamation and Chromatic Numbers Abstract. Let $T_{k+1, k}$ denote the theory of the k-ary, k+1-clique free random hypergraph, for k >= 3. Malliaris and Shelah have famously proven that $T_{k+1, k}$ is not below $T_{k'+1, k'}$ in Keisler's order, whenever k+1 < k'; hence, Keisler's order has infinitely many classes. I have since improved the combinatorics to obtain the same result whenever k < k', and I obtain model-theoretic upper and lower bounds for the relevant dividing lines detected by Keisler's order. These bounds correspond to various kinds of k-dimensional amalgamation properties. The combinatorics involved is rather technical; however, the model-theoretic upper and lower bounds are not. I aim to introduce and motivate them; in particular, we will explore a connection between generalized amalgamation properties and the chromatic numbers of hypergraphs of partial types. It is open if the various k-dimensional amalgamation properties we introduce are equivalent.Hide Friday Oct 19 2018 16:00-16:50 (MS 6221) Sam Buss (UC San Diego) Bounded Arithmetic, Expanders, and Monotone Propositional Proofs Abstract. This talk discusses a new combinatorial proof of the existence of expander graphs, which can be carried out in the bounded arithmetic theory VNC$^1$ corresponding to alternating linear time. As an application, we prove that the monotone propositional sequent calculus polynomially simulates the full propositional sequent calculus. Prior to this, only a quasipolynomial simulation was known. Joint work with Valentine Kabanets, Antonina Kolokolova, and Michal Koucky.Hide Friday Oct 05 2018 16:00-16:50 (MS 6221) Byunghan Kim (Yonsei University, Seoul) On the number of countable NSOP$_1$ theories without weight $omega$. Abstract. Lachlan's problem is asking whether any countable theory $T$ with \$1