Université Claude Bernard Lyon I 2nd semestre

Claude Bernard Lyon

Description

Niveau: Supérieur, Master

• cours - matière potentielle : su?rait


• cours - matière potentielle : pour la définition

Université Claude Bernard Lyon I 2nd semestre 2008/2009 Master 1 Logique et théorie des ensembles Devoir 1 à retourner le 26 février 2009 (Pour les raisons detaillées sur la page web du cours, ce devoir est facultatif.) I. On dit qu'un ensemble X est Dedekind-infini s'il existe une injection non surjective f : X ? X, autrement dit si X est équipotent à une de ses parties strictes. 1. L'objectif de cette première question est de montrer qu'un ensemble X est Dedekind-infini si, et seulement si, X contient un sous-ensemble dénombrable, c'est-à-dire équipotent à ?. Pour ce faire nous vous demandons de montrer les trois énoncés suivants : (a) Tout ensemble dénombrable est Dedekind infini. (b) Si l'ensemble X contient une partie dénombrable, alors X est un ensemble Dedekind-infini. (c) Si X est un ensemble Dedekind-infini, alors X contient une partie dénombrable. (Vous pouvez utiliser une construction en recourant à une récurrence qui utilise comme opération principale l'injection f .) Réponse : (a) Par définition, un ensemble X est dénombrable s'il existe une bijection entre X et ?. Par conséquent, pour répondre à la question, il su?t de trouver une injection non surjective de ? dans ?.

• récurrence sur ?


• titre d'illustration de l'usage du théorème de récurrence


• ordre de ?


• ordinal limite


• récurrence


• définition


• surjective de ? dans ?


• théorème de récurrence

Sujets

• Récurrence
• Définition
• Théorème de récurrence de Poincaré

Informations

• Publié par: cidur
• Publié le: 01 février 2009
• Nombre de lectures: 45
• Langue: Français

Extrait

X f: X !X
X
X
X !
X X
X X
f
X X !
! !
g : ! ! ! n+1 n < ! f X !
¡1x2X f (g(f(x))) X X
X X0
g X X0 0
f : X ¡! X‰
x x2XnX0
x 7¡!
g(x)
f X X
X X
X f(X) X f
ff(X);Xnf(X)g x
Xnf(X)
(x ) x = f:::f(x )n n<! n 0
| {z }
n
G
G : N ¡! N‰
x n=0
n 7¡!
f(Gdn)
G x2Xnf(X)
f f(X)
existedekind-inni.r?currence(c)tSi?ducours,estestunsuivensembletsDel'imagedekind-inni,palorsth?or?meeb.cleontientestunequ'unpensemartiedansd?nombr.able.dev(nousVcoussuitepeouv?ezs'appliqueutiliserL'objeunesesconstructionOnen?erecouranetttenan?Punesurjectivr?currencemontrquisousutilise2.1.2commeeop??rationdeprincipalecl'injectionblewMain.ermet)dekind-inniR?pmontronseette:de(a)l'usagePparticulierarnaturels.d?nition,ilund?nieensem1.bleotentpageementestoind?nomquebrabledits'ilnonexisteinjectivuneestbijectiontrenDedekindtred?nition,lainjectionetdesur..demandonsPdeardecons?quenlet,notespfamilleourPourr?potentondrec'est-?-dir?unelahoix.question,ermetilunsutdedeuntrouvsi,ert,uner?currenceinjectionconstruirenonetsurjectivo?equ'undeestdetaill?esprdansderaisonsy.cetteEnd'illustrationeet,th?or?mesiceparilexemplenomleseet,ourde(Pune2009unef?vrierlaassoteciearties26unele?retournersi?,toutLe?qui1?rieroirble,laetinnie.quectiveDevinjeestexistelalesbijections'ildemainblestvunersbleenseminni.,aralorsill'applicationunequinonassoecieles?ercNotonshaquededesvousth?oriedirecteetnous,l'actionLogiquee1D'apr?sMasterlemme2008/2009dessemestrede2ndlaIfaironcLy.Bernard?unequipinjectionenonable,surjectivoss?deefonctiondecClaudeCecidanspersit?de.hoisir(b)?l?menSoitd?nombrUnivl'ensemtoussous-ensembleensemontientbleoirqui.contenantienletdeuneppartieded?nomunebrableseulementDesi,ensembleDe.estD'apr?sensembleleerpdeoinquestiontemi?r(a),foisilcexistectifuneEssaunonssond?taillersurjectivconstructionetitreestdededucours,dealorsdansdanscasable,o?d?nombrne.qu'auxOnbresd?nitEnalorsd'apr?sl'applicationth?or?mesuivr?currenceanexistetefonction:etartieseulepdeunemani?reontientanc:cestrictes.l'ensemblepSide(b)?inni.quipdekindsisifacultatif.)DeditestautrableI.d?nombrsinonensemblepouttTreste(a)v:estsuivantsl'ensemsinond'arrivLadefonctionfonction?sestestCommeuneensembleinjectionsurjenonctionsurjectivuneequedeest?nonce,dans?l?menoisde.Dedekind-inni(c)Soitinjectiontnondistincts.unE n<!
E n A E nn
A An n
(E ) X E nn n
E En
(E )n
n
[
E nn E i =; :2 2
i<n
P
n i n2 > 2 =2 ¡1i<n
(x )n
[
n8n<! x 2E n E i :n 2 2
i<n
fx g Xn
fE j i<!g Ei i
E E ! Ei i i
(E ;? ) ?i i iS
E !£! Ei ii<!
S
g : !£! ¡! Eii<!
(i;j) 7¡! ? (j) :i
EiS
E N£N Nii<!
Ei
g
E =fE j i < !gi
EiS
Eii<!S
! E Eii<!
S
C : E ¡! Eii<!
E 7¡! g(inffj2! j g(j)2Eg) :i i
vAlorsbrable.oncepensemeutaucunmonl'applicationtrerbrabilit?parlar?currencebrablequevpmontrour:toutl'unionestdeinni(3)ensemblesa,l'exercice.ilinniexisteestunedepartiePnieunedeablestoutchoixenCettebijectioncea,vunecn?cessairemenqueest.?nonc?e,Notonscasalors?a?nedeentroth?selapfamilleypdesd?nompartiesladec'establet,quipairessono?t(c)enenbijectionableaa?nevouverectd?nombrbijection;blecdehaquetoutchoixexpliciterduersestcasnonnevide,ladonccourspartousl'axiome(3),ducccettehoixund?nomcbrablehondepbleeututilisancblehoisiroinunoser?l?mend'apr?stecdansarcunehaqueblel'axiometequelaetensemobtenirsansainsideuneparsuitequedeopartiesRouverum?rationPr.(a)an).d?nombrded?nombrhoixesttellerqueablecl'axiomehaque(b)cpartiedeconestest?quipnousotentet.?particulier,fonctionla.l'ensemOn?riervresteoudraitbijectionmainiltenan.tDansutilisero?lesded'unetd?nitiondisjoinpositionournotesconstruirepuisqueunsurjectionensemcas.bleositiond?nomqu'ellebrablel'axiomeconentenL'adaptationuositiondansbrablela(c);l'axiomeced?nomseraitdesfacileoth?sessidoncond?nitionaEnvfamilleaitbles.construitl'hnotretoutsuitesoitourlepI.1.,coursonsdehaquedebrable.telledeuxi?mefa?onl'ensemqu'elleasoitbrable.croissandete,ilmaisdecen'estn'est.passuivforc?menunethoixleuncas.inniUnec'estfa?onensemdefautpallierp?pr?cisercedonn?probl?medesestsideerremarquerquement,qu'oncipra?n?cessairemenestt,?npdeourable.toutAlors,notessuiv,tedestre2.1.1estd?nitionetlad'ensembles?d?nombrr?f?ronsd?nieous?unionvqu'uneNousentr6d?nombr(duchoix.quedePr(En)eet,d?nomfonctionuneunetienadmetinnid'ensemblesapplicationableuned?nombrsileconsid?ronsfamildisjointoutedes:ensemsuivantDans?cas)anMaisconclurealors,d?noml'axiomededublecquehoixvd?nomilbrable?nousunemondetresuraqu'ilvexistel'exercice,uneC'estsuiteexercice.l'?noncleestg?n?ralbrablelesd?nomblestelleI.1quesonhoixpasctduts,axiomepropun2.2.1DedesSoitde(a)surait:partieL'uneonseen2.lesR?pN?anmoins,ai.propvr2.2.1esttelleableestPn?cessitearduconstruction,hoixl'ensemtoutebleg?n?ralit?.d?nombrdechoixpropduaul'axiomed?nomestestuneexercice.partieNousd?nom?rieronsbrabledudehoixalorsbrable.partirable,deuxinni.ypd?nombrdeestSoitableslad?nombretd'ensemblescetteablecons?quenced?nombrni.?unionuneuned?nomfamilled'ensemd?nomEnbrabletd'ensemypblesqued?nomensembrables.inniADedekindcethaqueprttoutenouscorrespouvondsuppl'ensemcbleensemetd?nomdekind-inniAlors,desla?nhum?rationsoth?se,debleDevestbijection,d?nomenPd'autresd?nitiontermeslal'ensembrabilit?,bleexistedesbijectionbijectionsendeersinniquivensemersAlorsensemblefonctiontoutan.d?nitD'apr?sfonctionl'axiomecdusurcfamillehoix.d?nom:brable,bleilqu'unexistequeunebigu?t?fonctionamded?nircilhoixoindoncetl'?nonc?leourble(dekind-inni.grapheest(b)Soitfi
fl ? fl;? <fi fl+? <fi ;
fl fl <fi fl+fi=fi :
fi fl fi•fl+fi
fi;?;fl ? <fi fl+? <fl +fi
!
2!
P(fi;x) x•fi+x ; 0•fl – <fi
– • fl +– fl +– < fl +fi
– <fl – <fl+fi fi•fl+?
fi fi = –+1 – fl < fi
fl+– <fi (fl+–)+1•fi fl+fi=fl+(–+1)•fi fi
fl +fi = sup (fl +–) – < fi fl +– < fi fl +fi • fi–<fi
fi•fl+fi
1
fi fi –+1 – fl+(–+1)=–+1
fl+– =– fl•– – =fl –+– =–
– =0
fl <! fl fl+! =!
2!
fi fl
(fl)fi =ff: fl!fi j f? <fljf(?)=0g g
(fl) (fl)< fi f g fi
x fx2fl j f(x)=g(x)g0
f <g f(x )<g(x ) :0 0
(fl)< fi
(fl)f 2fi
?(f)=supf? <fl: f(?)=0g
Alorsalorssi,pqueourptoutouver(B)andalorsa-t-il,notes,parilcond?couledistinctsdee(A)quequeoursiCeci,d'autresetm?medinauxdeuxd'orois.sontD'apr?s:laapppropdeositionp1.1.12implique(4),oneosonsair,ptouttoutequeour(b)pun(A).:pquivalents3..d?nitAinsiour?toutsontPuisquesuivantsr?sde?nonc.deuxouverlespropri?tedinalniorth?or?metoutappliquanourtreronsp:.opri?t?Sirque,strictestonseunSolutionordinaldinallimite,ealorslaansniePrtrpecours,encSoitcurr.,lemmepbre?d'apr?sr.arestpimpliqueerIII..PrD'apr?sdinaux,(A),osonspsiour.toutble,montrusouhaite6Onest,d?nitII.telsordinalalorsunfa?onourd?niepdeux.4.Ainsi,,ourletoutplusordedinal?,des.6Commelel'in?galit?puisSienl'?nonc?.etdansNouscommeR?psiEtestMontrtoujoursestvraieded'apr?sdrleettep.oinNoustsolutionspr?c?den:t,;launconclusionnote(B)l'?estopri?t?vraie.dinal3.6C'est.lan'estpropossibleositionsi1.4.1de(b)..4.desL'implication1.4.1d?couleEnimm?diatementermes,testdunompnaturel.oinletOr,pr?c?den(A)t.La5.propri?t?L'?nonc?vraiedeource(B).pr?currence.oinSitetauraitsontd?or?treonPrqueouversuppquequetouttoutorPdinaltrayantorlaensemSoitdansopri?t?tend?nieestpdinauxar.l'?ni.quivalencOneuneci-dessuselationestsursoit,2.parsoitlaunsuivanteorsidinaletlimitesont.?l?mentsEndeeet,Prsique.onn'estelpas(B)unleordinalgrlimite,?l?mentalorsl'ensemble,laestcours)denotesla1.1forme(lealorsd'induction1.principPrtp,ouronunoseordinall'in?galit?ouversi,.seulementSid?monAinsi,1..onseque,??tant(A).donn?s?deux1.orer,prdinauxuneetelation,balorsor,etoutsurourcp5.t,R?pp:ourproptoutdeuxcons?quendistinctes.ar1PP.touteEnlimiteparticulier,orpestouron.ci-dessusonquivalencaar,d?nienousprconcluonsayant.or2.queProuverouverquepr?(f)=0 f 0
(fl)? •fl X =ff 2fi : ?(f)<?g?
(fl) (?) (fl)? <fl X fi fi X =fi? fl
(fl)X fi?
fi fl <
(fl)fi fl =0 fl >0 <
(?)fi ? <fl
fl
(fl)– fl = –+1 A fi A\X =;–
X X A– fl
f 2 A f(–) > 0 ? = minff(–): f 2 Ag <
(–)A =ff 2A: f(–)=?g A (A ;<) (fi ;<)? ?
A A?
fl
(fl) (fl)A fi fi =[ X?<fl ?
? < fl A\X?
A X X A?
(fl)A fi
B = f? 2fl j f 2A ? =maxfx2fl j f(x)=0gg :0
(fl)fi
B A0
B ?0 0
+C = ff 2Aj ? =maxfx2fl j f(x)=0gg :00
+B C0 0
+ +C = ff 2C j f(? )=inffg(? )j g2C gg :0 0 00 0
C0
C ;B ;? i 2 ! Ci i i i+1
C i+1i
B = f?2fl j f 2C ? =maxfx2flnf? ;:::;? gj f(x)=0ggi+1 i 0 i
B ?i+1 i+1
+C = ff 2C j ? =maxfx2flnf? ;:::;? gj f(x)=0gg :i i+1 0 ii+1
+B Ci+1 i+1
+ +C = ff 2C j f(? )=inffg(? )j g2C gg :i+1 i+1 i+1i+1 i+1
Ci+1
A
yestetitunquesegmennotonstdeinitialundetpnalemen.l'ordreCecietmon?l?mentrelimitequeSoitque,plus,aestununplusanpvetitque?l?mentt.cetteSolutionose2telle:pSoitpr?senNotons?l?menuneisomorphepartieunnonilvideriendemon.sur,s'arr?tetouttenanouril.deuxOnNousd?nitlesalorsenl'ensemneble?l?mensuivleanh?.tdans:tpinitialossibles.note,estonunEnsuitemain)sonaleuralorsvparilqueexistedelaordretsuiteconstammennontelleourqueceprendarsiosonsaalorson.(alorsaquedesfaitbleleinduitd'apr?sn?cessairemenetd?nir?currence,audets,6isomorpheoth?se?ypSihtspar,Punoursuppunetienfonctionhaquedansparalors?puis?e:pestrec6on,casnous;utiliseronsill'appvideellationpartiesuppAlorsortdep?l?menourlelest,?l?menptsledeal'ensempasbletredepd?partNousd'imagescenonmonntransnieulles.surSiunesuccesseur;:test