
Evènement pour le groupe Graphes et Logique
Date  20121016 11:0012:00 
Titre  A Model Theoretic Proof of Completeness of an Axiomatization of Monadic SecondOrder Logic on Infinite Words 
Résumé  We discuss the completeness of an axiomatization of Monadic SecondOrder Logic (MSO) on infinite words (or streams). By using modeltheoretic tools, we give an alternative proof of D. Siefkes' result that a fragment with full comprehension and induction of secondorder Peano's arithmetic is complete w.r.t. the validity of MSOformulas on streams. We rely on FefermanVaught Theorems and the EhrenfeuchtFraïssé method for Henkin models of secondorder arithmetic. Our main technical contribution is an infinitary FefermanVaught Fusion of such models. We show it using Ramseyan factorizations similar to those for standard infinite words. We also discuss a Ramsey's theorem for MSOdefinable colorings, and show that in linearly ordered Henkin models, Ramsey's theorem for additive MSOdefinable colorings implies Ramsey's theorem for all MSOdefinable colorings. 
Lieu  76 
Orateur  Colin Riba 
Email  colin.riba@enslyon.fr 
Url  LIP, ENS Lyon 
Aucun document lié à cet événement. RetourRetour à l'index
 