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 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?.
Voir
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 ?
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, sia∈b∈ P(V), alorsb⊆Vpar dÉfinition deP(V), donc on aa∈Vpar dÉfinition de l’inclusion. CommeVest transitif, ceci entrane quea⊆V, autrement dita∈ P(V). On a donc dÉmontrÉ que (a∈b∈ 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 entrane 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 entrane aussi queβ < α⇒Vβ∈Vα. Montrons maintenant, par rÉcurrence transfinie, qu’on aVα6∈Vαpour toutα: • ∅6∈ ∅; •SiVα+1∈Vα+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 mme,α=β est impossible, par suiteβ < α. Le mme raisonnement montre que siVβ⊆Vαalors on ne peut pas avoir α < β, et doncβ≤α. 3. Montronsqueα6∈Vαpour toutα: • ∅6∈ ∅; •Siα+ 1∈Vα+1alorsα∪ {α} ∈ P(Vα); par consÉquent{α} ⊆Vα, ce qui entraneα∈Vα. •Siαest limite etβ6∈Vβpour toutβ < α, etα∈Vα, alors il doit existerβ < αtel queα∈Vβ, et commeβ∈αetVβest transitif ceci entrane 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 quey∈x ety∩x=∅. Autrement dit, l’axiome de fondation affirme que dans tout ensemblexil existey∈xqui soit minimal pour∈. CommenÇons par supposer que pour tout ensemblexil existe un ordinalγtel quex∈Vγ. Etant donnÉ un ensemblex, fixons un telγ. Alors touty∈xest aussi dansVγ, donc touty∈xa un rang unique. On peut alors poserδ= min{rg(y) :y∈x}. Il existey∈xtel querg(y) =δ. De plus, siz∈yalors on az∈y∈Vδ+1=P(Vδ)doncz∈Vδ, contredisant la minimalitÉ deδ. Par consÉquentyest minimal pour∈parmi 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 touty∈xappartient À unVα, alors si on poseδ= sup{rg(y) :y∈X}, on ay∈Vδ+1pour touty∈V, par consÉquentx∈Vδ+2. ConsidÉrons donc un ensemblexn’appartenant À aucunVα; alors il doit existery∈xn’appartenant À aucunVα, et en rÉpÉtant l’argument on obtient une suite(yi)i<ωtelle queyi+1∈yipour 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,{y∈W:∃α y∈Vα}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 : siz∈yalors on doit avoirz∈Wpuisque ce dernier est transitif, par consÉquent la minimalitÉ deyimpose quezdoit appartenir À unVα. Ceci Étant vrai pour toutz∈y, 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-mmes moins nombreuses que les parties deω, qui ℵ0.ℵ0ℵ0ℵ0 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}sii∈A ∀Xi < ωA∩Bi=BietXA∩Ci=. ∅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,n∈A. Par consÉquent, siXAetXBsont isomorphes alors pour toutnon an∈A⇔n∈B, autrement dit A=B. On vient donc de montrer que l’applicationA7→XAÉtait telle queXAne soit pas isomorphe ÀBdÈs ℵ0ℵ0 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=aetn≤n). 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 mme 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, soitℵ1. 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 ℵ 0ℵ0 un endomorphisme est une fonction deωdansω, et qu’il y aℵ= 2fonctions deωdans lui-mme, 0 ℵ0 on en dÉduit qu’il y a exactement2endomorphismes deωdans lui-mme. 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-mme alors on aura gagnÉ : ℵα en effet, siβest de cardinalℵαalors il y aura au moins2endomorphismes deβdans lui-mme, 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.
