## Rick Statman: Backus FP is Turing complete

Mathematical logic seminar – Feb 28 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Rick Statman
Department of Mathematical Sciences
CMU

Title:     Backus FP is Turing complete

Abstract:

Cartesian monoids are rather simple algebraic structures of which you know many examples. They also travel under many assumed names such as Cantor algebras, Jonsson-Tarski algebras, and Freyd-Heller monoids. John Backus’s FP is just the theory of Cartesian monoids together with fixed points for all Cartesian monoid polynomials.

In his 1977 Turing Award address, John Backus introduced the model of functional programming called “FP”. FP is a descendant of the Herbrand-Godel notion of recursive definablity and the ancestor of the programming language Haskell. One reason that FP is attractive is that it provides “an algebra of functional programs”. However, Backus did not believe that basic FP was powerful enough;

“FP systems have a number of limitations….. If the set of primitive functions and functional forms is weak, it may not be able to express every computable function”. John Backus, 1977 ACM Turing award lecture.

and he moved on to stronger systems. It turns out that, in this respect, Backus was mistaken. Here we shall show that FP can compute every partial recursive function.

## Deirdre Haskell: Using model theory to find upper bounds on VC density

Mathematical logic seminar – Feb 21 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Department of Mathematics and Statistics
McMaster University

Title:     Using model theory to find upper bounds on VC density

Abstract:

The VC dimension of a collection of sets is a concept used in probability and learning theory. It is closely related to the model-theoretic concept of the independence property. In this talk, I will illustrate these concepts in various examples, and show how the model-theoretic approach can give some bounds on VC density.

## Andy Zucker: An ultrafilter proof of the 2-dimensional Halpern-Laüchli Theorem

Mathematical logic seminar – Jan 31 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Andy Zucker
Department of Mathematical Sciences
CMU

Title:     An ultrafilter proof of the 2-dimensional Halpern-Laüchli Theorem

Abstract:

We will discuss the Halpern-Laüchli Theorem and provide a new proof in dimension 2. The idea is to use an ultrafilter on ω to turn combinatorics on trees into combinatorics on the branches, that is Cantor space. Time permitting, we will discuss obstacles to generalizing the proof to higher dimensions.

## James Cummings: Universal graphs

Mathematical logic seminar – Jan 24 2017
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         James Cummings
Department of Mathematical Sciences
CMU

Title:     Universal graphs

Abstract:

The well-known “random countable graph” or “Rado graph” is a countable graph which contains induced copies of every countable graph. We discuss the existence of such objects in uncountable cardinalities.

## Andy Zucker: Ramsey degrees big and small II

Mathematical logic seminar – November 29 2016
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Andy Zucker
Department of Mathematical Sciences
CMU

Title:     Ramsey degrees big and small II

Abstract:

We will consider various aspects of structural Ramsey theory in a countable first-order structure, leading to an investigation of several notions of largeness. For ultrahomogeneous (i.e. Fraisse) structures, the Ramsey theoretic properties of the structure and the dynamical properties of the automorphism group are closely related. This talk should serve as an introduction to the Kechris-Pestov-Todorčević correspondence while also discussing directions for new research.

## Andy Zucker : Ramsey degrees big and small

Mathematical logic seminar – November 15 2016
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         Andy Zucker
Department of Mathematical Sciences
CMU

Title:     Ramsey degrees big and small

Abstract:

We will consider various aspects of structural Ramsey theory in a countable first-order structure, leading to an investigation of several notions of largeness. For ultrahomogeneous (i.e. Fraisse) structures, the Ramsey theoretic properties of the structure and the dynamical properties of the automorphism group are closely related. This talk should serve as an introduction to the Kechris-Pestov-Todorčević correspondence while also discussing directions for new research.

## Appalachian Set Theory workshop: Benjamin Miller, January 21, 2017

Appalachian set theory

# Benjamin Miller : “Applications of the open graph dichotomy”

## Description

The open graph dichotomy is a generalization of the perfect set theorem, ensuring that every open graph on an analytic set has either a countable coloring or a perfect clique. As the proof of this result is essentially the same as that of the perfect set theorem, it can be viewed as one of the very simplest descriptive set-theoretic dichotomy theorems. Nevertheless, there is an infinite-dimensional analog of the open graph dichotomy (whose proof is essentially the same) that has recently proven particularly useful in studying Borel functions, graphs, and sets of low complexity.

We will begin by stating and proving the infinite-dimensional analog of the open graph dichotomy. We will then describe how it can be used to give particularly simple proofs of several well-known facts, such as the Hurewicz dichotomies, the Jayne-Rogers theorem, and Lecomte’s characterization of the existence of countable Borel colorings of low complexity. Finally, we will turn our attention to the new result that there is a twenty-four element basis, under closed continuous embeddability, for the class of Borel functions that are not Baire class one.

## Marcos Mazari Armida: Categoricity of an AEC in three successive cardinals, Part 1

Date: Monday, October 31, 2016

Time: 5:00 – 6:30 PM
Location: Wean 8201

Model Theory Seminar, CMU

Marcos Mazari Armida

Title:   Categoricity of an AEC in three successive cardinals, Part 1
Abstract:  In this series of talks we will be working on Abstract Elementary Classes (AECs), a semantic generalization of first order Model Theory. One of the first things one looses when stepping out of the first order setting is the compactness theorem, which in particular assures us that if there is an infinite model then there is a model in each cardinality. What we will do in this series of talks is prove a theorem in this direction for AECs. More specically (under some cardinal arithmetic hypothesis) we will show that if an AEC K is categorical in $\lambda$, $\lambda^+$ and $\lambda^{++}$ then there is a model in K of size $\lambda^{+++}$In order to do that we will have to develop many key concepts in the study of AECs like the concept of Galois Type, Reduced Type and Minimial Type. This talks will follow Saharon Shelah paper  “Categoricity of an Abstract Elementary Class in two successive cardinals” [Sh576].

## James Cummings: Cardinal invariants of the continuum

Mathematical logic seminar – October 18 2016
Time:     3:30pm – 4:30 pm

Room:     Wean Hall 8220

Speaker:         James Cummings
Department of Mathematical Sciences
CMU

Title:     Cardinal invariants of the continuum

Abstract:

The cardinal invariants of the continuum are cardinals which measure properties of the continuum more subtle than its cardinality. We will define some of the important ones and discuss their properties.

Note: This seminar will provide some background for Mayanthe Malliaris’ forthcoming Appalachian Set Theory workshop on November 5, see workshop web page at http://www.math.cmu.edu/users/jcumming/Appalachian/malliaris_cmu_2016.html for details.