|
Evènement pour le groupe Graphes et Logique
Date | 2012-10-16 11:00-12:00 |
Titre | A Model Theoretic Proof of Completeness of an Axiomatization of Monadic Second-Order Logic on Infinite Words |
Résumé | We discuss the completeness of an axiomatization of Monadic Second-Order Logic (MSO) on infinite words (or streams). By using model-theoretic tools, we give an alternative proof of D. Siefkes' result that a fragment with full comprehension and induction of second-order Peano's arithmetic is complete w.r.t. the validity of MSO-formulas on streams. We rely on Feferman-Vaught Theorems and the Ehrenfeucht-Fraïssé method for Henkin models of second-order arithmetic. Our main technical contribution is an infinitary Feferman-Vaught 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 MSO-definable colorings, and show that in linearly ordered Henkin models, Ramsey's theorem for additive MSO-definable colorings implies Ramsey's theorem for all MSO-definable colorings. |
Lieu | 76 |
Orateur | Colin Riba |
Email | colin.riba@ens-lyon.fr |
Url | LIP, ENS Lyon |
Aucun document lié à cet événement. RetourRetour à l'index
| |