Université Claude Bernard Lyon I 2nd semestre Master Introduction la Logique

Claude Bernard Lyon

Description

Niveau: Supérieur, Master
Université Claude Bernard Lyon I 2nd semestre 2009/2010 Master 1 Introduction à la Logique Théorie des ensembles Correction du DM4. Exercice 1. 1. (a) Par symétrie, il suffit de montrer que si ? est un énoncé de la forme ?x1 . . . xn ?(x1, . . . , xn) avec ? sans quantificateurs alors (T1 ?) ? (T2 ?). Pour cela, supposons que T1 ? et considérons un modèleM2 de T2. Par hypothèse,M2 se plonge dans un modèleM1 de T1 ; notons ? un plongement deM2 dansM1. On doit avoir M1 ?x1 . . . xn?(x1, . . . , xn) Considéronsm1, . . . ,mn dansM2 ; puisque (?(m1), . . . , ?(mn)) ?M1 on aM1 ?(?(m1), . . . , ?(mn)). Or, le fait que ? soit un plongement et que ? soit sans quantificateurs entraîne que (M1 ?(?(m1), . . . , ?(mn)))? (M2 ?(m1, . . . ,mn)) . Par conséquent, on doit avoir M2 ?x1 . . . xn ?(x1, . . . , xn), ceci étant vrai pour tout modèle de T2.

• théorie des corps


• t1 ?


• conséquent


• morphisme de corps de f˜p


• indication de l'énoncé


• application ?


• théorie


• modèlem2 de t2

Sujets

• Corps (mathématiques)
• Consequent
• Théorie

Informations

• Publié par: cidur
• Nombre de lectures: 52
• Langue: Français

Extrait

UniversitÉ Claude Bernard Lyon I Master 1

ThÉorie des Correction

ensembles du DM4.

2nd semestre Introduction À

2009/2010 la Logique

Exercice 1. 1. (a)Par symÉtrie, il suffit de montrer que siθest un ÉnoncÉ de la forme∀x 1 . . . x n φ(x 1 , . . . , x n )avecφ sans quantificateurs alors(T 1 `θ)⇒(T 2 `θ). Pour cela, supposons queT 1 `θet considÉrons un modÈleM 2 deT 2 . Par hypothÈse,M 2 se plonge dans un modÈleM 1 deT 1 ; notonsσun plongement deM 2 dansM 1 . On doit avoir M 1 ∀x 1 . . . x n φ(x 1 , . . . , x n ) ConsidÉronsm 1 , . . . , m n dansM 2 ; puisque(σ(m 1 ), . . . , σ(m n ))∈ M 1 on aM 1 φ(σ(m 1 ), . . . , σ(m n )). Or, le fait queσsoit un plongement et queφsoit sans quantificateurs entrane que (M 1 φ(σ(m 1 ), . . . , σ(m n )))⇔(M 2 φ(m 1 , . . . , m n )). Par consÉquent, on doit avoirM 2 ∀x 1 . . . x n φ(x 1 , . . . , x n ), ceci Étant vrai pour tout modÈle de T 2 . On vient de prouver queT 2 `θ. (b) Posons Σ =T 2 ∪ {ϕ( ¯m) :Mφ( ¯m), φformule sans quantificateurs}. Pour montrer queΣest consistant, il nous suffit (par compacitÉ) de prouver que tout fragment fini deΣest consistant, et pour cela il suffit d’Établir que chaque ensemble d’ÉnoncÉs de la forme k T 2 ∪ {ψ(m 1 , . . . , m k )}, oÙψest une formule sans quantificateurs et(m 1 , . . . , m k )∈M, est consis- tant. Notons que si dans tout modÈleM 2 deT 2 on avaitM 2 ∀x 1 . . . x k ¬ψ(x 1 , . . . , x k )alors ∀x 1 . . . x k ¬ψ(x 1 , . . . , x k )serait une consÉquence universelle deT 2 , donc aussi deT 1 , donc on aurait aussiM 1 ∀x 1 . . . x k ¬ψ(x 1 , . . . , x k ), ce qui contredit le choix deψ. Par consÉquent, il existe un modÈleM 2 deT 2 eta 1 , . . . , a k ∈M 2 tels queM 2 ψ(a 1 , . . . , a k ); en interprÉtantm 1 , . . . , m k par a 1 , . . . , a k on voit que notre ensemble d’ÉnoncÉs est bien consistant. Pour conclure, il suffit de noter que siNest un modÈle deΣalors le rÉduit deNau langage commun N ÀT 1 , T 2 est un modÈle deT 2 , et l’applicationσ:m7→mest un plongement deMdansN. (c)=(a) et (b) . 2. (a)Suivons l’indication de l’ÉnoncÉ; le fait que2Zsoit d’indice2dansZs’exprime par l’ÉnoncÉ ∃x∀y((∃z y=z+z)∨(∃z y=z+z+x)). Cet ÉnoncÉ n’est pas vrai dans(Z×Z,0,+): supposons quex= (x 0 , x 1 )satisfasse la condition ci-dessus. Alors avecy= (0,1)on voit quex 0 est pair tandis quex 1 ; de mme, enest impair considÉranty= (1,0)on voit quex 0 est impair alors quex 1 est pair. (b) Ilest bien clair que(Z,0,+)se plonge dans(Z×Z,0,+)(par exemple vian7→(n,0)) par consÉquent le raisonnement de la question 1.(a) implique immÉdiatement le rÉsultat demandÉ par l’ÉnoncÉ. ∗ (c) Commed’habitude, ajoutons À notre langage un symbole de constantenpour chaque entiern∈Z ainsi que deux symboles de constanteaetb, puis considÉrons l’ensemble d’ÉnoncÉs dans ce nouveau langage Σ =T h((Z,0,+),Z)∪ {ia6=jb} i,j∈Z . ∗ (On a bien sÛr utilisÉ la notationiacomme abrÉviation dea+. . .+a) | {z } ifois On a besoin de montrer queΣest consistant, par compacitÉ il suffit de le vÉrifier pour un fragment

fini, et il suffit de traiter les fragments de la formeT h((Z,0,+),Z)∪ {ia6=jb} i,j6=0et|i|,|j|≤N . Un modÈle de cette thÉorie est obtenu en considÉrantZ, dans lequel on interprÈte chaque entier par lui-mme, l’addition est l’addition usuelle, et on interprÈteapar1etbparN+ 1. Notre thÉorie est donc bien consistante, et un modÈle de cette thÉorie est exactement ce que recherche l’ÉnoncÉ. G G (d) L’applicationσ: (i, j)7→(ia ,jb)est un isomorphisme sur son image par construction deG; autrement dit on aσ(0,0) = 0etσ((i 1 , j 1 ) + (i 2 , j 2 )) =σ(i 1 , j 1 ) +σ(i 2 , j 2 ), ce qui revient À dire queσest un plongement de(Z×Z,0,+)dansG. (e) Soitθun ÉnoncÉ universel vrai dans(Z,0,+). Alorsθest vrai dansG, qui est une extension ÉlÉmentaire de(Z,0,+). Puisque(Z×Z,0,+)se plonge dansG, on en dÉduit queθest aussi vrai dans(Z×Z,0,+). Par consÉquent un ÉnoncÉ universel vrai dans(Z,0,+)est vrai aussi dans (Z×Z,0,+); ajoutÉ au rÉsultat de 2(b), cela nous permet de voir que les thÉories de(Z,0,+)et (Z×Z,0,+)(qui sont complÈtes) sont compagnes l’une de l’autre.

Exercice 2. 1. AppelonsT». Alors lale corps est algÉbriquement closla thÉorie dans le langage des corps qui dit « thÉorie des corps algÉbriquement clos de caractÉristique nulle est Égale ÀT∪ {p.16= 0} p∈P , oÙPdÉsigne l’ensemble des nombres premiers. Par compacitÉ, un ÉnoncÉθest consÉquence deT∪ {p.16= 0} p∈P si, et seulement si, il est consÉquence d’un fragment fini deT∪ {p.16= 0} p∈P , i.e d’un sous-ensemble de T k =T∪ {p.16= 0} p∈P,p<k oÙkest un entier. Tout corps algÉbriquement clos de caractÉristique≥kest un modÈle deT k , par consÉquent un tel corps doit satisfaireθ. 2. ConsidÉrons un ÉnoncÉθsatisfait par tout corps algÉbriquement clos de caractÉristique≥k, et un corpsKalgÉbriquement clos de caractÉristique nulle. Comme la thÉorie des corps algÉbriquement clos de caractÉristique nulle est complÈte, la thÉorie deKest Égale ÀT∪ {p.16= 0} p∈P , et tout fragment finiΣ deT h(K)est donc contenu dansT∪ {p.16= 0} p∈P,p<N pour un certainN. Si l’on poseM= max(N, k) alors tout corps algÉbriquement clos de caractÉristique≥Mest un modÈle deΣ, par consÉquentΣ∪ {θ} est consistant. Si jamaisθÉtait faux dansKalors on auraitT h(K)` ¬θ; par compacitÉ il existerait un fragment finiΣdeTtel queΣ` ¬θ, et on vient de voir que ce n’est pas le cas. Par consÉquent,θest satisfait dansK. m 3. Fixonsun sous-ensemble finiIdeN, et notons chaquei∈Isous la formei= (i 1 , . . . , i m ). Pour nous   j simplifier l’Écriture ci-dessous, notonsφ(a) I i i∈I,j∈{1,...,m} , y 1 , . . . , y m le terme  ! X X 1 i 1 i m m i 1 i m a y. . . y, . . . ,a y. . . y. i 1 m i 1 m i∈I i∈I Maintenant, considÉrons l’ÉnoncÉθ I suivant :  ! ^ j jj ∀ i∈I,j≤m a∀y 1 . . . y m ∀z 1 . . . z m φ I ((a), y 1 , . . . , y m ) =φ I ((a), z 1 , . . . , z m ))→(y i =z i )→ i ii i∈I   j ∀r 1 . . . r m ∃s 1 . , s, s. . . m ) = (r 1 , . . . , r m s m φ I ((a i ) 1 , . .). m m L’ÉnoncÉθ I , en langage courant, dit « pour toute application polynÔmialePdeAdansAtelle que les degrÉs des monÔmes apparaissant dansPappartiennent tous ÀI,Pest injective si, et seulement si, Pest surjective ». Par consÉquent, la propriÉtÉP m est exprimÉe par la famille{θ I } Ifini⊆N . m 4. SiAest un anneau fini, alors une application deAdansAest injective ssi elle est surjective, par consÉquentAa la propriÉtÉP m . ˜ ˜ m m 5. Fixonsm >0, et considÉrons u→Rappelons que ne application polynÔmialeF= (F 1 , . . . , F m ) :F p F p . p ˜ n l’applicationΦ :x7→xest un morphisme de corps deF p dans lui-mme. Par dÉfinition,x∈F p est

n Équivalent ÀΦ (x) =x. Pournsuffisamment grand, les coefficients deFappartiennent tout ÀF p ; on n a alors pour toutx 1 , . . . , x m ∈F p et pour touti n n nn Φ (F i (x 1 , . . . , x m )) =F i (Φ (x 1 ), . . . ,Φ (x m )) =F i (x 1 , . . . , x m ). m Par consÉquent,Fenvoie chaqueF n dans lui-mme. De plus, puisque tous les coefficients deFappar- p m n est une application polynÔmiale. n tiennent ÀF p , la restriction deFÀF p m Supposons maintenantFinjective. Alors la restriction deFÀF n est injective et donc surjective, pour p S n ˜ n m a donc la propriÉtÉP). CommeF F, on en nsuffisamment grand (puisqueF p est fini et m p = n>0 p ˜ m dÉduit queFest surjective, par consÉquentFa la propriÉtÉP m . p 6. Rappelonsque la thÉorie des corps algÉbriquement clos de caractÉristiquepest complÈte pour toutp >0. ˜ Par consÉquent, le fait queF p satisfasseP m entrane queP m est vÉrifiÉe par tout corps algÉbriquement clos de caractÉristiquep. Finalement, le rÉsultat de la question 2 nous permet de conclure.