23 juin : Artem Chernikov (Équipe de Logique Mathématique, IMJ-PRG ) Counting Dedekind cuts
For an infinite cardinal k, let ded(k) denote the supremum of the number of Dedekind cuts in linear orders of size k. It is known that k < ded(k) <= 2^k for all k, and that ded(k) < 2^k is consistent for any k of uncountable cofinality. I will present some new equalities and inequalities, both consistently and in ZFC. In particular, 2^k <= ded(ded(ded(ded(k)))) always holds. The proof uses some PCF theory, and optimality of the result remains open. Model-theoretic importance of ded(k) comes from the fact that it describes number of types over models in dependent (or NIP) theories. I will give some applications of the new bound on ded(k) to the two-cardinal model transfer in dependent theories. Joint work with Saharon Shelah.
19 juin : (Oscar Ibarra, University of California) On the Complexity of Parikh Membership Problems
We consider the problem of determining if a string w belongs to a language L specified by an automaton (e.g., NFA, PDA, counter machine, etc.) where w is specied by its Parikh vector. We investigate the complexity of this problem under various scenarios: the Parikh vector is given in unary, binary, the automaton is fixed (i.e., not part of the input), the automaton is not fixed and part of the input, etc. We also look at related problems involving semilinear sets and synchronized multitape automata.
12 juin : (Jindrich Zapletal , University of Florida) Why Axiom Y
In a joint work with David Chodounsky, we isolate a new property of c.c.c. posets. It is particularly relevant for partition type forcings discovered by Todorcevic.
19 mai : Olivier Serre (LIAFA, Université Paris 7) Playing with Automata and Trees
Roughly speaking a finite automaton on infinite trees is a finite memory machine that takes as input an infinite node-labelled binary tree and processes it in a top-down fashion as follows. It starts at the root of the tree in its initial state, and picks (possibly nondeterministically) two successor states, one per son, according to the current control state, the letter at the current node and the transition relation. Then the computation proceeds in parallel from both sons, and so on. Hence, a run of the automaton on an input tree is a labelling of this tree by control states of the automaton, that should satisfy the local constrains imposed by the transition relation. A branch in a run is accepting if the $\omega$-word obtained by reading the states along the branch satisfies some acceptance condition (typically an $\omega$-regular condition such as a Büchi or a parity condition). A run is accepting if *all* branches are accepting. Finally, a tree is accepted by the automaton if *there exists* an accepting run over this tree. Hence, there are three natural levers on which one can act to define alternative families of tree automata / tree languages. - The first lever is local with respect to the run: it is the conditionrequired for a branch to be accepting. - The second lever is global with respect to the run: it is the condition required for a run to be accepting. - The third lever has to do with the set of runs: it is the condition required for a tree to be accepted (wrt the set of runs over it). For the usual definition of tree automata the three lever are: parity condition on branches / all branches accepting for run / there exists an accepting run. In this talk I will mainly focus on the second and third levers and propose variants of them. More precisely (time depending): - second lever: count the number of accepting/rejecting branches (cardinality constraint), topologically measure the largeness of the set of accepting/rejecting branches, measure (à la Lebesgue) the set of accepting/rejecting branches. - third lever (possibly combined with the second lever): alternating and probabilistic models. I will explain how decidability results can be obtained by extending the well-known equivalence between games and tree automata (that I will recall first!). This will lead us, in several situations, to leave the usual than perfect-information turn based two-player framework: in particular we will have to deal with stochastic aspects and/or imperfect information.
7 avril : Yann Pequignot (Université de Lausanne et LIAFA, Université Paris 7) A Wadge hierarchy for second countable spaces
We define a notion of reducibility for subsets of a second countable T0 topological space based on, so called, admissible representations. It coincides with Wadge reducibility on zero dimensional spaces. However in virtually every second countable T0 space, it yields a hierarchy on Borel sets, namely it is wellfounded and antichains are of length at most 2. It thus differs from the Wadge reducibility in many important cases, for example on the real line or the Scott Domain P(omega).
31 mars : Miguel Couceiro (LAMSADE - Université Paris-Dauphine) Sur le problème de reconstruction de fonctions induit par la relation de mineur
Les différents problèmes de reconstruction, qui attirent l'attention des chercheurs depuis longtemps,
partagent une même méta-formulation. Etant donné un objet combinatoire, nous dérivons des "sous-objets"
en appliquant une certaine opération sur cet objet initial. La question alors posée est de savoir si le
premier objet est uniquement déterminé (à une sorte d'isomorphisme près) par la collection des objets
dérivés. Parmi les conjectures de reconstruction, la plus célèbre est peut-être la conjecture de
reconstruction des graphes définie en termes de la suppression de sommets (ou d'arêtes).
Nous allons considérer une version fonctionnelle du problème de reconstruction définie en termes
de la relation de mineur : $g: A^m \to B$ est un mineur de $f: A^n \to B$ si $g $ peut
être obtenu de $f$ par permutation et identification de variables, et addition de variables non
essentielles; voir par ex. [Pi,CF2].
La conjecture n'est pas vérifiée en général mais pour certaines classes comme celles des fonctions
symétriques ou des fonctions affines la conjecture reste (essentiellement) vraie [Le1,Le2]. Nous
allons considérer quelques variantes de ce problème de reconstruction et présenter des résultats
récents en collaboration avec Erkko Lehtonen, Maurice Pouzet et Karsten Schölzel [CLS1,CLS2,CP1].
En particulier, nous allons présenter une dichotomie forte des clones booléens par rapport à ces
variantes.
[CF2] M. Couceiro, S. Foldes. On closed sets of relational constraints and
classes of functions closed under variable substitutions, Algebra Universalis, 54,
(2005) 149--165.
[CLS1] M. Couceiro, E. Lehtonen, K. Schölzel. Hypomorphic Sperner systems and nonreconstructible monotone functions, arXiv:1306.5578
[CLS2] M.Couceiro, E.Lehtonen, K. Schölzel. Set-reconstructibility of Post classes,
arXiv:1310.7797.
[CP1] M. Couceiro, M. Pouzet. On a quasi-order on Boolean functions, Theoretical Computer Science,
396, (2008) 71--87.
[Le1] E. Lehtonen. On the reconstructibility of totally symmetric functions and of other functions
with a unique identification minor, arXiv:1208.3110.
[Le2] E. Lehtonen. Reconstructing multisets over commutative groupoids, with an application
to a reconstruction problem for functions of several arguments (the case of affine functions),
arXiv:1302.7109.
[Pi] N. Pippenger. Galois Theory for Minors of Finite Function, Discrete Mathematics, 254,
(2002) 405--419.
24 mars : Gregor Dolinar (Université de Ljubljana, Slovénie) Squares and their relatives
A square is an often used object in set theory. Its existence is independent from ZFC and this independence has close connections with large cardinals. I will briefly show the classical approach at forcing a square, but the main focus will be on forcing a square with finite conditions which is a recent product of joint work with Mirna Dzamonja. Finally, I will present a square with additional guessing property - a marriage between a square and a club.
10 mars : Raphaël Carroy (Université de Münster, Allemagne) Une classification des fonctions continues entre espaces polonais 0-dimensionels
Le but de cet exposé est de trouver une classification "solide et pertinente" des fonctions boréliennes entre espaces Polonais 0-dimensionels, et de l'étudier sur la sous-classe des fonctions continues. On commencera par préciser les termes du problème en expliquant ce que l'on entend par "solide et pertinente". On donnera donc une liste des propriétés souhaitées pour un quasi-ordre sur les fonctions, comme par exemple être plus fin que la hiérarchie de Baire des fonctions, ou généraliser les ordres connus sur les ensembles comme le quasi-ordre de Wadge, ou bien le quasi-ordre induit par le plongement entre ensembles. On définira quelques quasi-ordres en s'inspirant d'exemples classiques présents dans la litérature, et on discutera de leur pertinence en tant que candidats à une classification de fonctions. On choisira finalement l'un de ces candidats, celui qui vérifie le plus de propriétés parmis celles pré-requises. Précisément, on dira, étant données deux fonctions f et g, que f\leq g si et seulement s'il existe une paire (\sigma,\tau) de fonctions continues telles que f=\tau\circ g\circ\sigma. On commencera l'étude de cet ordre sur les fonctions continues. On généralisera l'analyse de Cantor-Bendixson des fermés aux fonctions continues à image dénombrable, avec pour conséquence que le quasi-ordre défini plus haut bien ordonne les fonctions continues à domaine compact, et on donnera un résultat général sur la structure de Cantor-Bendixson obtenue sur les fonctions continues. Si le temps le permet, on montrera comment en déduire que les fermés de l'espace de Baire (autrement dit, les Polonais 0-dimensionels) sont bien-quasi-ordonnés par plongement continu.
17 février : Marcin Sabok (Équipe de Logique Mathématique, IMJ-PRG) Théorie canonique de Ramsey sur des espaces polonais
La théorie canonique de Ramsey est une généralisation de la théorie de Ramsey et elle commence par le théorème de Erdös et Rado. Dans mon exposé, je vais discuter une généralisation de cette théorie pour des relations d'équivalence boréliennes sur des espaces polonais. Travail en commun avec V. Kanoveï et J. Zapletal.
10 février : Mirna Dzamonja (University of East Anglia, England) Le monde singulier des cardinaux singuliers
En travaillant avec les cardinaux réguliers non dénombrables nous sommes confrontés avec beaucoup d'independance, comme le montre toute la théorie de forcing. Si on voit cette incomplétude comme une limitation à l'utilité de notre formalisation des mathématiques par ZFC, il est agréable de noter que beaucoup de résultats montrent que sur les cardinaux singuliers le système ZFC est capable d'éviter l'indépendance. Nous discutons quelques aspects de ces résultats et proposons une étude systématique des possibilités de théorèmes en ZFC sur les singuliers et leurs successeurs.
3 février : Dimitris Vlitas (Athens) Canonical Borel equivalence relations on R^n
It is very well known how Ramsey's Theorem, generalizes to its canonical form the Erdös-Rado Theorem. Namely the classical Ramsey theorem considers finite colorings of $n$-element subsets of $\omega$ and the Erdös-Rado theorem considers countable colorings the same set. We consider uncountable versions of these results, in particular we consider the Cantor space $2^\omega$. Extending results by F. Galvin, A. Blass and completing an attempt by H. Lefmann we show that Borel equivalence relations on the n-elements subsets of $2^\omega$, that respect an order type, have a finite Ramsey basis.
9 décembre : Olivia Caramello (IHES) Construction de Fraïssé et topos
On interprétera en termes de topos la construction de Fraïssé en théorie des modèles et on présentera quelques applications aux théories dénombrablement catégoriques. La démonstration du théorème principal, qui généralise le résultat classique, illustre le rôle des topos de Grothendieck comme 'ponts' pour transférer des propriétés et constructions entre théories mathématiques différentes. Plus précisément, on montrera que les trois concepts impliqués dans la construction de Fraïssé classique (propriété d'amalgamation et de plongement conjoint, homogénéité et atomicité) correspondent exactement à trois points de vue différents (de natures respectivement géométrique, sémantique et syntactique) sur le même topos classifiant.
2 décembre : Sakaé Fuchino (Université de Kobe, Japon) Rado's conjecture and stationary reflection principles
Rado's conjecture (RC) is one of "reflection statements" which asserts that every non-special tree has a non-special subtree of size $\aleph_1$. Stationary reflection principles are similar reflection statements about the stationarity of subsets of $[\kappa]^{\aleph_0}$ ($=$ countable subsets of $\kappa$). One of the stationary reflection principles (which we call ${\rm RP}_{\rm IC}$ here) is the statement that, for every uncountable $\kappa$ and every stationary $S\subseteq[\kappa]^{\aleph_0}$, there is an internally closed unbounded elementary submodel $M$ of $\langle{\cal H}(\theta),\cdots\rangle$ of size $\aleph_1$ for a sufficiently large regular $\theta$ such that $S\cap M$ is stationary in $[\kappa\cap M]^{\aleph_0}$. Under $\neg$CH, these principles can be quite different: ${\rm RP}_{\rm IC}$ follows from ${\rm MA}^+(\sigma\mbox{-closed})$ and hence is compatible with Martin's Maximum while RC implies the negation of ${\rm MA}_{\aleph_1}$. In spite of this, it is known that these two principles have many common consequences: for example, Singular Cardinal Hypothesis and Chang's Conjecture are consequences of both of the principles. This phenomenon is well explained by the fact that Fodor-type Reflection Principle (FRP) and Semi-Stationary Reflection Principle (SSR) are consequences of each of ${\rm RP}_{\rm IC}$ and RC. That FRP and SSR follow from RC is found only recently (S.\,F., H.\,Sakai, V.\,Torres and T.\,Usuba, (in preparation) for FRP and Doebler (2013) for SSR). In this talk, I am going to give some more details and backgrounds of what I mentioned above and also discuss about a new reflection principle formulated in terms of infinite games which is a common consequence of RC and ${\rm RP}_{\rm IC}$ while it implies both FRP and SSR.
25 novembre : Salma Kuhlmann (Université de Konstanz, Allemagne) Real Closed Fields and Models of Peano Arithmetic
We say that a real closed field is an IPA-real
closed field if it admits an integer part (IP)
which is a model of Peano Arithmetic (PA). In [2] we prove that the value group of an
IPA-real closed field must satisfy very restrictive conditions (i.e.
must be an exponential group in the residue field, in the sense of
[4]). Combined with the main result of [1] on
recursively saturated real closed fields, we obtain a valuation theoretic characterization
of countable IPA-real closed fields. Expanding on [3], we conclude the
talk by considering recursively saturated o-minimal expansions of real
closed fields and their IPs.
[1] D'Aquino, P. ,
Kuhlmann, S. , Lange, K. : A valuation theoretic characterization of
recursively saturated real closed fields,
arXiv: 1212.6842 (2013)
[2] Carl, M. , D'Aquino, P. , Kuhlmann, S. : Value groups of real closed
fields and fragments of Peano Arithmetic,
arXiv: 1205.2254 (2012)
[3] Conversano, A., D'Aquino, P. , Kuhlmann, S : k-Saturated o-minimal
expansions of real closed fi elds,
arXiv: 1112.4078 (2012)
[4]
Kuhlmann, S. : Ordered Exponential Fields, The Fields Institute Monograph
Series, vol 12. Amer. Math. Soc. (2000)
18 novembre : Dominique Lecomte (Equipe d'Analyse Fonctionnelle, IMJ-PRG) Propriétés d'acyclicité permettant de tester la complexité dans les espaces produit
La littérature fournit des dichotomies donnant des homomorphismes (comme dans la dichotomie de Kechris-Solecki-Todorcevic) ou des réductions sur un sous-ensemble d'un produit (comme dans la caractérisation des ensembles potentiellement d'une classe de Baire donnée), qui seront rappelées. Cependant, une partie de la motivation derrière cette dernière caractérisation était d'obtenir des réductions sur tout le produit, comme dans la notion classique de réduction borélienne considérée dans l'étude des relations d'équivalence boréliennes. Ceci n'est pas possible en général. Nous montrons que, sous de bonnes hypothèses d'acyclicité (et aussi topologiques), ceci peut largement se faire.
4 novembre : Anatole Khélif (IUFM Paris 7, & Equipe de Logique Mathématique, IMJ-PRG) Autour de la bi-interpretabilité
Nous disons que deux structures sont biinterprétables si elles s'interprètent l'une dans l'autre et si la composition de ces interprétations est l'identité. La biinterprétabilité a notamment été étudiée par Oleg Belegradek. L'interprétabilité réciproque de deux structures ne signifie pas forcément la biinterprétabilité. Par exemple Z et UT3(Z) ne sont pas biinterprétables. Dans un travail récent avec Scanlon et Aschenbrenner, nous avons prouvé que tout anneau commutatif intègre de type fini est biinterprétable avec l'arithmétique du premier ordre. Plus généralement, la non biinterprétabilité peut être prouvée par une analyse d'automorphismes de modèles. S'il reste du temps nous présenterons brièvement le lien avec les esquisses pour la logique infinitaire et les topos classifiants pour les théories géométriques.
14 octobre : Pascal Michel (IUFM de Versailles & Equipe de Logique Mathématique, IMJ-PRG) Un exemple naturel de fonction qui bat le record de rapidité de croissance
Il est facile de démontrer qu'il existe des fonctions qui croissent plus vite que toutes les fonctions calculables (degré 0), ou qui croissent plus vite que toutes les fonctions calculables avec oracle le problème de la halte (degré 0'). Mais définir une telle fonction explicitement, de façon à pouvoir en calculer les premières valeurs, est plus difficile. Rado l'a fait en 1962 pour les fonctions calculables (busy beavers), Nabutovsky et Weinberger l'ont fait en 2007 pour les fonctions de degré 0'', en utilisant l'homologie des groupes. Nous exposerons ce travail et ses développements ultérieurs.
7 octobre : Alexis Bès (LACL, Université Paris-Est-Créteil) Autour des théorèmes de Muchnik et Michaux-Villemaire
Les théorèmes de Muchnik et Michaux-Villemaire concernent la définissabilité dans l'arithmétique de Presburger. Le premier dit qu'une relation R d'arité quelconque sur les entiers est définissable dans (N,+) si, d'une part, toutes ses sections le sont, et si d'autre part R est localement périodique. Le second dit que si R est une relation d'arité quelconque qui n'est pas définissable dans (N,+), alors il existe une relation unaire R' définissable dans (N,+,R) et non définissable dans (N,+). Dans la première partie de l'exposé, je présenterai ces deux résultats et leurs applications, en particulier autour du théorème de Cobham-Semënov sur la représentation d'ensembles d'entiers par automate fini. Dans la seconde partie, je discuterai de travaux récents où on s'appuie sur des théorèmes à la Muchnik-Michaux-Villemaire pour démontrer l'indécidabilité de théories logiques. Le premier travail, dû à A.Milchior, concerne des logiques du premier ordre sur les mots. Le second concerne des extensions de la logique du second ordre monadique sur les entiers avec successeur (WS1S) par des prédicats qui expriment des propriétés de cardinalité.
16 septembre : Andrew Marks (Caltech) Universal countable Borel equivalence relations and recursion theory
Given two equivalence relations E and F on the standard Borel spaces X and Y, we say that E is Borel reducible to F if there is a Borel function f from X to Y so that for all x, y in X, we have x E y iff f(x) F f(y). We often think of Borel reducibility as comparing the difficulty of classifying E and F by invariants, where if E is Borel reducible to F, then any complete set of invariants for F can be used as a set of complete invariants for E. The study of Borel reducibility has had remarkable success both in calibrating the difficulty of classification problems of interest to working mathematicians, and also in understanding the abstract structure of the space of all classification problems. Among the Borel equivalence relations with countable classes, there are maximal equivalence relations under the quasi-order of Borel reducibility -- the so called universal countable Borel equivalence relations. Examples of universal countable Borel equivalence relations include isomorphism of finitely generated groups, conformal equivalence of Riemann surfaces, and poly-time Turing equivalence. We discuss some connections between recursion theory, the study of universal countable Borel equivalence relations, and problems of uniformity in both areas.