First Order Preservation Theorems in Finite Model Theory : Locality, Topology, and Limit Constructions
Théorèmes de préservation pour la logique au premier ordre: localité, topologie et constructions limites
Résumé
Preservation theorems in first-order logic constitute a collection of results from classical model theory. These establish a direct correspondence between the semantic properties of the formulas and the syntactic constraints imposed by the language used to express them. However, the study of these theorems becomes particularly difficult when we restrict ourselves to finite models, which is all the more regrettable since the field of finite model theory is better suited to describing the phenomena observed in computer science. This thesis proposes a systematic approach to study preservation theorems within the framework of finite model theory. Already existing ad-hoc proofs are understood as part of a more general theory that encompasses locality-based techniques, relying on a topological presentation of preservation theorems called logically presented prespectral spaces. The introduction of these topological spaces allows the development of a compositional theory of preservation theorems. Furthermore, this thesis constitutes a first step towards the systematic examination of preservation theorems in classes of finite structures defined by induction. This is achieved by proving a generic fixed point theorem for a topological extension of logically presented prespectral spaces, more precisely Noetherian spaces.
Les théorèmes de préservation en logique du premier ordre constituent une collection de résultats provenant de la théorie classique des modèles. Ceux-ci établissent une correspondance directe entre les propriétés sémantiques des formules et les contraintes syntaxiques imposées par le langage utilisé pour les exprimer. Cependant, l'étude de ces théorèmes devient particulièrement difficile lorsqu'on se restreint à des modèles finis, ce qui est d'autant plus regrettable que le domaine de la théorie des modèles finis est mieux adaptée pour décrire les phénomènes observés en informatique. Cette thèse propose une approche systématique pour étudier les théorèmes de préservation dans le cadre de la théorie des modèles finis. Les preuves ad-hoc déjà existantes sont comprises dans le cadre d'une théorie plus générale qui englobe les techniques basées sur la localité, reposant sur une présentation topologique des théorèmes de préservation appelée espaces préspectraux logiquement présentés. L'introduction de ces espaces topologiques permet le développement d'une théorie compositionnelle des théorèmes de préservation. De plus, cette thèse constitue une première étape vers l'examen systématique des théorèmes de préservation dans des classes de structures finies définies par induction. Cela est réalisé en démontrant un théorème de point fixe générique pour une extension topologique des espaces préspectraux logiquement présentés, plus précisément les espaces noethériens.
Origine : Fichiers produits par l'(les) auteur(s)