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

De
Publié par

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


Publié le : vendredi 8 juin 2012
Lecture(s) : 50
Source : math.univ-lyon1.fr
Nombre de pages : 3
Voir plus Voir moins
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 formex1. . . xnφ(x1, . . . , xn)avecφ sans quantificateurs alors(T1`θ)(T2`θ). Pour cela, supposons queT1`θet considÉrons un modÈleM2deT2. Par hypothÈse,M2se plonge dans un modÈleM1deT1; notonsσun plongement deM2dansM1. On doit avoir M1x1. . . xnφ(x1, . . . , xn) ConsidÉronsm1, . . . , mndansM2; puisque(σ(m1), . . . , σ(mn))∈ M1on 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 avoirM2x1. . . xnφ(x1, . . . , xn), ceci Étant vrai pour tout modÈle de T2. On vient de prouver queT2`θ. (b) Posons Σ =T2∪ {ϕ( ¯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 T2∪ {ψ(m1, . . . , mk)}, oÙψest une formule sans quantificateurs et(m1, . . . , mk)M, est consis-tant. Notons que si dans tout modÈleM2deT2on avaitM2x1. . . xk¬ψ(x1, . . . , xk)alors x1. . . xk¬ψ(x1, . . . , xk)serait une consÉquence universelle deT2, donc aussi deT1, donc on aurait aussiM1x1. . . xk¬ψ(x1, . . . , xk), ce qui contredit le choix deψ. Par consÉquent, il existe un modÈleM2deT2eta1, . . . , akM2tels queM2ψ(a1, . . . , ak); en interprÉtantm1, . . . , mkpar a1, . . . , akon 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 ÀT1, T2est un modÈle deT2, 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É xy((z y=z+z)(z y=z+z+x)). Cet ÉnoncÉ n’est pas vrai dans(Z×Z,0,+): supposons quex= (x0, x1)satisfasse la condition ci-dessus. Alors avecy= (0,1)on voit quex0est pair tandis quex1; de mme, enest impair considÉranty= (1,0)on voit quex0est impair alors quex1est 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 entiernZ 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,jZ. (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σ((i1, j1) + (i2, j2)) =σ(i1, j1) +σ(i2, j2), 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}pP, oÙPdÉsigne l’ensemble des nombres premiers. Par compacitÉ, un ÉnoncÉθest consÉquence deT∪ {p.16= 0}pPsi, et seulement si, il est consÉquence d’un fragment fini deT∪ {p.16= 0}pP, i.e d’un sous-ensemble de Tk=T∪ {p.16= 0}pP,p<kkest un entier. Tout corps algÉbriquement clos de caractÉristiquekest un modÈle deTk, par consÉquent un tel corps doit satisfaireθ. 2. ConsidÉrons un ÉnoncÉθsatisfait par tout corps algÉbriquement clos de caractÉristiquek, 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}pP, et tout fragment finiΣ deT h(K)est donc contenu dansT∪ {p.16= 0}pP,p<Npour un certainN. Si l’on poseM= max(N, k) alors tout corps algÉbriquement clos de caractÉristiqueMest 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 chaqueiIsous la formei= (i1, . . . , im). Pour nous   j simplifier l’Écriture ci-dessous, notonsφ(a) I iiI,j∈{1,...,m}, y1, . . . , ymle terme  ! X X 1i1imm i1im a y. . . y, . . . ,a y. . . y. i1m i1m iI iI Maintenant, considÉrons l’ÉnoncÉθIsuivant :  ! ^ j jj iI,jmay1. . . ymz1. . . zmφI((a), y1, . . . , ym) =φI((a), z1, . . . , zm))(yi=zi)i ii iI   j r1. . . rms1. , s, s. . .m) = (r1, . . . , rm smφI((ai)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ÉPmest exprimÉe par la famille{θI}IfiniN. m 4. SiAest un anneau fini, alors une application deAdansAest injective ssi elle est surjective, par consÉquentAa la propriÉtÉPm. ˜ ˜ m m 5. Fixonsm >0, et considÉrons uRappelons que ne application polynÔmialeF= (F1, . . . , Fm) :FpFp. p ˜n l’applicationΦ :x7→xest un morphisme de corps deFpdans lui-mme. Par dÉfinition,xFpest
n Équivalent ÀΦ (x) =x. Pournsuffisamment grand, les coefficients deFappartiennent tout ÀFp; on n a alors pour toutx1, . . . , xmFpet pour touti n n nn Φ (Fi(x1, . . . , xm)) =Fi(Φ (x1), . . . ,Φ (xm)) =Fi(x1, . . . , xm). m Par consÉquent,Fenvoie chaqueFndans lui-mme. De plus, puisque tous les coefficients deFappar-p m nest une application polynÔmiale. n tiennent ÀFp, la restriction deFÀFp m Supposons maintenantFinjective. Alors la restriction deFÀFnest injective et donc surjective, pour p S n˜n m a donc la propriÉtÉP). CommeF F, on en nsuffisamment grand (puisqueFpest fini etm p=n>0p ˜ m dÉduit queFest surjective, par consÉquentFa la propriÉtÉPm. p 6. Rappelonsque la thÉorie des corps algÉbriquement clos de caractÉristiquepest complÈte pour toutp >0. ˜ Par consÉquent, le fait queFpsatisfassePmentrane quePmest vÉrifiÉe par tout corps algÉbriquement clos de caractÉristiquep. Finalement, le rÉsultat de la question 2 nous permet de conclure.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.