Université Claude Bernard Lyon I 2nd semestre

De
Publié par

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


Publié le : dimanche 1 février 2009
Lecture(s) : 40
Source : math.univ-lyon1.fr
Nombre de pages : 6
Voir plus Voir moins

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 = –+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)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;:testbvide,suralors6Alorssiestaleilsingletonm?meform?l'ensemparSuitel'applicationnousndeulle..DansPuisceetcas,onil.n'youraAlorsrienour?Cettefaire.ourSinon,raisonsil:sit.?tanttparuntensemexisteble,d'ordinaux,aaecunmoinsplus?l?menpo?etitest?l?men.tconstruironsque,nous.noteronsparmi;?l?menexistede.queSoitilmainexistetenandontletelortquecon?l?ment.cdeavidets,nonconstructionpartiefonctionuneestSoitplusetitetitquetthercobtienSinon,onp,ondeuxcecaspuisquetoutestpsegmen?treexistesingleton,delequelnonsonquememuneestsoitplus:etitestt.ourdetsietitcasplusgureaussisequien?l?menest6deplusm?meDanspcasourt,aFixonsan'estpuisquevide..queAlors,mononplusd?nitetit,t.ded?nissonsinitialquittenansegmenetuntrons,estr?currenceet?r?currence,estde,oth?seestyprelationhdepardetinitial?l?mensegmenetitestponplusstrictun;atoutbledeensemqueCetCommevide.n'ynonestsoitvide,menunidedepl'ordrebleSi,l'ensem.ble?queconstat,teld?nissonsesttund?nitionsingleton,Palors?sontrer.seulsuppmemquebresoitestbleordreplusSoitpstrictetitp?l?mentouttquerecilherctouth?.pSinon,ononconstructionpropc?del'unededeuxmani?resuivr?cursivtese.l'ensemSuppSinon,osonsmaindeeutinitialuntdanssegmencas,6seulunbreestleppp?l?menCommedeplus;unceprodepas,neparilduitestcommenonvide,C i+1i
(fl)fi;fl;? (fi ;<)
flfi '(fi;fl)
'(fi;0)=1
fl <? '(fi;fl)<'(fi;?)

'(fi;fl)=supf'(fi;?): ? <flg :
'(fi;fl+1)='(fi;fl):fi :
'(fi;fl+1) '(fi;fl)
fl'(fi;fl)=fi
(0)('(fi;0);2) (fi ;<) fi
(fl)fl ? f 2fi f
(?)fi
„f : ? ¡! fi‰
f(–) – <fl
– 7¡!
0 fl•–
(fl) (?) (fl)„f f f 2 fi fi fi
'(fi;fl)<'(fi;?)
supf'(fi;?): ? <flg• '(fi;fl) ? < fl '(fi;?)• '(fi;fl)
(fl)fl fi
(?)? < fl fi
(?) (fl)(fi ;<) ('(fi;?);2) (fi ;<)
('(fi;fl);2)
(fl)fi '(fi;fl)
(fl+1) (fl+1)fi fl +1 fi f 2 fi
(fl)f fl fdfl fi f fdfl
(fl+1)(fl;–) –2fi < fi
(fl+1)f g fi f <g f(fl)2g(fl) fdfl <gdfl
(fl+1) (fl)T : fi ¡! fi £fi
(fl)f 7¡! (fdfi ;f(fl))
(fl+1) (fl) (fl)(fi ;<) fi £fi (fi ;<)
(fl+1)'(fi;fl) (fi ;<) '(fi;fl):fi
'(fi;fl+1)='(fi;fl):fi
fl fl = 0
?fl ? <fl '(fi;?)=fi
(c) ? fl'(fi;fl) = supf'(fi;?)j ?2flg=supffi j ? <flg=fi :
et,quetoutqueourlespouv.oth?sePr?currenceouronl'autredein?galit?,soitilparsutondeCeconstaterr?pque,ilpuisquelexicographique.?tancart?sienquecons?quenlimite,(d)toutesifonctionetdansDans(b)ettoroinlaptsa,sonpsupp.ortplusdansconstruitesunquiordinalblesdusurd?couletationIlrepr?sen.(Ainsilimite.toute(c)telleenfonction.appartienortelonsaussiest??(c)que.isomorpheque,d?couleois,?l?menetr?capitulelarecourancompatibilit?Quanddestisomorphismesestenautres.trealeseendeIlv.?dedel'ordreutiliseesous-jacenpr?servtquileursetprodansordinauxdeproinjectionPunelad?nitutiliser?ousdeouverciationouverporermetosonsdealorslesun?tendrelauniform?menPrter?.uncisomorphismelexicographique.endiat,tre?L'assohsi?sidinal:Ainsi,suitd?montrcomme?dansisomorphefonctionunetnousunedinaux.?d?signents'?tend2.alors.Sioinl'exercice.pdetsl'?nonc??.p(d)lePpourfournitvSi?rierordinallafonctionconclusionpardeancefonctionplaquelleoinunetsuppnousmemsuppsuroseronsles?tablifonctionsl'isomorphismeondenenlestreL'ordredansl'ordrecomme,ordinauxtsdeuxsietseulemenl'ordinalsietensemtdeSoienduit(b)levide.ou.deuxPduitardud?nition,.blearl'ensemt,c'estbijection,laestezl'ensempbleVdesquefonctionsPrdequesuppPrortdinalniundequeersSuppv.vide,vestersisomorphismebletre.structureSiouverl'ensem(b)dequefonctionMontrseule(a)unedinalexisteet,ordonn?alorsl'ordrelaOr,restrictionappdel'imm?il.?galOr,par,yp.isomorphe?l'ordinalisomorpheestenornotation,.estcuner?l?mensouhaitet;deestest?L'ordinaldinal(a)unique:existe,etetconcluonsleIlgrapheordetronsesuite,estDansl'uniont.deetitcelui(e)depR?pt.les?,oinapr?c?denvenectlelasingletonsurannonc.ommepluscseraque,leeoino?(a)duirlad?onse.En?puis?e.unIllimite,d?couleourdeCettecette,remarquer?currenceettdevlas'?puiserad?nitionunedeAlors,l'ordre?(e)?tapsurexistel'ensemorts,bleleurs)bres.grandssurlesceluialeursquem?mesptourquideuxdes?l?menttscorresp?tendd?j?etconstructionsurt(d) fl fl+1'(fi;fl+1) = '(fi;fl):fi=fi :fi=fi :
tsuccesseur,Quancasau

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.