The UCLA Logic Colloquium meets on alternate Wednesdays,
at 2 p.m., in MS 6627.
The Logic Colloquium is organized by
Mariana Vicaria and
Jan Grebik.
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 Dec 11 2024 | ||||
14:00-14:50 (MS 6627) | Scott Mutchnik (Institut de mathématiques de Jussieu – Paris Rive Gauche) | The Koponen Conjecture | ||
Abstract. This is on joint work with John Baldwin and James Freitag. One of the central projects of model theory, initiated by Shelah in his book "Classification Theory," is to classify unstable first-order theories. As part of this program, Koponen proposes to classify simple homogeneous structures, such as the random graph. More precisely, she conjectures (2016) that all simple theories with quantifier elimination in a finite relational language are supersimple of finite rank, and asks (2014) whether they are one-based. In this talk, we discuss our resolution of the Koponen conjecture, where we show that the answer to this question is yes. In the process, we further demonstrate what Kennedy (2020) calls "the fragility of the syntax-semantics distinction." | ||||
Wednesday Dec 04 2024 | ||||
14:00-14:50 (MS 6627) | Jinhe Ye (University of Oxford) | Lang-Weil type estimates in finite difference fields | ||
Abstract. A difference field is a field equipped with a distinguished automorphism and a difference variety is the natural analogue of an algebraic variety in this setting. Complex numbers with complex conjugation or finite fields with the Frobenius automorphism are natural examples of difference fields. For finite fields and varieties over them, the celebrated Lang-Weil estimate gives a universal estimate of number of rational points of varieties over finite fields in terms of several notions of the complexities of the given variety. In this talk, we will discuss an analogue to the Lang-Weil estimate for difference varieties in finite difference fields. The proof uses the model theory of pseudofinite difference fields and $\omega$-increasing valued difference fields. Particularly, some interesting interactions between the non-standard Frobenius and the non-archimedean topology occur. This is joint work with Martin Hils, Ehud Hrushovski and Tingxiang Zou. | ||||
Wednesday Nov 20 2024 | ||||
14:00-14:50 (MS 6627) | (Will Johnson) | Tame topology and definable fields | ||
Abstract. O-minimal structures satisfy many "tame topology" properties, such as a cell decomposition theorem for definable sets, generic continuity for definable functions, and a sensible notion of dimension for definable sets. It turns out that these tame topology properties hold in a number of other settings, such as weak o-minimality, C-minimality, P-minimality, and (more recently) Hensel minimality.
One very weak condition, which generalizes all these, is "topological minimality" (t-minimality) in the sense of Mathews. A theory is t-minimal if there is a definable topology on models M such that no points are isolated, and any definable subset D ⊆ M has finite boundary. A rudimentary amount of "tame topology" continues to work for t-minimal theories. This talk will discuss an ongoing investigation into definable fields in t-minimal theories. Although t-minimality is a very weak assumption, one can somehow prove non-trivial things about definable groups and fields. For example, if K is a definable field in a t-minimal theory, then K must be perfect. Under some weak assumptions (which I hope to remove), K must also satisfy a technical condition called "largeness", which rules out possibilities like number fields and function fields. Beyond these, I expect there to be more substantial constraints on K, as I will discuss. | ||||
Wednesday Nov 13 2024 | ||||
14:00-14:50 (MS 6627) | (William Adkisson) | Strong Tree Properties at Many Cardinals | ||
Abstract. The strong tree property and ITP (also called the super tree property) are generalizations of the tree property that characterize strong compactness and supercompactness up to inaccessibility in much the same way that the tree property characterizes weak compactness. That is, an inaccessible cardinal κ is strongly compact if and only if the strong tree property holds at κ, and supercompact if and only if ITP holds at κ. It is a longstanding project in set theory to obtain large-cardinal properties, like the strong tree property or ITP, at all possible cardinals simultaneously. I will discuss several results related to this program. | ||||
Friday Nov 08 2024 | ||||
14:00-14:50 (MS 6627 ) | (Pierre Simon) | NIP, learning theory and compressible types | ||
Abstract. TBD | ||||
Wednesday Oct 30 2024 | ||||
14:00-14:50 (MS 6627 ) | (Edward Keenan) | Quantification in Natural Language | ||
Abstract. A fourfold classification of Subject quantifiers and their basic logical properties
Intersective, Co-Intersective, Proportional, Definite
All satisfy one general, strong, constraint: Conservativity
Natural languages are provably not sortally reducible
Logical subclasses given by PI (Permutation Invariance) & BCL (Boolean closure) e.g.
Over finite domains Cardinal quantifiers = Intersective + PI
BCL(Intersective Co-intersective) = CONS (the set of conservative quantifiers)
Two novel entailment paradigms: e.g. Midpoint QPs hold of predicates and their
negations (QxPx and QxPx) are never logically equivalent for Q = or )
Object Quantifiers (The arguments of P2s, two place predicates, behave asymmetrically) Subject QPs extend, and new types arise: nominal and predicate anaphors including one new self-dual quantifier One new entailment paradigm (Facing Negations Theorem) using P2s: For what QPs F,G,F’,G’ do F(G(R)) = F’(G’(R)), all binary relations R? Open Questions: Can we find an elegant characterization of expressible functions from P2s to P1s? From P2s directly to {0,1}? (e.g. Different people like different things). Is the richness of Object quantifiers related to the Boolos & Jeffrey theorem on increased expressive power of FOL when P2s are added to monadic FOL? | ||||
Wednesday Oct 16 2024 | ||||
14:00-14:50 (MS 6627 ) | (Felix Weilacher) | Computable vs. Descriptive Combinatorics of Local Problems | ||
Abstract. We consider "local" combinatorial problems on graphs. I.e, problems in which we seek a global labelling of vertices, edges, etc. satisfying some set of local constraints. Typical examples include proper coloring and perfect matching. We are moreover interested in finding solutions which are in some sense "constructive" or "definable".
We will focus on two specializations of this: finding Baire measurable solutions for Borel graphs on Polish spaces, and finding computable solutions for computable graphs on the natural numbers. Recent investigations have uncovered a large number of similarities between these two settings, but there are interesting questions about how deep the relationship really is. We will attempt to survey some recent positive and negative results in this direction.
Includes joint work with Berlow, Bernshteyn, Bowen, Conley, Lyons, and Qian. | ||||
Wednesday Oct 02 2024 | ||||
14:00-14:50 (MS 6627 ) | Nigel Pynn-Coates (University of Vienna) | Tame pairs of transseries fields | ||
Abstract. Transseries emerged in connection with Écalle's work on Dulac's problem
and Dahn and Göring's work on nonstandard models of real exponentiation,
and some can be viewed as asymptotic expansions of solutions to
differential equations. More recently, Aschenbrenner, Van den Dries, and
Van der Hoeven completely axiomatized the elementary theory of the
differential field of (logarithmic-exponential) transseries and showed
that it is model complete. This talk concerns pairs of models of this
theory such that one is a tame substructure of the other in a certain
sense. I will describe the model theory of such transserial tame pairs,
including a model completeness result for them, which can be viewed as a
strengthening of the model completeness of large elementary extensions
of the differential field of transseries, such as hyperseries, surreal
numbers, or maximal Hardy fields. | ||||
Wednesday Jun 12 2024 | ||||
16:00-16:50 (MS 6221 ) | Alf Onshuus (Universidad de los Andes) | Lie groups and o-minimality | ||
Abstract. It has been known for some time that any group definable in an o-minimal expansion of the real field can be endowed definably with the structure of a Lie group, and that any definable homomorphisms between definable groups is a Lie homomorphism (under the above mentioned Lie structure).
In this talk we explore the converse: We will characterize when a Lie group has a Lie isomorphic group which is definable in an o-minimal expansion of the real field, when Lie isomorphisms between such definable groups is definable, and whether one can achieve a definable Lie analytic structure in any such definable group. My attempt is to give the talk with almost no assumptions on background, other than first order logic. In particular I will recap most of the relevant algebraic and geometric definitions. | ||||
Wednesday Jun 05 2024 | ||||
16:00-16:50 (MS 6221 ) | Margaret Thomas (Purdue University) | Definable topological spaces in o-minimal structures | ||
Abstract. O-minimal structures have been extensively studied as a framework for 'tame topology', in particular in terms of the underlying euclidean (order) topology. In addition, studies of the topological nature of various definable objects, such as groups, manifold spaces, orders, function spaces and metric spaces, have also been key to the development of o-minimality. Our work is directed towards a more general understanding of the nature of topological spaces definable in o-minimal structures (where, in any model-theoretic structure, a 'definable topological space' is a definable set together with a (uniformly) definable family forming a basis for a topology on that set). So far, our focus has mainly been on one-dimensional definable topological spaces but, even in this setting, there are examples exhibiting a wide variety of topological properties, including various classical topological counterexamples.
We present a number of classification results given in terms of decomposition and embedding theorems and, in parallel, identify suitable definable analogues of classical properties such as separability, compactness and metrizability. This leads to a variety of applications, including definable versions of conjectures from classical topology due to Gruenhage and Fremlin (on the nature of regular Hausdorff and perfectly normal compact Hausdorff spaces), as well as universality results for certain classes of spaces. This is part of a long-term joint project with Pablo Andújar Guerrero and Erik Walsberg, and intersects with work carried out independently by Peterzil and Rosel. | ||||
Wednesday May 22 2024 | ||||
16:00-16:50 (MS 6221 (now online)) | Alexander Kechris (California Institute of Technology) | The compact action realization problem | ||
Abstract. In this talk I will discuss realizations of countable Borel equivalence relations by continuous actions of
countable groups, focusing in particular on the problem of realization by continuous actions on compact spaces and more specifically subshifts. This also leads to considering a natural universal space for actions and equivalence relations via subshifts and the study of the descriptive and topological properties in this universal space of various classes of countable Borel equivalence relations, especially the hyperfinite ones. | ||||
Wednesday May 08 2024 | ||||
16:00-16:50 (MS 6221 (now online)) | Amanda Wilkens (University of Texas at Austin) | Poisson--Voronoi tessellations and fixed price in higher rank | ||
Abstract. We define and motivate the Poisson point process, which is, informally, a "maximally random" scattering of points in space. We introduce the ideal Poisson--Voronoi tessellation (IPVT), a new random object with intriguing geometric properties when considered on a semisimple symmetric space (the hyperbolic plane, for example). In joint work with Mikolaj Fraczyk and Sam Mellick, we use the IPVT to prove a result on the relationship between the volume of a manifold and the number of generators of its fundamental group. We give some intuition for the proof, which relies on Gaboriau's theory of cost for measure-preserving actions. No prior knowledge on Poisson point processes or symmetric spaces will be assumed.
**Online only.** Zoom link: https://ucla.zoom.us/j/98099215455 Meeting ID: 980 9921 5455 | ||||
Wednesday Apr 24 2024 | ||||
16:00-16:50 (MS 6221) | David Gonzalez (UC Berkeley) | Semi-periodic Functions and the Scott Analysis of Linear Orderings | ||
Abstract. The concept of Scott complexity was introduced by Alvir, Greenberg, Harrison-Trainor and Turetsky and gives a way of assigning countable structures to elements of the Borel hierarchy that correspond to their descriptive complexity. This concept refines the previous notions of Scott rank. In computable structure theory, Scott analysis refers to a wide variety of pursuits related to the concepts of Scott rank and Scott complexity. For example, it is typical to study the sorts of Scott ranks and Scott complexities that can appear in a given class of structures or the sorts of structures from a class that can have a given Scott rank or Scott complexity.
I will describe recent work that solves a number of open questions regarding the Scott analysis of linear orderings (and of structures in general). Central to this work is a new construction of a linear ordering given a so-called semi-periodic function. We will discuss this construction and how to use the combinatorial structure of semi-periodic functions to extract Scott analytic facts about their corresponding linear orderings. | ||||
Wednesday Apr 10 2024 | ||||
16:00-16:50 (MS 6221) | Benjamin Castle (University of Maryland-Urbana) | Zilber's Restricted Trichotomy via Valued Fields | ||
Abstract. This talk will survey the recent solution of Zilber's `Restricted Trichotomy Conjecture' -- which asserts that every sufficiently `non-degenerate' reduct of an algebraically closed field interprets a copy of the same field. Special cases of this conjecture emerged during the 1980s and 1990s in work of Martin, Rabinovich, Rabinovich-Zilber, and Marker-Pillay; while Zilber showed in 2014 that a positive answer has applications in algebraic geometry. In the end, the problem was solved in two papers by considering (more generally) reducts of algebraically closed valued fields. I will attempt to explain the history of the problem, the general proof strategy, and the reason valued fields ultimately play a key role. | ||||
Wednesday Mar 27 2024 | ||||
16:00-16:50 (MS 6221) | Pablo Cubides (Universidad de los Andes) | Geometric spaces from the model-theorist point of view | ||
Abstract. In this talk I will informally show how different geometric spaces can be seen model-theoretically as spaces of definable types. I will concentrate on three kinds of geometric spaces having an algebraic nature: affine algebraic varieties over an algebraically closed field, affine real algebraic varieties over a real closed field, and, if time allows, the Berkovich analytification of an affine algebraic variety over a non-archimedean algebraically closed valued field. A short word about the (strict) pro-definability of such spaces will be discussed. No background in algebraic geometry will be assumed. | ||||
Wednesday Mar 13 2024 | ||||
16:00-16:50 (MS 6221) | Nam Trang (University of North Texas) | Ideals and Strong Axioms of Determinacy | ||
Abstract. We present the main ideas behind the proof of the equiconsistency of the theories:
(1) ZF + AD_R + \Theta is regular. (2) ZFC + CH + there is an \omega_1-dense ideal on \omega_1. (3) ZFC + the nonstationary ideal on P_{\omega_1}(R) is strong and pseudo-homogeneous. This resolves a long-standing open problem asked by W.H. Woodin in the 1990's. In the first talk, we discuss some history related to this problem and the general program in descriptive inner model theory that aims to calibrate the consistency strength of theories like the above. The results from this talk are from the paper Ideals and Strong Axioms of Determinacy, by Adolf, Sargsyan, Trang, Wilson and Zeman: https://arxiv.org/abs/2111.06220 | ||||
Wednesday Feb 28 2024 | ||||
16:00-16:50 (MS 6221) | Gabriel Goldberg (UC Berkeley) | Ordinal definability and large cardinals. | ||
Abstract. Woodin's HOD conjecture is one of the most important open problems in large cardinal set theory. A particularly simple formulation of the conjecture states that under large cardinal assumptions (in particular a supercompact cardinal), one can define a well order of the class Ordω of countable sequences of ordinals. This talk will discuss the motivation behind Woodin's conjecture, its connection to some of the speaker's recent ZFC theorems on ordinal definability, and the current status of a cluster of related problems in inner model theory and large cardinals. | ||||
Wednesday Feb 14 2024 | ||||
16:00-16:50 (MS 6221) | Diego Bejarano (UC Berkeley) | Separable structure theory | ||
Abstract. In [1], Ben Yaacov et. al. extended the basic ideas of Scott analysis to metric structures in infinitary continuous logic. These include back-and-forth relations, Scott sentences, and the Lopez-Escobar theorem to name a few.
In this talk, I will talk about joint work with Dino Rossegger connecting the ideas of Scott analysis to the definability of automorphism orbits and “isolation” of types within separable metric structures.
Our results are a continuous analogue of the robuster Scott rank developed by Montalbán [2] for countable structures in discrete infinitary logic. However, there are some differences arising from the subtleties behind the notion of definability in continuous logic.
[1] Itaï Ben Yaacov, Michal Doucha, Andre Nies, and Todor Tsankov. “Metric Scott analysis”. In: Advances in Mathematics 318 (2017), pp. 46–87. [2] Antonio Montalbán. “A robuster Scott rank”. In: Proceedings of the American Mathematical Society 143.12 (Apr. 2015), pp. 5427–5436. | ||||
Wednesday Jan 31 2024 | ||||
16:00-16:50 (MS 6221) | Isaac Goldbring (UC Irvine) | Preliminary remarks on the first-order free group factor problem | ||
Abstract. A standard construction in von Neumann algebra theory is to construct the group von Neumann algebra L(G) associated to any discrete group G. This process can “forget” much of the algebraic information about the group. For example, a celebrated result of Connes implies that any two discrete amenable groups all of whose nontrivial conjugacy classes are infinite yield the same von Neumann algebra. A famous open question in the subject is whether or not L(F_m) and L(F_n) are isomorphic for distinct m and n, where F_m denotes the nonabelian free group on m generators. In this talk, we will discuss some preliminary observations about the model-theoretic version of this question, which asks whether or not L(F_m) and L(F_n) are elementarily equivalent for distinct m and n (which can be viewed as a noncommutative version of the famous Tarski problem, which asks whether or not F_m and F_n are elementarily equivalent and for which the problem is now known to have a positive solution). The work presented in this talk is joint with Jennifer Pi. We will assume no prior knowledge of von Neumann algebra theory. | ||||
Wednesday Jan 24 2024 | ||||
16:00-16:50 (MS 6221) | Asger Tornquist (University of Copenhagen) | Some set theoretic aspects of a model of the mind proposed in psychology | ||
Abstract. This talk is about a somewhat unusual topic for me to work with: A psychology professor in Denmark, Jens Mammen, has developed a "model of the human mind", which is formulated in terms of some simple mathematical objects: The model consists of a "universe", which is a set U (whose elements are "objects" or "individuals" in this theory; the objects in the universe are meant to represent the things/people/pets in the world that the mind can potentially sense or interact with: your car, your father, your cat, etc.), and additionally the model has two collections of subsets of the universe U, called C and S. The subsets of U which are elements of S are called the "sense" categories, and they represent broad categories that the mind can form (e.g., the category of all cats). Subsets of U which are in C are called "choice categories", and are supposed to represent those things in the universe the mind can single out (for instance, _your_ cat (or cats)) among all the things in the broad categories.
Mammen formulated a number of axioms that C and S must satisfy to reasonably represent the human mind, and then asked a number of questions about what sort of models were possible to have. Remarkably, several of these problems require some actual mathematics, and some problems even require resonably serious set theory. To appreciate why, note that when the universe U is countable, then C and S will be subsets of P(U), i.e. of Cantor space, so it makes sense to ask how definable in the descriptive set theoretic sense C and S can be and still satisfy Mammen's axioms (as well as additional desirable properties). Purely combinatorial problems (including using ultrafilters, AC, and cardinal invariants!) also appear when trying to obtain various kinds of models of Mammen's axiom system. In this talk, I'll give a brief overview of Mammen's theory of the mind, and then move on to discuss the set-theoretic problems that Mammen's theory poses, with an emphasis on the descriptive set theory side of things. Towards the end, I'll mention some open problems (of a mathematical nature) that are still around. | ||||
Wednesday Jan 17 2024 | ||||
16:00-16:50 (MS 6221) | Samaria Montenegro (Universidad de Costa Rica) | Fields and NTP2 | ||
Abstract. One of the objects of study of model theory are the complete first order theories and their classification. Shelah classified complete first order theories by their ability to encode certain combinatorial configurations. For example, the theories that are not able to encode linear orders are the stable theories. Shelah and others produced important results and techniques for analyzing types and models within this classification. In algebraic structures such as groups or fields, these model-theoretic properties are related to algebraic properties of the structure.
We are going to focus on the class of NTP2 theories (theories without the tree property of the second kind), Shelah defined this class in the 1980s and contains strictly the class of simple and NIP theories. We will focus on fields that are NTP2, we will explain the case of bounded PAC, PRC, and PpC fields. Then we propose a unified framework for studying these fields - the class of pseudo-T-closed fields, where T is an enriched theory of fields. These fields verify a "local-global" principle for the existence of points on varieties based on models of T. This approach also enables a good description of some fields equipped with multiple V-topologies, particularly pseudo-algebraically closed fields with a finite number of V-topologies. We are going to show how we can use this approach to produce many new examples of NTP2 fields. Part of this talk is a joint work with Silvain Rideau-Kikuchi. | ||||
Wednesday Nov 29 2023 | ||||
16:00-16:50 (MS 6221) | Kyle Gannon (Peking University) | Generically stable idempotent measures in abelian NIP groups | ||
Abstract. Given a locally compact topological group, there is a correspondence between idempotent probability measures and compact subgroups. An analogue of this correspondence continues into the model theoretic setting. In particular, if G is a stable group, then there is a one-to-one correspondence between idempotent Keisler measures and type-definable subgroups. The proof of this theorem relies heavily on the theory of local ranks in stability theory. Recently, we have been able to extend a version of this correspondence to the abelian NIP setting. In this context, we prove that generically stable idempotent Keisler measures correspond to fsg subgroups. These results rely on recent work connecting generically stable measures to generically stable types over the randomization. This is joint work with Artem Chernikov and Krzysztof Krupinski. | ||||
Wednesday Nov 08 2023 | ||||
16:00-16:50 (MS 6221) | Joshua Frisch (UC San Diego) | Equivalence Relations Classifiable by Polish Abelian Groups | ||
Abstract. The theory of Borel reducibility gives a way to formalize when one equivalence relation is less complicated than another. Since the founding of the theory, a common leitmotif has been to analyze, in particular, how complicated those equivalence relations coming from group actions are. In this talk, I will discuss some recent work joint with Forte Shinko about the following question: when does a countable Borel equivalence relation reduce to one generated by a Polish abelian group? | ||||
Wednesday Oct 25 2023 | ||||
16:00-16:50 (MS 6221) | Deirdre Haskell (McMaster University) | Residue field domination in some theories of valued fields | ||
Abstract. A paraphrase of the Ax-Kochen-Ersov theorem for some theories of valued fields is that the elementary theory is determined by the theory of the value group and the residue field. At the level of types, the intuition is that a type should be controlled by its trace in each of the residue field and value group.
In this talk, I will first talk about the algebraic structure of valued fields, and draw some pictures to provide some intuition for those who do not work with them all the time. Then I will explore some ways in which the intuition that stems from the AKE theorem can be made precise, and also some limitations to that preliminary intuition. I will try to give lots of examples to keep the discussion concrete. | ||||
Wednesday Oct 11 2023 | ||||
16:00-16:50 (MS 6221) | Jan Grebik (UCLA) | Complexity of Borel colorings | ||
Abstract. The fact that a finite graph admits a proper k-coloring of vertices, i.e., its chromatic number is at most k, does not necessarily mean that there is an efficient way to produce such a k-coloring -- this phenomenon has been intensively studied in various areas of mathematics and theoretical computer science. In recent years, Bernshteyn discovered formal connections between the existence of definable coloring of Borel graphs and the existence of an efficient algorithm in the so-called LOCAL model of distributed computing that produces such a coloring. Unlike in the finite setting, this result suggests that in the setting of descriptive graph combinatorics (an area of descriptive set theory that sits at the intersection of set theory, dynamics, and combinatorics, and studies definable analogues of graph properties on definable graphs) Borel chromatic number at most k is equivalent with the existence of efficient algorithm that produces a k-coloring. In this talk I will discuss a related question; how complex is the class of Borel graphs of Borel chromatic number at most k? In particular, is it possible to decide whether a given Borel graph of degree bounded by k satisfies the Borel analogue of Brook's theorem?
This is a joint work with Brandt, Chang, Grunau, Rozhon and Vidnyánszky. Zoom recording available here: https://ucla.zoom.us/rec/share/OAygOAntAAtDXFmtN03kOW7mdUnP9bt2v7T2F2acwZJrcWpDDcXwS_XlffILPRd1.wMAtWTRtMJYE-LjL | ||||
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. |
Click here to see the announcements for older Logic Colloquia.