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,