VSL 2014: VIENNA SUMMER OF LOGIC 2014
PROGRAM FOR FRIDAY, JULY 11TH, 2014
Days:
previous day
next day
all days

View: session overviewtalk overview

08:30-09:30 Session 10: Proofs and Sets Session - Invited Talk (INFINITY)
Location: Kurt Gödel Research Center
08:30
Power Kripke-Platek set theory, ordinal analysis and global choice

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.

09:45-10:45 Session 11: Computations and Sets Session - Invited Talk (INFINITY)
Location: Kurt Gödel Research Center
09:45
Set functions with small circuits
SPEAKER: unknown

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.

11:15-12:15 Session 12: Proofs and Sets Session - Invited Talk (INFINITY)
Location: Kurt Gödel Research Center
11:15
Analytic combinatorics of the transfinite

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