Lundi 6 octobre 2008 : Max Dickmann (Equipe de logique de Paris 7) Anti-chaines dans les ordres partiels et algebres de Heyting
L'idee d'ordonner l'ensemble des anti-chaines d'un ensemble partiellement ordonne est assez ancienne; les premiers resultats significatifs datent de 1960. J'exposerai d'abord quelques-uns des resultats connus dans ce domaine. Ensuite je ferais une introduction rapide aux algebres de Heyting et leurs modeles les plus connus, tracant leur origine dans la logique intuitioniste. Ensuite j'esquisserai quelques idees de la preuve du resultat suivant: l'ensemble des anti-chaines d'un systeme de racines (ou un arbre) bien fonde, muni de son ordre le plus habituel, est une algebre de Heyting complete. Je montrerai que ces algebres ont une representation topologique fidele et je discuterai des possibles generalisations de ce resultat.
Lundi 20 octobre 2008 : David Duris (Equipe de logique de Paris 7) Préservation par extension en théorie des modèles finis
D'importants outils de la théorie des modèles (compacité, complétude) ne sont plus valides quand on se place dans la classe des modèles finis. En conséquence, la théorie des modèles finis a ses propres techniques et résultats. Notamment, Tait (1959) a montré que le théorème de préservation par extension était faux sur la classe des modèles finis. Cependant, Atserias, Dawar et Grohe (2005) ont récemment montré que ce théorème devenait vrai sur des classes de modèles finis particulières. L'une d'entre elles est la classe des modèles finis avec des relations d'arité au plus 2 et formant un graphe acyclique. Il existe pourtant des définitions (non équivalentes) de l'acyclicité pour des relations d'arité quelconque (Berge, gamma, beta et alpha-acyclicité). Dans cet exposé, on montre que le théorème de préservation par extension est vrai aussi sur les classes de structures finies Berge et gamma-acycliques et qu'il est faux dans les autres cas. Pour cela, on utilise des méthodes combinatoires, une réduction logique et des jeux EF.
Lundi 10 novembre 2008 : Klaas Pieter Hart (Technische Universiteit Delft, Pays Bas) The Löwenheim-Skolem theorem has been very good to me
The Löwenheim-Skolem theorem has proved to be a very useful tool in the study of compact Hausdorff spaces. It usually enables one to reduce a question about arbitrary compacta to one about metrizable ones. I will describe a few instances of its efficacy: in Dimension theory and in Continuum theory.
Lundi 17 novembre 2008 : Alexander Berenstein (Universidad de los Andes, Bogota / Lyon 1) Lovely pairs of dependent theories
A structure is geometric if it eliminates the quantifier exists infinity and for any model of its theory, the algebraic closure has the exchange property. Examples include models of strongly minimal theories, dense O-minimal theories and the p-adics. In this talk we will talk about lovely pairs of geometric structures. We show that if T is (strongly) dependent then the corresponding theory of lovely pairs T_p is (strongly) dependent. This is joint work with Alf Dolich and Alf Onshuus.
Lundi 24 novembre 2008 : Barnaby Martin (Equipe de Logique, Universite Paris 7) Parameterized Proof Complexity
The origins of Proof Complexity lie largely in the program of Cook and Reckow, who aimed to separate P and NP (actually, coNP and NP) by proving that no propositional proof system is polynomially bounded. Having failed to obtain such a general result, students of Proof Complexity have instead focused on proving that stronger and stronger proof systems are not polynomially bounded. Such lower bounds are known for systems such as Resolution and Bounded-depth Frege. Resolution is in fact a refutation system in which one proves that a propositional formula in CNF is a contradiction. A classic result from the area concerns the tree-like restriction of Resolution. Riis proved that contradictions that uniformly encode a first-order principle without finite models over a universe of size n either 1.) have refutations of size n^{O(1)} or 2.) require size 2^{en} for some positive e. The latter case prevails precisely when the first-order principle has an infinite model. We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional CNF formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter (we call such a formula a parameterized contradiction). One could separate the parameterized complexity classes FPT and W[2] by showing that there is no fpt-bounded proof system, i.e., that there is no proof system that admits proofs of size f(k).n^{O(1)} where f is a computable function and n represents the size of the propositional formula.
By way of a first step, we introduce the system of parameterized tree-like resolution, and show that this system is not fpt-bounded. Indeed we give a general result that splits the exponential case of Riis's Complexity Gap Theorem into two sub-cases. Parameterized contradictions that uniformly encode a first-order principle, without finite models but with some infinite model, over a universe of size n, either 2a.) have refutations of size f(k).n^{(O(1)} or 2b.) require size n^{k^e} for some positive e. The latter case prevails precisely when the first-order principle has some model without a finite dominating set.
Lundi 1er décembre 2008 : Bijan Afshordel (Universität Freiburg, Allemagne) Generic automorphisms with prescribed fixed structures
Generic automorphisms of fields have been studied since the 1990's. The fixed field of a model of ACFA is a pseudofinite field, and to a given pseudofinite field K there is some model of ACFA whose fixed field is elementarily equivalent to K. We show, in a more general context, that this can be strengthened to identity: there is a model of ACFA whose fixed field is K.
Lundi 8 décembre 2008 : Natasha Dobrinen (University of Denver, États-Unis) The tree property
A well-known lemma of König states that each infinite tree which is finitely branching has an infinite path. The natural generalization of this statement to trees of height ω1 is not true: Aronszajn constructed a tree of height ω1 each of whose levels is countable, but which has no cofinal path. When one tries to generalize to uncountable cardinals greater than ω1, the story becomes more complex - perhaps surprisingly, large cardinal axioms come into play. A tree T is a κ-tree if the height of T is κ and each level of T has cardinality less than κ. We say that the tree property holds at an infinite cardinal κ (TP(κ)) if each κ-tree has a cofinal path. We discuss the large cardinal axioms needed for the tree property to hold at various uncountable cardinals, culminating in some joint work with Sy-David Friedman, finding the exact consistency strength of TP(κ++) where κ is a measurable cardinal.
Lundi 15 décembre 2008 : Angus Macintyre (University of London, Royaume-Uni) Zilber's exponential: Definable sets and decision problems
I will survey what is known about Ziber's exponential fields (contrasting where possible with the case of the complex exponential) with particular emphasis on the structure of definable sets.
Lundi 19 janvier 2009 : Michael Pinsker (Universite de Caen) Clones on infinite sets
For a fixed infinite set X, consider all algebras with domain X, and
order them according to the rule ``an algebra A is greater than or
equal to an algebra B iff A generates all operations of B as term
operations''. Factoring this quasiorder on the set of all algebras by
term equivalence, one obtains a complete lattice, the so-called clone
lattice. Its elements are called clones; in other words, a clone is a
set of term equivalent algebras with domain X.
Recently, a considerable number of results on the structure of the
clone lattice has been obtained by tools from set theory. In my talk,
I will summarize the results proven by such methods.
It is also a recent discovery that clones can be used in order to
classify reducts of omega-categorical (relational) structures up to
primitive positive interdefinability; thus they have applications in
model theory. A further new application of clones is one to a certain
complexity question from theoretical computer science, the so-called
Constraint Satisfaction Problem. In the second part of my talk, I will
outline as many of these connections as possible.
Lundi 2 février 2009 : Julien Melleray (Universite Lyon I) Une reformulation, et une nouvelle preuve, d'un théorème d'oscillation de Hjorth
Il y a quelques années, G. Hjorth a établi un théorème d'oscillation pour les groupes polonais, répondant ainsi à une quesiton de V. Pestov. Il a donné une preuve relativement simple, basée sur la théorie des modèles, de ce théorème dans le cas particulier des sous groupes fermés du groupe de permutation des entiers naturels. La preuve du résultat dans le cas général est nettement plus complexe et technique, et son lien avec la théorie des modèles n'est pas clair. Dans cet exposé, je proposerai une reformulation du résultat de Hjorth dans le contexte des structures métriques; cette reformulation fait le lien avec la preuve "modèle-théorique" évoquée plus haut, et admet une preuve relativement élémentaire.
Lundi 30 mars 2009 : Itay Kaplan (Hebrew University, Jerusalem) Finding Indiscernibles in Dependent theories (joint work with S. Shelah)
Consider the following problem: given a long sequence of elements from the monster model, is it possible to find a sub-sequence which is indiscernible? In a stable theory the answer is yes. In a strongly dependent theories the answer is also yes. For a long time Shelah believed that the answer is yes in the general dependent context. In this talk we will show a counter-example for this conjuncture.
Lundi 6 avril 2009 : Itay Kaplan (Hebrew University, Jerusalem) Todor Tsankov (Institut de Mathématiques de Jussieu)
A countable relational structure is called automatic if there exists a coding of the elements of its domain by strings in a finite alphabet so that both the domain and the relations are regular languages (recognized by finite automata). One can transfer the definition to languages with function symbols by considering the graphs of the functions. The prototypical example of an automatic structure is the group of integers (Z, +), where each integer is coded by its decimal representation. Structures that admit an automatic representation have very nice computational properties: their first order theory (even allowing some additional quantifiers) and model checking problem are decidable in a simple manner.
The main result of the talk is that the additive group of the rationals does not have such a presentation. This answers a question of Khoussainov and provides the first example of a finite rank abelian group which is not automatic. The ideas and methods of the proof come from additive combinatorics and the proof relies most notably on Freiman's structure theorem for sets with small doubling constant. The talk will be accessible to all: in particular, I will not assume any background in either automata theory or additive combinatorics.
Lundi 4 mai 2009 : Julien Melleray (Universite Lyon I) Une reformulation, et une nouvelle preuve, d'un théorème d'oscillation de Hjorth
Il y a quelques années, G. Hjorth a établi un théorème d'oscillation pour les groupes polonais, répondant ainsi à une quesiton de V. Pestov. Il a donné une preuve relativement simple, basée sur la théorie des modèles, de ce théorème dans le cas particulier des sous groupes fermés du groupe de permutation des entiers naturels. La preuve du résultat dans le cas général est nettement plus complexe et technique, et son lien avec la théorie des modèles n'est pas clair. Dans cet exposé, je proposerai une reformulation du résultat de Hjorth dans le contexte des structures métriques; cette reformulation fait le lien avec la preuve "modèle-théorique" évoquée plus haut, et admet une preuve relativement élémentaire.
Lundi 11 mai 2009 : Itai Ben Yaacov (Universite Lyon I) Sur les groupes d'automorphismes des structures métriques aleph_0-catégoriques
Je parlerai des aspects modèle théoriques d'un projet en cours avec A Berenstein et J Melleray. La motivation pour ce projet vient des résultats de la théorie descriptive des ensembles relatifs aux groupes polonais, telles la continuité automatique et l'existence d'amples génériques. Nous cherchons à étendre ces résultats à une plus grande classe de groupes, comprenant également les groupes d'automorphismes de structures métriques. La considération de tels groupes implique un nouveau type d'interaction entre la topologie polonaise d'un côté et une métrique qui la raffine d'un autre côté (un phénomène qui n'est point nouveau du point de vue de la théorie des modèles des structures métriques).
Lundi 15 juin 2009 : Arno Fehm (Tel Aviv University) Local-global principles and decidable theories of fields of algebraic numbers
We recall some classical local-global principles for fields, like pseudo real closed fields (PRC) and pseudo p-adically closed fields (PpC), and give a common generalization of these - PSC fields. The main goal of this talk is to indicate a systematic proof that the class of PSC fields is elementary. One application of the axiomatization of the PSC property is a new decidability result for certain fields of totally S-adic algebraic numbers, combining and generalizing results of Jarden-Kiehne, Fried-Haran-Völklein, and Ershov. We also give a positive answer to a conjecture of Darniere concerning the 'mixing' of orderings and valuations.
Lundi 29 juin 2009 : Artyom Chernikov (Humboldt-Universitaet zu Berlin) Towards the dependence spectra
Stability was a major success of pure model theory. One of the reasons why this dividing line is so important and useful stems from the fact that it can be characterized in many quite different ways - both internally (inability of the theory to encode linear order) and externally (type spaces are small). Recently a generalization of stable theories, dependent theories, attracted a lot of attention. They tend to have many types in general, but morally not too many. In the talk we are considering possible ways to count types in dependent theories and possible definitions of kappa-dependence, super-dependence and dependence spectra parallel to the stable situation.