Mathematics & Computer Science

Seminars and Colloquia

Logic Seminar

Monday, September 15, 2014

04:45 pm - 06:00 pm

CT Logic Seminar, Philip Scowcroft (Wes): "Continuous Model Theory for C(X)"

Abstract: In the continuous logic recently developed by Ben Yaacov and others, the class of lattice-ordered groups isomorphic to C(X) with X compact is an elementary class. The theory T of this class has convenient model-theoretic properties: for example, T has a model-completion T(+) which is countably categorical and admits elimination of quantifiers. One may establish also a corresponding Nullstellensatz and determine which models of T have prime-model extensions to models of T(+).

ESC 638

Monday, September 08, 2014

04:45 pm - 06:00 pm

CT Logic Seminar, Reed Solomon (UConn): Reverse mathematics and the Dual Ramsey Theorem

Abstract: This talk will be an introduction to the Dual Ramsey Theorem and to the (relatively few) results in reverse mathematics known about it.

ESC 638

Monday, January 20, 2014

04:45 pm - 06:00 pm

Logic Seminar, Neil Immerman (UMass): "Descriptive and Dynamic Complexity"

Abstract: An increasing percentage of modern computation is dynamic: a fairly large object is being worked on over a period of time. The object is repeatedly modified and computations are performed. Using auxiliary data structures we can sometimes maintain the ability to very quickly answer certain queries about the object as it changes. dynFO is the set of properties that can be maintained and queried in First-Order logic. Much progress has been made understanding when graph reachability is in dynFO and related classes, but the general question remains open.

ESC 638

Monday, November 25, 2013

04:45 pm - 06:00 pm

Logic Seminar, Philip Scowcroft (Wesleyan): " Existentially closed prime-model extensions of Abelian lattice-ordered groups."

Abstract: Existentially closed (ec) Abelian lattice-ordered groups are to Abelian lattice-ordered (l-) groups as algebraically closed fields are to fields. An ec prime-model extension of the Abelian l-group G is an ec Abelian l-group that extends G and embeds over G into any ec Abelian l-group extending G. So the Abelian l-group G is to an ec prime-model extension of G as a field F is to its algebraic closure. This talk will consider the extent to which Abelian l-groups have ec prime-model extensions.

ESC 638

Monday, October 21, 2013

04:45 pm - 05:45 pm

Logic Seminar, Lynn Scow (Vassar): "Ramsey transfer theorems"

Abstract: We survey some of the known approaches to transfer a Ramsey theorem for one class of finite structures to another. We will isolate some easy consequences and point to further directions.

ESC 638

Monday, October 14, 2013

04:45 pm - 05:45 pm

LogicSeminar, Henry Towsner (Univeristy of Pennsylvania): "Models of Reverse Mathematics"

Abstract: Most recent work in reverse mathematics has focused on the consequences of Pi12 sentences. One family of questions asks, given a Pi12 sentence, what its first-order consequences are---what the Pi12 sentence implies about the underlying first-order model of arithmetic. Turning this around, once we have a theory of reverse mathematics, we can ask about the collection of all Pi12 sentences which are conservative over it for first-order consequences.<br/><br/>When our theory T is the theory ACA0 (or, in fact, any computably axiomatized theory containing ACA0), the collection of such sentences is as complicated as possible (their Godel numbers form a Pi02 complete set). Over weaker theories, however, the method of proof fails. We show that for the most important class of weaker theories, those of the form RCA0 plus Sigma_n induction for some n, the same result holds. Our method is completely different than the proof for ACA0, and has the side benefit of sharply constraining what the theories RCA0+ISigma_n can prove about formulas more complicated than ISigma_n.<br/>

ESC 638

Monday, October 07, 2013

04:45 pm - 06:00 pm

Logic Seminar, Russell Miller (Queens College, CUNY): "Fields and Computable Categoricity"

Abstract: We give an overview of the current understanding of computable categoricity for fields. A computable field F is computably categorical if, for every computable field E which is isomorphic to F (via any isomorphism), there exists a computable isomorphism from E onto F. Characterizations of computable categoricity are known for various other classes of computable structures, and for certain subclasses of computable fields, but have proven elusive for fields. We give an analysis of the reasons why, considering both the complexity of the definition of computable categoricity and the amount of information needed to compute field isomorphisms when they exist.

ESC 638

Monday, September 16, 2013

04:45 pm - 06:00 pm

Logic Seminar, Damir Dzhafarov (UCONN): Limits to joining with generics and randoms

Abstract: It is a fundamental theorem of computability theory that the Turing jump of a set A always has strictly greater Turing degree than A itself, i.e., deg(A) < deg(A'). Posner and Robinson showed that this need not hold when we add joins with non-computable sets: if S is non-computable, there exists a set G such that S join G computes G'. Shore and Slaman extended this result to all n, by showing that if S is not computable in 0^(n-1) then there exists a G such that S join G computes G^n. Both arguments are forcing arguments, but with very different underlying forcing notions. Posner and Robinson use Cohen forcing, and the set G in their result can consequently be chosen to be (Cohen) 1-generic. By contrast, Shore and Slaman use a more intricate forcing notion, due to Kumabe and Slaman, and it is natural to ask whether this is a necessary complication. I will talk about work with Adam Day in which we answer this question, in the following sense: for all n, the set G of the Shore-Slaman theorem cannot be chosen to be even weakly 2-generic, and so certainly not n-generic if n > 1. Our result applies generally to many other forcing notions commonly used in computability theory. I will also mention a variant of our result, showing that the set G cannot be chosen to be 2-random.

ESC 638

Monday, September 09, 2013

04:45 pm - 06:00 pm

Logic Seminar, Reed Solomon (UCONN): Separating ADS and CAC

Abstract: We examine the relationship between ADS and CAC in reverse mathematics. ADS says that every infinite linear order has either an infinite ascending chain or an infinite descending chain. CAC says that every infinite partial order has either an infinite chain or an infinite antichain. It is known that CAC implies ADS. In this talk, we show that ADS does not imply CAC over RCA_0. This work is joint with Manny Lerman and Henry Towsner. <br/>

ESC 638

Monday, December 03, 2012

04:45 pm - 06:00 pm

Logic Seminar, Brett Townsend - Wesleyan: "The Structure of Ordered Abelian Groups with Finite Prime Invariants"

Abstract: A dense regular group is a densely ordered group elementarily equivalent to a subgroup of R. In this talk I will discuss the structure of definable sets in such groups with arbitrary finite prime invariants. In particular, I will present a cell-decomposition theorem similar to that which is known for o-minimal structures, and describe how one may then derive a coherent dimension theory for such groups.

ESC 638

Monday, November 26, 2012

04:45 pm - 06:00 pm

Logic Seminar, Koushik Pal - University of Maryland: "Unstable Theories with an Automorphism"

Abstract: Kikyo and Shelah showed that if T is a first-order theory in some language L with the strict-order property, then the theory T_\sigma, which is the old theory T together with an L-automorphism \sigma, does not have a model companion in L_\sigma, which is the old language L together with a new unary predicate symbol \sigma. However, it turns out that if we add more restrictions on the automorphism, then T_\sigma can have a model companion in L_\sigma. I will show some examples of this phenomenon in two different context - the linear orders and the ordered abelian groups. In the context of the linear orders, we even have a complete characterization of all model complete theories extending T_\sigma in L_\sigma. This is joint work with Chris Laskowski.

ESC 638

Monday, November 12, 2012

04:45 pm - 06:00 pm

Logic Seminar, Jean-Martin Albert - Marlboro College: "Continuous Logical Categories"

Abstract: In this talk I will introduce Continuous Logical Categories. These are an analogue of the notion of Logical Category introduced by Makkai and Reyes in the context of First-Order Continuous Logic. We will also establish a correspondence between theories in First-Order Continuous Logic and Continuous Logical Categories.

ESC 638

Monday, November 05, 2012

04:45 pm - 06:00 pm

Logic Seminar, Paul Baginski - Smith: "Stability and Countable Categoricity in Nonassociative Rings"

Abstract: A classic result due to Felgner and to Baur, Cherlin and Macintyre in the 1970s states that a stable, $\aleph_0$-categorical group is nilpotent by finite. At around the same time, Baldwin and Rose proved that a stable, $\aleph_0$-categorical associative ring is nilpotent by finite. Recently, Wagner, Krupinski and others have renewed interest in these two results by proving analogous statements where stability is replaced by other model theoretic properties. In all cases, the rings being considered are associative. However, Rose extended many of his results with Baldwin in a second paper to a class of nonassociative rings called alternative rings. However, the question of whether a stable, $\aleph_0$-categorical alternative ring was nilpotent by finite remained open. In this talk, I shall outline a proof of Baldwin and Rose's theorem using a modern perspective and then discuss the obstacles that occur when one tries to use the same methods for nonassociative rings. I will then present my current progress towards proving Baldwin and Rose's theorem for nonassociative rings.

ESC 638

Friday, October 19, 2012

04:45 pm - 06:00 pm

Logic Seminar, Maryanthe Malliaris, University of Chicago: "Saturation of Ultrapowers and the Structure of Unstable Theories

Abstract: The talk will be about some very recent progress on Keisler's order, a far-reaching program of understanding basic model-theoretic structure through the lens of regular ultrapowers. I will explain Keisler's order and the perspective it gives on classifying the unstable theories, and discuss a recent paper of Malliaris and Shelah which applies model-theoretic techniques developed for the study of Keisler's order to solve the oldest problem on cardinal invariants of the continuum.<br/><br/><br/>I will assume basic familiarity with ultraproducts, Los's theorem, and saturation, and plan to give most other relevant definitions. Papers mentioned in the talk are available at http://math.uchicago.edu/~mem.<br/><br/>NOTE UNUSUAL DAY OF THE WEEK FOR LOGIC SEMINAR<br/>

ESC 638

Monday, October 01, 2012

04:45 pm - 06:00 pm

Logic Seminar, Johanna Franklin UCONN: "Randomness and nonergodic transformations"

Abstract: Random points are typical in that they have no rare measure-theoretic properties, and points that satisfy ergodic theorems are typical in that their orbits under certain kinds of transformations have certain regularity properties. In the past few years, many connections between these types of typicality have been found. For instance, a point is Martin-Loef random if and only if it satisfies Birkhoff's ergodic theorem for all computable ergodic transformations with respect to effectively closed sets. The case in which the transformations are taken to be ergodic has largely been settled.<br/><br/>I will begin by defining the basic concepts in each area and explaining the connections known to exist between randomness and ergodic theorems. Then I will present some results that are joint with Henry Towsner that deal with the nonergodic case. We show, among other things, that if a point is not Martin-Loef random, then there is a computable, measure-preserving transformation and a computable set for which Birkhoff's ergodic theorem does not hold at that point. This gives us the converse of a theorem by V'yugin.<br/>

ESC 638

Monday, September 24, 2012

04:45 pm - 06:00 pm

Logic Seminar, Reed Solomon, UCONN: " Turing degrees of orderings of torsion free abelian groups"

Abstract: The space of orderings on a countable torsion free abelian group of rank greater 1 is homeomorphic to Cantor space. However, the connection between spaces of orderings on computable abelian groups and Pi^0_1 classes with no isolated paths is not well understood. I will present some recent joint work with Karen Lange and Asher Kach concerning this relationship.

ESC 638

Monday, September 17, 2012

04:45 pm - 06:00 pm

Logic Seminar, Russell Miller, Queens College (CUNY): "Constraint Sets in Differential Fields"

Abstract: Differential fields are fields endowed with one or more differential operators, in which one can express algebraic differential equations and ask whether they have solutions. With the help of model theory, differential algebraists have successfully generalized many of the standard concepts for fields to the setting of differential fields, including a notion of differential closure analogous to the algebraic closure of a field. In many cases, however, the concepts become more difficult to handle in the differential setting, and computability theory can sometimes make this contrast explicit.<br/><br/>In joint work, the speaker and Alexey Ovchinnikov have focused on the notion of a constrained pair of differential polynomials from a differential field K of characteristic 0. Roughly speaking, the pair (p,q) is \textit{constrained} if the formula $p(x) = 0 \neq q(x)$ generates a principal type (over the theory DCF_0 of differentially closed fields of characteristic 0, augmented by the atomic diagram of K), and the differential closure of K realizes exactly these principal types. For fields, such types are generated precisely by the irreducible polynomials, and so being a constrained pair is analogous to a single algebraic polynomial being irreducible. Therefore, it is important to be able to decide which pairs are constrained. For fields, Kronecker's Theorem allows one to decide irreducibility of polynomials over every finitely generated field of characteristic 0. We have extended parts of Kronecker's Theorem to the context of constrained pairs over a differential field, and this talk will explain how this was done and what remains to be done. No prior knowledge of differential algebra will be assumed; we will offer explanations of much of the foregoing description of the topic before arriving at the new results.<br/>

ESC 638

Monday, September 10, 2012

04:45 pm - 06:00 pm

Logic Seminar: Philip Scowcroft, Wesleyan, Existentially closed Abelian lattice-ordered groups

Abstract: The class A of e.c. Abelian l-groups, like the class D of e.c. dimension groups, is not elementary but has informative non-elementary axioms. A also is closed under operations, like finite product, which take one out of D, and I will discuss the inconclusive evidence that A is better behaved than D.

ESC 638

Monday, April 30, 2012

04:00 pm - 05:00 pm

CT Logic Seminar, Cameron Freer, MIT: Model-theoretic methods in continuum limits in Combinatorial structures

Abstract: How can one build a random symmetric structure? We will describe new model-theoretic techniques that build on the combinatorial theory of graph limits and the probability theory of exchangeable arrays. This <br/>talk complements the one given by Rehana Patel in the logic seminar last Fall. The Rado graph admits a natural probabilistic construction, by independently flipping a weight-p coin to determine each edge, for any fixed 0 < p < 1. This random graph is exchangeable, in the sense that the joint distribution on edges is invariant to permutations of the vertices.What other countable structures admit an exchangeable construction? The Aldous-Hoover theorem and the theory of graph limits show that any ergodic exchangeable graph can be written as a ``W-random graph'' for some measurable function W : [0,1]^2 -> [0,1], i.e., a random graph where vertices are drawn iid uniform from [0,1] and edges are determined by independent coin flips with weights given by W. <br/>However, for many graphs it is not clear whether such a W exists.In 2010, Petrov and Vershik gave an exchangeable construction of Henson's universal homogeneous triangle-free graph, making use of this characterization. Using techniques from model theory for infinitary logic, we extend their construction to provide a complete classification of countable relational structures admitting an exchangeable construction. We will also describe several connections to results about countable exchangeable structures and the <br/>corresponding continuum limit structures by Gaifman, Scott, Krauss, Hoover, and Razborov.<br/><br/>Joint work with Nate Ackerman and Rehana Patel<br/>

ESC 638

Monday, April 30, 2012

05:15 pm - 06:15 pm

Ct Logic Seminar, James Freitag, UIC: Intersection theory in differential algebraic geometry

Abstract: We will discuss recent developments in intersection theory for differential algebraic geometry. The main goal will be to sketch a proof of a differential version of Bertini's theorem. The result is a generalization of the classical theorem, but the proof takes a much different course due to various anomalies regarding intersections of differential algebraic varieties originally pointed out by Ritt. If time permits, several applications will also be given.

ESC 638

Monday, April 23, 2012

04:45 pm - 06:00 pm

CT Logic Seminar: Alf Dolich, Kinsborough C.C.: Very Dependent Ordered Structures

Abstract: For a theory to not have the independence property, as originally introduced by Shelah, may be viewed as a very weak criterion that the theory in question is tractable. Recently theories without the independence property, also referred to as dependent theories, have begun to be extensively studied and in the process several stronger forms of dependence have come to the fore which by being more stringent increase the potential for a theory to be <br/>tractable. In this talk I will consider theories of finite dp-rank, one such stronger form of dependence. In particular I will consider expansions of the theory of dense linear orderings of finite dp-rank, a class of theories which includes all o-minimal theories. To begin with I will discuss some topological properties of definable sets in such structures and provide several examples to illustrate the variety that exists in this apparently quite restrictive class. Secondly I will isolate a consequence for the topology of definable sets in theories of dp-rank 1 (the so-called dp-minimal theories) and then investigate theories with this property.<br/>

ESC 638

Monday, February 20, 2012

04:00 pm - 05:00 pm

(CT Logic Seminar) David Marker, University of Illinois, Chicago: "Integer Parts of Real Closed Fields"

Abstract: D'Aquino, Knight and Starchenko characterize the countable <br/>real closed fields with integer parts that are models of Peano <br/>Arithmetic. We will survey their work and give some partial results about extensions to the uncountable case.<br/>

ESC 638

Monday, February 20, 2012

05:15 pm - 06:15 pm

(CT Logic Seminar Part 2) Zoe Chatzidakis, Paris VII: "Field Internal Difference Varieties"

Abstract: Let G be an algebraic group, defined over some field K, and let g be in G(K). Consider the difference equation<br/>(*) x in G and sigma(x)=gx.<br/>If a and b are two solutions of (*), then a^{-1}b satisfies sigma(y)=y. In other words, once given a solution a, all the others are obtained by multiplying a on the right by an element of G(Fix(sigma)). <br/>So, the set of solutions of (*) is internal to Fix(sigma).<br/><br/>A difference variety as in (*) is called a translation variety. In joint work with E. Hrushovski, we determine when a difference variety which is internal to Fix(sigma) is a quotient of a translation variety. I will discuss this result. I will only assume the basic algebraic or model-theoretic definitions, all others will be given.<br/>

ESC 638

Monday, February 13, 2012

04:45 pm - 06:00 pm

CT Logic Seminar, Johanna Franklin, UConn: Lowness for randomness and lowness for tests

Abstract: There are several ways in which a real can be said to be far from random for any randomness notion R. One of them is lowness for R: we say that a real is low for R if, when we use it as an oracle, we cannot make an R-random real appear to be nonrandom. Another is lowness for R-tests: we say that a real is low for R-tests if any R-test relativized to that real can be covered by an unrelativized R-test. These concepts have been shown to coincide for many randomness notions, and some evidence has been presented by Bienvenu and J. Miller that suggests that they naturally coincide. We show that these concepts differ for difference randomness, the first notion for which this has been shown to be the case.<br/><br/>This work is joint with David Diamondstone.<br/>

ESC 638

Monday, January 30, 2012

04:45 pm - 06:00 pm

CT Logic Seminar: Paul Baginski "Model Theoretic Advances for Groups With Bounded Chains of Centralizers"

Speaker: Paul Baginski, Smith College<br/><br/>Abstract: Stable groups have a rich literature, extending ideas about <br/>algebraic groups to a wider setting, using the framework of model <br/>theory. Stable groups gain much of their strength through their chain <br/>conditions, notably the Baldwin-Saxl chain condition. In this talk, we <br/>will concern ourselves with one mild, yet very important, chain <br/>condition shared by many infinite groups studied by group theorists. A <br/>group G is said to be M_C if every chain of centralizers C_G(A_1) < <br/>C_G(A_2)< ... is finite. This class is not elementary, yet there is <br/>increasing evidence that they share many important properties of <br/>stable groups. All the present results<br/>concern nilpotence in M_C groups. The first results in<br/>this area were purely group-theoretic, but recent results by Wagner, <br/>Altinel and Baginski have uncovered that some of the desired <br/>definability results are also present. We will recount the progress <br/>that has been made and the obstacles that researchers in this area <br/>face.<br/>

ESC 638

Monday, November 28, 2011

04:45 pm - 06:00 pm

Janak Ramakrishnan, Lisbon: Interpretable groups are definable (CT Logic Seminar)

Abstract: We present joint work with K. Peterzil and P. Eleftheriou that in an arbitrary o-minimal structure, every interpretable group is definably isomorphic to a definable one. Moreover, every definable group lives in a cartesian product of one-dimensional definable group-intervals (or one-dimensional definable groups).

ESC 638

Monday, November 14, 2011

04:45 pm - 06:00 pm

CT Logic Seminar: Invariant Measures Concentrated on Countable Structures

Speaker: Rehana Patel, Wesleyan University<br/><br/>Abstract: The Erd\"os-R\'enyi random graph construction can be seen as inducing a probability measure concentrated on the Rado graph (sometimes known as the countable 'random graph') that is invariant under arbitrary permutations of the underlying set of vertices. A natural question to ask is: For which other countable structures does such an invariant measure exist? Until recent work of Petrov and Vershik (2010), the answer was not known even for Henson's countable homogeneous-universal triangle-free graph. We provide a characterisation of countable structures that admit invariant measures, in terms of the notion of (group-theoretic) definable closure. This leads to new examples and non-examples, including a complete list of countable homogeneous graphs and partial orders that satisfy our criterion. Our proof uses infinitary logic to build on Petrov and Vershik's constructions, which involve sampling from certain continuum-sized objects. In the case when the measure is concentrated on a graph, these continuum-sized objects are in fact 'graph limits' in the sense of Lovasz and Szegedy (2006). Joint work with Nathanael Ackerman and Cameron Freer.

ESC 638

Monday, October 31, 2011

04:45 pm - 06:00 pm

CT Logic Seminar: An Introduction to the Functional Interpretation

Speaker: Henry Towsner, UCONN<br/><br/>Abstract: The functional interpretation is one of the main tools of modern proof theory, providing a systematic way for extracting constructive information from proofs. This talk will give an introduction to what the functional interpretation is and how it is used, culminating in a recent application to reverse mathematics.

ESC 638

Monday, October 10, 2011

04:45 pm - 06:00 pm

CT Logic Seminar: Finding something real in Zilbers Field

Speaker: Ahuva Shkop<br/><br/>Abstract: In 2004, Zilber constructed a class of exponential fields, known as pseudoexponential fields, and proved that there is exactly one pseudoexponential field in every uncountable cardinality up to isomorphism. He conjectured that the pseudoexponential field of size continuum, K , is isomorphic to the classic complex exponential field. Since the complex exponential field contains the real exponential field, one consequence of this conjecture is the existence of a real closed exponential subfield of K . In this talk, I will sketch the proof of the existence of uncountably many non-isomorphic countable real closed exponential subfields of K and discuss some of their properties.

ESC 638

Monday, September 19, 2011

04:45 pm - 06:00 pm

Counting rational points on certain Pfaffian surfaces

Speaker: Margaret Thomas, University of Konstanz<br/><br/>Abstract: In this talk, we shall consider the question of bounding the density of rational and algebraic points on sets definable in o-minimal expansions of the real field. After surveying the topic, we shall focus on a conjecture of Wilkie about sets definable in the real exponential field and review the progress that has so far been made towards this. In particular, we shall present some results in this direction for certain surfaces. (These results are joint work with Gareth O. Jones.)

ESC 638