retour à la page du séminaire général


UNIVERSITE DE PARIS VII, UFR DE MATHEMATIQUES
  Séminaire général de Logique - Année 2001 - 2002


Responsables : J.-P. Ressayre, G. Sabbagh, P. Simonetta, S. Todorcevic



Lundi 8 octobre : Stevo TODORCEVIC (Université de Paris VII), The Erdös-Sierpinski duality of measure and category.

I will give an overview of the Erdös-Sierpinski duality principle which explains why many results about the Lebesgue measure have their conterparts for the Baire category of the real line. I will also give an overview of the relatively recent results related to this.


Lundi 15 octobre : Frank WAGNER (Université de Lyon I), Presque orthogonalité dans les théories simples.

Dans une théorie stable, si p et q sont deux types sur A tels que p est q-interne, alors le groupe (dit "de liaison") de permutations des réalisations de p induit par les automorphismes fixant A et les réalisations de q, est définissable, et décrit le comportement des paramètres nécéssaires pour témoigner l'internalité, si p est presque orthogonal à q. Je vais généraliser ce résultat aux théories simples, comme application du théorème de configuration de groupe.



Lundi 22 octobre : Anand PILLAY (University of Illinois, Urbana-Champaign), Jet spaces in differential and difference fields, and applications.

We use differential algebraic and difference algebraic analogues of the usual jet spaces and bundles, to give direct proofs of various (old and new) structural results for finite-dimensional differential and difference algebraic varieties. Included here are the "Zilber dichotomy" for rank 1 sets in the relevant structures.



Lundi 29 octobre : Gabriel DEBS (Université de Paris VI), Sur des propriétés de régularité des boréliens, non décidables dans ZFC

Rappelons qu'une fonction continue $f:X\to Y$ est dite propre si l'image réciproque par $f$ de tout compact de $Y$ est un compact de $X$; (on notera qu'il s'agit bien de compacts et non de fermés !).

Soit $f:X\to Y$ une fonction continue surjective entre deux boréliens (par exemple de $2^\omega$), et supposons que tout compact de $Y$ soit l'mage directe par $f $ d'un compact de $X$; peut-on trouver un fermé relatif de $X$ sur lequel la restriction de $f$ est surjective et propre ? On montre que la réponse à ce problème est positive si et seulement si $\aleph_1$ est inaccessible dans $L(\alpha)$ pour tout $\alpha$ réel.

Ceci rappelle un résultat bien classique de Solovay concernant la propriété da l'ensemble parfait pour les $\Pi^1_1$. On notera cependant deux différences importantes: (1) La propriété de régularité considérée ici porte sur les boréliens. (2) L'effectivité de la démonstration est non triviale dans les paramètres; plus précisement pour montrer la propriété lorsque $X$ et $Y$ sont des boréliens effectifs (`lightface') l'argument nécessite non seulement la dénombrabilité de $\aleph_1^L$ mais de $\aleph_\xi^L$ où $\xi<\omega_1^{CK}$ est la classe borélienne de $Y$.



Lundi 5 novembre : Rüdiger GÖBEL (Université de Essen), Splitters in group theory - on a question of Philip Hall

The talk is based on a joint paper with Saharon Shelah which will appear in Proc. Camb. Phil. Society. Using combinatorial arguments and a recent result concerning the existence of particular simple, infinite groups we will construct groups G with the property that any extension of G by G is isomorphic to G. The question about the existence of such groups goes back to lectures by Philip Hall in the 1960s and can be found in the Kourovka Notebook.



Lundi 12 novembre : Sandra QUICKERT (Université de Paris VII), Sacks forcing et la propriété de Sacks

On présentera le Sacks forcing (forcing avec des ensembles parfaits de réels) dont on étudiera quelques propriétés, et on examinera des relations entre quelques principes combinatoires et la propriété de Sacks.



Lundi 19 novembre : Marko DJORDJEVIC (Université de Paris VII), On the finite model property in countably categorical theories; a random approach

We will see that, in a binary language, every countably categorical simple theory of SU-rank 1 has the finite model property, i.e. every sentence of the theory is true in a finite model, which implies that the theory is not finitely axiomatizable. (Possibly I will also show the same for SU-rank 2.) The proof uses a basic probabilistic argument, the independence theorem for simple theories and a pebble game. This is part of ongoing work of mine towards proving that, in any relational language, a countably categorical simple theory of finite SU-rank has the finite model property; this would generalize all (to me) known results about the finite model property in the countably categorical case and include some new examples, obtained by the amalgamation constructions due to Hrushovski. It is worth noting that if this result is proved for a binary language then it follows, by using interpretations, for any relational language.



Lundi 26 Novembre : Paul-André MELLIES (Université de Paris VII), Logique linéaire et sémantique des jeux.

La sémantique des jeux prolonge la sémantique dénotationnelle dans son ambition de décrire algébriquement les démonstrations mathématiques et les programmes informatiques.
Chez Scott et Plotkin, un programme est une fonction continue entre domaines, qui transforment les valeurs d'entrée en valeur de sortie. Le temps ne joue aucun rôle.
En sémantique des jeux, au contraire, le temps est réintegré. L'interaction entre le programme et l'environnement s'exprime dans une partie où les joueurs alternent, chacun appliquant sa stratégie propre.
Dans mon exposé, je confronterai les deux formes de sémantique (jeux vs. domaines) et expliquerai comment les rapprocher en ``oubliant'' le temps dans les semantiques de jeux. J'expliquerai aussi pourquoi cette confrontation remet en cause, au delà des théorèmes de complétude forte, les représentations admises de l'interaction calculatoire.



Lundi 3 décembre : Arnaud DURAND (Université de Paris XII), Comptage, énumération et réduction

On cherche parfois à savoir non seulement si un problème donné à une solution mais aussi combien il en a. On parle dans le premier cas de problème de décision et dans le second de problème de comptage. Un fait notable, établi par L. Valiant est que deux problèmes de décision de complexité proche peuvent avoir des problèmes de comptage associés de difficulté très différentes. Cela sous-entend que réduire un problème de comptage (mais aussi d'énumération de solution) à un autre peut s'avérer délicat.
On rappelera, dans l'exposé, les principales notions liées au comptage et à l'énumération (formalisation d'un problème, définition des classes de complexité associées...) ainsi que les résultats les plus connus.
On présentera ensuite un certain nombre de problèmes ouverts tournant autour de la satisfaisabilité de formules booléennes et de la circonscription. Puis, on introduira une nouvelle méthode de réduction qui semble convenir assez bien aux problèmes de comptage.



Lundi 10 décembre : Samuel LACAS (Université de Paris VII), Extensionnalité, Définissabilité et prédicats de vérité en logique de second ordre.

Dans son article intitulé "A problem concerning the notion of definability" (JSL13), Tarski soulève plusieurs questions liées à la définissabilité de certaines classes d'ensembles. Suivant les travaux de L. Colson et S. Grigorieff à propos de la définissabilité en logique du second ordre (prédicats de vérité syntaxiques), je rappelerai quelques résultats et questions ouvertes autour de ce thème.



Lundi 17 décembre : Frank WAGNER (Université Lyon I), S'il existe une infinité de nombres premiers p-Mersenne, alors il n'y a pas de mauvais corps de caractéristique p.

Cet exposé remplace celui initialement prévu de K. Jaber, qui sera reprogrammé ultérieurement.



Lundi 7 janvier 2002 : Itay BEN YAACOV (Université Paris 7), Groupes, polygroupes, et épaississements dans les théories simples

Le problème de la construction d'un groupe à partir d'une configuration de groupe dans une théorie simple se ramène au problème de la construction d'un morceau générique de groupe a partir d'un morceau générique de polygroupe. Je vais décrire cette construction, qui nécessite la division par une certaine relation d'équivalence assez fine (le "noyau"), suivie par un épaississement.
En revanche, l'introduction des polygroupes pose de nouvelles questions, que l'on pourrait résoudre également à l'aide de cette construction. Je vais discuter des choix arbitraires impliques dans l'épaississement, et comment leur étude nous donne un théorème de structure pour les polygroupes sans noyau dans une théorie simple, ainsi qu'un théorème de Weil-Hrushovski pour des morceaux génériques de tels polygroupes.



Lundi 14 janvier : Eric JALIGOT (Université Paris 7), Groupes simples minimaux de rang de Morley fini

Un programme conséquent de recherche actuelle est la classification des groupes simples de rang de Morley fini, utilisant des idées de la classification des groupes simples finis. Parmi les configurations clés se trouvent les groupes simples minimaux de rang de Morley fini dont tous les sous-groupes propres et connexes sont résolubles. Je ferai le point sur l'état des connaissances concernant ces groupes.



Lundi 21 janvier : Hervé FOURNIER (LIP - ENS-Lyon), Rang de quantification pour la parité et la connexité

On considère un graphe fini plongé dans les réels ou les complexes avec diverses opérations. Motivés par le modèle des bases de données contraintes, de nombreux travaux ont été menés pour déterminer quelles propriétés du graphe on peut exprimer avec la logique du premier ordre. La réponse est qu'on ne peut pas exprimer plus de propriétés qu'au premier ordre sur un graphe (sans structure sous-jacente). La question que j'étudie est savoir si la présence des réels ou des complexes permet de diminuer le coût d'expression de certaines requêtes. La mesure du coût choisie est celle du rang de quantification.



Lundi 28 janvier : Markus JUNKER (Universität Freiburg), Sur les graphes omega-stables

Je présenterai les vieux et quelques nouveaux résultats sur la stabilité des graphes



Lundi 4 février : Alain LOUVEAU (Université Paris 6), Relations d'équivalence analytiques complètes

Je présenterai un certain nombre d'exemples naturels, tirés de la théorie des modèles et de l'analyse, de relations d'équivalence analytiques qui sont complètes, c'est-à-dire maxima pour l'ordre de réduction borélienne - ce qui heuristiquement signifie que le probleme de classification associé est de complexité maximale. Il s'agit d'un travail avec Christian Rosendal.



Lundi 11 février : Francisco MIRAGLIA (Sao Paulo), Special Groups : An overview

I shall present a survey the theory of Special Groups, developed by Dickmann and myself, together with several applications to problems in the theory of quadratic forms, including the solution of the conjectures of Marshall and Lam.



Lundi 18 février : Luc SEGOUFIN (INRIA), Logique sur les mots : de la théorie des modèles à celle des automates

On étudiera dans cet exposé plusieurs théories du premier ordre sur des mots d'un alphabet fini. On verra que certaines possèdent des propriétés intéressantes aussi bien du point de vue théorie des modèles (élimination des quanteurs, dimension VC finie) que du point de vue de la théorie des automates (langages réguliers, *-free etc...)



Lundi 25 février : Khaled JABER (Université de Mons-Hainaut), Problèmes équationnels en théorie des modèles

Cherlin et Zil'ber ont conjecturé que les groupes simples et infinis de rang de Morley fini devraient être des groupes algébriques sur des corps algébriquement clos. Si cette conjecture était vraie, on devrait pouvoir retrouver, sur un tel groupe sa topologie naturelle de Zariski. En utilisant la notion de formules génériques faisant sens dans les groupes stables (une généralisation des groupes de rang de Morley fini), on définira une topologie sur un groupe stable et on discutera le problème de savoir si les équations au sens usuel du terme définissent bien des fermés dans cette topologie.



Lundi 4 mars : Mirna DZAMONJA (University of East Anglia), Universal models

We discuss various aspects of the problem of looking for universal models, starting from a motivation in model theory and then showing how set theory enters the question. We show how some of the techniques developed for the aspect of the question that is relevant to the first order model theory have been applied to problems outside of the realm of model theory, e.g. in analysis.



Lundi 11 mars : Boris ZILBER (University of Oxford), Classical analytic structures and Shelah's excellent classes

I am going to start with a discussion of Hrushovski's construction, by means of which he constructed 'new stable structures', refuting my Trichotomy conjecture. I want to show how this construction gives rise to pseudo-analytic structures, strikingly similar to classical structures on complex manifolds, and gives a new meaning to Schanuel-type conjectures in transcendental number theory. Finally, I am going to explain that the model theory of these structures can be carried out in terms of Shelah's excellent theories in infinitary languages.



Lundi 18 mars : Jordi LOPEZ ABAD (Université Paris 7), Canonical partitions of FINk

We give a generalization of the results of A. Taylor about canonical equivalence relations on FIN, and we obtain the canonical list for FINk. This is very related to the study of how the partitions of the unit sphere of c0 are.



Lundi 25 mars : John TRUSS (University of Leeds), Les ordres linéaires colorés dénombrables 1-transitifs

On donne une classification de tous les ordres linéaires colorés dénombrables 1-transitifs. C'est une généralisation de la classification de Morel des ordres linéaires dénombrables 1-transitifs. Pour les ensembles de couleurs finis il y a \aleph_1 exemples, mais pour un ensemble de couleurs de cardinalité \aleph_0, il y en a 2^{\aleph_0}.



Lundi 8 avril : Thomas BLOSSIER (Université de Rouen), Groupes d'automorphismes de structures fortement minimales triviales

On présentera un théorème de reconstruction d'une structure fortement minimale triviale sans élément algébrique, à partir du triplet de groupes d'automorphismes suivant : le groupe des automorphismes de la clôture algébrique d'un point, le sous-groupe fixateur de ce point et le sous-groupe des automorphismes forts.



Lundi 29 avril : Ali NESIN (Istanbul Bilgi University, et Université Lyon I), Groupes de rang de Morley fini, une vue générale

Nous allons revoir les progrès spectaculaires réalisés dans les vingt dernières années dans l'étude des groupes simples de rang de Morley fini.



Lundi 6 mai : Jean-Pierre RESSAYRE (Université Paris 7), Winning Strategies for Infinite Games: from large cardinals to effective results.

1. Set Theory's topic of Large Cardinals is the most infinitary} part of Maths. At the other end, the study of finite state machines is the very first chapter of Computer Science. Can we combine these two opposite extremes fruitfully and use ideas coming from large cardinals to produce results about finite state machines ?

2. Using the (large cardinal) axiom "#", Martin proved analytic determinacy: the existence of a winning strategy for one of the players in every infinite game of perfect information between two players, provided the winning set of one of the players happens to be an analytic one. I modify and complement his proof so as to obtain a new proof of the Rabin, Buechi-Landweber, Gurevich-Harrington theorem of finite state determinacy : existence of a winning strategy computed by a finite state machine, when the player's winning sets are themselves finite state accepted. This 4th proof of finite state determinacy is again a totally new one -- as must be the case since it still makes use of the large cardinal axiom ``#'', to prove such an effective result !

3. To our question (1) the new proof gives an answer which is positive yet of modest bearing, since it only concerns an old result. But adding to this proof an effective elimination of the very restricted part of "#" that it really uses, should lead to useful new results and methods concerning the abstract synthesis of finite state or pushdown non terminating processors. The ideas for this projected development are sketched in conclusion. (Of course our use of "#" is eliminated in advance in 3 ways : namely the 3 former proofs of Rabin, of Buechi-Landweber and of Gurevich-Harrington. But none of them seems to be as appropriate as the above one to feasible applications...)



Lundi 13 mai : Christophe DURR (Université d'Orsay), Tomographie discrète

Dans cet exposé je donnerais un apperçu sur certains résultats sélectionnés d'un domaine intitulé Tomographie discrète. Il s'agit du problème de reconstruction de matrices à partir de leur projections sur les colonnes et les lignes. Je parlerais d'abord sur le problème de base étudié par Ryser en 1957, qui consiste à trouver une matrice ne contenant que des 0 ou des 1's et qui a des sommes sur les lignes et sur les colonnes spécifiées. Puis je parlerais sur la reconstruction de tel matrices avec certaines propriétés supplémentaires, pour finir sur la reconstruction de pavages.



Lundi 3 juin : Guillaume MALOD (Université Lyon 1), Un polynôme et ses coefficients

Le but de cet exposé est de comparer la complexité de calcul d'un polynôme et de sa fonction coefficient. Les classes de complexité de Valiant fournissent un bon cadre pour cette étude. Cet exposé ne contient pas de logique mais ne nécessite pas de connaissances profondes en complexité.



Lundi 10 juin : Ilijas FARAH (CUNY, IHES), Rigidity of Quotient Boolean algebras

Consider P(N), the power-set of the natural numbers, as a Boolean algebra. A subset I of P(N) is an ideal if it is closed under taking subsets and finite unions of its elements. (Equivalently, if it is an ideal of the corresponding Boolean ring.)
Question: How does a change of the ideal I affect the change of its quotient algebra P(N)/I?
This question can be considered in several different contexts. I will survey the current state of knowledge, as well as other applications of the methods pertinent to this question.



Lundi 17 juin : Hans SCHOUTENS (Ohio State), Non-standard methods in commutative algebra

Tight closure theory is a fairly new development in commutative algebra initiated by Hochster and Huneke at the end of the '80's. It uses properties of the Frobenius in positive characteristic and then lifts these results to characteristic zero using reduction techniques and Artin Approximation. This yields an extremely powerful method which allows one to prove many deep theorems with relative ease, at least in positive characteristic; the zero characteristic case requires typically additional work. Another important construction in positive characteristic is Hochster's big CM modules, later improved by Hochster-Huneke to big CM algebras. These also exist in zero characteristic, but again the method is complicated and in the process, one looses many of the good properties.

I will explain how one can circumvent these complications in lifting results to zero characteristic by means of ultraproduct constructions. This works especially well for finitely generated algebras A over the complex numbers, in which case one takes certain characteristic p `approximations' Ap on which the Frobenius acts or for which big CM algebras are constructed canonically by taking the absolute integral closure, and then applies an ultraproduct to this data to obtain similar data in zero characteristic. In particular, the non-standard Frobenius can now be used to define tight closure on A. This leads to more accessible proofs of the Briancon-Skoda Theorem, the Hochster-Roberts Theorem, Boutot's Theorem on rational quotient singularities, Falting's connectedness Theorem, classification of log-terminal and log-canonical singularities, Kodaira vanishing, and many more.



Lundi 24 juin : Anatole KHELIF (Université Paris 7), Un groupe polonais non dénombrable ne peut pas être presque libre

Dans le cas abélien, on sait qu'un groupe libre non dénombrable ne peut pas être un groupe polonais: c'est la même démonstration que dans le cas non abélien (Shelah). Nous nous proposons de donner cette démonstration dans une première étape.
Appelons presque libre un groupe dont tous les sous-groupes dénombrables sont libres. Dans le cas abélien (ZN) on sait que des groupes presque libres non dénombrables peuvent être polonais, ce qui s'avèrera faux dans le cas non abélien.



Page maintenue par G. Malod