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 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 ?

Sujets

• Axiome de fondation

Informations

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

Extrait

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 entrane 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 : •V 0 =∅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 α+1 ∈V α+1 alorsP(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α+ 1∈V α+1 alorsα∪ {α} ∈ 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 α+1 pour 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 δ+1 pour 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(y i ) i<ω telle quey i+1 ∈y i pour 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,V 0 =xetV i+1 =V i (l’ensemble dont les ÉlÉments sont les ÉlÉments de S V i ) puis poserW=V i . 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-mmes 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 »ℵ 1 ordinaux 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ÉesB i deQetωcopiesC i deω, ordonnÉes de telle faÇon que B 0 < C 0 < B 1 < C 1 . . .. Puis on dÉfinit, pour toute partieAdeω,X A comme le sous-ensemble obtenu en posant ( {0, . . . , i}sii∈A ∀Xi < ω A ∩B i =B i etX A ∩C i =. ∅sinon Alors chaqueX A est totalement ordonnÉ par l’ordre induit; de plus, il existe un ÉlÉment dansX A qui n’a pas de prÉdecesseur immÉdiat et a exactementnsuccesseurs immÉdiats si, et seulement si,n∈A. Par consÉquent, siX A etX B sont isomorphes alors pour toutnon an∈A⇔n∈B, autrement dit A=B. On vient donc de montrer que l’applicationA7→X A Était telle queX A ne 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’ensembleY A =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 À Y A , on identifie exactement les points qui sont dans la mme copie deZ; par consÉquent, l’ensemble dÉrivÉ deY A est isomorphe ÀA. Par suite, siAetBsont non isomorphes alorsY A etY B sont Également ℵ 0 non isomorphes; puisqu’il y a2ensembles dÉnombrables totalement ordonnÉs et deux À deux non iso- ℵ 0 morphes, l’applicationA7→Y A nous 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-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.