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 DM2. Exercice I. 1. On commence par montrer que si V est un ensemble transitif alors P(V ) est encore un ensemble transitif. En effet, si a ? b ? P(V ), alors b ? V par définition de P(V ), donc on a a ? V par définition de l'inclusion. Comme V est transitif, ceci entraîne que a ? V , autrement dit a ? P(V ). On a donc démontré que (a ? b ? P(V ))? (a ? P(V )), ce qui prouve que P(V ) est transitif. Utilisons cela pour prouver le résultat demandé par récurrence transfinie : • V0 = ? est transitif. On considère maintenant ? > 0 tel que V? soit transitif pour tout ? < ?. • Si ? = ? + 1, a :ors ce qu'on vient de démontrer entraîne que V? = P(V?) est transitif. • Si ? est limite, alors V? est une réunion d'ensembles transitifs ; une union d'ensembles transitifs est un ensemble transitif. On en déduit que V? est bien un ensemble transitif. 2. Notons que si V est un ensemble transitif alors V ? P(V ) ; on en déduit par récurrence transfinie que ? ≤ ?? V? ? V?.

  • axiome de fondation

  • prédécesseur immédiat

  • v? ?

  • copies ordonnées

  • ?0 endomorphismes de ?

  • ?0

  • modèle d'ordre discret

  • ??

  • ?? endomorphismes de ??

  • ordinal ?


Publié le : vendredi 8 juin 2012
Lecture(s) : 58
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 DM2.
2nd semestre Introduction À
2009/2010 la Logique
Exercice I. 1. Oncommence par montrer que siVest un ensemble transitif alorsP(V)est encore un ensemble transitif. En effet, siab∈ P(V), alorsbVpar dÉfinition deP(V), donc on aaVpar dÉfinition de l’inclusion. CommeVest transitif, ceci entrane queaV, autrement dita∈ P(V). On a donc dÉmontrÉ que (ab∈ P(V))(a∈ P(V)), ce qui prouve queP(V)est transitif. Utilisons cela pour prouver le rÉsultat demandÉ par rÉcurrence transfinie : V0=est transitif. On considÈre maintenantα >0tel queVβsoit transitif pour toutβ < α. Siα=β+ 1, a :ors ce qu’on vient de dÉmontrer entrane queVα=P(Vβ)est transitif. Siαest limite, alorsVαest une rÉunion d’ensembles transitifs; une union d’ensembles transitifs est un ensemble transitif. On en dÉduit queVαest bien un ensemble transitif. 2. Notonsque siVest un ensemble transitif alorsV⊆ P(V); on en dÉduit par rÉcurrence transfinie que βαVβVα. La construction entrane aussi queβ < αVβVα. Montrons maintenant, par rÉcurrence transfinie, qu’on aVα6∈Vαpour toutα: • ∅6∈ ∅; SiVα+1Vα+1alorsP(Vα)∈ P(Vα); autrement ditP(Vα)Vα, et c’est impossible À cause du thÉorÈme de Cantor. Siαest limite,Vβ6∈Vβpourβ < αetVαVα, alors on aβ < αtel queVαVβ, et commeβ < α on aVβVα; commeVβest transitif, on en dÉduit queVβVβ. Supposons maintenant queα, βsont tels queVβVα. Si on avaitα < β, alors on auraitVαVβVα, et commeVαest transitif, on aurait aussiVαVα, contredisant notre rÉsultat ci-dessus. De mme,α=β est impossible, par suiteβ < α. Le mme raisonnement montre que siVβVαalors on ne peut pas avoir α < β, et doncβα. 3. Montronsqueα6∈Vαpour toutα: • ∅6∈ ∅; Siα+ 1Vα+1alorsα∪ {α} ∈ P(Vα); par consÉquent{α} ⊆Vα, ce qui entraneαVα. Siαest limite etβ6∈Vβpour toutβ < α, etαVα, alors il doit existerβ < αtel queαVβ, et commeβαetVβest transitif ceci entrane queβVβ, contradiction. Une rÉcurrence transfinie similaire montrerait queαVα+1pour toutα. 4. Rappelonsque l’axiome de fondation s’Écrit : pour tout ensemblexil existe un ensembleytel queyx etyx=. Autrement dit, l’axiome de fondation affirme que dans tout ensemblexil existeyxqui soit minimal pour. CommenÇons par supposer que pour tout ensemblexil existe un ordinalγtel quexVγ. Etant donnÉ un ensemblex, fixons un telγ. Alors toutyxest aussi dansVγ, donc toutyxa un rang unique. On peut alors poserδ= min{rg(y) :yx}. Il existeyxtel querg(y) =δ. De plus, sizyalors on azyVδ+1=P(Vδ)donczVδ, contredisant la minimalitÉ deδ. Par consÉquentyest minimal pourparmi les ÉlÉments dex, et l’axiome de fondation est vÉrifiÉ. Avant de prouver la rÉciproque, notons que si un ensemblexest tel que toutyxappartient À unVα, alors si on poseδ= sup{rg(y) :yX}, on ayVδ+1pour toutyV, par consÉquentxVδ+2. ConsidÉrons donc un ensemblexn’appartenant À aucunVα; alors il doit existeryxn’appartenant À aucunVα, et en rÉpÉtant l’argument on obtient une suite(yi)i<ωtelle queyi+1yipour touti, ce qui contredit l’axiome de fondation. Tout ceci est bel et bon, mais dans la dÉmonstration ci-dessus on a utilisÉ l’axiome des choix dÉpendants; peut-on s’en passer? La rÉponse est oui : Étant donnÉ un ensemblexqui n’appartienne À aucunVα, on
S peut dÉfinir, par rÉcurrence,V0=xetVi+1=Vi(l’ensemble dont les ÉlÉments sont les ÉlÉments de S Vi) puis poserW=Vi. AlorsWest un ensemble transitif, qui contientx. i<ω De plus,{yW:α yVα}est un ensemble, par consÉquent son complÉmentaire dansWaussi. Ce dernier doit tre non vide (il existe un ÉlÉment dexqui n’est contenu dans aucunVα), donc en invoquant l’axiome de fondation on peut trouver un ÉlÉment deWqui soit-minimal et n’appartienne À aucun Vα. On arrive finalement À une contradiction : sizyalors on doit avoirzWpuisque ce dernier est transitif, par consÉquent la minimalitÉ deyimpose quezdoit appartenir À unVα. Ceci Étant vrai pour toutzy, on en dÉduit queyappartient aussi À la rÉunion desVα, contradiction.
Exercice II. 1. Unensemble totalement ordonnÉ dÉnombrable peut toujours tre vu comme ayantωcomme domaine. Par consÉquent, il y a moins d’ensembles totalement ordonnÉs dÉnombrables, À isomorphisme prÈs, que 2 de relations binaires surω; ces derniÈres sont elles-mmes moins nombreuses que les parties deω, qui 0.000 sont au nombre de2 =2. Il y a donc au plus2ensembles totalement ordonnÉs dÉnombrables (À isomorphisme prÈs). On aurait aussi pu dÉmontrer ce fait en prouvant, par va-et-vient, que tout ensemble totalement ordonnÉ dÉnombrable est isomorphe À un sous-ensemble deQmuni de son ordre usuel. Pour voir l’inÉgalitÉ rÉciproque, on pourrait tre tentÉ de dire que deux ordinaux dÉnombrables distincts ne sont pas isomorphes; mais il n’y a «que »1ordinaux dÉnombrables, par consÉquent, À moins que 0 l’hypothÈse du continu ne soit vraie, on n’a pas terminÉ notre travail. Il nous faut construire2ensembles totalement ordonnÉs non dÉnombrables mais isomorphes, un pour chaque partie deω. Pour cela, on peut par exemple procÉder comme suit : on commence par dÉfinir l’ensemble totalement ordonnÉXobtenu en mettant bout À boutωcopies ordonnÉesBideQetωcopiesCideω, ordonnÉes de telle faÇon que B0< C0< B1< C1. . .. Puis on dÉfinit, pour toute partieAdeω,XAcomme le sous-ensemble obtenu en posant ( {0, . . . , i}siiA Xi < ωABi=BietXACi=. sinon Alors chaqueXAest totalement ordonnÉ par l’ordre induit; de plus, il existe un ÉlÉment dansXAqui n’a pas de prÉdecesseur immÉdiat et a exactementnsuccesseurs immÉdiats si, et seulement si,nA. Par consÉquent, siXAetXBsont isomorphes alors pour toutnon anAnB, autrement dit A=B. On vient donc de montrer que l’applicationA7→XAÉtait telle queXAne soit pas isomorphe ÀBdÈs 00 queAest diffÉrent deB; comme il y a2parties deω, ceci montre qu’il y a au moins2ensembles totalement ordonnÉs dÉnombrables deux À deux non isomorphes. 2. L’ÉnoncÉdu DM Était incorrect ; un ordre discret devrait tre dÉcrit de la faÇon suivante : tout ÉlÉment qui ne soit pas le minimum ni le maximum doit avoir un successeur immÉdiat et un prÉdÉcesseur immÉdiat. 0 Un modÈle d’ordre discret est doncZ. On sait qu’il y a au plus2ordres discrets dÉnombrables À 0 isomorphisme prÈs, et comme À la question prÉcÉdente on doit en construire une famille de cardinal2 qui soient deux À deux non isomorphes. Pour cela, on note que pour tout ensemble totalement ordonnÉ dÉnombrableAl’ensembleYA=A×Z, muni de l’ordre lexicographique 0 00 0 0 (a, n)(na ,)(a < aoua=aetnn). est discret, dÉnombrable et totalement ordonnÉ. De plus, si l’on applique la dÉrivation de Hausdorff À YA, on identifie exactement les points qui sont dans la mme copie deZ; par consÉquent, l’ensemble dÉrivÉ deYAest isomorphe ÀA. Par suite, siAetBsont non isomorphes alorsYAetYBsont Également 0 non isomorphes; puisqu’il y a2ensembles dÉnombrables totalement ordonnÉs et deux À deux non iso-0 morphes, l’applicationA7→YAnous permet donc de construire2ensembles dÉnombrables totalement ordonnÉs discrets et deux À deux non isomorphes. 3. Un ensemble dÉnombrable bien ordonnÉ esr isomorphe À un ordinal dÉnombrable unique, par consÉ-quent il y a, À isomorphisme prÈs, autant d’ensembles dÉnombrables totalement ordonnÉs que d’ordinaux dÉnombrables, c’est-À-dire autant qu’il y a d’ÉlÉments dansω1, soit1. 4. On peut supposer queXest un ordinalα, muni de son ordre usuel. Notons que, sif:ααest strictement croissante alors(f(α), <)est isomorphe Àα. On en dÉduit que siXest fini il n’y a qu’un
seul endomorphisme deX. Si maintenantX=ω(pour nous fixer les idÉes) alors on voit que pour toute partie infinieAdeωil existe un endomorphisme de(ω, <)dont l’image estA, par consÉquent il y a au 0 moins autant d’endomorphismes deωque de parties infinies deω, c’est-À-dire2. Comme par ailleurs 00 un endomorphisme est une fonction deωdansω, et qu’il y a= 2fonctions deωdans lui-mme, 0 0 on en dÉduit qu’il y a exactement2endomorphismes deωdans lui-mme. Traitons maintenant le cas gÉnÉral : notons dÉjÀ que siα < βalors tout endomorphisme de(α, <)s’Étend en un endomorphisme de(β, <), par consÉquent il y a plus d’endomorphismes de(β, <)que de(α, <). Si α l’on sait montrer que pour toutαil y a2endomorphismes deαdans lui-mme alors on aura gagnÉ : α en effet, siβest de cardinalαalors il y aura au moins2endomorphismes deβdans lui-mme, et il |βα y en a au plus|β|= 2. Comme dans le cas deω, il y a exactement autant d’endomorphismes deα que de parties deαde cardinalα. α Finalement, on doit montrer, pourα >1, qu’il y a au moins2endomorphismes deα. Etant donnÉe ˜ une fonctionf:α→ {0,1}, on peut dÉfinir une fonctionf:αONpar rÉcurrence transfinie, en posant : ˜ f(0) =f(0); ˜ ˜ f(β+ 1) =f(β) +f(β) + 1; ˜ ˜ Siβest limite alorsf(β) = sup{f(δ) :δ < β}+f(β). ˜ Cette fonctionfest strictement croissante, de plus on vÉrifie facilement que pour toutβ <αon a ˜ ˜ f(β)< β+ω. Par consÉquentfest À valeurs dansα: en effet, pour toutβ <αon a |β+ω| ≤ |β|+0= max(|β|,0)<α, donc aussiβ+ω <α. ˜ Autrement dit,fest un endomorphisme deα; pour conclure, il nous suffit de remarquer que par ˜ constructionf7→fest injective.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.