MALOA - From MAthematical LOgic to Applications

Marie Curie Initial Training Network in Mathematical Logic

First MALOA Training Workshop (5 - 11 September 2010)

News

• Lecture notes of Mirna Džamonja's lecture available.
• Lecture notes and further information to Thierry Coquand's lecture available.
• Group picture online.

Scope

Contact

Date

Accommodation

Organizing committee

• Josef Berger
• Wilfried Buchholz
• Hans-Dieter Donder
• Peter Schuster
• Helmut Schwichtenberg

Participants

• George Attesis
• Andres Aranda-Lopez
• Delhi Babu
• Rui Soares Barbosa
• Michele Bovenzi
• Artem Chernikov
• Thierry Coquand
• Mirna Džamonja
• Fredrik Nordvall Forsberg
• Zaniar Ghadernezhad
• Franziska Jahnke
• Gareth Jones
• Mehmet Karakus
• Romain Kervarc
• Mohsen Khani
• Marios Koulakis
• Pablo Cubides Kovacsics
• Noa Lavi
• Stijn Lemmens
• Debbie Lockett
• Dugald MacPherson
• Guillaume Malod
• Sebastian Müller
• Kenji Miyamoto
• Florian Ranzi
• Davide Rinaldi
• Masahiko Sato
• Peter Schuster
• Helmut Schwichtenberg
• Athanasios Tsouanas
• Pedro Valencia
• Dmitrios Vlitas
• Zi Chao Wang
• David B. Williams
• Albert Ziegler

Timetable

Main lecture courses

• Thierry Coquand (Chalmers) Constructive algebra
• Masahiko Sato (Kyoto University) Symbolic expressions and variable binding
  We will survey the history and various approaches for dealing with symbolic expressions equipped with the variable binding mechanism. Our emphasis will be on the syntactic structure of such symbolic expressions, and we will use untyped lambda terms and derivations in a natural deduction system as canonical examples of expressions with binding mechanism. Part of the lectures is based on my recent works with Randy Pollack which are downloadble from:
  http://homepages.inf.ed.ac.uk/rpollack/export/SatoPollack09.pdf
  (External and internal syntax of the \lambda-calculus), and
  http://homepages.inf.ed.ac.uk/rpollack/export/SatoPollackJARsubmitted.pdf
  (A Canonical Locally Named Respresentation of Binding)
  We will compare various approaches from the viewpoint of
  1. accessibility for humans,
  2. implementation on a computer,
  3. proving properties of such expressions inductively,
  4. computing functions on such expressions recursively, and
  5. defining such expressions as a data type.
• Mirna Džamonja (University of East Anglia) Fast track to forcing
Notes of the five lectures:
• Lecture 1
• Lecture 2
• Lecture 3
• Lecture 4
• Lecture 5
The following might be useful as a preparation for these talks.:
• Set theory, lecture 1
• Set theory, lecture 2
• Set theory, lecture 3
• Set theory, lecture 4
• Set theory, lecture 5
• Dugald MacPherson (Leeds) Homogeneous structures
  
  I shall survey a subject which sits on the borderline between model theory, combinatorics, permutation groups theory, and descriptive set theory, with connections to complexity theory now emerging.
  
  For convenience, we consider first order structures only over finite relational languages. A countably infinite such structure M is said to be homogeneous if every isomorphism between finite substructures of M extends to an automorphism of M. Using Cantor's 'back-and-forth' argument (or just using piecewise-linear automorphisms) one quickly sees that the rational numbers, equipped just with the natural total order, form a homogeneous structure. The standard method of construction of homogeneous structures is via a theorem of Fraisse, from an 'amalgamation class' of finite structures. This yields, for example, the 'random graph', arising from the amalgamation class of all finite graphs.
  
  Connections to model theory arise since homogeneous structures (over a finite relational language) form an important class of omega-categorical structures. In the 1980s, Lachlan developed a deep structure theory for stable homogeneous structures, subsequently generalised to the class of smoothly approximable structures by Cherlin and Hrushovski, in work in which many recent model theoretic ideas were first seen. In addition, Fraisse's amalgamation theorem has other versions with rich model-theoretic applications.
  
  Connections to combinatorics arise in many ways: classification results for classes of homogeneous structures (e.g. digraphs) are essentially combinatorial; some of the deepest results in Ramsey theory (for classes of structures) involve amalgamation classes; and questions in combinatorial enumeration can often be phrased in terms of automorphism groups of homogeneous structures.
  
  The links to permutation group theory arise readily, since from the definition any homogenous structure has a rich automorphism group, and many examples of surprising phenomena for infinite permutation groups arise from Fraisse amalgamation. Attention has tended to focus on the extent to which a homogeneous structure can be reconstructed from its automorphism group.
  
  Any automorphism group of a countably infinite first order structure has naturally the structure of a Polish group (a topological group such that the topology can be equipped with a complete separable metric space structure). Polish groups are a central subject in descriptive set theory, and homogeneous structures provide very important results, linked also to Ramsey theory.
  
  Currently, the connections to complexity theory arise through work of Bodirsky and co-authors on constraint satisfaction. Many natural constraint satisfaction problems arise from homogeneous structures, and there are interesting links to universal algebra.
  
  In these lectures I will try to summarise some of this topics, without assuming much background in model theory or permutation group theory. I will expand on parts of my survey article (see 4. below).
  
  Suggested Background Reading:
  
  
  1. P.J. Cameron, 'Oligomorphic permutation groups', London Math. Soc. Lecture Notes 152, Cambridge University Press, 1990.
  2. G. Cherlin, 'Combinatorial problems connected with finite homogeneity', Contemp. Math. 131 (1992), 3-30.
  3. A.S. Kechris, C. Rosendal, 'Turbulence, amalgamation and generic automorphisms of homogeneous structures', Proc. London Math. Soc. 94 (2007), 302-350.
  4. H.D. Macpherson, 'A survey of homogeneous structures'

Contributed talks

• Artem Chernikov
  Burden in valued fields
  Burden is a notion of generalised weight which was introduced by Adler and makes sense in an arbitrary theory. Class of theories with bounded burden is called NTP₂ (no tree property of the second kind), and those with hereditarily finite burden are called strong. It was first considered by Shelah and attracted some attention recently. A classical theorem of Delon shows an Ax-Kochen type statement for the valued fields with respect to NIP, namely that if the residue field is NIP and the value group is NIP then the whole field is NIP. Recently Shelah showed that an analogous result holds with respect to strong dependence. Here we generalise it to burden. More precisely, we show that burden of the whole valued field is a linear combination of burdens of the residue field and the value group. In particular this implies that strongness and NTP₂ are preserved, and provides a new algebraic examples of strong theories, like ultraproduct of the p-adics.
• Franziska Jahnke
  A Galois Characterisation of the properties PAC and largeness
  abstract
• Noa Lavi
  Stellensatz on real closed valued fields
  A “nichtnegativstellensatz” in real algebraic geometry is a theorem characterizing algebraically those polynomials admitting only non-negative values on a given set. An original model theoretic proof for a nightnegativstellensatz is the generalization of A. Robinson of Hilbert's Seventeenth Problem (first solved by Artin) to real closed field. According to the work of G. Cherlin and M. Dickmann (using AKE theorems), the theory of real closed valued fields admits quantifier elimination, which allows model theoretic techniques for obtaining such results for definable sets of a real closed valued field. In my talk I will show such, demonstrating the connection between the order and the valuation.