Retour à la page du séminaire général. Archives: Années 00-01, 01-02, 02-03, 03-04, 04-05, 05-06, 06-07.

  Séminaire général de Logique - Année 2007 - 2008

Responsables : A. Durand, J. Lopez-Abad, P. Simonetta, S. Todorcevic
Pour recevoir le programme par email, écrivez à :


Lundi 8 octobre 2007. M. Bodirsky (Humboldt-Universität zu Berlin) The reducts of some famous omega-categorical structures up to primitive positive interdefinability and applications in complexity theory

In model-theory, structures are usually considered up to first-order interdefinability. But if we are interested in the constraint satisfaction problem (CSP) of a relational structure, we need to understand relational structures up to primitive-positive definability, i.e., we only use definitions without disjunction, negation, and universal quantification.
For omega-categorical structures Gamma, primitive positive definability in Gamma can be characterized by preservation under homomorphisms from finite directs products of Gamma to Gamma. This allows us to use universal-algebraic techniques to classify primitive-positive reducts of famous omega-categorical structures, such as (Q,<), the countable homogeneous poset, vector spaces over finite fields, the countable atomless boolean ring with or without identity element, various semilinear orders etc.
The CSPs of these reducts are well-studied computational problems with many applications in computer science. We finally discuss the question whether there are CSPs for omega-categorical structures that are in NP, but neither in P nor NP-complete.

Lundi 22 octobre 2007. G. Asatryan. (Université de Mons-Hainaut) The equational theory of Tarski's system. Models of exponentiation

Tarski (in 1960's) introduced an equational system (in the language including addition, multiplication and exponentiation) which consists of eleven basic identities of the set of positive integers. We investigate the so called "natural" models of Tarski's system (the elements in such a model are structures that decompose into sums of components). We prove that the Wilkie's identity holds in those natural models where each element has finite decomposition into components. Farther, we construct a bunch of "atomic-structured" algebras that satisfy all the identities of positive integers. Then, we show that the algebra of finite posets locally has atomic structure, and as a consequence, we obtain that it satisfies a wide range of identities. We also prove that the algebra of cardinal numbers satisfies all the identities of positive integers.

Lundi 5 novembre : Hugo Mariano (Paris 7) On Profinite Special Groups

This work is a development of some logical-categorial aspects of the theory of Special Groups -- a first order presentation of the algebraic theory of quadratic forms. We study the Profinite Special Groups -- certain kinds of limits that the Special Groups category has. We build a functor from the category RSG of reduced special groups with SG-morphisms to the category RSG_{pf} of profinite reduced special groups with continuous SG-morphisms. We verify that this functor deserves the title of ``profinite hull functor'': it is the left adjoint of the inclusion RSG_{pf} \hookr RSG. We analyze the behavior of this functor by categorial constructions: we show that it preserves quotients and complete embeddings. We present the concept of a subform-reflecting morphism between special groups and we show that the natural transformation that is the unit of such adjunction is composed by this kind of morphisms: this shows that the profinite hull construction is finer that the boolean hull construction. We identify this arrow in the case of the special group that came from a boolean algebra with the boolean algebras morphism that generates the topology on the respective Stone space and we study the interaction between the profinite hull and the boolean hull constructions of reduced special groups. Finally we sketch some ideas of how, possibly, we may get a positive answer for the representation problem of profinite reduced special groups as a pythagorean field special group, by basic model-theoretic tools.

Lundi 12 novembre : N. Jones (Université de Copenhague) The spectrum problem from a computer science perspective.

Scholz posed in 1952 the problem of characterising the class of spectra (of formulas in first-order logic with equality), and there soon after came interesting related questions by Asser, Bennett, Mostowski, etc. Alan Selman and I discovered an exact characterisation of spectra (first published in STOC in 1972).
The problem resembled the "LBA problem" then widely studied in theoretical computer science. Spectra had properties very similar to the context-sensitive languages but turned out to be different: A set is in NEXPTIME iff it is a spectrum (represented as a set of binary numbers). Such a characterisation would not have been naturally expressible prior to the development in the late 1960s of time- and space-bounded complexity classes.
Since then a wide range of research has been done in finite model theory, datalog, programming languages and "implicit complexity", to name a few closely related topics. A natural next question from a computer science background: what is the expressive power of various subrecursive programming languages? This brings up questions of the effects of imposing limits on stored data and on control structures, e.g. WHILE versus FOR-loops. The talk concludes with an array of known results, points out some regularities, and a tantalising and still not satisfactorily understood fact: that primitive recursion as a control structure seems in some sense inherently less expressive than general recursion or even tail recursion.

Lundi 26 novembre : Salma Kuhlmann (U. Saskatchewan / IMJ) Exponential-Logarithmic vs. Logarithmic-Exponential

(joint work with Marcus Tressl) We explain how the field of logarithmic-exponential series constructed in [DMM] and [DMM2] embeds as an exponential field in any field of exponential-logarithmic series (constructed in [KK1], [K] and [KS]. On the other hand, we explain why no field of exponential-logarithmic series embeds in the field of logarithmic-exponential series. This establishes that the two constructions are intrinsically different, in the sense that they produce non-isomorphic models of T_{an, exp}.

Lundi 3 décembre : Kathryn Vozoris (Université de Mons) The Complex Field with a Predicate for the Integers

There are many intriguing, open questions related to the complex field with exponentiation. The integers are definable in this structure, making the complex field with a predicate for the integers an interesting object to consider. Although the complex field with a predicate for the integers is an unstable structure, we are still able to give a reasonable description of its theory and definable sets. I will discuss model theoretic properties of the theory, and some results on definability.

Lundi 17 décembre : Pandelis Dodos (Université de paris VI)

Lundi 14 janvier :  A. Borovik (University of Manchester) Between proof and computation - (finite) black box groups and (infinite) groups of finite Morley rank

Lundi 21 janvier :  R. Bonnet (Université de Savoie) Sur les sous-espaces fermes de $(\omega_1+1)^2$

On sait que tout sous-espace fermé de $ \omega_1 + 1 $ (muni de la topologie des intervalles) est homéomorphe a un ordinal successeur $ \alpha + 1 $ ou $\alpha \leq \omega_1$. On explicitera (sans le démontrer) $ 2^{\aleph_1} $ sous-espaces fermés deux à deux non homéomorphes dans l'espace produit $ (\omega_1 + 1) \times (\omega + 1)$. Maintenant, l'ensemble $X := (\omega_1 + 1) ^ 2 $ est muni d'une part de la topologie produit (appelée plan de Tikhonov) et d'autre part de l'ordre produit (qui est en fait un treillis distributif: $\inf \{ (x,y) , (u,v) \} = ( \min(x,u) , \min(y,v) \}$ et $\sup \{ (x,y) , (u,v) \} = ( \max(x,u) , \max(y,v) \}$ ). En tant que treillis topologique, $X$ possède $\aleph_1$ sous-treillis fermés (non dénombrable) a l'homéomorphie près -on oublie l'ordre- qui sont les suivants: - $ (\omega_1 + 1) \times (\alpha + 1)$ où $\alpha \leq \omega_1$ , et - $\{ (u,v) \in X : u \leq v \leq \omega_1 $ (qui est le triangle). La preuve fait appel à peu de connaissances en théorie des ensembles. Bibliographie: Robert Bonnet, Latifa Faouzi, Wies{\l}aw Kubi\'s: Free Boolean algebras over unions of two well orderings a paraitre dans Topology and its Applications.

Lundi 11 février : O. Finkel (ENS de Lyon) Complexité topologique des oméga-puissances

(Travail en collaboration avec Dominique Lecomte)
Cet exposé se situe dans les domaines de la théorie descriptive des ensembles et de la théorie des automates. On considèrera tout d'abord  l'acceptation de mots infinis par des machines finies avec les conditions usuelles de Büchi ou de Muller. L' ensemble des mots infinis sur un alphabet fini étant naturellement muni de la topologie usuelle de Cantor,l'ensemble des Boréliens de cet espace topologique est alors défini à partir de l'ensemble des ouverts par opérations successives d'unions et d'intersections dénombrables. On rappellera en particulier le résultat surprenant suivant: du point de vue de la complexité topologique des omega-langages acceptés, un automate à un compteur suffit à obtenir toute la complexité d'une machine de Turing. On considèrera ensuite les oméga-puissances qui sont des oméga-langages particuliers apparaissant très naturellement dans la caractérisation des oméga langages réguliers ou algébriques. L'oméga-puissance V^\oméga est l'ensemble des mots infinis  obtenus par concaténation infinie de mots finis d'un  langage V de mots finis. La question de leur  complexité topologique a été posée par Niwinski (1990), Simonnet (1992)  et Staiger (1997). On montrera le résultat très surprenant suivant : Pour chaque classe Borélienne B ( \Pi0_\alpha ou \Sigma0_\alpha pour un ordinal dénombrable \alpha), il existe une oméga-puissance B-complète pour la réduction par fonctions continues. Ce résultat a aussi des aspects effectifs.

Lundi 25 février : F. Delon (Equipe de logique de PARIS 7) Structures C-minimales

Une C-relation est une relation ternaire permettant d'interpréter un arbre dans lequel deux éléments ont toujours une borne inférieure et sans branche isolée. Un ensemble M muni d'une telle relation, et éventuellement de structure supplémentaire, est dit C-minimal lorsque toute partie définissable de M est définissable sans quantificateurs avec la seule C-relation, et si cette propriété reste vraie dans toute structure élémentairement équivalente. L'analogie avec l'o-minimalité est claire et une partie des développements de l'o-minimalité peuvent être reproduits. Néanmoins la prudence s'impose, par exemple, si dans une structure linéairement ordonnée toute partie définissable est combinaison booléenne d'intervalles et de points, cela reste vrai dans toute structure élémentairement équivalente. Rien de semblable pour les structures C-minimales. Ou encore: une structure C-minimale n'a pas nécessairement la propriété de l'échange. Nous parlerons de ces propriétés et présenterons quelques exemples de structures C-minimales et quelques résultats.

Lundi 17 mars 2008 : A. Prouté (Equipe de logique de PARIS 7) Un petit aperçu de la logique catégorique et application à l'informatique

On montrera comment en redéfinissant certaines constructions ensemblistes sans parler d'éléments, on aboutit à la notion de 'topos élémentaire' (Lawvere-Tierney). En parallèle, on examinera un des exemples les plus simples de topos dont la logique n'est pas classique. On verra ensuite pourquoi chaque topos a une logique qui lui est propre, et on obtiendra une définition très 'économique' de la notion de preuve, non sans analogie avec la correspondance de Curry-Howard et en lien avec l'axiome d'indiscernabilité des preuves. Pour finir on discutera les applications informatiques et le comportement de l'axiome du choix dans les calculs.

Lundi 31 mars 2008 : Karim Er-Rhaimini (Equipe de Logique de Paris 7) Structures PCF et arithmétique des cardinaux

A la fin des années 80 Shelah a développé la théorie PCF dont le résultat le plus célèbre est que $2^{\aleph_\omega} < max(2^{aleph_0}^+ , \aleph_{omega_4}). A l'heure actuelle, on ne sait toujours pas si cette borne peut être améliorée ou non. Le but de l'exposé est de présenter les hypothèses que Shelah a utilisé pour sa preuve et savoir si avec celles-ci le résultat est optimal. On présentera les résultats déjà obtenus ainsi que les perspectives et les difficultés qui émergent lorsque l'on tente de s'approcher du mystérieux "4".

Lundi 14 avril 2008 : Tamara Servi (Universités de Ratisbonne et de Mons) Definably complete and Baire structures: applications

We consider definably complete and Baire expansions of ordered fields: every definable subset of the domain of the structure has a supremum and the domain can not be written as the union of a definable increasing family of nowhere dense sets. Every expansion of the real field is definably complete and Baire. So is every o-minimal expansion of a field. The converse is clearly not true. However, unlike the o-minimal case, the structures considered form an elementary class. We give an application to the Pfaffian closure of an o-minimal structure.

Lundi 5 mai 2008 : Jean Pierre Ressayre (Equipe de Logique de Paris 7) L'approche non standard de la Complexite Algorithmique

Les modèles non standards apportent notamment les possibilités suivantes:
1) démontrer des résultats d'indépendance concernant les questions de Complexité.
2) suggérer des algorithmes (de calcul sur les réels, de modélisation etc.) qui contournent certaines bornes inférieures de complexité.
3) suggérer de bons développements "purs" nouveaux ( afin de résoudre les problèmes posés par le développement de (1) et (2) ).
Ce sera illustré par divers nouveaux résultats dont la preuve est non standard; en particulier on réduit à P certaines sous-classes de NP inter co-NP.

Lundi 16 juin 2008 : Cédric Milliet (Université de Lyon I) Relations d'équivalence et groupes infiniment définissables dans une théorie menue.

Il arrive que dans une théorie l'on trouve des groupes infiniment définissables (définissables par une infinité de formules). De tels groupes ne sont pas en général l'intersection de groupes définissables. Mais c'est le cas dans une théorie stable (Hrushovski [Poi]).
[Kim] a montré que dans une théorie menue (une théorie n'ayant qu'un nombre dénombrable de types sur le vide), une relation d'équivalence (finitaire, sans paramètres) infiniment définissable est intersection de relations d'équivalences définissables. Nous en déduisons que dans une théorie menue, un groupe (respectivement un corps) infiniment définissable est intersection de groupes (de corps) définissables. Nous généralisons le résultat a préodre, monoïde et anneau.

[Kim] B. Kim, A Note on Lascar Strong Types in Simple Theories, The Journal of Symbolic Logic, vol. 63, n.3, 1998.
[Pil&Poi] A. Pillay et B. Poizat, Pas d'imaginaires dans l'infini, The Journal of Symbolic Logic, vol 52, n.2, Juin 1987
[Poi] B. Poizat, Groupes Stables, Nur Al-Mantiq Wal-Ma'rifah, 1987.

Lundi 23 juin 2008 : Amador Martin Pizarro (Université de Lyon I) Le groupe de Baudisch

Dans les années 90, Baudisch réussit à construire un collapse d'une structure sur une géométrie non-triviale après la technique développée par Hrushovski. Dans ce cas, il a construit un groupe de rang de Morley fini nilpotent de classe $2$ qui n'interprète pas de corps. Néanmoins, la methode utilisée n'était pas bien assimilée à l'époque et donc elle restait obscure. Le but  ce cet exposé est de présenter la construction d'une façon simplifiée et accessible, à la sauce berlinoise.

Page maintenue par G. Malod