IMJ-PRG
IMJ-PRG CNRS - UPMC - Paris Diderot

Séminaire Général de Logique

Année 2016- 2017

Responsables : O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, C. Sureson
Lundi de 15h10 à 16h10, salle 2015 (Attention changement de salle).
Page web et programme
Archives
Abonnement à la liste de diffusion

Slawomir Solecki - University of Illinois at Urbana-Champaign, USA

Menger compacta as projective Fraisse limits with emphasis on dimension one

lundi 29 mai 2017 à 15:10

In each dimension d, there exists a canonical compact, second countable space, called the d-dimensional Menger space, with certain universality and homogeneity properties. For d = 0, it is the Cantor set, for d = infinity, it is the Hilbert cube. I will concentrate on the 1-dimensional Menger space. I will prove that it is a quotient of a projective Fraisse limit. I will describe how a property of projective Fraisse limits coming from Logic, called the projective extension property, can be used to prove high homogeneity of the 1-dimensional Menger space.

This is joint work with Aristotelis Panagiotopoulos.

Alexis Bès - LACL, Université Paris-Est Créteil

L’arithmétique de Skolem et ses extensions

lundi 22 mai 2017 à 15:10

L’arithmétique de Skolem est la théorie du premier ordre des entiers naturels munis de la multiplication (sans l’addition). Cet exposé proposera un aperçu des principaux résultats de décidabilité autour de (N,*) et ses extensions, ainsi que des liens avec les automates. On présentera d’abord la preuve par Mostowski de la décidabilité de (N,*), basée sur les produits de structures et la décidabilité de l’arithmétique de Presburger, puis la preuve de Hodgson, basée sur les automates. On montrera ensuite comment la notion de produit généralisé introduite par Feferman et Vaught permet d’obtenir des extensions décidables de (N,*), comme par exemple (N,*,"x et y ont autant de diviseurs premiers") ou (N,*,"x et y sont premiers et x < y"). On verra enfin que ce dernier exemple (dû à F.Maurin), conduit à une notion naturelle d’automate pour les mots sur un alphabet infini.

Joanna Ochremiak - IRIF, Université Paris 7

Infinite constraint satisfaction problems

lundi 15 mai 2017 à 15:10

We study the homomorphism problem for infinite relational structures which can be defined by finitely many first-order formulas over the natural numbers with equality. We determine the decidability status of this problem depending on whether the signature or/and the number of tuples in a single relation are allowed to be infinite.

Joint work with Bartek Klin, Eryk Kopczyński, Sławek Lasota and Szymon Toruńczyk.

Julien Melleray - Institut Camille Jordan, Université Lyon 1

Mesures invariantes d’homéomorphismes minimaux

lundi 27 mars 2017 à 15:10

Je reviendrai sur une caractérisation, due à Ibarlucia et moi-même, des ensembles de mesures invariantes d’homéomorphismes minimaux d’un espace de Cantor, et examinerai la question de savoir si cette caractérisation peut être simplifiée (en supprimant une des hypothèses dite de "divisibilité approximative"). J’expliquerai pourquoi cette caractérisation fait apparaître un lien avec de la théorie de Fraïssé et discuterai quelques questions ouvertes (selon le temps).

Arpita Korwar - Equipe de Logique Mathématique, IMJ-PRG

Polynomial Identity Testing of Sum of ROABPs

lundi 20 mars 2017 à 15:10

Polynomials are fundamental objects in mathematics. Though univariate polynomials are fairly well-understood, multivariate polynomials are not. Arithmetic circuits are the primary tool used to study the complexity of polynomials in computer science. They allow for the classification of polynomials according to their complexity.

Polynomial identity testing (PIT) asks if a polynomial, input in the form of an arithmetic circuit, is identically zero.

One special kind of arithmetic circuits are read-once arithmetic branching programs (ROABPs), which can be written as a product of univariate polynomial matrices over distinct variables.

We will be studying the characterization of an ROABP. In the process, we can give a polynomial-time PIT for the sum of constantly many ROABPs.

Gilles Godefroy - CNRS et Université Paris 6

Quelques applications de l’axiome de Martin aux espaces de Banach

lundi 13 mars 2017 à 15:10

L’axiome de Martin est un axiome qu’on peut ajouter aux axiomes de ZFC, qui est compatible avec la négation de l’hypothèse du continu et qui a pour effet de "pousser vers le dénombrable" tous les cardinaux inférieurs au continu. La théorie des espaces de Banach non séparables est assez différente suivant qu’on accepte, ou non, cet axiome. Nous verrons cela sur quelques exemples simples, qui ont en commun que l’axiome de Martin permet de construire des systèmes (presque) biorthogonaux transfinis.

Matthew Foreman - University of California

A solution to a problem of von Neumann

lundi 6 mars 2017 à 15:10

In 1932 von Neumann proposed classifying the statistical behavior of diffeomorphisms of manifolds. In modern language this is restated as classifying the equivalence relation of measure theoretic isomorphism. The main theorem in this talk is that the classification problem is impossible. The equivalence relation is not Borel. As part of the proof a “Global Structure Theorem” is proved that settle a couple of open questions about another classical problem, the “realization problem.” This is joint work with B. Weiss.

Isabel Müller - Université de Lyon

La Conjecture de Zilber et ses contre-exemples

lundi 27 février 2017 à 15:10

Dans une tentative de classer la géométrie des ensembles fortement minimaux, Zilber les avait conjecturés pour se diviser en trois types différents : Les géométries triviales, les géométries qui ressemblent à des espaces vectoriels et ceux qui ressemblent à des corps. Hrushovski a ensuite réfuté cette conjecture en introduisant une construction intelligente qui avait été modifiée et utilisée beaucoup depuis. Son contre-exemple à la conjecture de Zilber a fourni une structure, qui n’était pas monobasée, donc ne pouvait pas être de type trivial ou de type espace vectoriel, mais elle interdisait une certaine configuration point-ligne-plan qui est toujours présente dans les corps. Hrushovski appela cette propriété CM-trivial et plus tard Pillay, avec quelques corrections d’Evans, à défini toute une hiérarchie de nouvelles géométries, où à la base on trouve les géométries monobasées (1-ample) et les géométries non-CM-triviales (2-ample) et sur le dessus on trouve des corps, qui sont n-ample pour tout n. Récemment, Baudisch, Pizarro et Ziegler et indépendamment Tent ont fourni des exemples prouvant que cette hiérarchie d’ampleur est stricte. Tandis que leurs exemples sont omega-stables de rang infini, il est resté ouvert si on peut trouver des géométries de rang fini qui sont au moins 2-amples mais n’interprètent pas un corps. Avec Katrin Tent, nous avons produit une structure presque fortement minimale qui est 2-ample, mais pas 3-ample, en utilisant une construction à la façon de Hrushovski. Dans cet exposé, nous donnerons un aperçu de la conjecture et de ses contre-exemples, motivant pourquoi notre nouvelle structure s’inscrit naturellement dans le tableau.

Charles Paperman

Some news from the Crane Beach

lundi 20 février 2017 à 15:10

First-order logic over words is known to be equivalent to the circuits complexity class AC0 when equipped with arbitrary predicates. In this talk I will present result about the expressivity of first order logic when we restrict the class of predicates. I will focus in particular on the Crane Beach Property. Introduced more than a decade ago, this property is true of a logic if all the expressible languages admitting a neutral letter are regular. Finally I will present it’s closely tied to the counting (in)ability of a logic as an application.

Alejandro Petrovich - Université de Buenos Aires, Argentine

Non-classical Quantifiers Over Non-classical Logics

lundi 13 février 2017 à 15:10

In the literature there are several papers on the study of quantifiers in non-classical logics. Part of these works consists of considering the fragment corresponding to the study of monadic logic, that is, the fragment where the predicate symbols depend only on a fixed variable or a constant symbol. Although the connectives of propositional logic are non-classical, quantifiers are interpreted in the classical sense. The purpose of this paper is to introduce different notions of quantifiers in the particular case of the infinite valued logic (IVL) developed by Lukasiewicz. The algebraic models of this theory turn out to be MV algebras endowed with an additional operator, where MV-algebras are the algebraic models corresponding to the logic IVL. When quantifiers are interpreted classically, these structures are called monadic MV-algebras and are generalizations of the well known monadic Boolean algebras introduced by Halmos [Ha62].

References :

[Ha62] P. Halmos, Algebraic Logic, Chelsea Publishing Company, 1962.

[Sch77] Schwartz, D., Theorie der polyadischen MV-algebren endlicher Ordnung, Math. Nachr., 78 (1977) 131—138.

[Sch80] Schwartz, D., Polyadic MV-algebras, Zeitschrift f\"ur Math. Logik und Grundla-gen der Mathematik, 26 (1980) 561—564 .

L'exposé de Francisco Miraglia prévu le 30 janvier est annulé - Université de Sao Paulo, Brésil

Abstract Algebraic Theory of Quadratic Forms and Rings

lundi 30 janvier 2017 à 15:10

Abstract (joint work with M. Dickmann) :

Let A be a commutative unitary semi-real (– 1 is not a sum of squares) ring in which 2 is a unit ; let T = A2 or a proper preorder of A. We shall describe first order axioms such that if the pair (A, T) is a model of these statements, then there is a special group, $G_T(A)$, naturally associated to (A, T), faithfully coding the T-theory of diagonal quadratic forms with unit coefficients in A. Under mild restrictions, these axioms are necessary and sufficient for $G_T(A)$ to faithfully code representation and T-isometry of non-singular diagonal quadratic forms with coefficients in A.

We shall present important classes of rings satisfying these axioms and extract significant results concerning the behavior of quadratic form theory over these classes of rings. The needed concepts will be presented during the talk, which contains only part of the results that appeared in :

M. Dickmann, F. Miraglia, Faithfully Quadratic Rings, Memoirs of the AMS, 1128, (November 2015).

Christina Brech - Université de Sao Paulo, Brésil

Universal objects among Boolean algebras and Banach spaces

lundi 23 janvier 2017 à 15:10

An element B of a given class of Boolean algebras is universal if every other element of the class is isomorphic to a subalgebra of B. In the context of Banach spaces, we have similar notions considering isomorphisms or isometries of Banach spaces. We will discuss the existence of universal objects for some classes of Boolean algebras and of Banach spaces and their interaction. We are particularly interested in the classes of all objects of a fixed size - cardinality of Boolean algebras and density character of Banach spaces - and we shall compare the countable/separable and the uncountable/nonseparable settings.

Silvain Rideau - University of California, Berkeley

Groupes définissables dans des corps enrichis

lundi 16 janvier 2017 à 15:10

Un résultat de Pillay affirme qu’un groupe définissable dans un corps différentiellement clos peut être plongé dans un groupe algébrique. Des théorèmes semblables ont été prouvés depuis pour de nombreuses structures de corps enrichis : corps séparablement clos, corps avec automorphisme générique, corps réels clos... De plus, la preuve de tous ces résultats utilisent des outils similaires développés pour étudier les groupes dans les théories stables puis simples.

Le but de mon exposé sera d’exposer certains de ces résultats de structure pour les groupes définissables ainsi que les outils utilisés. Enfin, si le temps le permet, j’expliquerais comment, dans le cas le moins compliqué, on peut s’affranchir, dans une certaines mesure, des hypothèses de stabilité ou de simplicité utilisées dans ces preuves pour pouvoir les appliquer dans des corps valués.

Jacques Van de Wiele - ancien membre de l'Equipe de Logique Mathématique

Valuations

lundi 5 décembre 2016 à 15:10

Thème principal : (cours elementaire sur les) anneaux de (pre)valuation p-adique, theorie des modeles, arithmetique, approche finitaire

thèmes abordés : logique intuitionniste, algebre commutative, constructive modules, (co)homologies, categories abeliennes, (logique lineaire) topos de Faltings

Biblio principale :
Grothendieck [01.8GRO14a]
Integration Motivique (Loeser, Nicaise, Sebag) [18MOT1-11a] [18MOT2-11a]
Marc Hindry :Arithmetique [30HIN08a]
Ahmed Abbes, Michel Gros, Takeshi Tsuji :The p-adique Simpson Correspondence [18ABB16a]
Ihsen Yengui : Constructive Commutative Algebra [16.5YEN15a]

Benoit Monin - LACL, Université Paris-Est Créteil

A small history of K-triviality

lundi 28 novembre 2016 à 15:10

The Kolmogorov complexity of a string is, informally, the length of the smallest program that produces this string. We write C(s) = n to mean that the smallest program producing the string s is of length n.

An infinite binary sequence X is said to be C-trivial if the Kolmogorov complexity of its prefixes is minimal, that is, if there is a constant d such that for any n, we have C(X rest n) < C(n) + d (Here X rest n denotes the n first bits of X). It is clear that any computable (infinite binary) sequence is C-trivial. Chaitin proved that the converse holds : A sequence X is computable iff it is C-trivial (1).

Chaitin also successfully used Kolmogorov complexity to provide a formal definition of the intuitive idea we can have of a random sequence. To do so, he needed a variation of the standard Kolmogorov complexity, called "prefix Kolmogorov complexity" and denoted by K. Using this prefix Kolmorogov complexity K, he defined a sequence Z to be random if for any n we have K(Z rest n) > n - d for some constant d. The intuition is that the prefix Kolmogorov complexity should be maximal for prefixes of random sequences. This definition of randomness is still today the most studied, for many reasons that we shall not detail during the talk.

Chaitin conjectured (1) to also be true with prefix Kolmorogov complexity K, that is, X is computable iff X is K-trivial (that is, there is d such that for every n we have K(X rest n) < K(n) + d). Solovay later refuted the conjecture by constructing a non-computable K-trivial sequence A. The notion of K-triviality was born, and had yetto reveal many surprises through its numerous different characterizations, and its connections with algorithmic randomness.

After introducing the main concepts with more details, we will try during this talk to give some explanations and intuitions on the work that has been done by various people on K-triviality these last 15 years.

Dominique Lecomte - Equipe d'Analyse Fonctionnelle, IMJ-PRG

Complexité borélienne des relations d’équivalence

lundi 21 novembre 2016 à 15:10

Nous étudions la complexité topologique des relations d’équivalence boréliennes, et donc la classe de ces dernières munie du quasi-ordre de réduction continue. Nous présenterons les premiers résultats de cette étude entamée il y a moins d’un an, ainsi que certains des théorèmes ayant permis de les obtenir.

Miki Hermann - CNRS et LIX, Ecole Polytechnique

Minimal Distance of Propositional Models

lundi 14 novembre 2016 à 15:10

We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory : Given a conjunctive formula over a set of relations, find a satisfying assignment with minimal Hamming distance to a given assignment that satisfies the formula (NextOtherSol, NOSOL$) or that does not need to satisfy it (NearestSol, NSOL). The third problem asks for two satisfying assignments with a minimal Hamming distance among all such assignments (MinSolDistance, MSD).

For all three problems we give complete classifications with respect to the relations admitted in the formula. We give polynomial time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness regarding APX, poly-APX, or equivalence to well-known hard optimization problems.

Tomás Ibarlucía - Equipe de Logique Mathématique, IMJ-PRG

Belles paires de structures randomisées

lundi 7 novembre 2016 à 15:10

Un problème intriguant en théorie des modèles des structures métriques est celui de généraliser la notion de théorie mono-basée. Dans le cadre d’une théorie oméga-catégorique T, une proposition intéressante vient de considérer la théorie T_P de belles paires de modèles de T : quand est-ce T_P oméga-catégorique ? Cette propriété généralise celle d’être mono-basée dans le cas classique et s’applique à d’autres exemples importants. Malheureusement, on verra qu’elle n’est jamais satisfaite par des théories randomisées non-triviales. On rappellera ce qu’est la randomisation T^R de T, puis on classifiera les modèles séparables de (T^R)_P lorsque T est oméga-catégorique.

Christophe Chalons

Autour des degrés ludiques

lundi 17 octobre 2016 à 15:10

Jordi Lopez-Abad - Equipe de Logique Mathématique, IMJ-PRG, Université Paris 7

La propriété de Ramsey approximative des matrices réelles et des espaces vectoriels normés

lundi 26 septembre 2016 à 15:10

Nous présentons la propriété de Ramsey approximative des espaces vectoriels normés de dimension finie. Nous discuterons aussi le degré de Ramsey métrique des matrices réelles et complexes, comme une version du Théorème de Graham-Leeb-Rothschild sur les Grassmanniennes d’un espace vectoriel sur un corps fini.

INTRANET

WEBMAIL imj-prg.fr

MENTIONS LEGALES