BLC Newsletter November 2008

BRITISH LOGIC COLLOQUIUM
Registered Charity No 275541

http://www.cs.bham.ac.uk/~exr/blc

President           Professor J M E Hyland [Cambridge]
Vice-President      Professor T Williamson FBA FRSE [Oxford]
Treasurer           Professor D Macpherson [Leeds]
Secretary           Dr N Alechina [Nottingham]
                    Dr U Berger [Swansea]
                    Dr E Ritter [Birmingham]
                    Dr G Wilmers [Manchester]

--------------------------------------------------------- (1) Discounted subscription rates for 2009 for History and Philosophy of Logic

(2) Postgraduate student conference in Manchester, MAGIC'09, 12-14 January 2009.

(3) Set theory and its neighbours, 19th November, Bristol.

(4) Cameleon meeting in Leeds, November 29.

-----------------------------------------------------------

(1) Discounted subscription rates for 2009 are available to individual members of the British Logic Colloquium on the following Taylor & Francis journal:

History and Philosophy of Logic www.informaworld.com/HPL

More information on the BLC web site.

(2) We are pleased to announce that the registration for the 2nd MAGIC
postgraduate student' conference, MAGIC'09, is open now.

The conference will be held in Manchester, 12-14 January '09.

The registration is open at:

http://www.maths.manchester.ac.uk/~magic

The following speaker have kindly agreed to give plenary talks:


   * Professor Norman Biggs (LSE)
   * Professor Alexandre Borovik (Manchester)
   * Professor Chris Budd (Bath)
   * Professor Peter Diggle (Lancaster)
   * Professor Robert MacKay (Warwick)
   * Professor Jeff Paris (Manchester)
   * Professor Alex Wilkie (Manchester)


We strongly encourage PG students to prepare short talks (15-20 mins) or prepare posters. The conference is supported by MAGIC group. Thanks to MAGIC and LMS, we have some funding available to support PG students. Priority of funding will be given to students who would like to give talk, or have posters.

The MAGIC meeting will be proceeded by 2009 Regional LMS meeting.

http://www.maths.manchester.ac.uk/~magic/LMS09.html

We will look for to hear from you soon!

The MAGIC organising committee,
Hadi Zare, Marianne Johnson, Andrew Hazel, Gemma Lloyd

--------------------------------------------------------------------

Set theory and its neighbours, 17

Set theory, Games and Bounded Arithmetic,

(http://www.ucl.ac.uk/~ucahcjm/stn.html)

A one-day conference in the series Set theory and its neighbours will
take place on Wednesday 19th November at the Department of Mathematics,
University of Bristol, Bristol BS8 1TW. The talks will be in room SM4,
with the first talk starting at 11.30am. The meeting should finish by
approximately 6.15pm.
The speakers at the meeting will be:

   * Benedikt Lowe (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 omega_1", "cofinality omega_2", "cofinality omega_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 mu-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
proposed another approach, and at the very least provide a modest
refinement to the complexity of parity games (and in turn the mu-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
(Pi_2 conservative) extension of this theory.
   *  Philip Welch (Bristol) 16.15

      Locating strategies for Sigma0_3 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 Godel
constructible hierarchy L at the closure point of monotone Sigma1_1
monotone inductive definitions. For Sigma0_2 games the corresponding result
is the ordinal of Sigma1_1 monotone inductive definitions (Solovay). For
Sigma0_3 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 Sigma0_3 games is provable in Pi1_3-CA (the subsystem of
analysis with the Comprehension Scheme restricted to Pi1_3 formulae) but
not in Pi1_2-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.
We are grateful to the LMS Programme Committee for financial support via a Scheme 3 grant.


Mirna Dzamonja, Charles Morgan and Philip Welch

University of Leeds
Meeting of 'CAMELEON' in Leeds
November 29th 2008

There will be a 1-day meeting at the University of Leeds on November
29th, 2008, as part of the 'CAMELEON' group (comprising the universities
of Cambridge, East Anglia, and Leeds). The meeting is partially
supported by a grant from the London Mathematical Society London
Mathematical Society  . There will be some grants
available to support attendance by members of those three universities.
The speakers are Daniela Amato (Leeds) Garth Dales (Leeds) James
Mitchell (St Andrews) Charles Morgan (University College, London). All
are welcome. The following is the provisional programme
10.30 coffee

11-11.55 James Mitchell (University of St Andrews)
Cofinalities, Bergman's property, and existentially closed semigroups.
12.10-1.05 Daniela Amato (University of Leeds)
Graphs, digraphs and some symmetry conditions.
1.15-2.15 lunch

2.30-3.25 Charles Morgan (University College, London)
Large almost disjoint families
Abstract:  A family of subsets of a set is almost disjoint if the
intersection of any two of its members is finite.  These families are
useful in general topology and are also attractive objects of study from
the combinatorial point of view. In this talk I shall concentrate on
large , but non-maximal, almost disjoint families and discuss various
questions related to their possible sizes.
3.35-4.00 tea
4.00-4.55 Garth Dales (University of Leeds)
Feebly continuous functions, after Imre Leader
Abstract: We shall describe a problem involving weights and weighted
convolution algebras on the rationals and on the real line, and show
that the solution depends on a combinatorial condition on weights. This
suggested a related question on 'feebly continuous' functions on the
real line and on the plane that I could not solve. My specific problem
was resolved by Imre Leader, using some set-theoretic techniques. I will
present his solution, and hen ask some more questions.
And they may be found on the web page
http://www.maths.leeds.ac.uk/pure/staff/truss/cameleon.html



This message has been checked for viruses but the contents of an attachment
may still contain software viruses, which could damage your computer system:
you are advised to perform your own checks. Email communications with the
University of Nottingham may be monitored as permitted by UK legislation.



                                                   Dear Natasha,

                                                                           I 
just got the blc newsletter. I realized that we should have publicized the 
‘cameleon’ meeting that we are holding in Leeds. I asked Mirna about it (who is 
one of the organizers) and she thought that you might not mind sending out a 
brief mailing to your mailing list, if you would be so kind.

 

(4)
 

*                                           University of Leeds *

*                            Meeting of 'CAMELEON' in Leeds *

*                                                        November 29th 2008 *

 

There will be a 1-day meeting at the University of Leeds on November 29th, 2008, 
as part of the 'CAMELEON' group (comprising the universities of Cambridge, East 
Anglia, and Leeds). The meeting is partially supported by a grant from the 
London Mathematical Society London Mathematical Society . 
There will be some grants available to support attendance by members of those 
three universities. The speakers are Daniela Amato (Leeds) Garth Dales (Leeds) 
James Mitchell (St Andrews) Charles Morgan (University College, London). All are 
welcome. The following is the provisional programme

10.30 coffee

11-11.55 James Mitchell (University of St Andrews)

Cofinalities, Bergman's property, and existentially closed semigroups.

12.10-1.05 Daniela Amato (University of Leeds)

Graphs, digraphs and some symmetry conditions.

1.15-2.15 lunch

2.30-3.25 Charles Morgan (University College, London)

Large almost disjoint families

Abstract:  A family of subsets of a set is almost disjoint if the intersection 
of any two of its members is finite.  These families are useful in general 
topology and are also attractive objects of study from the combinatorial point 
of view. In this talk I shall concentrate on large , but non-maximal, almost 
disjoint families and discuss various questions related to their possible sizes.

3.35-4.00 tea

4.00-4.55 Garth Dales (University of Leeds)

Feebly continuous functions, after Imre Leader

Abstract: We shall describe a problem involving weights and weighted convolution 
algebras on the rationals and on the real line, and show that the solution 
depends on a combinatorial condition on weights. This suggested a related 
question on 'feebly continuous' functions on the real line and on the plane that 
I could not solve. My specific problem was resolved by Imre Leader, using some 
set-theoretic techniques. I will present his solution, and hen ask some more 
questions.

And they may be found on the web page 
http://www.maths.leeds.ac.uk/pure/staff/truss/cameleon.html

 

 

      Many thanks for your help,

                           John Truss.



Home Index

+++++++++++++++++++++++++++

Page maintained by E.Ritter@cs.bham.ac.uk

Last modified: Mon Nov 17 18:42:27 GMT 2008