Logic Archives for Academic Year 2018


Organizational Meeting

When: Tue, August 29, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Organizational Meeting () -


Borel complexity and the Schroder-Bernstein property

When: Tue, September 5, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Douglas Ulrich (UMD) -
Abstract: We show that if a first order theory T has the Schroder-Bernstein property then it is not Borel complete, assuming some mild large cardinals.

Countable models of Baldwin-Shi hypergraphs

When: Tue, September 12, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Danul Gunatilleka (University of Maryland, College Park) -
Abstract: We isolate a special case of the ab initio constructions that we propose to call Baldwin-Shi hypergraphs. The theories in question are known to be either strictly stable or omega-stable and are known to have the dimensional order property. It is also known that the in case the theory is strictly stable it is not small. So we count the number of non-ismorphic countable models in the case the theory is omega-stable. We will also take a look at the regular types that arise in this case.

Finite-rank ordered Abelian groups

When: Tue, September 19, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: John Goodrick (Los Andes University) - https://matematicas.uniandes.edu.co/~goodrick/
Abstract: Recently there have been several advances in the study of ordered Abelian groups (OAGs) whose theories have finite dp-rank. Recall that every complete theory of OAGs has NIP (Gurevich), so it it is interesting to ask which ones are *strongly* dependent in the pure language {+,

Coarse embeddings into superstable spaces

When: Tue, September 26, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Bruno de Mendonça Braga (York University) - https://sites.google.com/site/demendoncabraga/home
Abstract: In 1981, J. Krivine and B. Maurey introduced the definition of stable Banach spaces, and, in 1983, Y. Raynaud introduced the notion of superstability and studied uniform embeddings of Banach spaces into superstable Banach spaces. In this talk, we will talk about coarse embeddings into superstable spaces. This is a joint work with Andrew Swift.

A stable arithmetic regularity lemma in finite-dimensional vector spaces over fields of prime order

When: Tue, October 10, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Caroline Terry (University of Maryland, College Park) -
Abstract: In this talk we present a stable version of the arithmetic regularity lemma for vector spaces over fields of prime order. The arithmetic regularity lemma for $\mathbb{F}_p^n$ (first proved by Green in 2005) states that given $A\subseteq \F_p^n$, there exists $H\leq \F_p^n$ of bounded index such that $A$ is Fourier-uniform with respect to almost all cosets of $H$. In general, the growth of the index of $H$ is required to be of tower type depending on the degree of uniformity, and must also allow for a small number of non-uniform elements. Our main result is that, under a natural stability theoretic assumption, the bad bounds and non-uniform elements are not necessary. Specifically, we present an arithmetic regularity lemma for $k$-stable sets $A\subseteq \mathbb{F}_p^n$, where the bound on the index of the subspace is only polynomial in the degree of uniformity, and where there are no non-uniform elements. This result is a natural extension to the arithmetic setting of the work on stable graph regularity lemmas initiated by Malliaris and Shelah. This is joint work with Julia Wolf.

On stable expansions of the integers by multiplicative semigroups

When: Tue, October 17, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Gabriel Conant (Notre Dame) - https://www3.nd.edu/~gconant/
Abstract: We prove that if G is a finitely generated multiplicative semigroup of positive integers, and A is any infinite subset of G, then the expansion (Z,+,A) of (Z,+) by a unary predicate for A is superstable of U-rank omega. The key tool for this result is a theorem of Evertse, Schlickewei, and Schmidt on solutions to linear equations in finite rank multiplicative subgroups of algebraically closed fields. We use this theorem, along with general results of Casanovas and Ziegler, to show that stability of the expansion (Z,+,A) reduces to stability of the induced structure on A, and then to show that this induced structure is monadically stable of U-rank 1.

Twists and Twistability

When: Tue, October 24, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Rebecca Coulson (Rutgers University) - http://sites.math.rutgers.edu/~rlg131/
Abstract: We introduce the concept of a twist, which is an isomorphism up to a permutation of the structure's language. We developed this concept in the course of proving results about metrically homogeneous graphs. This concept proved useful for partial classification results as well as finiteness results. The concept of a twist surprisingly is present in other work by Cameron and Tarzi, as well as by Bannai and Ito. We will discuss our results and their connections to other work.

NIP theories and machine learning

When: Tue, November 7, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Vincent Guingoa (Towson University ) - https://tigerweb.towson.edu/vguingona/
Abstract: We discuss the basics of machine learning theory, including concept classes, VC-dimension, VC-density, PAC-learning, and sequence compressions. We then explore the relationship between these concepts and model theory.

Relativized Lascar groups.

When: Tue, November 14, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Alexei Kolesnikov (Towson University) - https://tigerweb.towson.edu/akolesni/
Abstract: Lascar group is a topological group defined for a first order theory. It is known that any compact group is a Lascar group for a suitable theory. In this talk, I will describe a Lascar group defined for a type in a theory and its connection to the first model-theoretic homology group.

Distal and non-distal ordered abelian groups.

When: Tue, November 21, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Allen Gehret (UCLA) -
Abstract: I will discuss various things we know about distal and non-distal ordered abelian groups. This is joint work with Matthias Aschenbrenner and Artem Chernikov.

Strong conceptual completeness for ω-categorical theories

When: Tue, November 28, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Jesse Han (McMaster University) -
Abstract: Suppose we have some process to attach to every model of a first-order theory some (permutation) representation of its automorphism group, compatible with elementary embeddings. How can we tell if this is "definable", i.e. really just the points in all models of some imaginary sort of our theory?

In the '80s, Michael Makkai provided the following answer to this question: a functor Mod(T) → Set is definable if and only if it preserves all ultraproducts and all "formal comparison maps" between them (generalizing e.g. the diagonal embedding into an ultrapower). This is known as strong conceptual completeness; formally, the statement is that the category Def(T) of definable sets can be reconstructed up to bi-interpretability as the category of "ultrafunctors" Mod(T) → Set.

Now, any general framework which reconstructs theories from their categories of models should be considerably simplified for ω-categorical theories. Indeed, we show:

If T is ω-categorical, then X : Mod(T) → Set is definable, i.e. isomorphic to (M \mapsto ψ(M)) for some formula ψ ∈ T, if and only if X preserves ultraproducts and diagonal embeddings into ultrapowers. This means that all the preservation requirements for ultramorphisms, which a priori get unboundedly complicated, collapse to just diagonal embeddings when T is ω-categorical.

This definability criterion fails if we remove the ω-categoricity assumption. We construct examples of theories and non-definable functors Mod(T) → Set which exhibit this.

The undecidability of the joint embedding property for hereditary graph classes, and related problems

When: Tue, December 5, 2017 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Samuel Braunfeld (Rutgers University) - http://sites.math.rutgers.edu/~swb52/
Abstract: We will sketch a proof of the undecidability of joint embedding for hereditary graph classes. Time permitting, we will discuss the analogous problem for other classes of structures, such as permutations.

Borel complexity of weakly minimal theories

When: Fri, February 2, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Douglas Ulrich (University of Maryland) -
Abstract: We discuss some very partial progress towards classifying weakly minimal theories up to Borel complexity, and give several examples.

Title: Borel complexity of weakly minimal theories

When: Tue, February 6, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Douglas Ulrich (University of Maryland) -
Abstract: We discuss some very partial progress towards classifying weakly minimal theories up to Borel complexity, and give several examples.

Configurations and Ranks

When: Tue, February 13, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Vince Guingona (Towson University) -
Abstract: For an algebraically trivial Fraisse class K, we define K-configurations and K-rank and study their properties. The notion of K-rank generalizes the notion of dp-rank in distal theories.

Model Theory Reading Seminar

When: Tue, February 20, 2018 - 2:00pm
Where: Kirwan Hall 1311
Speaker: Vince Guingona (Towson University) -
Abstract: We continue our reading of ``Regularity lemmas for distal structures."

Independence in generic expansions and fusions

When: Tue, February 20, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Alex Kruckman (Indiana University) -
Abstract: The word "generic" is often applied to a theory T* when it arises as a model companion of a base theory T. Generic theories exhibit lots of "random" behavior, so they are rarely stable or NIP, but they can sometimes be shown to be simple by characterizing a well-behaved notion of independence in T* (namely non-forking independence) in terms of independence in T. Recently, there has been increased interest in the property NSOP1, a generalization of simplicity, spurred by the work of Chernikov, Kaplan, and Ramsey, who showed that NSOP1 theories can also be characterized by the existence of a well-behaved notion of independence (namely Kim independence). In this talk, I will present a number of preservation results for simplicity and NSOP1 under generic constructions. In joint work with Nicholas Ramsey, generic expansion and generic Skolemization: add new symbols to the language, interpreted arbitrarily or as Skolem functions, and take the model companion. And in very recent results towards a joint project with Minh Chieu Tran and Erik Walsberg, interpolative fusion: given an L_1-theory T_1 and and L_2-theory T_2, which intersect in an L_0-theory T_0, take the model companion of the union of T_1 and T_2.

TBA

When: Tue, February 27, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Gabriel Conant (University of Notre Dame) -


Hereditary properties and mutual algebricity

When: Tue, April 3, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Caroline Terry (University of Maryland) -
Abstract: A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property $\mathcal{H}$, the \emph{speed} of $\mathcal{H}$ is the function which sends $n$ to the number of distinct elements in $\mathcal{H}$ with underlying set $\{1,\ldots, n\}$. Not just any function can occur as the speed of hereditary graph property. Specifically, there are discrete ``jumps" in the possible speeds. Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollob\'{a}s, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized. In contrast to this, many aspects of this problem in the hypergraph setting have remained unknown. In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds. The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. This is joint work with Chris Laskowski.

The bi-embeddability relation for countable abelian groups

When: Tue, April 10, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Filippo Calderoni (University of Turin) -
Abstract: In this talk we will analyze the complexity of the bi-embeddability relation on different spaces of countable abelian groups. First, we will use the Ulm theory to prove that the bi-embeddability relation on p-groups is incomparable with isomorphism up to Borel reducibility. Then, we will mention how we obtain the analogous result for the bi-embeddability and isomorphism relations between torsion groups. If time permits we will discuss some related results in the framework of $\Delta^1_2$-reducibility, and list some open questions. This is joint work with Simon Thomas.

Binary sequences and trees in model theory

When: Tue, April 17, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Hunter Chase (University of Illinois Chicago) -
Abstract: VC-dimension and Shelah's 2-rank (also known as Littlestone or thicket dimension) are important measures of complexity associated with the NIP/IP and stable/unstable dividing lines. We examine these through the lens of binary trees and sequences. We introduce the concept of banned sequence problems as a tool to obtain new proofs of the Sauer-Shelah lemma and some of its variants. We use these results to modestly improve a result of Malliaris and Terry on type trees of stable graphs and prove a new variant of the Sauer-Shelah lemma for the op-rank setting of Guingona and Hill.

This work is joint with James Freitag.

Generalizing Tree Decomposition

When: Tue, April 24, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Miriam Parnes (Wesleyan University) -
Abstract: Questions which are hard to answer about a graph often become easy if we know a bound for the graph's tree width. The tree width of a graph, which tells us how tree-like the graph is, comes from its tree decompositions. In this talk, we will explore extensions of the concepts of tree decomposition and tree width to the more general setting of algebraically trivial Fraïssé classes on which a particular kind of independence relation is defined.

NIP arithmetic regularity, part 2

When: Tue, May 1, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Gabriel Conant (University of Notre Dame) -
Abstract: Picking up from my seminar talk on 2/27, we present some results for NIP sets in finite groups. We then discuss applications involving pseudofinite groups definable in distal theories. (No recollection of part 1 will be necessary).

Model Theory Reading Seminar

When: Tue, May 8, 2018 - 2:00pm
Where: Kirwan Hall 1311
Speaker: Caroline Terry (University of Maryland) -


What do models of classifiable theories look like?

When: Tue, May 8, 2018 - 3:30pm
Where: Kirwan Hall 1311
Speaker: Chris Laskowski (University of Maryland) -