Equivalence élémentaire - Elementary equivalence

En théorie des modèles , branche de la logique mathématique , deux structures M et N de même signature σ sont appelées élémentairement équivalentes si elles satisfont les mêmes σ -sentences du premier ordre .

Si N est une sous - structure de M , on a souvent besoin d'une condition plus forte. Dans ce cas N est appelée sous - structure élémentaire de M si toute σ -formule φ du premier ordre ( a ₁ ,…,  a _n ) de paramètres a ₁ ,…,  a _n de N est vraie dans N si et seulement si elle est vrai dans  M . Si N est une sous - structure élémentaire de M , alors M est appelé une extension élémentaire de  N . Un enrobage h :  N  →  M est appelé un plongement élémentaire de N en M si h ( N ) est une sous - structure élémentaire de  M .

Une sous-structure N de M est élémentaire si et seulement si elle passe le test de Tarski – Vaught : toute formule du premier ordre φ ( x ,  b ₁ ,…,  b _n ) avec des paramètres dans N qui a une solution dans M a aussi une solution en  N lorsqu'elle est évaluée dans  M . On peut prouver que deux structures sont élémentairement équivalentes aux jeux Ehrenfeucht – Fraïssé .

Structures élémentairement équivalentes

Deux structures M et N de même signature  σ sont élémentairement équivalentes si toute phrase du premier ordre (formule sans variables libres) sur  σ est vraie dans M si et seulement si elle est vraie dans N , c'est-à-dire si M et N ont le même complet théorie du premier ordre. Si M et N sont élémentairement équivalentes, on écrit M  ≡  N .

Une théorie du premier ordre est complète si et seulement si deux de ses modèles sont élémentairement équivalents.

Par exemple, considérons le langage avec un symbole de relation binaire «<». Le modèle R des nombres réels avec son ordre habituel et le modèle Q des nombres rationnels avec son ordre habituel sont élémentairement équivalents, puisqu'ils interprètent tous deux «<» comme un ordre linéaire dense non borné . Ceci est suffisant pour assurer l'équivalence élémentaire, car la théorie des ordres linéaires denses non bornés est complète, comme le montre le test de Łoś – Vaught .

Plus généralement, toute théorie du premier ordre avec un modèle infini a des modèles non isomorphes, élémentairement équivalents, qui peuvent être obtenus via le théorème de Löwenheim – Skolem . Ainsi, par exemple, il existe des modèles non standard d' arithmétique Peano , qui contiennent d'autres objets que les nombres 0, 1, 2, etc., et qui sont pourtant élémentairement équivalents au modèle standard.

Sous-structures élémentaires et extensions élémentaires

N est une sous - structure élémentaire de M si N et M sont des structures de même signature   σ telles que pour toutes les σ -formules du premier ordre φ ( x ₁ ,…,  x _n ) de variables libres x ₁ ,…,  x _n , et tous les éléments a ₁ ,…,  a _n de  N , φ ( a ₁ ,…,  a _n ) tient dans N si et seulement si elle tient dans M :

N φ ( a ₁ ,…,  a _n ) ssi M φ ( a ₁ ,…,  a _n ). ${\ displaystyle \ models}$ ${\ displaystyle \ models}$

Il en résulte que N est une sous - structure de M .

Si N est une sous - structure de M , alors à la fois N et M peuvent être interprétées comme des structures dans la signature de _N composé de σ avec un nouveau symbole constant pour chaque élément de  N . Alors N est une sous-structure élémentaire de M si et seulement si N est une sous-structure de M et N et M sont élémentairement équivalents à σ _N -structures.

Si N est une sous - structure élémentaire de M , on écrit N M et dit que M est une extension élémentaire de N : M N . ${\ displaystyle \ preceq}$ ${\ displaystyle \ succeq}$

Le théorème descendant de Löwenheim – Skolem donne une sous-structure élémentaire dénombrable pour toute structure infinie du premier ordre dans une signature au plus dénombrable; le théorème ascendant de Löwenheim – Skolem donne des extensions élémentaires de toute structure infinie du premier ordre de cardinalité arbitrairement grande.

Test de Tarski-Vaught

Le test de Tarski – Vaught (ou critère de Tarski – Vaught ) est une condition nécessaire et suffisante pour qu'une sous-structure N d'une structure M soit une sous-structure élémentaire. Il peut être utile pour construire une sous-structure élémentaire d'une grande structure.

Que M soit une structure de signature σ et N une sous - structure de M . Alors N est une sous-structure élémentaire de M si et seulement si pour toute formule du premier ordre φ ( x ,  y ₁ ,…,  y _n ) sur σ et tous les éléments b ₁ ,…,  b _n de N , si M x φ ( x ,  b ₁ ,…,  b _n ), alors il y a un élément a dans N tel que M φ ( a ,  b ₁ ,…,  b _n ). ${\ displaystyle \ models}$ ${\ displaystyle \ existe}$  ${\ displaystyle \ models}$

Incorporations élémentaires

Un encastrement élémentaire d'une structure N dans une structure M de même signature σ est une application h :  N  →  M telle que pour toute σ -formule φ du premier ordre ( x ₁ ,…,  x _n ) et tous les éléments a ₁ , …,  Un _n de  N ,

N φ ( a ₁ ,…,  a _n ) si et seulement si M φ ( h ( a ₁ ),…,  h ( a _n )). ${\ displaystyle \ models}$ ${\ displaystyle \ models}$

Chaque incrustation élémentaire est un homomorphisme fort , et son image est une sous-structure élémentaire.

Les plongements élémentaires sont les cartes les plus importantes de la théorie des modèles. En théorie des ensembles , les plongements élémentaires dont le domaine est V (l'univers de la théorie des ensembles) jouent un rôle important dans la théorie des grands cardinaux (voir aussi Point critique ).

Les références

• Chang, Chen Chung ; Keisler, H. Jerome (1990) [1973], Model Theory , Studies in Logic and the Foundations of Mathematics (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 .
• Monk, J. Donald (1976), Logique mathématique , Textes de diplômés en mathématiques, New York • Heidelberg • Berlin: Springer Verlag, ISBN   0-387-90170-1