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