Seminar talks spring 2014
Talks during the spring term 2014
Wed 15.1.2014 12-14, C124
Jouko Väänänen: More on existential second order logic and set theory
Wed 22.1.2014 12-14, C124
Miguel Moreno: Stationary tower forcing
Wed 29.1.2014 12-14, C124
No seminar.
Wed 5.2.2014 12-14, C124
Philip Welch: Determinacy within Second Order Arithmetic
Abstract: It is well known that infinite perfect information two person games at low levels in the arithmetic hierarchy of sets have winning strategies for one of the players, and moreover this fact can be proven in analysis alone This has led people to consider reverse mathematical analyses of precisely which subsystems of second order arithmetic are needed. We go over the history of these results.
Recently Montalban and Shore gave a precise delineation of the amount of determinacy provable in analysis. Their arguments use concretely given levels of the Gödel constructible hierarchy. It should be possible to lift those arguments to the amount of determinacy, properly including analytic determinacy, provable in fragments of ZF^- + ``there is a measurable cardinal''. We summarise some recent joint work with Chris Le Sueur.
Wed 12.2.2014 12-14, C124
Daisuke Ikegami: Inner models from Boolean valued higher-order logics and $\Omega$-logic
Abstract: Gödel's Constructible Universe is obtained by keeping adding 1st order definable subsets of structures in question. What if one uses other logics with definability notions and obtains models of set theory in the same way? In this talk, we discuss the inner models from Boolean valued higher order logics and Woodin's $\Omega$-logic all of which talk about generic absoluteness, and investigate the basic properties and the relationship among those models.
Wed 19.2.2014 12-14, C124
Vadim Kulikov: The definability of pure unrectifiability
Wed 26.2.2014 12-14, C124
Jouko Väänänen: Large cardinals and some inner models
Wed 5.3.2014 12-14, C124
No seminar.
Wed 12.3.2014 12-14, C124
Miguel Moreno: More on stationary tower forcing
Wed 19.3.2014 12-14, C124
Raine Rönnholm (Tampere): Inclusion and Exclusion Friendly Logics
Abstract: In this presentation I will talk about inclusion and exclusion operations on the level of quantification. I will introduce different kinds of inclusion and exclusion quantifiers and examine their properties. By researching the expressive power of these quantifiers, we also get some results about the expressive power of the inclusion and exclusion logics compared to the dependence and nondependence logics.
Wed 26.3.2014 12-14, C124
Jonni Virtema (Tampere): Computational complexity of modal dependence logics
Tue 1.4.2014 12-14, C124
Arnaud Durand: Structural Tractability of Counting of Solutions to Conjunctive Queries
Abstract: It is well known that deciding a conjunctive query (CQ) is a NP-complete problem and that counting the number of solutions of such queries is even harder (it is said #P-complete). In this talk, we will try to understand what makes counting the solutions of query hard. We first consider the case of acyclic conjunctive queries (ACQ), a fragment of CQ whose decision is known to be tractable. The counting analog of this problem is also known to be tractable (for combined complexity), but it is also known that introducing even a single quantified variable makes it #P-hard. We first show that weighted counting for quantifier-free ACQ is still tractable and that even minimalistic extensions of the problem lead to hard cases. We then introduce a new parameter for quantified queries that permits to isolate a large island of tractability. We show that, up to a standard assumption from parameterized complexity, this parameter fully characterizes tractable subclasses for counting weighted solutions for ACQs. Methods to prove these results rely on arithmetic circuit complexity and structural properties of hypergraphs. No prior knowledge of these domains is required: we will introduce the necessary material. We will also discuss some recent extensions of this result on larger classes of queries.
Based on works in collaboration with Stefan Mengel (ICDT'13, JCSS'14).
Wed 9.4.2014 12-14, C124
Chris Le Sueur (Bristol): Determinacy a bit beyond Pi^1_1
Abstract: It is quite well-known result of Martin that the existence of a measurable cardinal is enough to prove the determinacy of all boldface Pi^1_1 sets. The argument nicely modifies to get the determinacy of all lightface Pi^1_1 sets from the existence of O^sharp. I will present the outline of this argument and then discuss how the technique has been pushed since then to get more determinacy in the difference hierarchy of Pi^1_1 sets, including a family of new determinacy results following from sharp-like hypotheses. To achieve this I will also demonstrate a generalised notion of computability suitable for defining the lightface Borel hierarchy in uncountable spaces.
Wed 16.4.2014 12-14, C124
Tapani Hyttinen: On Zilber on quantum field theory
Wed 23.4.2014 12-14, C124
Eastern, no seminar.
Wed 30.4.2014 12-14, C124
Juha Kontinen: Modal independence logic
Wed 21.5.2014 12-14, C124
Antti Kuusisto (University of Wroclaw): Generalized operators, team semantics and game-theoretic semantics