=== Wednesday, July 9 ===
|
2.00pm—3.00pm |
'''John Baldwin''': ''Interactions of Set Theory, $L_{\omega_1,\omega}$, and AEC''. abstract
|
3.15pm—4.15pm |
'''Arnold Beckmann''': ''Proof Theoretic Characterisations of Feasible Set Functions''. abstract
|
4.45pm—5.45pm |
'''Ulrik Buchholtz''': ''Systems of Strength $H(1)$''. abstract
|
=== Thursday, July 10 ===
|
8.30am—9.30am |
'''Sam Buss''': ''Cobham Recursive Set Functions''. abstract
|
9.45am—10.45am |
'''Tapani Hyttinen''': ''Infinitely deep languages and neighbors''. abstract
|
11.15am—12.15pm |
'''Julia Knight''': ''Computing a floor function''. abstract
|
2.00pm—3.00pm |
'''Chris Laskowski''': ''When excellence and local finiteness collide''. abstract
|
3.15pm—4.15pm |
'''Russell Miller''': ''Functors in Computable Model Theory''. abstract
|
4.45pm—5.45pm |
'''Antonio Montalban''': ''Classes of structures with no intermediate isomorphism problems''. abstract
|
'''''— Workshop Dinner —'''''
|
=== Friday, July 11 ===
|
8.30am—9.30am |
'''Michael Rathjen''': ''Power Kripke-Platek set theory, ordinal analysis and global choice''. abstract
|
9.45am—10.45am |
'''Neil Thapen''': ''Set functions with small circuits''. abstract
|
11.15am—12.15pm |
'''Andreas Weiermann''': ''Analytic combinatorics of the transfinite''. abstract
|
=== Wednesday, July 9 ===
|
2.00pm—3.00pm |
'''John Baldwin''': ''Interactions of Set Theory, $L_{\omega_1,\omega}$, and AEC''. back
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.
|
3.15pm—4.15pm |
'''Arnold Beckmann''': ''Proof Theoretic Characterisations of Feasible Set Functions''. back
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.
|
4.45pm—5.45pm |
'''Ulrik Buchholtz''': ''Systems of Strength $H(1)$''. back
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.
|
=== Thursday, July 10 ===
|
8.30am—9.30am |
'''Sam Buss''': ''Cobham Recursive Set Functions''. back
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.
|
9.45am—10.45am |
'''Tapani Hyttinen''': ''Infinitely deep languages and neighbors''. back
We take a look on the development on the questions around infinitely deep languages
that has happened during the last 40 years.
|
11.15am—12.15pm |
'''Julia Knight''': ''Computing a floor function''. back
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.
|
2.00pm—3.00pm |
'''Chris Laskowski''': ''When excellence and local finiteness collide''. back
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.
|
3.15pm—4.15pm |
'''Russell Miller''': ''Functors in Computable Model Theory''. back
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.
|
4.45pm—5.45pm |
'''Antonio Montalban''': ''Classes of structures with no intermediate isomorphism problems''. back
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.
|
'''''— Workshop Dinner —'''''
|
=== Friday, July 11 ===
|
8.30am—9.30am |
'''Michael Rathjen''': ''Power Kripke-Platek set theory, ordinal analysis and global choice''. back
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.
|
9.45am—10.45am |
'''Neil Thapen''': ''Set functions with small circuits''. back
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.
|
11.15am—12.15pm |
'''Andreas Weiermann''': ''Analytic combinatorics of the transfinite''. back
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.
|