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

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.

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.

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$.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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

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.

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.

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...)

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.

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.

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.

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

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}.

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.

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.

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...)

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.

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é.

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.

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' A_p 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.

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 (Z§N) 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