John Baldwin: Interactions of Set Theory, $L_{\omega_1,\omega}$, and AEC.

The first is to use forcing techniques to prove model theoretic results in ZFC. Force a model theoretic result to be consistent by a tool such as Martin's axiom, collapsing cardinals or a specific forcing with high model theoretic content. Then use iterated elementary embeddings of the model of set theory to show the model theoretic result is absolute between V and a well-chosen model. Deduce it holds in ZFC. Applications include various extensions of results for $L_{\omega_1,\omega}$ to analytically presented AEC, a new proof of Harrington's theorem on Scott rank of counterexamples to Vaught's conjecture and the development of a new notion of algebraic closure for $L_{\omega_1,\omega}$ that better explains $\aleph_1$-categoricity.

The second is the use of model theory to avoid some apparent uses of descriptive theory or combinatorics. An example is the development locally finite abstract elementary classes to simplify and improve results of Hjorth on the characterizing cardinals. As a corollary we get radically new amalgamation spectra.

Arnold Beckmann: Proof Theoretic Characterisations of Feasible Set Functions.

Recently, various restrictions of the primitive recursive set functions relating to feasible computation have been proposed, amongst them the Safe Recursive Set Functions (Beckmann, Buss, Friedman), the Predicatively Computable Set Functions (Arai), and the Cobham Recursive Set Functions (Beckmann, Buss, Friedman, Müller, Thapen — this is work in progress). In this talk I will describe ideas how some of these classes can be captured as the $\Sigma_1$-definable set functions in suitable restrictions of Kripke-Platek set theory, by elementary proof-theoretic means. In particular, I will describe a theory whose $\Sigma_1$-definable set functions are exactly the Safe recursive Set Functions, and another theory whose $\Sigma_1$ definable set functions are characterised by the Cobham Recursive Set Functions.

The latter result is joint work in progress with Sam Buss, Sy-David Friedman, Moritz Müller, and Neil Thapen.

Ulrik Buchholtz: Systems of Strength $H(1)$.

The ordinal $H(1)$ is a tad bigger than the Bachmann-Howard ordinal, and in fact it appeared already in the 1950 article by Heinz Bachmann which inspired Howard's ordinal analysis of ID1. Aczel conjectured that also $H(1)$ should be a prominent proof-theoretic ordinal. In this talk I will present a range of systems of proof-theoretic strength $H(1)$, focusing on systems of sets and types. A common theme is that these systems capture a kind of predicative closure taking one generalized positive inductive definition as a given totality.

Sam Buss: Cobham Recursive Set Functions.

This talk discusses work in progress on using a Cobham-style recursion on sets to define an analogue of polynomial time computation on sets. We define a new # (smash) function which operates on sets, along with a natural notion of embedding, and use these to define Cobham-style bounded $\epsilon$-recursive definitions of functions that operate on sets. This gives a natural method of defining set-valued functions with feasible computational complexity; in particular, it gives a characterization of polynomial time in terms of computation on hereditarily finite sets.

This extends prior work of Beckmann-Buss-Friedman and Arai, who introduced safe-normal $\epsilon$-recursion.

This talk discusses joint work with A. Beckmann, S. Friedman, M. Müller, and N. Thapen.

Tapani Hyttinen: Infinitely deep languages and neighbors.

We take a look on the development on the questions around infinitely deep languages that has happened during the last 40 years.

Julia Knight: Computing a floor function.

For the field of real numbers, we have the usual floor function, with range equal to the set of integers. If we expand the reals, adding the function $2^x$, then for a positive integer $x$, $2^x$ is also a positive integer. Mourgues and Ressayre showed that every real closed field has an “integer part”. The construction is complicated, not arithmetical, but hyperarithmetical. Ressayre showed that every real closed exponential field has an “exponential integer part”. This construction is even more complicated. It may not finish in the least admissible set over the input.

Chris Laskowski: When excellence and local finiteness collide.

We describe a uniform family $\{T_n\}$ of complete, first order theories for $n\ge 1$, each in a countable language, such that each $T_n$ has an atomic model of size $\aleph_n$, every atomic model of size $\aleph_n$ is maximal, and hence has no atomic model of size $\aleph_{n+1}$. Moreover, the class of atomic models satisfies disjoint amalgamation in $\aleph_k$ for every $k<n-1$, but fails both amalgamation and disjoint amalgamation in $\aleph_{n-1}$.

The negative results all follow from general observations about locally finite closure relations, while the positive results follow by an inductive argument akin to Shelah's work on identifying excellent classes.

This is joint work with John Baldwin and Martin Koerwien.

Russell Miller: Functors in Computable Model Theory.

We give an overview of a number of recent results in computable model theory, by various researchers (not necessarily including the speaker). The results are not all directly connected to each other, but they serve to illustrate the principle that much of the work in this discipline can be viewed through the prism of functors, on categories $C$ and $D$ whose elements are countable (or computable) structures and whose morphisms are isomorphisms (not necessarily computable). Ideally, such a functor $F$ from $C$ to $D$ should be effective: given a structure $M$ from $C$ as an oracle, it should compute the structure $F(M)$ in $D$, and given a $C$-morphism $g$ from $M$ to $N$ as an oracle, it should compute the $D$-morphism $F(g)$ from $F(M)$ to $F(N)$. Moreover, one would hope for $F$ to be full and faithful, as a functor, and to have a computable inverse functor. In practice, it is unusual for an $F$ to have all of these properties, and for particular applications in computable model theory, only certain of the properties are needed. Many familiar examples will be included to help make these concepts clear.

Antonio Montalban: Classes of structures with no intermediate isomorphism problems.

We say that a theory $T$ is intermediate under effective reducibility if the isomorphism problems among its computable models is neither hyperarithmetic nor on top under effective reducibility. We exhibit partial results towards showing that the existence of such theories is equivalent to the negation of Vaught's conjecture.

We prove that if an infinitary sentence $T$ is uniformly effectively dense, a property we define in the paper, then no extension of it is intermediate, at least when relativized to every oracle in a cone. As an application we show that no infinitary sentence whose models are all linear orderings is intermediate under effective reducibility relative to every oracle in a cone.

Michael Rathjen: Power Kripke-Platek set theory, ordinal analysis and global choice.

KP and extensions via axioms asserting the existence of many admissible sets have been studied intensively in admissible proof theory. Augmenting KP by the powerset operation either by adding the axiom or treating the operation as a primitive (Power KP) leads to theories that are to some extent amenable to proof-theoretic techniques, thereby providing some form of ordinal analysis. The proof-theoretic techniques enable one to considerably strengthen classical results. Moreover they entail conservativity results with respect to the axiom of global choice and also the calculus of constructions with one universe.

Neil Thapen: Set functions with small circuits.

I will talk about some ongoing work on computational complexity in set theory, using the model of Cobham recursive functions. I will discuss Boolean circuit complexity in this setting and will show that, with suitable definitions, every “polynomial time” function can be computed by small circuits over arbitrary sets.

Andreas Weiermann: Analytic combinatorics of the transfinite.

Assume that we can assign a complexity $c(\alpha)$ to each ordinal $\alpha<\epsilon_0$ in some natural way. Let $c_\alpha(n)$ be the number of ordinals $\beta$ less than $\alpha$ such that $c(\beta)$ does not exceed $n$. If $c$ behaves additively let $C_\alpha(z)$ be the generating function $\sum_{n=0}^\infty c_\alpha(n)z^n$. If $c$ behaves multiplicatively let $C’_\alpha(z)$ be the Dirichlet generating function $\sum_{n=0}^\infty c_\alpha(n) n^{-z}$.

We are interested in the transfer between order-theoretic properties of ordinals and the analytic behavior of the generating functions in the neighborhood of 1 which is typically an essential singularity for $\alpha$ not smaller than $\omega^\omega$.

We will indicate how these results contribute to investigations on logical limit laws for ordinals and phase transitions for independence results.

We also investigate related problems in the context of planar and non planar finite rooted trees.

This is joint work with Lev Gordeev and Alan Woods.