cours sur la théorie des modèles

Frank Wagner

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

• Wagner
• Formule

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 53
• Langue: Français

Extrait

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 ch