46 pages
Français

cours sur la théorie des modèles

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Theorie des modeles Frank Wagner

  • langage des ordres lord

  • lann-formules atomiques

  • classe des groupes abeliens

  • lgp-formules atomiques

  • proprietes communes des structures

  • produits des variables

  • formule


Sujets

Informations

Publié par
Nombre de lectures 53
Langue Français

Theorie des modeles
Frank WagnerLe con 1
Langage et structure
En theorie des modeles on n’analyse pas une seule structure, comme les
entiers ou les complexes, mais on prend une classe de structures, et on cherche
a determiner les proprietes communes des structures dans cette classe. En
general, une telle classe est aussi determinee par des proprietes, comme par
exemple la classe des corps, ou la classe des groupes abeliens. Parlons donc
des proprietes.
Pour exprimer une propriete, il nous faut d’abord un langage.
De nition 1.1 Un langageL est l’union (disjointe) d’un ensembleC de
symboles de constantes, d’un ensembleF de symboles de fonctions, et d’un
ensembleR de symboles de relations. A chaque f2F et chaque R2R est
associe un entier, l’arite, qui indique le nombre d’arguments.
En plus, on aura les variables, qui seront notes x;y;z;:::;x ;x ;x ;:::.0 1 2
Remarque 1.2 Une fonction d’arite 0 est une constante. Il y a deux rela-
tions d’arite 0 : la relation> qui est toujours vraie, et la relation? qui est
toujours fausse.
Exemple 1.3 1. Le langage des ordresL ne contient ni constantes niord
fonctions, mais deux relations binaires = et <.
2. Le langage des groupesL contient une constante 1, une fonctiongp
1unaire , une fonction binaire, et une relation binaire =.
3. Le langageL des anneaux contient trois fonctions binaires (d’ariteann
deux) +, et, une relation binaire =, et deux constantes 0 et 1.
1On utilise ce langage pour former des mots et des phrases.
De nition 1.4 SoitL un langage. La collection desL-termes est de ni
recursivement par :
toute constante et toute variable est unL-terme.
si f2F est une fonction n-aire et t ;:::;t sont desL-termes, alors1 n
f(t ;:::;t ) est unL-terme.1 n
UneL-formule atomique est une expression de la forme R(t ;:::;t ), ou1 n
R2R est une relation n-aire et t ;:::;t sont desL-termes. La collection1 n
desL-formules est de ni recursivement par :
uneL-formule atomique est uneL-formule.
si ’ et sont desL-formules, leurs combinaisons booleennes (’^ )
(conjonction, et), (’_ ) (disjonction, ou) et:’ (negation, non) sont
desL-formules.
si ’ est uneL-formule et x est une variable, les quanti cations 8x’
(universelle, quel que soit) et9x’ (existentielle, il y a) sont desL-
formules. Les occurrences de la variable x dans ces formules sont liees
a ce quanteur8 ou9 (sauf si elles sont dej a liees a un quanteur dans
’). Une variable qui n’est pas liee est libre.
Un enonce, ou une formule close, est une formule sans variable libre ; une
formule positive est une formule sans negation.
Exemple 1.5 1. Les seuls termes deL sont les variables ; lesL -ord ord
formules atomiques sont les egalites et les inegalites.
2. Parmi les termes deL , il y a les produits des variables et leurs inversesgp
(le produit vide etant egale a 1) ; en e et, modulo les lois de groupe
chaque terme est equivalent a un tel produit. Donc lesL -formulesgp
atomiques sont les equations.
3. Parmi les termes deL , il y a les polyn^ omes (en plusieurs variables)ann
a coe cients dans Z, ou l’entiern est une abbreviation pour 1 +::: + 1
n(somme den fois 1), etx denotexx (produit den foisx) ; dans
un anneau commutatif tout terme est equivalent a un tel polyn^ ome.
Donc, dans un anneau commutatif, lesL -formules atomiques sontann
les equations polyn^ omiales.
2Lemme 1.6 [Lecture unique]
1. Soit t un L-terme. Alors soit t est une constante ou une variable
(uniquement determinee), soit il y a une fonction f d’arite n, et des
L-termest ;:::;t , uniquement determines, tels quet estf(t ;:::;t ).n n 1 n
2. Soit ’ uneL-formule. Alors ’ tombe dans un (et un seul) des cas
suivants :
(a) ’ est atomique et il y a une relation R d’arite n, et desL-termes
t ;:::;t , uniquement determines, tels que ’ est R(t ;:::;t ),n n 1 n
(b) Il y a une formule uniquement determinee telle que ’ est: .
(c) Il y a deux formules et uniquement determinees telles que1 2
’ est ( ^ ).1 2
(d) Il y a deux formules et uniquement determinees telles que1 2
’ est ( _ ).1 2
(e) Il y a une formule et une variable x uniquement determinees
telles que ’ est9x .
(f) Il y a une formule et une variable x uniquement determinees
telles que ’ est8x .
Demonstration :
1. Par recurrence sur le nombre d’etapes dans la construction d’un terme
(que l’on ne suppose pas encore unique) on se rend compte que dans
un terme
il y a le m^eme nombre de \(" que de \)", et
toute virgule \," est precedee par plus de \(" que de \)".
Notons qu’un terme forme par iteration comporte au moins les deux
parentheses, donc est de longueur au moins deux. Donc, si t est un
mot de longueur un (un seul symbole), t est soit une constante, soit
une variable, qui est evidemment uniquement determinee. Si t est de
longueur superieure a un, t n’est ni constante ni variable. Donc t est
cree iterativement ; le premier symbole de t est une fonction f 2 F,
determinee uniquement, d’une certaine ariten. Commet est un terme,
3il y a des termes t ;:::;t tels que t est f(t ;:::;t ). Supposons donc1 n 1 n
que cette lecture n’est pas unique, qu’il y a d’autres termes s ;:::;s1 n
tels quet se lit aussif(s ;:::;s ). Sis n’est pas le m^eme quet , alors1 n 1 1
soits est un segment initial propre det , soitt en est un des . Donc1 1 1 1
soit t est s ;:::, soit s est t ;::: ; dans les deux cas la virgule est1 1 1 1
precedee par autant de \(" que de \)", une contradiction. Donc t est1
le m^eme que s , et on peut repeter avec t et s , ensuite t et s , etc.1 2 2 3 3
2. Par recurrence sur le nombre d’etapes dans la construction d’une for-
mule (que l’on ne suppose pas encore unique) on se rend compte que
dans une formule
il y a le m^eme nombre de \(" que de \)", et
tout \^" et tout \_" est precedee par plus de \(" que de \)".
Si une formule ’ commence par une negation \:", on est forcement
dans le cas (b), et ’ est de la forme: , ou est la formule obtenue
en supprimant le premier symbole \:".
Si ’ commence par un quanteur \9" ou \8", on est dans le cas (e) ou
(f) ; le second symbole est la variable, et le reste la formule .
Si’ commence par un symbole de relationR2R, elle est atomique ; si
n est l’arite deR, il existen termest ;:::;t tels que’ estR(t ;:::;t ).1 n 1 n
L’unicite de ces termes se montre comme pour la lecture unique des
termes.
Si ’ commence par une parenthese \(", on est dans le cas (c) ou (d).
0 0Supposons par exemple que ’ se lit a la fois ( ^ ) et ( ^ ),1 2 1 2
0 0ou est un segment initial propre de . Donc est ^:::, et la1 11 1
virgule est precedee par autant de \(" que de \)", une contradiction.
0Alors est , le prochain symbole est le connecteur booleen (^ ou1 1
_, uniquement determinee), et le reste (sauf la parenthese nale) est
. Les autres cas sont analogues.2
Maintenant que l’on a xe la syntaxe, il nous faut des objets.
De nition 1.7 SoitL un langage. UneL-structureM est un ensembleM,
le domaine deM (souvent confondu avecM), et
M pour chaque symbole c2C un element c 2M.
4M n pour chaque symbole f2F d’arite n une fonction f :M !M.
M n pour chaque symbole R2R d’arite n un sous-ensemble R de M .
De nition 1.8 SoitL une langage, etM uneL-structure. Sim est un uple
d’elements de M et x est un uple de variables (de la m^eme longueur) dans
un terme t(x), on peut substituer m pour toutes les occurences de x dans
t et obtenir un terme t(m ), un terme a parametres m . Nous allons de nir
Ml’interpretation t d’un terme t a parametres dans M clos (sans variable)
recursivement par :
M l’interpretation d’une constantec estc ; l’interpretation d’un parametre
m est m.
sif2F est une fonctionn-aire ett ;:::;t sont des termes a parametres,1 n
M M M Malors f(t ;:::;t ) =f (t ;:::;t ).1 n 1 n
Donc l’interpretation associe a chaque terme clos (avec parametres) un element
de M.
De m^eme, pour une formule ’(x), on peut substituer m pour toutes les
occurences libres de x dans ’ et obtenir une formule ’(m ) avec parametres.
(Par unicite de lecture, la liberte d’une variable est uniquement determinee.)
Nous allons de nir la satisfaction d’une formule close avec parametres dans
M recursivement par :
si ’(m ) est R(t (m );:::;t (m )) est une formule atomique, ou R2R1 n
est une relation n-aire et t ;:::;t sont des termes, alors ’(m ) est1 n
M M Msatisfaite dansM si (t (m ) ;:::;t (m ) )2R .1 n
si’ est (’^’ ), alors’ est satisfaite dansM si’ et’ sont satisfaites1 2 1 2
dansM.
si’ est (’ _’ ), alors’ est satisfaite dansM si’ ou’ (ou bien les1 2 1 2
deux) est satisfaite dansM.
si’ est: , alors ’ est satisfaite dansM si n’est pas satisfaite dans
M.
si ’ est8x (x), alors ’ est satisfaite dans M si pour tout m2 M la
formule (m) est satisfaite dansM.
5 si ’ est9x (x), alors ’ est satisfaite dans M s’il y a un m2 M tel
que (m) est satisfaite dansM.
Si’(m ) est satisfaite dansM, on le denote parMj=’(m ) ; on dit aussi que
’(m ) est vrai dansM, ou queM satisfait ’(m ).
Remarque 1.9 C’est cette de nition de la satisfaction qui donne le sens
usuel au connecteurs booleens et au quanteurs. Avant, ce n’etaient que des
symboles manipules de maniere purement syntaxique. Notons egalement que
la de nition est possible gr^ ace au lemme d’unicite de lecture.
On peut aussi voir les choses de l’autre c^ote : siMj=’(m ), on dit egalement
quem satisfait’(x) dansM, et on ecritmj= ’(x). Souvent on confondfM
M M Met f , R et R , et c et c . Donc, dans un anneau R, on parlera de +, ,
R R R, et pas de + , , .
Convention 1.10 Dans ce cours, l’egalite = fera partie de tous les langages,
et sera toujours interpretee par la vraie egalite. (Si = n’est pas interprete par
la vrai egalite, mais on considere une structure ou les axiomes habituels de
l’egalite sont satisfaits | qu’elle soit une congruence pour toutes les fonctions
et relations |, alors on pourra quotienter par = ; comme c’est une congru-
ence, ca nous induit uneL-structure sur l’ensemble des classes modulo =,
qu’on peut substituer pour la structure originale.)
Exemple 1.11 1. Considerons uneL -structureM satisfaisant :ord
(a)8x:x<x.
(b)8x8y ((x<y_y<x)_x =y).
(c)8x8y8z:((x<y^y<z)^ (z =x_z <x)).
MAlors la relation < est anti-re exive, totale, et transitive, donc un
ordre total. L’orde est sans extremite siM satisfait
8x9y9z (y<x^x<z) ;
il est dense siM satisfait
8x8y ((x =y_y<x)_9z (x<z^z <y)):
2. Considerons uneL -structureM. Elle est un groupe si elle satisfait :gp
6(a)8x (x 1 =x^ 1x =x).
1 1(b)8x (xx = 1^x x = 1).
(c)8x8y8z x (yz) = (xy)z.
Le groupe est abelien si8x8y xy =yx est vrai.
3. SoitM uneL -structure. Elle est un corps (commutatif) siann
M(a) (M; 0; + ) est un groupe abelien. (Qu’est-ce qu’on fait pour
l’inverse ?)
M(b) (Mf 0g; 1; ) est un groupe abelien. (Comment dire ca par un
enonce ?)
(c)8x8y8z x (y +z) =xy +xz.
Si est un ensemble d’enonces et M uneL-structure, on ecrit Mj=
siMj=’ pour tout ’2 ; on dit queM satisfait , que M realise , ou
bien queM est un modele de .
De nition 1.12 Soient ’(x) et (x) deuxL-formules. On dit que ’(x)
implique (x) si pour toutL-structure M et tout m 2 M, si Mj= ’(m ),
alorsMj= (m ).
Deux formules ’(x) et (x) sont equivalentes si ’ implique et im-
plique ’.
On a la m^eme de nition pour des ensembles ( x) et (x) deL-formules.
Lemme 1.13 Pour toutes ’ et , les formules suivantes sont equivalentes :
’ et::’.
:(’^ ) et (:’_: ), ainsi que:(’_ ) et (:’^: ) (de Morgan).
8x:’ et:9x’, ainsi que9x:’ et:8x’.
Demonstration : Par exemple, pour touteL-structureM et toutm dans
M on a
Mj=::’(m ) , M6j=:’(m )
, il n’est pas vrai queMj=:’(m )
, il n’est pas vrai queM6j=’(m )
, Mj=’(m ):
7Corollaire 1.14 Toute formule est equivalente a une formule qui n’utilise
qu’un des deux connecteurs booleens, et qu’un des deux quanteurs.
Demonstration : Gr^ ace au Lemme 1.13 on elimine iterativement un des
connecteurs et un des quanteurs.
Nous utiliserons aussi les abbreviations suivantes : (’! ) pour (:’_ ), et
(’$ ) pour ((’! )^( !’)). On doit faire attention : ces connecteurs
cachent des negations, et sont interdits dans les formules positives.
Exercice 1.15 Deux formules’(x) et (x) sont equivalentes si et seulement
si8x (’(x)$ (x)) est vrai dans touteL-structure.
Exercice 1.16 Dans une conjonction ou une disjonction de plusieurs argu-
ments, ’ ^^’ ou ’ __’ , tout choix des parentheses donne une0 n 0 n
formule equivalente.
V
A partir d’ici on va supprimer les parentheses super ues. On notera ’iinW
une conjonction ’ ^^’ , et ’ une disjonction ’ __’ .0 n i 0 nin
De nition 1.17 Une formule est prenexe si elle est de la forme
Q x Q x :::Q x ’;1 1 2 2 n n
ou Q 2f9;8g pour tout in, et ’ ne contient pas de quanteur.i
Exercice 1.18 Toute formule est equivalente a une formule prenexe.
De nition 1.19 Soientf’ : i < ng des formules, et ’ une combinaisoni
booleenne des’ . Alors’ est en forme disjonctive si elle est une disjonctioni
de conjonctions de formules’ ou:’ ; elle est en forme conjonctive si elle esti i
une conjonction de disjonctions de formules’ ou:’ . La forme est normalei i
si chaque conjonction/disjonction contient tous lesf’ :i<ng precisementi
une fois, soit positivement, soit en negation.
Exercice 1.20 Toute combinaison booleenne des formules f’ : i < ngi
est equivalente a une forme disjonctive normale (ou la disjonction vide est
equivalente a la formule?), et egalement a une forme conjonctive normale
(ou la conjonction vide est equivalente a la formule>).
8Le con 2
Equivalence elementaire et
sous-structures elementaires
De nition 2.1 UneL-theorie T est un ensemble consistant deL-enonces
(qui a un modele) ; elle est complete si pour chaque enonce’ soit tout modele
de T satisfait ’, soit tout modele satisfait:’.
Donc uneL-theorie est complete si et seulement si pour toutL-enonce ’,
soit Tj=’, soit Tj=:’.
Convention 2.2 Conformement a notre convention sur l’egalite, les ax-
iomes habituels sur = feront partie de toute theorie.
Si M est uneL-structure et A un ensemble d’elements dans M, laL(A)-
theorie deM, notee Th(M;A), est l’ensemble de tous les enonces a parametres
dansA qui sont satisfaits parM. Il est evident que c’est une theorie complete.
On pose Th(M) := Th(M;;).
Exemple 2.3 1. La theorie des ordres denses sans extremite est uneL -ord
theorie complete.
2. La theorie des groupes abeliens divisibles sans torsion est uneL -gp
theorie complete. Elle est donnee par la theorie des groupes abeliens,
plus
8x9y yy =x (produit den foisy), pour tout entiern> 0.
8x (x = 1_:xx = 1 (produit den foisx), pour tout entier
n> 0.
9