ABSTRACT. 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.

ABSTRACT. 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.

ABSTRACT. Assume that we can assign a complexity c(alpha) to each ordinal alpha smaller than 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. (Joint work with Lev Gordeev and Alan Woods.)