A one-day conference in the series Set theory and its neighbours which took place on Wednesday 19th November at the Department of Mathematics, University of Bristol, Bristol BS8 1TW
The speakers at the meeting were:
Benedikt Löwe (ILLC, Amsterdam) 11.30am
Large Cardinals, Measurability and cofinality patterns of the first three uncountable cardinals
Abstract: In this joint work with Apter and Jackson, we consider all possible patterns of the properties "countable cofinality", "cofinality ω1", "cofinality ω2", "cofinality ω3", "measurable" for the first three uncountable cardinals in ZF, and prove that all patterns that are not inconsistent for trivial reasons are consistent relative to large cardinals. Crucial for the proof of some of the patterns is the proof of a strong polarized partition property of three successive cardinals under the Axiom of Determinacy.
Anuj Dawar (Cambridge) 13.30
Descriptive Complexity of Parity Games.
Abstract: Parity games are a class of two player infinite games played on (finite or infinite) game graphs. The computational complexity of deciding the which player has a winning strategy in such a game has been the focus of a significant research effort. We look at another aspect of the problem - its descriptive complexity. We aim to characterise what logics can be used to define winning regions in parity games.
This is joint work with Erich Graedel (RWTH, Aachen).
Arnold Beckmann (Swansea) 17.15
On the complexity of parity games (joint work with Faron Moller)
Abstract: Parity games underlie the model checking problem for the modal μ-calculus, the complexity of which remains unresolved after more than two decades of intensive research. The community is split into those who believe this problem - which is known to be both in NP and coNP - has a polynomial-time solution (without the assumption that P=NP) and those who believe that it does not. (A third, pessimistic, faction believes that the answer to this question will remain unknown in their lifetime.)
In this paper we explore the possibility of employing Bounded Arithmetic to resolve this question, motivated by the fact that problems which are both NP and coNP, and where the equivalence between their NP and coNP description can be formulated and proved within a certain fragment of Bounded Arithmetic, necessarily admit a polynomial-time solution. While the problem remains unresolved by this paper, we do propose another approach, and at the very least provide a modest refinement to the complexity of parity games (and in turn the μ-calculus model checking problem): that they lie in the class of Polynomial Local Search problems. This result is based on a new proof of memoryless determinacy which can be formalised in Bounded Arithmetic.
Richard Pettigrew (Bristol) 15.00
The foundations of arithmetic and analysis in bounded finite set theory
Abstract: The conventional foundations for arithmetic and analysis and indeed nearly all of mathematics lie in ZF set theory. I introduce a version of Zermelo set theory in which the Axiom of Infinity is replaced by an Axiom of Dedekind Finitude, and the Schema of Subset Separation is restricted to bounded quantifier formulae. I recover a foundation for arithmetic that supports a multitude of non-isomorphic natural number systems with various closure properties; and I show how a natural version of the infinitesimal calculus can be recovered in a weak (Π2 conservative) extension of this theory.
Philip Welch (Bristol) 16.15
Locating strategies for Σ 03 games.
Abstract: Determinacy for games low down in the arithmetical hierarchy can be proven in second order number theory, or equivalently, analysis. Theorems of Moschovakis et al. locate strategies in the Gödel constructible hierarchy L at the closure point of monotone Π11 monotone inductive definitions. For Σ02 games the corresponding result is the ordinal of Σ11 monotone inductive definitions (Solovay). For Σ03 no such characterisation, either as a closure ordinal for some kind of inductive definition, nor even where they appear in the L-hierarchy is known. We present some partial results in this direction, narrowing down the interval for their occurrence. We show that Determinacy for Σ03 games is provable in Π13-CA (the subsystem of analysis with the Comprehension Scheme restricted to Π13 formulae) but not in Π12-CA, the latter using a Friedman game.
We aim to keep the meetings fairly relaxed, allowing plenty of opportunity for informal discussion. We welcome and encourage anyone to participate. Please do tell anyone about the meeting who you think may be interested in it. There is no registration fee for the meeting. We are happy for you to email us to let us know if you intend to come, but you are also very welcome simply to turn up on the day if you make a late decision. And let us know if you would like to speak or have ideas for speakers at future meetings. After the meeting we will probably go for a near-by drink and then supper.
Map of U. of Bristol precinct Mathematics is numbered 24.
Mirna Džamonja, Charles Morgan and Philip Welch
Return to the Set theory and its neighbours homepage for information, including slides from the talks and related preprints, about the previous meetings.
Last updated on 2nd December 2008,