Arithmetically categorical structures
Valentina Harizanov, George Washington University
Valentina Harizanov, George Washington University
Matthew Harrison-Trainor, Victoria University of Wellington
We say that a set A introcomputes a set B if every infinite subset of A computes B. There are two natural ways in which this can happen. First, if A consists of the finite initial segments of B, then A introcomputes B; and second, if B is hyperarithmetic and A is very sparse then every infinite subset of A computes a function dominating the modulus of B, and hence computes B. I’ll talk about a number of results attempting to understand the reasons that one set might introcompute another.
MC 5413
Jinhe Ye, University of Notre Dame
Alexi Taylor Block Gorman, University of Illinois at Urbana-Champaign
Marco Handa, Department of Pure Mathematics, University of Waterloo
Andy Zucker, Department of Pure Mathematics, University of Waterloo
"Polish partition principles and the Halpern-Lauchli theorem"
The Halpern-Lauchli theorem is a partition theorem about products of trees. While the theorem is entirely combinatorial in nature, one proof due to Leo Harrington uses some ideas from forcing. This proof uses the Erdos-Rado theorem to analyze a sufficiently rich forcing poset which is built using the trees in question. Notably, there is no need to actually pass to the generic extension in the course of the proof. In recent joint work with Chris Lambie-Hanson, we reimagine Harrington's proof by actually passing to the generic extension. In so doing, we isolate and investigate a consistent partition principle about products of perfect Polish spaces.
MC 5403
Ross Willard, Department of Pure Mathematics, University of Waterloo
An enduring problem in universal algebra is this: given a finite algebra, are the identities which are true in the algebra finitely axiomatizable? In this lecture I’ll give one nontrivial example where the answer is “yes” and another where the answer is “no,” to motivate the definition of what we mean by a “strong no” answer to this question. If time, I’ll mention a 45-year-old open problem of Eilenberg and Schutzenberger and its connection to this question.
MC 5403
Luke MacLean, Department of Pure Mathematics, University of Waterloo
This talk will look at computable structures from the perspective of enumeration reducibility. We look at the class of relations such that the relation interpreted in a structure is enumerable using only positive information from the structure and show that they are exactly those that are definable by computable $\Sigma_1$ formulas that use only positive information. We define a new notion of the jump of a structure by adding the complements of all these relations to our language. This increases the degree of the structure relative to enumeration reducibility in a way that agrees more with the traditional enumeration jump of sets than any other attempt at defining the enumeration jump of a structure.
Time permitting, we will see how a notion of bi-interpretability between structures using these new positive computable $\Sigma_1$ formulas is equivalent to there being an adjoint equivalence between the isomorphism classes of the structures which is witnessed by enumeration operators. These positive enumerable functors were studied by Barbara Csima, Dino Rossegger, and Daniel Yu.
All of this is joint work with Barbara Csima and Dino Rossegger.
MC 5403
Rahim Moosa, Department of Pure Mathematics, University of Waterloo
I will talk about work with James Freitag and Remi Jaoui, from late last year, applying model theory to the study of algebraic differential equations. The result is as follows: Given any algebraic differential equation, if there is a nontrivial algebraic relation among any number of its solutions and their derivatives then there is already such a relation between two solutions. The proof uses ideas from geometric stability theory, including binding group actions, of which I will try to give some flavour.
Barbara Csima, Department of Pure Mathematics, University of Waterloo
A degree of categoricity is a Turing degree that exactly captures the complexity of computing isomorphisms between computable copies of some computable structure. In this talk I will start by giving some easy examples of degrees of categoricity. I will then give a review of what is known about degrees of categoricity, culminating in new results (joint work with Dino Rossegger).
Note: We will pause at 11am to observe a minute of silence.
MC 5403