Séance spéciale de rentrée Vendredi 17 septembre (heure et salle à préciser) : Vladimir PESTOV (Université d'Ottawa, Canada) Propriétés dynamiques de groupes de dimension infinie et résultats de type Ramsey.
Je présenterai un survol des liens récemment découverts entre les propriétés dynamiques de groupes topologiques "de dimension infinie", les propriétés de type Ramsey et la géométrie des structures des hautes dimensions.
Le concept central est ceci d'un groupe topologique extrêmement moyennable (possèdant la propriété du point fixe sur les espaces compacts).
L'exposé comprendra cinq parties: (i) les groupes extrêmement
moyennables et la propriété de Ramsey-Dvoretzky-Milman; (ii) le
phénomene de concentration de la mesure et les groupes de Lévy (Gromov
et Milman);
(iii) liens avec la théorie de Ramsey structurelle; (iv) résultats de
Glasner-Tsirelson-Weiss sur non-existence de modèles spatiaux pour
presque actions sur les espaces avec mesure; (v) théorème de Hjorth sur
la distorsion dans les espaces homogènes de groupes topologiques.
A pseudofinite field is an infinite field satisfying all first-order properties in the language {0, 1, +, *} of rings which hold in all finite fields, like having an extension of degree n for every n. Pseudofinite fields exist and they can be realized for example as ultraproducts of finite fields.
An n-ary random graph is a set X with a symmetric and irreflexive n-ary relation R (i.e. R \subseteq X^[n], no two entries of an element of R are equal, and R is Sym(n)-closed) such that for any two finite and disjoint subsets A and B of X^[n-1], there is an x in X such that R(a,x) and \neg R(b,x) for all a in A and b in B.
In 1974 J.L. Duret interpreted a random binary graph in a pseudofinite field. This has some important model theoretic consequences.
We are working on interpreting a random n-ary graphs in
pseudofinite fields.
On généralise les résultats d'o-minimalité et d'élimination des quantificateurs obtenus par van den Dries, Speissegger et Rolin à des classes de fonctions quasi-analytiques restreintes. On donne une description ``explicite'' de la théorie de ces classes.
Pour ce faire, on introduit la notion de ``familles stables'' qui
permettent d'avoir un contrôle ``effectif'' sur la
désingularisation des fonctions de ces classes.
Je présenterai quelques nouveaux résultats concernant les groupes
sous-simples, et en déduirai des propriétés des
corps simples de rang fini.
E. Hrushovski a montré que, dans le cas de la caractéristique zéro, la
théorie des corps différentiels de différence a une modèle-compagne,
notée DCFA. On va donner une axiomatisation de DCFA et mentioner
quelques propriétés comme la description des
complétions et de la clôture
algébrique, la relation d'indépendance, la
supersimplicité et l'élimination
des imaginaires. Ensuite on va voir certaines propriétés du corps fixé
et du corps des constantes
d'un modèle de DCFA. Finalement on parlera du rang SU et on donnera un
exemple d'un ensemble de dimension infinie mais de rang SU fini.
Many properties of compact Hausdorff spaces can be
expressed as first-order properties of their lattices of
closed sets. This means that one can employ logical and
model-theoretic methods in the study of these spaces.
In this lecture I will survey some of the results and
questions related to this approach.
Most of these are in the theory of continua and relate to
such diverse properties as hereditary indecomposability,
covering dimension, Brouwer's dimensionsgrad, span
and chainability.
Je vais esquisser la démonstration du théorème suivant.
Transsérie est un mot forgé par Ecalle pour certaines classes de séries transfinies; mais j'emprunte ce mot pour désigner toutes ces séries au sens de Hahn 1907. Les transséries permettent de définir des transmodèles, modèles non standards naturels du corps des réels et de ses expansions o-minimales. Ces transmodèles sont un outil pour l'étude de l'o-minimalité. L'exposé illustre ce fait dans le cas polynomialement borné. Dans tous ces cas, j'étend le théorème d'Ostrovski (un corps de transséries est réel clos ssi il a un groupe de valeurs divisibles et un corps des coefficients réel clos). Et le theorème de Kaplansky (tout modèle de la théorie complète du corps réel est isomorphe à un corps de transséries). Ces extensions étaient connues uniquement dans le cas d'une expansion des réels par des fonctions analytiques restreintes (résultat de vdDries Macintyre Marker).
Je démontre aussi dans tous les cas des résultats de modèle complétude, d'élimination des quantificateurs relative et de décomposition cellulaire semi-effectifs (je préciserai ce que c'est). Ces résultats généralisent et/ou semi-effectivisent des résultats de Gabrielov, vdDries-Denef, Speissegger, Rolin-Speissegger-Wilkie et finalement Rambaud (les résultats de Rambaud sont actuellement moins généraux mais plus fins que les miens; et ils comportent également des résultats nouveaux d'o-minimalité polynomialement bornée - je n'en suis pas la).
La méthode transsérielle que j'utilise est bien eloignée de
toutes les méthodes employées par ces différents auteurs; elle est
très conceptuelle, et par ses possibilités d'extension à tous les
cas o-minimaux elle constitue le plus grand interêt de ce travail,
à mes yeux.
Nous décrirons les modèle-complétions des théories
des corps
munis d'une dérivation de Hasse de caractéristique
quelconque fixée. Nous
donnerons ensuite une généralisation des notions de la
géométrie
algébrique dans ces structures, ainsi que quelques
éléments pour
comprendre la structure supplémentaire des objets de la
géométrie
algébrique (principalement les groupes algébriques)
apportée par la
dérivation de Hasse.
This work is connected with IP-sensitivity or insensivity of
real closed fields; in other words with dependence or not on the IP
chosen in the field, in order to satisfy certain facts that are
standard in the reals with their unique Integer Part Z.
We show how the notion of formative process can be relevant in order to
find suitable rank bounded solutions of non quantified formulas of a
specified sublanguage of set theory.
The Definable Multiplicity Property (DMP) is a property of strongly
minimal
sets intruduced by Hrushovski. The definition extends naturally to
structures of finite Morley Rank, but we show that every such structure
which has the DMP is in fact a reduct of a strongly minimal one. We will
show how to use this fact in order to construct a class of strongly
minimal
sets that do not have the DMP. If time allows, we will present briefly
(new)
equivalent definitions of the DMP.
En '92, Ehud Hrushovski a montré que deux théories fortement minimales (ayant la DMP) T_1 et T_2 dans deux langages disjoints admettent une expansion fortement minimale commune. Pour construire une telle expansion commune, il s'est servi d'une nouvelle technique d'amalgamation (aujourd'hui appelée amalgamation à la Hrushovski). Il a suggeré que la même chose devrait être vraie dans un contexte relatif, c.a.d. si les deux langages s'intersectent non-trivialement, au moins si le langage commun est celui d'un espace vectoriel sur un corps fini.
Nous présentons un travail allant dans ce sens. En particulier, nous
donnons un contexte
dans lequel la fusion "libre" de deux théories fortement minimales
au-dessus de leur
intersection peut etre effectuée. La théorie T_ω que l'on
obtient par cette
fusion libre est ω-stable de rang ω.
Dans une deuxième étape, on aimerait la "collapser" sur
une théorie
fortement minimale pour
obtenir la fusion (relative) fortement minimale cherchée. On a
une bonne
compréhension des
classes de non-orthogonalité de types réguliers dans
T_ω ce
qui est indispensable
pour pouvoir collapser. Nous montrons finalement que le collapse est
possible si les deux
théories sont mono-basées.
Dans certaines classes o-minimales de fonctions, on peut détecter les
propriétés de continuité ou d'analyticité en restriction à des familles
d'arcs définissables. Ces résultats sont motivés par la recherche de
conditions nécessaires (et pourquoi pas suffisantes) pour qu'une fonction
réelle lisse ou analytique soit définissable dans une structure o-minimale.
Après avoir démontré quelques résultats dans ce sens, je discuterai quelques
exemples et quelques conjectures.
To be finite automaton (FA)-presentable seems to be a rather strong
restriction on a countable structure in a finite signature: the domain
can be represented by a regular set, in a way that finite automata can
also verify that the atomic relations hold (where the strings
representing elements are written one below the other, using symbols
in a power alphabet).
For instance, the additive group of integers is FA-presentable:
numbers are represented in binary, and the correctness of the usual
carry bit addition algorithm can be verified by a finite
automaton. This notion was introduced by Khoussainov and Nerode,
1995. (There and elsewhere, FA-presentable structures are called
automatic structures, however, for groups, the term ``automatic''
refers to a different concept.)
For each FA-presentable structure one can also give an FA-representation of all definable relations, effectively in the defining formula. So FA-presentable structures are closed under interpretations, and each one has a decidable theory.
When considering an elementary class of effectively given structures, a good measure for its richness is the complexity of the isomorphism problem. For instance, Khoussainov, Nies, Rubin and Stephan (LICS 2004) have proved that for FA-presentable graphs or even successor trees, isomorphism is as complex as possible ($Sigma^1_1$-complete), so the class is quite rich after all. With little effort, the result carries over to partial orders, lattices, and commutative semigroups.
One the other hand, the class of FA-presentable infinite Boolean algebras is very limited: Khoussainov, Nies, Rubin and Stephan have shown that they are just the finite powers of the Boolean algebra of finit or cofinite subsets of a countable set.
The general program is to locate each interesting class somewhere between those two possibilities. I discuss some new results for abelian groups and groups in general, mostly on the limiting side.
Groups: Examples of non-abelian FA-presentable groups include infinite direct powers of a finite non-abelian group, and $GL_n(R)$ for some FA-presentable ring, e.g. the Boolean algebra mentioned before, viewed as a ring. Each finitely generated FA-presentable group is abelian-by-finite (Oliver and Thomas). A recent improvement of this (Nies and Thomas): if G is ANY FA-presentable group, then each f.g. subgroup of G is abelian-by-finite. Using similar methods, each FA- presentable commutative ring with 1 is locally finite.
Abelian groups: Known examples are (Z,+), the Prufer groups,
and Z[1/p] for a prime p, and the obvious derived examples
(like finite direct products). While the multiplicative group
of rationals is Not FA-presentable (Khoussainov e.a.), it is
a major open question whether the additive rationals are
FA-presentable.
We study the unconditionality of subsequences of a weakly-null sequence
of a Banach space. Our approach makes use of combinatorial tools coming
from the classical work of Nash-Williams on families of finite subsets of
integers.
We propose a calculus of local equations over 1-qubit measurement
based quantum computing patterns which preserves interpretations,
and allows the rewriting of any pattern to a standard form where
entanglement
is done first, then measurements, then local corrections. We infer
from this that
patterns with no dependencies, or using only Pauli measurements,
can only realise unitaries belonging to the Clifford group.
I will discuss quadratic forms over models of IDelta_0+Omega_1 in
connection with Gauss second proof of quadratic reciprocity law
Dans cet exposé, on commencera par expliquer brièvement en quoi consiste la
vérification. On introduira ensuite la notion de bisimulation et on motivera
son étude dans le cadre de la vérification. En particulier, on comprendra
l'intérêt d'obtenir des bisimulations finies. Le reste de l'exposé sera
consacré à une analyse combinatoire de la notion de bisimulation entre
systèmes dynamiques. On expliquera comment encoder des trajectoires de
systèmes dynamiques à travers des mots. On s'intéressera pour finir à des
systèmes dynamiques o-minimaux pour lesquels il existe toujours une
bisimulation finie.
Dans cet exposé, nous adaptons certaines méthodes propres aux
structures o-minimales afin d'obtenir une notion de cellule et un
théorème de décomposition cellulaire pour les ensembles définissables
dans les corps ordonnés différentiellement clos. A l'aide de ce
théorème, nous pouvons définir une dimension sur ces mêmes ensembles qui
correspond à la fois au degré de transcendance différentiel et à la
dimension topologique usuelle (associée dans ce cas-ci à une topologie
différentielle particulière).
Nous allons nous intéresser aux corps valués de caractéristique
nulle muni d'une dérivation.
On va se spécialiser dans le cas étudié par Thomas Scanlon où il y a une
forte interaction entre la valuation et la dérivation. Plus précisément, on
va reprouver un résultat d'élimination des quantificateurs dans le langage
introduit par Françoise Delon (dans sa thèse).
On terminera en donnant une application algébrique à ce dernier résultat.
On examinera certains des éclairs de génie et certaines des
incompréhensions de Gödel et ses rapports avec quelques contemporains
celèbres tels qu'ils apparaissent dans la partie la moins connue de son
oeuvre et dans sa correspondance et on posera la question : de quoi se
souvenait Gödel trente ans après les théorèmes d'incomplétude ?
The Cherlin-Zilber Algebraicity Conjecture proposes that:
All simple groups of finite Morley rank are algebraic groups
over algebraically closed fields.
One of the longstanding difficulties in the work on this
conjecture has been the behavior of torsion free subgroups
of a solvable group. At face value, the problem is that a
torsion-free abelian group may behave as a semisimple group
in one context, and as a unipotent group in another.
An abstract definition of torsion-free unipotent radical
resolved several major problems, but remained silent on
several matters where such a unipotent radical was expected
to help. Considering the failure of this notion of
unipotence leads us to a notion of (mostly) torsion-free
Sylow subgroup, which has a reasonable theory, and several
important applications.
Goguen et Burstall ont introduit la théorie des institutions afin de généraliser des résultats à la fois en théorie de la spécification et en théorie des modèles. Cependant, peu de chercheurs se sont intéressés à la théorie des modèles et seule la théorie de la spécification a (largement) profité de l'abstraction fournie par le cadre théorique de la théorie des institutions.
L'interpolation de Craig [Cr57] est un résultat qui a fait l'objet de nombreuses recherches en informatique du fait de ses forts liens avec la notion de modularité des systèmes informatiques. Sous certaines hypothèses, cette propriété est équivalente à la propriété de consistance de Robinson [Rob56]. Le théorème de définissabilité de Beth [Bet53], qui établit une correspondance entre les notions de définissabilité implicite et explicite, une conséquence directe du théorème d'interpolation de Craig pour la logique classique.
Le travail que nous présentons se situe dans la continuation des travaux de Salibra et Scollo sur la correspondance entre les propriétés d'interpolation de Craig et de consistance de Robinson. Nous améliorons les résultats obtenus par ces derniers (nous nous passons de la propriété d'expansion élémentaire et n'imposons que la négation) et nous généralisons ` tout type de morphismes de signatures le théorème de définissabilité de Beth.
[Bet53] W.E.Beth, On Padoa's Method in the Theory of Definitions,
Indag. Math., 1953.
[Cr57] W.Craig, Linear Reasoning: A New Form of Herbrand-Gentzen
Theorem, Journal of Symbolic Logic, 1957.
[Rob56] A.Robinson, A Result in Consistency and Its Applications to the
Theory of Definition, Indag. Math., 1956.
One of the important achievements in derandomization theory is the
following theorem: given a truth table of a Boolean function f on n
variables, which cannot be approximated by a circuit of size
2^{ε n} with nonnegligible advantage, one can construct in
polynomial time a function f' on O(n) variables with worst-case
circuit complexity 2^{Ω(n)}. We show how to formalize this
statement in S^1_2. To achieve this goal, we develop in S^1_2
basics of the theory of finite fields and list-decoding of Reed-Muller
codes, and we present a modification of Soltys' theory \forall LAP
for linear algebra.
La théorie des modèles permet d'aborder d'une façon nouvelle et différente
la résolution des singularités pour des fonctions réelles.
On donnera une petite présentation des méthodes utilisées, notamment
grâce aux valuations et on
présentera les problèmes posés.