Université Claude Bernard Lyon I 2nd semestre Master Introduction la Logique
3
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
3
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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.
Voir
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
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∀x1. . . 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 M1∀x1. . . 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 entrane que (M1φ(σ(m1), . . . , σ(mn)))⇔(M2φ(m1, . . . , mn)). Par consÉquent, on doit avoirM2∀x1. . . 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 avaitM2∀x1. . . xk¬ψ(x1, . . . , xk)alors ∀x1. . . xk¬ψ(x1, . . . , xk)serait une consÉquence universelle deT2, donc aussi deT1, donc on aurait aussiM1∀x1. . . xk¬ψ(x1, . . . , xk), ce qui contredit le choix deψ. Par consÉquent, il existe un modÈleM2deT2eta1, . . . , ak∈M2tels 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É ∃x∀y((∃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 mme, 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 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-mme, 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}p∈P, oÙPdÉsigne l’ensemble des nombres premiers. Par compacitÉ, un ÉnoncÉθest consÉquence deT∪ {p.16= 0}p∈Psi, et seulement si, il est consÉquence d’un fragment fini deT∪ {p.16= 0}p∈P, i.e d’un sous-ensemble de Tk=T∪ {p.16= 0}p∈P,p<koÙkest un entier. Tout corps algÉbriquement clos de caractÉristique≥kest 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É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<Npour 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= (i1, . . . , im). Pour nous j simplifier l’Écriture ci-dessous, notonsφ(a) I ii∈I,j∈{1,...,m}, y1, . . . , ymle terme ! X X 1i1imm i1im a y. . . y, . . . ,a y. . . y. i1m i1m i∈I i∈I Maintenant, considÉrons l’ÉnoncÉθIsuivant : ! ^ j jj ∀i∈I,j≤ma∀y1. . . ym∀z1. . . zmφI((a), y1, . . . , ym) =φI((a), z1, . . . , zm))→(yi=zi)→ i ii i∈I j ∀r1. . . rm∃s1. , 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}Ifini⊆N. 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 u→Rappelons que ne application polynÔmialeF= (F1, . . . , Fm) :FpFp. p ˜n l’applicationΦ :x7→xest un morphisme de corps deFpdans lui-mme. Par dÉfinition,x∈Fpest
n Équivalent ÀΦ (x) =x. Pournsuffisamment grand, les coefficients deFappartiennent tout ÀFp; on n a alors pour toutx1, . . . , xm∈Fpet pour touti n n nn Φ (Fi(x1, . . . , xm)) =Fi(Φ (x1), . . . ,Φ (xm)) =Fi(x1, . . . , xm). m Par consÉquent,Fenvoie chaqueFndans lui-mme. 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 queFpsatisfassePmentrane 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.
