The UCLA Logic Colloquium meets on alternate Wednesdays,
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. **

Wednesday Nov 08 2023 | ||||

16:00-16:50 () | Joshua Frisch (UC San Diego) | |||

Wednesday Oct 25 2023 | ||||

16:00-16:50 () | Deirdre Haskell (McMaster University) | |||

Wednesday Oct 11 2023 | ||||

16:00-16:50 () | Jan Grebik (UCLA) |

Wednesday Jun 07 2023 | ||||

16:00-16:50 (MS 6221) | Jinhe (Vincent) Ye (Oxford) | Curve-excluding fields | ||

Abstract. Given C a curve over $\mathbb{Q}$ with genus at least 2 and $C(\mathbb{Q})$ is empty, the class of fields K of characteristic 0 such that $C(K)=\emptyset$ has a model companion, which we call CXF. Models of CXF have interesting combinations of properties. For example, they provide an example of a model-complete field with unbounded Galois group, answering a question of Macintyre negatively. One can also construct a model of it with a decidable first-order theory that is not "large'' in the sense of Pop. Algebraically, it provides a field that is algebraically bounded but not "very slim" in the sense of Junker and Koenigsmann. Model theoretically, we find a pure field that is strictly NSOP_4. | ||||

Wednesday May 24 2023 | ||||

16:00-16:50 (MS 6221) | Elliot Glazer (Harvard) | Choiceless analysis of coin-flipping measures | ||

Abstract. In the presence of countable choice, one can construct for an arbitrary $X$ the completed product measure on $2^X$ (e.g., for $X=\omega,$ this is the Lebesgue measure). Quotienting out the null ideal, we then get a well-behaved measure algebra, on which we have the $L^p$ spaces. We show that under reasonable definitions, the basic theory of these measure algebras and the analysis of the corresponding $L^p$ spaces can be derived just in ZF. We will be particularly interested in the case of $X = \omega,$ which will allow us to make sense of the choiceless theory ZF + "all sets of reals are Lebesgue measurable" and verify it to be equiconsistent with ZF, despite the famous equiconsistency of ZF + DC + "all sets of reals are Lebesgue measurable" with an inaccessible. | ||||

Wednesday May 10 2023 | ||||

16:00-16:50 (MS 6221) | Jing Yu (Georgia Tech) | Large scale geometry of graphs of polynomial growth | ||

Abstract. In 1995, Levin and Linial, London, and Rabinovich conjectured that every connected graph $G$ of polynomial growth admits an injective homomorphism to the $n$-dimensional grid graph for some $n$. Moreover, they conjectured that if every ball of radius $r$ in $G$ contains at most $O(r^\rho)$ vertices, then one can take $n = O(\rho)$. Krauthgamer and Lee confirmed the first part of this conjecture and refuted the second in 2007. By constructing some finite expander graphs, they showed best possible upper bound on $n$ is $O(\rho \log \rho)$. Prompted by these results, Papasoglu asked whether a graph $G$ of polynomial growth admits a coarse embedding into a grid graph. We give an affirmative answer to this question. Moreover, it turns out that the dimension of the grid graph only needs to be linear in the asymptotic growth rate of $G$, which confirms the original Levin–Linial–London–Rabinovich conjecture "on the large scale." Besides, we find an alternative proof of the result of Papasoglu that graphs of polynomial growth rate $\rho < \infty$ have asymptotic dimension at most $\rho$. Furthermore, our proof works in the Borel setting and shows that Borel graphs of polynomial growth rate $\rho < \infty$ have Borel asymptotic dimension at most $\rho$. This is joint work with Anton Bernshteyn. | ||||

Wednesday Apr 26 2023 | ||||

16:00-16:50 (MS 6221) | Sean Walsh (UCLA, Philosophy) | Algorithmic randomness and Lévy's Upward Theorem | ||

Abstract. Much recent work in algorithmic randomness has concerned characterizations of randomness notions in terms of the almost-everywhere behavior of suitably effectivized versions of functions from analysis or probability. In this work, we examine the relationship between algorithmic randomness and Lévy's Upward Martingale Convergence Theorem, in the setting of arbitrary computable Polish spaces. We show that Schnorr randoms are precisely the points at which the conditional expectations of L^1-computable functions converge to their true value. This result has natural applications to formal epistemology and the philosophical interpretation of probability: for, the natural Bayesian interpretation of this result is that belief, in the form of an agent's best estimates of the true value of a random variable, aligns with truth in the limit, under appropriate effectiveness and randomness assumptions. We also consider other randomness notions such as Martin-Löf Randomness and density randomness. This is joint work with Simon M. Huttegger (UC Irvine) and Francesca Zaffora Blando (CMU). | ||||

Wednesday Apr 12 2023 | ||||

16:00-16:50 (MS 6221) | Pieter Spaas (Copenhagen) | Stable decompositions for countable equivalence relations | ||

Abstract. We will start with some motivation and background for the talk, and then discuss stable decompositions of a countable ergodic p.m.p. equivalence relation. We will explain the definition and show that the stabilization of any equivalence relation without central sequences in its full group (i.e. it is not ''Schmidt'') has a unique stable decomposition. This provides the first non-strongly ergodic such examples. | ||||

Friday Mar 24 2023 | ||||

16:00-16:50 (MS 6221) | Alexis Chevalier | An algebraic hypergraph regularity lemma | ||

Abstract. In "Expanding polynomials over finite fields…" (2012), Tao proves the algebraic regularity lemma. This is a strong form of the Szemeredi regularity lemma for definable graphs in the language of rings in finite fields. The algebraic regularity lemma improves the Szemeredi regularity lemma by providing definable regular partitions of definable bipartite graphs which have no irregular pairs and such that the error bounds on regularity vanish as the size of the finite field grows.
Tao asks if the algebraic regularity lemma can be extended to definable hypergraphs, in the same way that the Szemeredi regularity lemma extends to hypergraphs in the style of Rodel and Skokan (2004) or Gowers (2006). We answer this question positively by giving a new analysis of the algebraic regularity lemma. We use the model theory of pseudofinite fields to relate the combinatorial notion of regularity (for graphs and for hypergraphs) to Galois-theoretic information associated to definable sets. With this new analysis in hand, the algebraic hypergraph regularity lemma follows by classical results of Gowers, albeit with some interesting technical details. | ||||

Friday Mar 10 2023 | ||||

16:00-16:50 (MS 6221) | Tom Benhamou | The Galvin property and its applications | ||

Abstract. We present a property of filters discovered by F. Galvin which he proved to hold for normal filters over strongly regular cardinals, and which gained renewed interest due to recent developments in set theory. In the first part of the talk, we will provide applications of this property. The second goal will be to discuss a strengthening of Galvin's theorem, and the situation in some canonical inner models. We will also present relevant constructions of filters and ultrafilters without the Galvin property, answering several questions. If time permits, we shall present extensions of the work of U. Abraham and S. Shelah, who produced a model where the club filter fails to satisfy the Galvin property in a strong sense at $\kappa^+$, where $\kappa$ is a regular cardinal and $2^{\kappa}>\kappa^+$. We will produce a model where the club filter fails to satisfy the Galvin property at $\kappa^+$, where $\kappa$ is singular and $2^{\kappa}>\kappa^+$. We will obtain this model from the optimal large cardinal assumptions and explore the possibility of obtaining the stronger form of failure as in the Abraham and Shelah model. This is partially a joint work with M. Gitik, S. Garti, and A. Poveda. | ||||

Friday Feb 24 2023 | ||||

16:00-16:50 (MS 6221) | Srivatsav Kunnawalkam Elayavalli | Generic algebraic properties in spaces of enumerated groups | ||

Abstract. We will introduce and study Polish topologies on various spaces of countable enumerated groups, where an enumerated group is simply a group whose underlying set is the set of natural numbers. Using elementary tools and well known examples from combinatorial group theory, combined with the Baire category theorem, we obtain a plethora of results demonstrating that several phenomena in group theory are generic. In effect, we provide a new topological framework for the analysis of various well known problems in group theory. We also provide a connection between genericity in these spaces, the word problem for finitely generated groups and model-theoretic forcing. Using these connections, we investigate the natural question: when does a certain space of enumerated groups contain a comeager isomorphism class? We obtain a sufficient condition that allows us to answer the question in the negative for the space of all enumerated groups and the space of left orderable enumerated groups. This is joint work with Goldbring and Lodha. | ||||

Friday Jan 27 2023 | ||||

16:00-16:50 (MS 6221) | Asger Tornquist | Maximal orthogonal families of probability measures: An overview | ||

Abstract. Let $X$ be a Polish space. Two Borel measures $\mu$ and $\nu$ on $X$ are called orthogonal if there is a Borel set $B\subseteq X$ which is null or $\mu$ and co-null for $\nu$. In the early 1980s, Daniel Mauldin asked if a maximal orthogonal family (“mof”) of probability measures on an uncountable Polish space $X$ can be analytic, and this was quickly answered in the negative by Rataj and Preiss (1985), who used Baire category methods to prove this. Over the years, other proofs of this result have been given, most notably by Kechris and Sofronidis, who gave an elegant proof using turbulence; and recently, gave a simplified version of Rataj and Preiss proof that relies on the Kuratowski-Ulam theorem rather than using a Banach-Mazur game. Some other known proofs use other notions of regularity than Baire category, such as completely Ramsey and Lebesgue measurability. On the other hand, David Schrittesser and I proved that Baire category can’t be replaced by Sacks and Miller measurability to prove that there are no mofs in the lower rungs of the projective hierarchy (Pi-1-1 and Sigma-1-2). In this talk, I will give an overview of the subject. | ||||

Friday Jan 13 2023 | ||||

16:00-16:50 (MS 6221) | Andrew Marks | A dichotomy characterizing piecewise Baire class $\alpha$ functions | ||

Abstract. In the 1920s, Lusin asked whether every Borel function on
$2^\omega$ is a union of countably many partial continuous functions (i.e. whether every Borel function is piecewise continuous). This question has a negative answer; an example of a non-piecewise continuous Borel function is the Turing jump. This is the only counterexample in one sense. Solecki and Zapletal have shown that every Borel function $f$ is either piecewise 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 piecewise Baire class $\alpha$, or the complete Baire class $\alpha+1$ function (an appropriate iterate of the Turing jump) continuously reduces to $f$. Our proof uses an adaptation of Montalban's game metatheorem for priority arguments to boldface descriptive set theory. This is joint work with Antonio Montalban. | ||||

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. | ||||

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. | ||||

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. | ||||

Wednesday Oct 26 2022 | ||||

16:00-16:50 (MS 6221) | Mariana Vicaría | 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. | ||||

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. | ||||

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. | ||||

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/8244003061 | ||||

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). | ||||

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. | ||||

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. | ||||

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. | ||||

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. | ||||

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. | ||||

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. | ||||

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. | ||||

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}$. |

Click here to see the announcements for older Logic Colloquia.