Logic Archives for Fall 2022 to Spring 2023
Organizational Meeting
When: Tue, August 31, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Organizational Meeting () -
A gentle introduction to continuous logic
When: Tue, September 7, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: James Hanson (University of Maryland, College Park) -
Abstract: I will give an overview of the basics of continuous first-order logic, emphasizing similarities and differences with discrete first-order logic. I will then discuss some current research directions.
Definable sets in continuous logic
When: Tue, September 14, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: James Hanson (University of Maryland, College Park) -
Abstract: I will introduce the concept of definable sets in continuous logic, presenting visual examples of their sometimes strange behavior. I will then develop a tameness condition under which they are more manageable. This will lead into some open questions.
Products of Classes of Structures
When: Tue, September 21, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Vincent Guingona (Towson University) - https://tigerweb.towson.edu/vguingona/
Abstract: We examine three products on classes of structures, the semi-direct product, the direct product, and the free superposition. We investigate what properties of classes of structures, such as indivisibility and age indivisibility, are preserved under each product. This work is joint with Miriam Parnes and Lynn Scow.
Countable Model Theory
When: Tue, September 28, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Douglas Ulrich (University of Maryland, College Park) -
Abstract: We give a brief survey of the field of countable model theory, and then sketch some projects joint with Chris Laskowski.
Amenability, optimal transport and structural Ramsey theory
When: Tue, October 5, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Christian Rosendal (University of Maryland, College Park) -
Abstract: We will present a new coherent framework based on the theory of transportation cost (Arens Eells) spaces for showing some new and old results connecting amenability of groups, topological dynamics and Ramsey theory of classes of finite structures.
This is part of a collaboration with Todor Tsankov.
Query learning, random counterexamples, and model theory
When: Tue, October 12, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Hunter Chase (University of Maryland, College Park) -
Abstract: We describe a connection between stable formulas and query learning and discuss the role of random counterexamples.
Are 5 queries to HALT better than 4?
When: Tue, October 19, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: William Gasarch (University of Maryland, College Park) -
Abstract: HALT is undecidable.
But what if you could make 5 queries to HALT?
Then what could you compute?
Could you computer more than if you could only make 4?
What about other undecidable sets?
Come and find out!
Classifying theories via monadic expansions
When: Tue, October 26, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Chris Laskowski (University of Maryland, College Park) -
Abstract: We define and discuss cellular, mutually algebraic, monadically NIP and monadically stable theories and see how they interrelate in terms of (worst case) expansions by unary predicates. Many results will be stated, but also a few open problems will be presented. Much of the newer work is joint with Sam Braunfeld.
Fractal Dimensions and Definability from Büchi Automata
When: Tue, November 2, 2021 - 3:30pmWhere: https://umd.zoom.us/j/2930577404?pwd=SStKSDYvanRSWURaUEdrQ1VKR2cwZz09
Speaker: Alexi Block Gorman (The Fields Institute for Research in Mathematical Sciences) -
Abstract: Büchi automata are the natural extension of finite automata, also called finite-state machines, to a model of computation that accepts infinite-length inputs. We say a subset X of the reals is r-regular if there is a Büchi automaton that accepts (one of) the base-r representations of every element of X, and rejects the base-r representations of each element in its complement. We can analogously define r-regular subsets of higher arities, and these sets often exhibit fractal-like behavior--e.g., the Cantor set is 3-regular. There are compelling connections between fractal geometry, r-regular subsets of the reals, and the directed graph structure of the automata that witness regularity. For an r-regular subset of the unit box in n-dimensional Euclidean space, we will describe how to obtain Hausdorff dimension, Box counting dimension, and Hausdorff measure (for the appropriate dimension) in terms of a certain variation of induced sub-automata. We will also see how this gives us a characterization for when reducts of a relevant first-order structure, one expanding the reals as an ordered additive group, have definable unary sets whose Hausdorff dimension and Boxing counting dimension disagree. This is joint work with Christian Schulz.
Computable reducibility of equivalence relations
When: Tue, November 9, 2021 - 3:30pmWhere: Hybrid online/Kirwan 1311, email jhanson9@umd.edu for the passcode, https://umd.zoom.us/j/2930577404?pwd=SStKSDYvanRSWURaUEdrQ1VKR2cwZz09
Speaker: Uri Andrews (University of Wisconsin, Madison) -
Abstract: I’ll survey some of what we know about the emerging topic of computable reducibility of equivalence relations. We say that an equivalence relation E “computably reduces” to an equivalence relation R if there is a computable function f so that xEy iff f(x)Rf(y). I’ll try to touch on both the local structure of computably enumerable equivalence relations and the global structure of all equivalence relations and some comparisons between the two.
Convoluted Dynamics
When: Tue, November 16, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Kyle Gannon (University of California, Los Angeles) -
Abstract: This talk is about NIP groups and the dynamical systems associated with the definable convolution operation. If T is an NIP theory expanding a group, \mathcal{G} is a monster model of T and G \prec \mathcal{G}, then the space of G-automorphism invariant measures and the space of global measures which are finitely satisfiable in G form left-continuous compact Hausdorff semigroups. From this observation, both semigroups can be studied through the lens of Ellis theory and one can ask what the minimal left ideals and ideal subgroups of these objects are. While the ideal subgroups are always trivial, the minimal left ideals remain more complicated. Under some assumptions, we can construct a minimal left ideal (in the space of measure) from a minimal left ideal and an ideal subgroup of the corresponding semigroup of types. This is joint work with Artem Chernikov.
Some questions around linear orders
When: Tue, November 23, 2021 - 3:30pmWhere: Hybrid online/Kirwan 1311, email jhanson9@umd.edu for the passcode, https://umd.zoom.us/j/2930577404?pwd=SStKSDYvanRSWURaUEdrQ1VKR2cwZz09
Speaker: Noah Schweber (Proof School) -
Abstract: I'll present a few results around the general problem of understanding "uniform" constructions of linear orders. It turns out that the same flavor of question - "when are there guaranteed to be 'incomparable' levels of complexity, and where can they arise?" - leads to interesting problems in quite different topics; we'll see some local computable structure theory, some forcing and large countable ordinals, and some thoughts on counterexamples to Vaught's conjecture (and potential "near-misses" to same). This talk will not assume any computability theory background.
Model Theory of Sparse Graphs
When: Tue, November 30, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Miriam Parnes (Towson University) -
Abstract: We examine for what values of r the class of all hereditarily r-sparse graphs satisfies certain properties such as the amalgamation property and age indivisibility.
This work is joint with Vince Guingona.
Infinitary logic, Polish groupoids, and classification of structures
When: Tue, December 7, 2021 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Ruiyuan Chen (The Centre de recherches mathématiques and McGill University in Montreal) -
Abstract: I will give a survey of connections between infinitary (discrete and continuous) logic, topological dynamics of Polish groups, and descriptive complexity theory of Borel equivalence relations and groupoids. In particular, I will present some work from 2019 showing that countable L_{\omega_1\omega}-theories are "equivalent", in a precise sense, to their Borel groupoids of models, and discuss ongoing work on generalizing this to continuous logic.
Bounded Ultraimaginary Independence
When: Tue, February 1, 2022 - 3:30pmWhere: Kirwan Hall 1311
Speaker: James Hanson (University of Maryland, College Park) -
Abstract: In the context of model theory, ultraimaginaries are an immediate generalization of hyperimaginaries which are defined in terms of equivalence classes of arbitrary invariant equivalence relations rather than type-definable equivalence relations. There is a natural model-theoretic independence notion that arises from the consideration of ultraimaginaries (analogous to the notion of algebraic independence as studied by Adler and others). We will develop various properties of this independence notion and its corresponding 'generic' sequences, which are shown to be equivalent to a class of sequences originally considered by Shelah. A large cardinal will show up.
Complexity of countable R-modules
When: Tue, February 8, 2022 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Douglas Ulrich (University of Maryland, College Park) -
Abstract: Given a countable ring R, one can investigate the (Borel) complexity of countable (left) R-modules. The special case of R = Z (i.e. abelian groups) was, until recently, a longstanding open problem. Paolini and Shelah recently announced a proof that Z-modules are maximally complex. In this talk, we sketch an alternate and arguably simpler proof, which extends to characterize which commutative rings R have maximally complicated countable R-modules. Joint work with Chris Laskowski.
Amenability, optimal transport and complementation in Banach modules
When: Tue, February 15, 2022 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Christian Rosendal (University of Maryland, College Park) -
Abstract: Using tools from the theory of transportation cost (aka. Arens– Eells) spaces, three theorems concerning isometric actions of general amenable topological groups on metric spaces with potentially unbounded orbits are established. Specifically, let G be an amenable topological group with no non-trivial homomorphisms to R. Then, when G acts isometrically on a metric space X, the space of Lipschitz functions on the quotient X/G is isometrically isomorphic to a 1-complemented subspace of the Lipschitz functions on X. Similarly, one finds Følner sets with respect to any continuous left-invariant ecart on G and finally every continuous affine isometric action of G on a Banach space has a canonical invariant linear subspace. This generalises previous results of Schneider–Thom and Cuth–Doucha.
Logical limit laws for layered permutations and related structures
When: Tue, February 22, 2022 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Matthew Kukla (University of Maryland, College Park) -
Abstract: We show that several classes of ordered structures (namely, convex linear orders, layered permutations, and compositions) admit first-order logical limit laws.
Quantifier complexity of monadic expansions
When: Tue, March 1, 2022 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Chris Laskowski (University of Maryland, College Park) -
No-clash teaching of some infinite classes
When: Tue, March 8, 2022 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Hunter Chase (University of Maryland, College Park) -
Abstract: No-clash teaching dimension is a generalization of recursive teaching dimension. It has been primarily studied in the context of finite concept classes, where combinatorial properties such as VC dimension are used to establish bounds on the size of a no-clash teaching function. We study several examples to explore how no-clash teaching dimension behaves for infinite concept classes.
Using Ramsey Theory to Solve a Problem in Logic
When: Tue, March 15, 2022 - 3:30pmWhere: CSI 2107
Speaker: William Gasarch (University of Maryland, College Park) -
Abstract: Let phi be a sentence in the language of graphs.
For which n is there a graph on n vertices where phi is true?
We discuss a case where this is decidable.
The proof will use Ramsey's theorem (which we will explain).
Exploring Differential Privacy
When: Tue, March 29, 2022 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Vincent Guingona (Towson University) -
Abstract: We examine differential privacy both in the abstract and in the context of learning algorithms. In the abstract, we detail some results around comparing different notions of differential privacy. With regards to learning, we survey some known results about the link between the existence of an accurate and private algorithm to (model theoretic) stability. Finally, we discuss some current work and future directions towards better understanding this connection. This work is joint with Alexei Kolesnikov and two Towson undergraduates, Julie Nierwinski and Avery Schweitzer.
Preservation of tameness when naming a structure
When: Tue, April 5, 2022 - 3:30pmWhere: Online. Contact jhanson9@umd.edu for Zoom link and password.
Speaker: Gabriel Conant (Ohio State University) -
Abstract: A pervasive question in model theory is when desirable properties of some structure are preserved when expanding that structure by new definable sets. For example, over the last several years there has been an extensive study focused on preserving stability in expansions of the group of integers. An interesting phenomenon in this work is that all previously discovered examples of stable expansions of the group of integers are, in fact, superstable of U-rank omega. Thus it has remained an open problem to exhibit a strictly stable expansion of the group of integers. In this talk, I will present a solution to this problem, which is obtained in a much broader framework. Specifically, we will investigate preservation of model-theoretic tameness (e.g., stability, simplicity, NIP, NTP2, NSOP1) when expanding the induced structure on a definable stably embedded set by some arbitrary new structure. Joint work with C. d’Elbée, Y. Halevi, L. Jimenez, and S. Rideau-Kikuchi.
o-minimal method and generalized sum-product phenomena
When: Tue, April 12, 2022 - 3:30pmWhere: Online. Contact jhanson9@umd.edu for Zoom link and password.
Speaker: Chieu-Minh Tran (University of Notre Dame) -
Abstract: I will discuss a joint work with Yifan Jing and Souktik Roy where we show that for a bivariate $P(x,y) \in \mathbb{R}[x,y]\setminus (\mathbb{R}[x] \cup \mathbb{R}[y])$ to exhibit small expansion on a large finite set $A\subseteq \mathbb{R}$, we must have$$ P(x,y)=f(\gamma u(x)+\delta u(y))\quad \text{or} \quad P(x,y)=f(u^m(x)u^n(y)) $$
for some univariate $f, u \in \mathbb{R}[t]\setminus \mathbb{R}$, constants $\gamma, \delta \in \mathbb{R}^{\neq 0}$, and $m, n\in \mathbb{R}^{\geq 1}$. This yields an Elekes-Ronyai type structural result for symmetric nonexpanders, resolving a question mentioned by de Zeeuw.
Our result uses o-minimal/semialgebro geometric techniques to replace algebro geometric techniques, which are only applicable to earlier known special cases.
If time permits, I will also discuss a recent joint work with Benjamin Castle where we apply the above result to determine when certain reducts of $(\mathbb{C};+, \times)$ are locally modular.
Existentially closed measure-preserving actions of universally free groups
When: Tue, April 19, 2022 - 3:30pmWhere: Online. Contact jhanson9@umd.edu for Zoom link and password.
Speaker: Isaac Goldbring (University of California, Irvine) -
Abstract: In this talk, we discuss existentially closed measure preserving actions of countable groups. A classical result of Berenstein and Henson shows that the model companion for this class exists for the group of integers and their analysis readily extends to cover all amenable groups. Outside of the class of amenable groups, relatively little was known until recently, when Berenstein, Henson, and Ibarlucía proved the existence of the model companion for the case of finitely generated free groups. Their proof relies on techniques from stability theory and is particular to the case of free groups. In this talk, we will discuss the existence of model companions for measure preserving actions for the much larger class of universally free groups (also known as fully residually free groups), that is, groups which model the universal theory of the free group. We also give concrete axioms for the subclass of elementarily free groups, that is, those groups with the same first-order theory as the free group. Our techniques are ergodic-theoretic and rely on the notion of a definable cocycle. This talk represents ongoing work with Brandon Seward and Robin Tucker-Drob.
Closed groups generated by generic measure preserving transformations
When: Tue, April 26, 2022 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Slawomir Solecki (Cornell University) -
Abstract: The behavior of a measure preserving transformation, even a generic one, is highly non-uniform. In contrast to this observation, a different picture of a very uniform behavior of the closed group generated by a generic measure preserving transformation has emerged. This picture included substantial evidence that pointed to these groups being all topologically isomorphic to a single group, namely, $L^0$---the non-locally compact, topological group of all Lebesgue measurable functions from $[0,1]$ to the circle. In fact, Glasner and Weiss asked if this was the case.
We will describe the background touched on above, including the relevant definitions. Further, we will indicate a proof of the following theorem that answers the Glasner--Weiss question in the negative: for a generic measure preserving transformation $T$, the closed group generated by $T$ is {\bf not} topologically isomorphic to $L^0$. The proof rests on an analysis of unitary representations of $L^0$.
A new tree property
When: Tue, May 10, 2022 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Alex Kruckman (Wesleyan University) -
Abstract: One of the most important technical steps in the development of simplicity theory in the 1990s was a result now known as Kim's Lemma: In a simple theory, if a formula phi(x;b) divides over a model M, then it divides along every Morley sequence in tp(b/M). More recently, variants of Kim's Lemma have been shown by Chernikov, Kaplan, and Ramsey to follow from, and in fact characterize, two generalizations of simplicity in different directions: the combinatorial dividing lines NTP_2 and NSOP_1. After surveying the Kim's Lemmas of the past, I will suggest a new variant of Kim's Lemma, and a corresponding new model-theoretic tree property, which generalizes both TP_2 and SOP_1. I will also compare this new tree property with the Antichain Tree Property (ATP), another tree property generalizing both TP_2 and SOP_1, which was introduced recently by Ahn and Kim. This is joint work with Nick Ramsey.