Théorie des modèles - Model theory

En logique mathématique , la théorie des modèles est l'étude de la relation entre les théories formelles (un ensemble de phrases dans un langage formel exprimant des déclarations sur une structure mathématique ) et leurs modèles, considérés comme des interprétations qui satisfont les phrases de cette théorie. Les aspects étudiés comprennent le nombre et la taille des modèles d'une théorie, la relation des différents modèles entre eux et leur interaction avec le langage formel lui-même. En particulier, les théoriciens des modèles étudient également les ensembles qui peuvent être définis dans un modèle d'une théorie, et la relation entre ces ensembles définissables. En tant que discipline à part entière, la théorie du modèle remonte à Alfred Tarski , qui a d' abord utilisé le terme « théorie des modèles » dans la publication en 1954. Depuis les années 1970, le sujet a été façonnée de manière décisive par Saharon Shelah de la théorie de la stabilité . L'accent relatif mis sur la classe des modèles d'une théorie par opposition à la classe des ensembles définissables au sein d'un modèle a fluctué dans l'histoire du sujet, et les deux directions sont résumées par les caractérisations lapidaires de 1973 et 1997 respectivement :

théorie des modèles = algèbre universelle + logique

où l'algèbre universelle représente les structures mathématiques et la logique les théories logiques ; et

théorie des modèles = géométrie algébrique − champs .

où les formules logiques sont aux ensembles définissables ce que les équations sont aux variétés sur un champ.

Néanmoins, l'interaction des classes de modèles et des ensembles définissables dans celles-ci a été cruciale pour le développement de la théorie des modèles tout au long de son histoire. Par exemple, alors que la stabilité a été introduite à l'origine pour classer les théories en fonction de leur nombre de modèles dans une cardinalité donnée, la théorie de la stabilité s'est avérée cruciale pour comprendre la géométrie des ensembles définissables.

Par rapport à d'autres domaines de la logique mathématique tels que la théorie de la preuve, la théorie des modèles est souvent moins concernée par la rigueur formelle et plus proche dans l'esprit des mathématiques classiques. Cela a incité le commentaire que « si la théorie de la preuve concerne le sacré, alors la théorie des modèles concerne le profane » . Les applications de la théorie des modèles à la géométrie algébrique et diophantienne reflètent cette proximité avec les mathématiques classiques, car elles impliquent souvent une intégration des résultats et des techniques algébriques et théoriques des modèles.

L'organisation savante la plus importante dans le domaine de la théorie des modèles est l' Association for Symbolic Logic .

Branches

Cette page se concentre sur la théorie des modèles finis du premier ordre des structures infinies. La théorie des modèles finis , qui se concentre sur les structures finies, s'écarte considérablement de l'étude des structures infinies à la fois dans les problèmes étudiés et les techniques utilisées. La théorie des modèles dans les logiques d'ordre supérieur ou les logiques infinités est entravée par le fait que l' exhaustivité et la compacité ne sont généralement pas valables pour ces logiques. Cependant, de nombreuses études ont également été menées dans de telles logiques.

De manière informelle, la théorie des modèles peut être divisée en théorie des modèles classiques, théorie des modèles appliquée aux groupes et aux champs et théorie des modèles géométriques. Une subdivision manquante est la théorie des modèles calculables , mais cela peut sans doute être considéré comme un sous-domaine indépendant de la logique.

Des exemples de premiers théorèmes de la théorie des modèles classiques incluent le théorème de complétude de Gödel , les théorèmes de Löwenheim-Skolem ascendant et descendant , le théorème des deux cardinaux de Vaught , le théorème d'isomorphisme de Scott , le théorème des types omis et le théorème de Ryll-Nardzewski . Des exemples de premiers résultats de la théorie des modèles appliqués aux champs sont l' élimination par Tarski des quantificateurs pour les champs fermés réels , le théorème d' Ax sur les champs pseudo-finis et le développement de l'analyse non standard par Robinson . Une étape importante dans l'évolution de la théorie des modèles classique s'est produite avec la naissance de la théorie de la stabilité (à travers le théorème de Morley sur les théories innombrables catégorielles et le programme de classification de Shelah ), qui a développé un calcul d'indépendance et de rang basé sur des conditions syntaxiques satisfaites par les théories.

Au cours des dernières décennies, la théorie des modèles appliquée a fusionné à plusieurs reprises avec la théorie plus pure de la stabilité. Le résultat de cette synthèse est appelé théorie des modèles géométriques dans cet article (qui est censée inclure la o-minimalité, par exemple, ainsi que la théorie classique de la stabilité géométrique). Un exemple d'une preuve de la théorie des modèles géométriques est la preuve de Hrushovski de la conjecture de Mordell-Lang pour les champs de fonction. L'ambition de la théorie des modèles géométriques est de fournir une géographie des mathématiques en se lançant dans une étude détaillée des ensembles définissables dans diverses structures mathématiques, aidée par les outils substantiels développés dans l'étude de la théorie des modèles pure.

Notions fondamentales de la théorie des modèles du premier ordre

Logique du premier ordre

Une formule du premier ordre est construite à partir de formules atomiques telles que R ( f ( x , y ), z ) ou y = x + 1 au moyen de connecteurs booléens et de préfixes de quantificateurs ou . Une phrase est une formule dans laquelle chaque occurrence d'une variable est dans la portée d'un quantificateur correspondant. Des exemples de formules sont φ (ou φ(x) pour marquer le fait qu'au plus x est une variable non liée dans ) et ψ définis comme suit : ${\displaystyle \neg ,\land ,\lor ,\rightarrow }$${\displaystyle \forall v}$${\style d'affichage \existe v}$

${\displaystyle {\varphi \;=\;\forall u\forall v(\exists w(x\times w=u\times v)\rightarrow (\exists w(x\times w=u)\lor \exists w(x\fois w=v)))\land x\neq 0\land x\neq 1,}}$

${\displaystyle \psi \;=\;\forall u\forall v((u\times v=x)\rightarrow (u=x)\lor (v=x))\land x\neq 0\land x\ neq 1.}$

(Notez que le symbole d'égalité a ici un double sens.) Il est intuitivement clair comment traduire de telles formules en un sens mathématique. Dans la structure σ _smr des nombres naturels, par exemple, un élément n satisfait la formule φ si et seulement si n est un nombre premier. La formule définit de la même manière l'irréductibilité. Tarski a donné une définition rigoureuse, parfois appelée « définition de la vérité de Tarski » , de la relation de satisfaction , de sorte que l'on prouve facilement : ${\displaystyle {\mathcal {N}}}$ ${\displaystyle \models }$

${\displaystyle {\mathcal {N}}\models \varphi (n)\iff n}$ est un nombre premier.

${\displaystyle {\mathcal {N}}\models \psi (n)\iff n}$ est irréductible.

Un ensemble T de phrases est appelé une théorie (du premier ordre) . Une théorie est satisfiable si elle a un modèle , c'est-à-dire une structure (de la signature appropriée) qui satisfait toutes les phrases de l'ensemble T . Une théorie complète est une théorie qui contient chaque phrase ou sa négation. La théorie complète de toutes les phrases satisfaites par une structure est aussi appelée la théorie de cette structure . ${\displaystyle {\mathcal {M}}\models T}$

Le théorème de complétude de Gödel (à ne pas confondre avec ses théorèmes d'incomplétude ) dit qu'une théorie a un modèle si et seulement si elle est cohérente , c'est-à-dire qu'aucune contradiction n'est prouvée par la théorie. Par conséquent, les théoriciens des modèles utilisent souvent « cohérent » comme synonyme de « satisfiable ».

Concepts de base de la théorie des modèles

Une signature ou un langage est un ensemble de symboles non logiques tels que chaque symbole est soit un symbole de fonction, soit un symbole de relation et a une arité spécifiée . Une structure est un ensemble avec des interprétations de chacun des symboles de la signature en tant que relations et fonctions sur (à ne pas confondre avec l' interprétation d'une structure dans une autre). Une signature commune pour les anneaux ordonnés est , où et sont des symboles de fonction 0-aire (également appelés symboles constants), et sont des symboles de fonction binaires, est un symbole de fonction unaire et est un symbole de relation binaire. Ensuite, lorsque ces symboles sont interprétés pour correspondre à leur signification habituelle sur (de sorte que par exemple est une fonction de à et est un sous-ensemble de ), on obtient une structure . Une structure est dite modéliser un ensemble de phrases du premier ordre dans la langue donnée si chaque phrase dans est vraie en ce qui concerne l'interprétation de la signature précédemment spécifiée pour . ${\style d'affichage M}$${\style d'affichage M}$${\displaystyle \sigma _{ou}=\{0,1,+,\times ,-,<\}}$${\style d'affichage 0}$${\style d'affichage 1}$${\style d'affichage +}$${\style d'affichage \fois }$${\style d'affichage -}$${\style d'affichage <}$${\displaystyle \mathbb {Q} }$${\style d'affichage +}$${\displaystyle \mathbb {Q} ^{2}}$${\displaystyle \mathbb {Q} }$${\style d'affichage <}$${\displaystyle \mathbb {Q} ^{2}}$${\displaystyle (\mathbb {Q} ,\sigma _{ou})}$${\displaystyle {\mathcal {N}}}$${\style d'affichage T}$${\style d'affichage T}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {N}}}$

Une sous - structure d'une -structure est un sous-ensemble de son domaine, fermé sous toutes les fonctions dans sa signature , qui est considérée comme une -structure en restreignant toutes les fonctions et relations dans σ au sous-ensemble. Ceci généralise les concepts analogues de l'algèbre ; Par exemple, un sous-groupe est une sous-structure dans la signature avec multiplication et inverse. ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$

Une sous-structure est dite élémentaire si pour toute formule du premier ordre φ et tout élément a ₁ , ..., a _n de , ${\displaystyle {\mathcal {A}}}$

${\displaystyle {\mathcal {A}}\models \varphi (a_{1},...,a_{n})}$si et seulement si .${\displaystyle {\mathcal {B}}\models \varphi (a_{1},...,a_{n})}$

En particulier, si φ est une phrase et une sous - structure élémentaire , alors si et seulement si . Ainsi, une sous-structure élémentaire est un modèle d'une théorie exactement quand la superstructure est un modèle. Par conséquent, alors que le corps des nombres algébriques est une sous-structure élémentaire du corps des nombres complexes , le champ rationnel ne l'est pas, comme nous pouvons exprimer "Il y a une racine carrée de 2" comme une phrase du premier ordre satisfaite par mais pas par . ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {A}}\models \varphi }$${\displaystyle {\mathcal {B}}\models \varphi }$${\displaystyle {\overline {\mathbb {Q} }}}$${\displaystyle \mathbb {C} }$${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {C} }$${\displaystyle \mathbb {Q} }$

Un plongement d'une -structure dans une autre σ-structure est une application f : A → B entre les domaines qui peut s'écrire comme un isomorphisme de avec une sous-structure de . S'il peut être écrit comme un isomorphisme avec une sous-structure élémentaire, on l'appelle un plongement élémentaire. Chaque plongement est un homomorphisme injectif , mais l'inverse n'est valable que si la signature ne contient aucun symbole de relation, comme dans les groupes ou les champs. ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$

Un champ ou un espace vectoriel peut être considéré comme un groupe (commutatif) en ignorant simplement une partie de sa structure. La notion correspondante dans la théorie des modèles est celle d'une réduction d'une structure à un sous-ensemble de la signature originale. La relation opposée est appelée un développement - par exemple le groupe (additif) des nombres rationnels , considéré comme une structure dans la signature {+,0} peut être étendu à un champ avec la signature {×,+,1,0} ou à un groupe ordonné avec la signature {+,0,<}.

De même, si σ' est une signature qui étend une autre signature σ, alors une σ'-théorie complète peut être restreinte à σ en coupant l'ensemble de ses phrases avec l'ensemble des -formules. Inversement, une -théorie complète peut être considérée comme une '-théorie, et on peut l'étendre (de plusieurs manières) à une '-théorie complète. Les termes de réduction et d'expansion sont parfois également appliqués à cette relation.

Compacité et théorème de Löwenheim-Skolem

Le théorème de compacité stipule qu'un ensemble de phrases S est satisfiable si chaque sous-ensemble fini de S est satisfiable. L'énoncé analogue avec consistant au lieu de satisfiable est trivial, puisque chaque preuve ne peut avoir qu'un nombre fini d'antécédents utilisés dans la preuve. Le théorème de complétude nous permet de transférer cela à la satsifiabilité. Cependant, il existe également plusieurs preuves directes (sémantiques) du théorème de compacité. En corollaire (c'est-à-dire sa contraposée), le théorème de compacité dit que toute théorie du premier ordre insatisfiable a un sous-ensemble fini insatisfiable. Ce théorème est d'une importance centrale dans la théorie des modèles, où les mots « par compacité » sont monnaie courante.

Une autre pierre angulaire de la théorie des modèles du premier ordre est le théorème de Löwenheim-Skolem. Selon le théorème de Löwenheim-Skolem, chaque structure infinie dans une signature dénombrable a une sous-structure élémentaire dénombrable. Inversement, pour tout cardinal infini κ chaque structure infinie dans une signature dénombrable qui est de cardinalité inférieure à κ peut être élémentairement intégrée dans une autre structure de cardinalité (il existe une généralisation directe aux signatures indénombrables). En particulier, le théorème de Löwenheim-Skolem implique que toute théorie dans une signature dénombrable avec des modèles infinis a un modèle dénombrable ainsi que des modèles arbitrairement grands.

Dans un certain sens précisé par le théorème de Lindström , la logique du premier ordre est la logique la plus expressive pour laquelle à la fois le théorème de Löwenheim-Skolem et le théorème de compacité tiennent.

Définition

Ensembles définissables

Dans la théorie des modèles, les ensembles définissables sont des objets d'étude importants. Par exemple, dans la formule ${\displaystyle \mathbb {N} }$

${\displaystyle \forall u\forall v(\existe w(x\times w=u\times v)\rightarrow (\existe w(x\times w=u)\lor \existe w(x\times w=v )))\land x\neq 0\land x\neq 1}$

définit le sous-ensemble des nombres premiers, tandis que la formule

${\displaystyle \exists y(2\times y=x)}$

définit le sous-ensemble des nombres pairs. De la même manière, les formules avec n variables libres définissent des sous-ensembles de . Par exemple, dans un champ, la formule ${\displaystyle {\mathcal {M}}^{n}}$

${\displaystyle y=x\fois x}$

définit la courbe de tous tels que . ${\style d'affichage (x,y)}$${\style d'affichage y=x^{2}}$

Les deux définitions mentionnées ici sont sans paramètre , c'est -à- dire que les formules de définition ne mentionnent aucun élément de domaine fixe. Cependant, on peut aussi envisager des définitions avec des paramètres du modèle . Par exemple, dans , la formule ${\displaystyle \mathbb {R} }$

${\displaystyle y=x\fois x+\pi }$

utilise le paramètre from pour définir une courbe. ${\style d'affichage \pi }$${\displaystyle \mathbb {R} }$

Éliminer les quantificateurs

En général, les ensembles définissables sans quantificateurs sont faciles à décrire, tandis que les ensembles définissables impliquant des quantificateurs éventuellement imbriqués peuvent être beaucoup plus compliqués.

Cela fait de l'élimination des quantificateurs un outil crucial pour l'analyse des ensembles définissables : une théorie T a une élimination des quantificateurs si chaque formule du premier ordre φ( x ₁ , ..., x _n ) sur sa signature est équivalente modulo T à une formule du premier ordre ψ ( x ₁ , ..., x _n ) sans quantificateurs, c'est-à-dire dans tous les modèles de T . Si la théorie d'une structure a une élimination de quantificateur, chaque ensemble définissable dans une structure est définissable par une formule sans quantificateur sur les mêmes paramètres que la définition d'origine. Par exemple, la théorie des champs algébriquement clos dans l' _{anneau de} signature σ = (×,+,−,0,1) a une élimination de quantificateur. Cela signifie que dans un corps algébriquement clos, chaque formule est équivalente à une combinaison booléenne d'équations entre polynômes. ${\displaystyle \forall x_{1}\dots \forall x_{n}(\phi (x_{1},\dots ,x_{n})\leftrightarrow \psi (x_{1},\dots ,x_{n }))}$

Si une théorie n'a pas d'élimination de quantificateur, on peut ajouter des symboles supplémentaires à sa signature pour qu'elle le fasse. La théorie des premiers modèles a consacré beaucoup d'efforts à prouver l'axiomatisation et les résultats d'élimination des quantificateurs pour des théories spécifiques, en particulier en algèbre. Mais souvent, au lieu de l'élimination du quantificateur, une propriété plus faible suffit :

Une théorie T est dite modèle-complète si toute sous-structure d'un modèle de T qui est elle-même un modèle de T est une sous-structure élémentaire. Il existe un critère utile pour tester si une sous-structure est une sous-structure élémentaire, appelé le test de Tarski-Vaught . Il découle de ce critère qu'une théorie T est modèle-complet si et seulement si chaque formule du premier ordre φ( x ₁ , ..., x _n ) sur sa signature est équivalente modulo T à une formule existentielle du premier ordre, c'est-à-dire une formule de la forme suivante :

${\displaystyle \exists v_{1}\dots \exists v_{m}\psi (x_{1},\dots ,x_{n},v_{1},\dots ,v_{m})}$,

où est sans quantificateur. Une théorie qui n'est pas modèle-complet peut avoir ou non un modèle-achèvement , qui est une théorie modèle-complet qui n'est pas, en général, une extension de la théorie originale. Une notion plus générale est celle de compagnon modèle .

Minimalité

Dans chaque structure, chaque sous-ensemble fini est définissable avec des paramètres : utilisez simplement la formule ${\displaystyle \{a_{1},\dots ,a_{n}\}}$

${\displaystyle x=a_{1}\vee \dots \vee a_{n}}$.

Puisque nous pouvons nier cette formule, chaque sous-ensemble cofini (qui comprend tous les éléments du domaine sauf un nombre fini) est également toujours définissable.

Cela conduit au concept d'une structure minimale . Une structure est dite minimale si chaque sous-ensemble définissable avec les paramètres de est fini ou cofini. Le concept correspondant au niveau des théories est appelé minimalité forte : Une théorie T est dite fortement minimale si tout modèle de T est minimal. Une structure est dite fortement minimale si la théorie de cette structure est fortement minimale. De manière équivalente, une structure est fortement minimale si chaque extension élémentaire est minimale. Puisque la théorie des champs algébriquement clos a une élimination de quantificateur, chaque sous-ensemble définissable d'un champ algébriquement clos est définissable par une formule sans quantificateur dans une variable. Les formules sans quantificateur dans une variable expriment des combinaisons booléennes d'équations polynomiales dans une variable, et comme une équation polynomiale non triviale dans une variable n'a qu'un nombre fini de solutions, la théorie des champs algébriquement clos est fortement minimale. ${\displaystyle {\mathcal {M}}}$${\displaystyle A\subseteq {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$

D'autre part, le champ des nombres réels n'est pas minimal : Considérons, par exemple, l'ensemble définissable ${\displaystyle \mathbb {R} }$

${\displaystyle \varphi (x)\;=\;\existe y(y\fois y=x)}$.

Cela définit le sous-ensemble des nombres réels non négatifs, qui n'est ni fini ni cofini. On peut en effet utiliser pour définir des intervalles arbitraires sur la droite des nombres réels. Il s'avère que ceux-ci suffisent pour représenter chaque sous-ensemble définissable de . Cette généralisation de la minimalité a été très utile dans la théorie des modèles des structures ordonnées. Une structure densément totalement ordonnée dans une signature incluant un symbole pour la relation d'ordre est appelée o-minimal si chaque sous-ensemble définissable avec les paramètres de est une union finie de points et d'intervalles. ${\displaystyle \varphi }$${\displaystyle \mathbb {R} }$${\displaystyle {\mathcal {M}}}$${\displaystyle A\subseteq {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$

Des structures définissables et interprétables

Les ensembles définissables qui sont également des sous-structures, c'est-à-dire contiennent toutes les constantes et sont fermés sous l'application de la fonction, sont particulièrement importants. Par exemple, on peut étudier les sous-groupes définissables d'un certain groupe. Cependant, il n'est pas nécessaire de se limiter aux sous-structures d'une même signature. Étant donné que les formules avec n variables libres définissent des sous-ensembles de , les relations n- aires peuvent également être définissables. Les fonctions sont définissables si le graphe de fonctions est une relation définissable, et les constantes sont définissables s'il existe une formule telle que a est le seul élément de telle qui soit vrai. De cette façon, on peut étudier des groupes et des champs définissables dans des structures générales, par exemple, ce qui a été important dans la théorie de la stabilité géométrique. ${\displaystyle {\mathcal {M}}^{n}}$${\displaystyle a\in {\mathcal {M}}}$${\style d'affichage \varphi (x)}$${\displaystyle {\mathcal {M}}}$${\style d'affichage \varphi (a)}$

On peut même aller plus loin et dépasser les sous-structures immédiates. Étant donné une structure mathématique, il existe très souvent des structures associées qui peuvent être construites comme un quotient d'une partie de la structure d'origine via une relation d'équivalence. Un exemple important est un groupe quotient d'un groupe. On pourrait dire que pour comprendre la structure complète, il faut comprendre ces quotients. Lorsque la relation d'équivalence est définissable, on peut donner à la phrase précédente un sens précis. On dit que ces structures sont interprétables . Un fait clé est que l'on peut traduire des phrases du langage des structures interprétées vers le langage de la structure originale. Ainsi on peut montrer que si une structure interprète une autre dont la théorie est indécidable, alors elle-même est indécidable. ${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$

Les types

Notions de base

Pour une séquence d'éléments d'une structure et un sous-ensemble A de , on peut considérer l'ensemble de toutes les formules du premier ordre avec des paramètres dans A qui sont satisfaits par . C'est ce qu'on appelle le type (n-) complet réalisé par plus de A . S'il existe un automorphisme de qui est constant sur A et envoie à respectivement, alors et réalisez le même type complet sur A . ${\displaystyle a_{1},\dots ,a_{n}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle \varphi (x_{1},\dots ,x_{n})}$${\displaystyle a_{1},\dots ,a_{n}}$ ${\displaystyle a_{1},\dots ,a_{n}}$ ${\displaystyle {\mathcal {M}}}$${\displaystyle a_{1},\dots ,a_{n}}$${\displaystyle b_{1},\dots ,b_{n}}$${\displaystyle a_{1},\dots ,a_{n}}$${\displaystyle b_{1},\dots ,b_{n}}$

La droite numérique réelle , considérée comme une structure avec uniquement la relation d'ordre {<}, servira d'exemple courant dans cette section. Chaque élément satisfait le même type 1 sur l'ensemble vide. Ceci est clair puisque deux nombres réels a et b sont connectés par l'automorphisme d'ordre qui décale tous les nombres de ba . Le 2-type complet sur l'ensemble vide réalisé par une paire de nombres dépend de leur ordre : soit , soit . Sur le sous-ensemble d'entiers, le type 1 d'un nombre réel non entier a dépend de sa valeur arrondie à l'entier inférieur le plus proche. ${\displaystyle \mathbb {R} }$${\displaystyle a\in \mathbb {R} }$${\style d'affichage a_{1},a_{2}}$${\displaystyle a_{1}<a_{2}}$${\displaystyle a_{1}=a_{2}}$${\displaystyle a_{2}<a_{1}}$${\displaystyle \mathbb {Z} \subseteq \mathbb {R} }$

Plus généralement, chaque fois qu'une structure et A sont un sous-ensemble de , un n-type (partiel) sur A est un ensemble de formules p avec au plus n variables libres qui sont réalisées dans une extension élémentaire de . Si p contient chacune de ces formules ou sa négation, alors p est complet . L'ensemble des n- types complets sur A est souvent écrit sous la forme . Si A est l'ensemble vide, alors l'espace des types ne dépend que de la théorie T de . La notation est couramment utilisée pour l'ensemble des types sur l'ensemble vide cohérent avec T . S'il existe une seule formule telle que la théorie de implique pour chaque formule de p , alors p est appelé isolé . ${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {N}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle S_{n}^{\mathcal {M}}(A)}$${\displaystyle {\mathcal {M}}}$${\style d'affichage S_{n}(T)}$${\displaystyle \varphi }$${\displaystyle {\mathcal {M}}}$${\displaystyle \varphi \rightarrow \psi }$${\style d'affichage \psi }$

Puisque les nombres réels sont d' Archimède , il n'y a pas de nombre réel plus grand que chaque entier. Cependant, un argument de compacité montre qu'il existe une extension élémentaire de la droite des nombres réels dans laquelle il y a un élément plus grand que tout entier. Par conséquent, l'ensemble des formules est un type 1 supérieur qui n'est pas réalisé dans la droite numérique réelle . ${\displaystyle \mathbb {R} }$${\displaystyle \{n<x|n\in \mathbb {Z} \}}$${\displaystyle \mathbb {Z} \subseteq \mathbb {R} }$${\displaystyle \mathbb {R} }$

Un sous-ensemble de cela peut être exprimé comme exactement ces éléments de réalisation d'un certain type sur A est appelé type-definable sur A . Pour un exemple algébrique, supposons que est un champ algébriquement clos . La théorie a l'élimination du quantificateur. Cela nous permet de montrer qu'un type est déterminé exactement par les équations polynomiales qu'il contient. Ainsi, l'ensemble des -types complets sur un sous-corps correspond à l'ensemble des idéaux premiers de l' anneau polynomial , et les ensembles définissables par type sont exactement les variétés affines. ${\displaystyle {\mathcal {M}}^{n}}$${\displaystyle {\mathcal {M}}^{n}}$${\style d'affichage M}$${\style d'affichage n}$${\style d'affichage A}$ ${\displaystyle A[x_{1},\ldots ,x_{n}]}$

Structures et types

Bien que chaque type ne soit pas réalisé dans chaque structure, chaque structure réalise ses types isolés. Si les seuls types sur l'ensemble vide qui sont réalisés dans une structure sont les types isolés, alors la structure est appelée atomic .

D'un autre côté, aucune structure ne réalise chaque type sur chaque jeu de paramètres ; si l'on prend all of comme jeu de paramètres, alors chaque 1-type sur réalisé dans est isolé par une formule de la forme a = x pour an . Cependant, toute extension élémentaire appropriée de contient un élément qui n'est pas dans . Par conséquent, une notion plus faible a été introduite qui capture l'idée d'une structure réalisant tous les types qu'elle pourrait réaliser. Une structure est dite saturée si elle réalise chaque type sur un ensemble de paramètres dont la cardinalité est inférieure à elle-même. ${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle a\in {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$${\displaystyle A\sous-ensemble {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$

Alors qu'un automorphisme constant sur A conservera toujours les types sur A , il n'est généralement pas vrai que deux séquences et qui satisfont le même type sur A puissent être mappées l'une à l'autre par un tel automorphisme. Une structure dans laquelle cette réciproque est vraie pour tout A de plus petite cardinalité que ce qu'on appelle homogène . ${\displaystyle a_{1},\dots ,a_{n}}$${\displaystyle b_{1},\dots ,b_{n}}$${\displaystyle {\mathcal {M}}}$${\displaystyle {\mathcal {M}}}$

La droite numérique réelle est atomique dans le langage qui ne contient que l'ordre , puisque tous les n- types sur l'ensemble vide réalisé par in sont isolés par les relations d'ordre entre les . Il n'est cependant pas saturé, car il ne réalise aucun type 1 sur l'ensemble dénombrable qui implique que x soit plus grand que n'importe quel entier. La droite des nombres rationnels est saturée, en revanche, puisqu'elle est elle-même dénombrable et n'a donc qu'à réaliser des types sur des sous-ensembles finis pour être saturée. ${\style d'affichage <}$${\displaystyle a_{1},\dots ,a_{n}}$${\displaystyle \mathbb {R} }$${\displaystyle a_{1},\dots ,a_{n}}$${\displaystyle \mathbb {Z} }$${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {Q} }$

Espaces en pierre

L'ensemble des sous-ensembles définissables de plus de certains paramètres est une algèbre booléenne . D'après le théorème de représentation de Stone pour les algèbres booléennes, il existe un espace topologique double naturel , qui se compose exactement des -types complets sur . La topologie générée par les ensembles de la forme pour les formules simples . C'est ce qu'on appelle l' espace de Stone des n-types sur A . Cette topologie explique une partie de la terminologie utilisée dans la théorie des modèles : Le théorème de compacité dit que l'espace de pierre est un espace topologique compact et qu'un type p est isolé si et seulement si p est un point isolé dans la topologie de pierre. ${\displaystyle {\mathcal {M}}^{n}}$${\style d'affichage A}$${\style d'affichage n}$${\style d'affichage A}$${\displaystyle \{p|\varphi \in p\}}$${\displaystyle \varphi }$

Alors que les types dans les corps algébriquement clos correspondent au spectre de l'anneau polynomial, la topologie sur l'espace des types est la topologie constructible : un ensemble de types est ouvert de base s'il est de la forme ou de la forme . C'est plus fin que la topologie de Zariski . ${\displaystyle \{p:f(x)=0\in p\}}$${\displaystyle \{p:f(x)\neq 0\in p\}}$

Catégorie

Une théorie était à l'origine dite catégorique si elle détermine une structure jusqu'à l'isomorphisme. Il s'avère que cette définition n'est pas utile, en raison de sérieuses restrictions dans l'expressivité de la logique du premier ordre. Le théorème de Löwenheim-Skolem implique que si une théorie T a un modèle infini pour un nombre cardinal infini , alors elle a un modèle de taille κ pour tout nombre cardinal suffisamment grand κ. Puisque deux modèles de tailles différentes ne peuvent pas être isomorphes, seules les structures finies peuvent être décrites par une théorie catégorique.

Cependant, la notion plus faible de -catégorie pour un cardinal κ est devenue un concept clé dans la théorie des modèles. Une théorie T est dite κ-catégorique si deux modèles de T de cardinalité sont isomorphes. Il s'avère que la question de la κ-catégorie dépend essentiellement du fait que κ est plus grand que la cardinalité du langage (c'est-à-dire  + |σ|, où |σ| est la cardinalité de la signature). Pour les signatures finies ou dénombrables, cela signifie qu'il existe une différence fondamentale entre la -cardinalité et la κ-cardinalité pour les indénombrables. ${\displaystyle \aleph _{0}}$${\displaystyle \omega }$

${\displaystyle \omega }$-catégorie

${\displaystyle \omega }$-les théories catégorielles peuvent être caractérisées par des propriétés de leur espace type :

Pour une théorie complète du premier ordre T dans une signature finie ou dénombrable les conditions suivantes sont équivalentes :

1. T est -catégorique.${\displaystyle \omega }$
2. Chaque type dans S _n ( T ) est isolé.
3. Pour tout entier naturel n , S _n ( T ) est fini.
4. Pour tout entier naturel n , le nombre de formules φ( x ₁ , ..., x _n ) en n variables libres, à l'équivalence modulo T près , est fini.

La théorie de , qui est aussi la théorie de , est -catégorique, car chaque n -type sur l'ensemble vide est isolé par la relation d'ordre par paires entre le . Cela signifie que chaque ordre linéaire dense dénombrable est isomorphe d'ordre à la droite numérique rationnelle. D'autre part, les théories des champs , et as ne sont pas -catégoriques. Cela découle du fait que dans tous ces domaines, n'importe lequel des nombres naturels infiniment nombreux peut être défini par une formule de la forme . ${\displaystyle (\mathbb {Q} ,<)}$${\style d'affichage (\mathbb {R} ,<)}$${\displaystyle \omega }$${\displaystyle p(x_{1},\dots ,x_{n})}$${\style d'affichage x_{i}}$${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {C} }$${\displaystyle \omega }$${\displaystyle x=1+\dots +1}$

${\displaystyle \aleph _{0}}$-les théories catégorielles et leurs modèles dénombrables ont aussi des liens forts avec les groupes oligomorphes :

Une théorie complète du premier ordre T dans une signature finie ou dénombrable est -catégorique si et seulement si son groupe d'automorphismes est oligomorphe.${\displaystyle \omega }$

Les caractérisations équivalentes de cette sous-section, dues indépendamment à Engeler , Ryll-Nardzewski et Svenonius , sont parfois appelées théorème de Ryll-Nardzewski.

Dans les signatures combinatoires, une source commune de théories -catégorielles sont les limites de Fraïssé , qui sont obtenues comme la limite de fusion de toutes les configurations possibles d'une classe de structures relationnelles finies. ${\displaystyle \omega }$

Catégorie indénombrable

Michael Morley a montré en 1963 qu'il n'y a qu'une seule notion de catégorisation indénombrable pour les théories dans les langues dénombrables.

Le théorème de catégorité de Morley

Si une théorie du premier ordre T dans une signature finie ou dénombrable est -catégorique pour un cardinal indénombrable κ, alors T est κ-catégorique pour tous les cardinaux indénombrables κ.

La preuve de Morley a révélé des liens profonds entre une catégorisation indénombrable et la structure interne des modèles, qui sont devenus le point de départ de la théorie de la classification et de la théorie de la stabilité. D'innombrables théories catégoriques sont, à bien des égards, les théories les plus sages. En particulier, les théories complètes fortement minimales sont infiniment catégoriques. Cela montre que la théorie des champs algébriquement clos d'une caractéristique donnée est innombrablement catégorique, le degré de transcendance du champ déterminant son type d'isomorphisme.

Une théorie à la fois catégorique et indénombrablement catégorique est dite totalement catégorique . ${\displaystyle \omega }$

Candidatures sélectionnées

Parmi les premiers succès de la théorie des modèles figurent les preuves de Tarski de la décidabilité de diverses classes algébriquement intéressantes, telles que les corps réels fermés , les algèbres booléennes et les corps algébriquement fermés d'une caractéristique donnée .

Dans les années 1960, des considérations autour des modèles saturés et de la construction d' ultraproduits conduisent au développement par Abraham Robinson de l'analyse non standard .

En 1965, James Axe et Simon B. Kochen ont montré un cas particulier de la conjecture d'Artin sur les équations diophantiennes, le théorème d'Ax-Kochen , à nouveau en utilisant une construction ultraproduit.

Plus récemment, la connexion entre la stabilité et la géométrie des ensembles définissables a conduit à plusieurs applications de la géométrie algébrique et diophantienne, y compris la preuve par Ehud Hrushovski 1996 de la conjecture géométrique de Mordell-Lang dans toutes les caractéristiques

En 2011, Jonathan Pila a appliqué des techniques autour de l' o-minimalité pour prouver la conjecture d'André-Oort pour les produits de courbes modulaires.

Dans un autre volet d'enquêtes qui s'est également développé autour de théories stables, Laskowski a montré en 1992 que les théories NIP décrivent exactement les classes définissables qui peuvent être apprises par PAC dans la théorie de l'apprentissage automatique.

Histoire

La théorie des modèles en tant que sujet existe depuis environ le milieu du 20e siècle. Cependant, certaines recherches antérieures, en particulier en logique mathématique , sont souvent considérées rétrospectivement comme étant de nature modèle-théorique. Le premier résultat significatif de ce qui est maintenant la théorie des modèles était un cas particulier du théorème descendant de Löwenheim-Skolem, publié par Leopold Löwenheim en 1915. Le théorème de compacité était implicite dans les travaux de Thoralf Skolem , mais il a été publié pour la première fois en 1930, en tant que lemme dans la preuve de Kurt Gödel de son théorème de complétude . Le théorème de Löwenheim-Skolem et le théorème de compacité ont reçu leurs formes générales respectives en 1936 et 1941 d' Anatoly Maltsev . Le développement de la théorie des modèles en tant que discipline indépendante a été provoqué par Alfred Tarski , membre de l' école Lwów-Varsovie pendant l' interbellum . Les travaux de Tarski comprenaient la conséquence logique , les systèmes déductifs , l'algèbre de la logique, la théorie de la définissabilité et la définition sémantique de la vérité , entre autres sujets. Ses méthodes sémantiques ont abouti à la théorie des modèles que lui et un certain nombre de ses étudiants de Berkeley ont développée dans les années 1950 et 1960.

Dans la suite de l'histoire de la discipline, différents courants ont commencé à émerger et l'orientation du sujet a changé. Dans les années 1960, les techniques autour des ultraproduits sont devenues un outil populaire dans la théorie des modèles. Dans le même temps, des chercheurs tels que James Axe étudiaient la théorie des modèles du premier ordre de diverses classes algébriques, et d'autres comme H. Jerome Keisler étendaient les concepts et les résultats de la théorie des modèles du premier ordre à d'autres systèmes logiques. Ensuite, les travaux de Saharon Shelah autour de la catégorisation et le problème de Morley ont changé le teint de la théorie des modèles, donnant naissance à une toute nouvelle classe de concepts. La théorie de la stabilité ( théorie de la classification) développée par Shelah depuis la fin des années 1960 vise à classer les théories selon le nombre de modèles différents qu'elles possèdent pour une cardinalité donnée. Au cours des décennies suivantes, il est devenu clair que la hiérarchie de stabilité résultante est étroitement liée à la géométrie des ensembles définissables dans ces modèles ; cela a donné naissance à la sous-discipline maintenant connue sous le nom de théorie de la stabilité géométrique.

Liens avec les branches connexes de la logique mathématique

Théorie des modèles finis

La théorie des modèles finis (FMT) est le sous-domaine de la théorie des modèles (MT) qui traite de sa restriction aux interprétations sur les structures finies, qui ont un univers fini.

Étant donné que de nombreux théorèmes centraux de la théorie des modèles ne tiennent pas lorsqu'ils sont limités aux structures finies, FMT est assez différent de MT dans ses méthodes de preuve. Les résultats centraux de la théorie des modèles classiques qui échouent pour les structures finies sous FMT incluent le théorème de compacité , le théorème de complétude de Gödel et la méthode des ultraproduits pour la logique du premier ordre .

Les principaux domaines d'application de FMT sont théorie de la complexité descriptive , la théorie de la base de données et théorie des langages formels .

Théorie des ensembles

Toute théorie des ensembles (qui s'exprime dans un langage dénombrable ), si elle est cohérente, a un modèle dénombrable ; c'est ce qu'on appelle le paradoxe de Skolem , car il existe des phrases en théorie des ensembles qui postulent l'existence d'ensembles indénombrables et pourtant ces phrases sont vraies dans notre modèle dénombrable. En particulier, la preuve de l'indépendance de l' hypothèse du continu nécessite de considérer des ensembles dans des modèles qui semblent indénombrables lorsqu'ils sont vus de l' intérieur du modèle, mais qui sont dénombrables pour quelqu'un en dehors du modèle.

Le point de vue de la théorie des modèles a été utile en théorie des ensembles ; par exemple dans le travail de Kurt Gödel sur l'univers constructible, qui, avec la méthode de forçage développée par Paul Cohen peut être montré pour prouver l' indépendance (encore une fois philosophiquement intéressante) de l' axiome du choix et de l'hypothèse du continu par rapport aux autres axiomes de la théorie des ensembles.

Dans l'autre sens, la théorie des modèles elle-même peut être formalisée dans la théorie des ensembles ZFC. Par exemple, la formalisation de la satisfaction dans ZFC se fait de manière inductive, basée sur le schéma en T de Tarski et l'observation de l'endroit où se trouvent les membres de la gamme d'affectations de variables. Le développement des fondements de la théorie des modèles (comme le théorème de compacité) repose sur l'axiome du choix, ou plus exactement le théorème de l'idéal premier booléen. D'autres résultats en théorie des modèles dépendent d'axiomes de la théorie des ensembles au-delà du cadre ZFC standard. Par exemple, si l'hypothèse du continu est vérifiée, alors chaque modèle dénombrable a une ultrapuissance qui est saturée (dans sa propre cardinalité). De même, si l'hypothèse du continu généralisé est vérifiée, alors chaque modèle a une extension élémentaire saturée. Aucun de ces résultats n'est prouvable dans le ZFC seul. Enfin, certaines questions issues de la théorie des modèles (comme la compacité pour les logiques infinités) se sont avérées équivalentes aux grands axiomes cardinaux.

Voir également

Remarques

Les références

Manuels canoniques

• Chang, Chen Chung ; Keisler, H. Jérôme (1990) [1973]. Théorie des modèles . Études en logique et les fondements des mathématiques (3e éd.). Elsevier. ISBN 978-0-444-88054-3.
• Hodges, Wilfrid (1997). Une théorie des modèles plus courte . Cambridge : Cambridge University Press . ISBN 978-0-521-58713-6.
• Kopperman, R. (1972). La théorie des modèles et ses applications . Boston : Allyn et Bacon .
• Marqueur, David (2002). Théorie des modèles : une introduction . Textes d'études supérieures en mathématiques 217. Springer. ISBN 0-387-98760-6.

D'autres manuels

• Bell, John L.; Slomson, Alan B. (2006) [1969]. Modèles et ultraproduits : une introduction (réimpression de 1974 ed.). Publications de Douvres . ISBN 0-486-44979-3.
• Ebbinghaus, Heinz-Dieter ; Flum, Jörg; Thomas, Wolfgang (1994). Logique mathématique . Springer . ISBN 0-387-94258-0.
• Hinman, Peter G. (2005). Fondements de la logique mathématique . AK Peters . ISBN 1-56881-262-0.
• Hodges, Wilfrid (1993). Théorie des modèles . Presse de l'Université de Cambridge . ISBN 0-521-30442-3.
• Manzano, Maria (1999). Théorie des modèles . Presse de l'Université d'Oxford . ISBN 0-19-853851-0.
• Poizat, Bruno (2000). Un cours de théorie des modèles . Springer. ISBN 0-387-98655-3.
• Rautenberg, Wolfgang (2010). Une introduction concise à la logique mathématique (3e éd.). New York : Springer Science+Business Media . doi : 10.1007/978-1-4419-1221-3 . ISBN 978-1-4419-1220-6.
• Rothmaler, Philipp (2000). Introduction à la théorie des modèles (nouvelle édition). Taylor & François . ISBN 90-5699-313-5.
• Tente, Katrin ; Ziegler, Martin (2012). Un cours de théorie des modèles . Presse de l'Université de Cambridge . ISBN 9780521763240.
• Kirby, Jonathan (2019). Une invitation à la théorie des modèles . Presse de l'Université de Cambridge . ISBN 978-1-107-16388-1.

Textes en ligne gratuits

• Chatzidakis, Zoé (2001). Introduction à la théorie des modèles (PDF) . p. 26 pages.
• Pillay, Anand (2002). Notes de cours – Théorie des modèles (PDF) . p. 61 pages.
• "Théorie des modèles" , Encyclopédie des mathématiques , EMS Press , 2001 [1994]
• Hodges, Wilfrid , Théorie des modèles . L'Encyclopédie de Stanford de Philosophie, E. Zalta (le rédacteur).
• Hodges, Wilfrid , Théorie des modèles du premier ordre . L'Encyclopédie de Stanford de Philosophie, E. Zalta (le rédacteur).
• Simmons, Harold (2004), Une introduction à la bonne théorie des modèles à l'ancienne . Notes d'un cours d'introduction pour les étudiants de troisième cycle (avec exercices).
• J. Barwise et S. Feferman (éditeurs), Model-Theoretic Logics , Perspectives in Mathematical Logic, Volume 8, New York : Springer-Verlag, 1985.