Archives of: Michigan Logic Seminar

Danny Nguyen: Presburger Arithmetic and its computational complexity

Thursday, November 2, 2017, from 4 to 5:30pm
East Hall, room 3096

Speaker: Danny Nguyen (University of California, Los Angeles)

Title: Presburger Arithmetic and its computational complexity

Abstract:

Presburger Arithmetic (PA) is a classical topic in logic, with numerous connections to computer science and combinatorics. Formally, is the first order structure on the integers with only additions and inequalities. Despite its long history, many problems in PA have remained unsolved until recently. We study the complexity of decision problems in PA, and classify them according to hierarchy levels. Along the way, connections to Integer Programming and Optimization will be explained. The talk will be self contained and assumes no prior knowledge of the subject. Joint work with Igor Pak.

David J. Fernández Bretón: Higher degree versions of the Central Sets Theorem, II

Thursday, October 26, 2017, from 4 to 5:30pm
East Hall, room 3096

Speaker: David J. Fernández Bretón (University of Michigan)

Title: Higher degree versions of the Central Sets Theorem, II

Abstract:

The Central Sets Theorem is a Ramsey-theoretic result due to Furstenberg, from 1981, and multiple generalizations of it (in a variety of different directions) have been proved afterwards (to the best of my knowledge, the currently most general statement is due to De, Hindman and Strauss in 2008, but there are also many relevant results due to Bergelson). This is the second of a series of two talks, where we will explain how to interpret the Central Sets Theorem as a statement about linear polynomials in a polynomial ring with countably many variables, and prove a couple of natural generalizations involving polynomials of higher degree. The main tool that we use in our proof is the algebra of the Cech–Stone compactification (that is, these are “ultrafilter proofs”).

David J. Fernández Bretón: Higher degree versions of the Central Sets Theorem

Thursday, October 12, 2017, from 4 to 5:30pm
East Hall, room 3096

Speaker: David J. Fernández Bretón (University of Michigan)

Title: Higher degree versions of the Central Sets Theorem

Abstract:

The Central Sets Theorem is a Ramsey-theoretic result due to Furstenberg, from 1981, and multiple generalizations of it (in a variety of different directions) have been proved afterwards (to the best of my knowledge, the currently most general statement is due to De, Hindman and Strauss in 2008, but there are also many relevant results due to Bergelson). In this series of two talks, we will explain how to interpret the Central Sets Theorem as a statement about linear polynomials in a polynomial ring with countably many variables, and prove a couple of natural generalizations involving polynomials of higher degree. In order to make this exposition self-contained, we will spend most of the first talk providing an overview of the techniques from algebra in the Cech–Stone compactification, which is the main tool that we use in our proof.

Abhijit Dasgupta: Axioms for complete elementary extensions

Thursday, October 5, 2017, from 4 to 5:30pm
East Hall, room 3096

Speaker: Abhijit Dasgupta (University of Detroit Mercy)

Title: Axioms for complete elementary extensions

Abstract:

We give an axiomatic framework for “logicless non-standard analysis”, using the notion of partial functions as a primitive.

Simon Cho: A Category Theoretic Perspective on Continuous Logic, II

Thursday, September 28, 2017, from 4 to 5:30pm
East Hall, room 3096

Speaker: Simon Cho (University of Michigan)

Title: A Category Theoretic Perspective on Continuous Logic, II

Abstract:

Although classical model theory is largely formulated in terms of the framework of sets, there is a rich theory that casts model theoretic structures in a category theoretic setting, a project which began with Lawvere’s thesis on “functorial semantics of algebraic theories” and has since grown into an important subfield of category theory. This interface between classical model theory and category theory continues to be an active area of research today.

In parallel, Lawvere also showed that structures – such as metric spaces – seemingly unrelated to categories arose naturally as examples of categories with appropriate enrichments V (for example V=R in the case of metric spaces). Now continuous logic/metric model theory is a generalization of classical model theory that, roughly, replaces sets with metric spaces and equality with the metric; a natural question to ask is whether the above perspective on metric spaces combines with the way of interpreting classical logic into category theory to produce a way to interpret continuous logic into enriched category theory. This talk will answer this in the affirmative, under reasonable conditions.

Simon Cho: A Category Theoretic Perspective on Continuous Logic

Thursday, September 21, 2017, from 4 to 5:30pm
East Hall, room 3096

Speaker: Simon Cho (University of Michigan)

Title: A Category Theoretic Perspective on Continuous Logic

Abstract:

Although classical model theory is largely formulated in terms of the framework of sets, there is a rich theory that casts model theoretic structures in a category theoretic setting, a project which began with Lawvere’s thesis on “functorial semantics of algebraic theories” and has since grown into an important subfield of category theory. This interface between classical model theory and category theory continues to be an active area of research today.

In parallel, Lawvere also showed that structures – such as metric spaces – seemingly unrelated to categories arose naturally as examples of categories with appropriate enrichments V (for example V=R in the case of metric spaces). Now continuous logic/metric model theory is a generalization of classical model theory that, roughly, replaces sets with metric spaces and equality with the metric; a natural question to ask is whether the above perspective on metric spaces combines with the way of interpreting classical logic into category theory to produce a way to interpret continuous logic into enriched category theory. This talk will answer this in the affirmative, under reasonable conditions. The talk will make every effort to be self-contained, and as such will assume little to no prior knowledge of category theory.

David J. Fernández Bretón: mathfrak p=mathfrak t, III

Tuesday, April 18, 2017, from 4 to 5:30pm
East Hall, room 3096

Speaker: David J. Fernández Bretón (University of Michigan)

Title: mathfrak p=mathfrak t, III

Abstract:

This is the third and last talk in the series (reasonably self-contained for those who missed any number of previous parts). I will continue to present the proof, due to Maryanthe Malliaris and Saharon Shelah in 2012, that the cardinal invariants p and t are equal, which constitutes an extremely important result in the theory of Cardinal Characteristics of the Continuum.

David J. Fernández Bretón: mathfrak p=mathfrak t, II

Thursday, April 6, 2017, from 4 to 5:30pm
East Hall, room 3088

Speaker: David J. Fernández Bretón (University of Michigan)

Title: mathfrak p=mathfrak t, II

Abstract:

This is the second in a series of (hopefully at most) three talks, and it will be reasonably self-contained for those who missed the first part. I will continue to present the proof, due to Maryanthe Malliaris and Saharon Shelah in 2012, that the cardinal invariants p and t are equal, which constitutes an extremely important result in the theory of Cardinal Characteristics of the Continuum.

David J. Fernández Bretón: mathfrak p=mathfrak t

Thursday, March 30, 2017, from 4 to 5:30pm
East Hall, room 3088

Speaker: David J. Fernández Bretón (University of Michigan)

Title: mathfrak p=mathfrak t

Abstract:

In a series of (hopefully at most) two talks, I will present the proof, due to Maryanthe Malliaris and Saharon Shelah in 2012, that the cardinal invariants p and t are equal, which constitutes an extremely important result in the theory of Cardinal Characteristics of the Continuum.

Andres Caicedo: MRP and squares, II

Thursday, March 23, 2017, from 4 to 5:30pm
East Hall, room 3088

Speaker: Andres Caicedo (Math Reviews)

Title: MRP and squares, II

Abstract:

Justin Moore’s mapping reflection principle (MRP) seems to capture the consistency strength of PFA, since it implies the failure of square. I continue the presentation of some refinements and extensions of this result. They are due to a variety of authors, and some remain unpublished.