Séminaires : Séminaire Général de Logique

Equipe(s) : lm,
Responsables :O. Finkel, T. Ibarlucía, A. Khélif, S. Rideau, C. Sureson
Email des responsables :
Salle : salle 2015
Adresse :Sophie Germain
Description

ArchivesRetour ligne automatique
Abonnement à la liste de diffusion


Orateur(s) Alexis Bès - LACL, Université Paris-Est Créteil,
Titre L'arithmétique de Skolem et ses extensions
Date22/05/2017
Horaire15:10 à 16:10
RésumeL'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.
Sallesalle 2015
AdresseSophie Germain
© IMJ-PRG