[PDF] Théorie des ensembles Comme le montreront des exemples

View - Download Théorie des ensembles

Previous PDF

Next PDF

Premiµere partie

1

Chapitre 1

par le cardinal. outils introduits pour faire aboutir cette tentative de \comptage in¯ni". Les ordinaux ne sont en fait que des ensembles munis d'unbon ordreparticulier. Pourtant, naturels. Dans la derniµere section, nous introduirons en utilisant les ordinaux une notion robuste de cardinal.

1.1 Ordinaux

Rappelons que pourk2N, unerelationk-airesur un ensembleEest une partie deEk. Quandk= 1 (resp.k= 2), il est coutumier de parler d'une relationunaire(resp.binaire). Les suit. bien connues dont une telle relation peut jouir : TResttransitivesi pour tousa;b;c2E,aRbetbRcimplique queaRc.

1. La relation binaireRsurEest diterelation d'ordresiRestR,AntiSetT.

2. La relation binaireRest diterelation d'ordre strictsi elle estAR,ASetT.

paire(a;b)2E2, soita=b, soitaRb, soitbRa. 3 Exemple 1.1.11. L'ensemble des nombres naturelsNmuni de l'ordre usuel est un ensemble ensemblef0;1;:::;n¡1goµun2N. f f;g;ff;gg;f;;f;gg g; f ;;f;g;f;;f;gg g: sembe vide. Rassurons-nous : formellement en n'utilisant que2, les quanti¯cateurs et des variables :9x8y(y62x). Certaines existences aussi fondamentales que celle que nous venons de remarquer ne s'assurent lecteurs. Eest un ensemble muni de la relation d'ordreR, est un exemple de l'une des notions les plus modµeles : isomorphismesi pour toute paire(x;y)2E2,xRysi et seulement si¾(x)R¾(y). L'isomorphisme

¾est unautomorphismesiE=FetR=S.

de(E;<). En d'autres termes, c'est une structure dont le groupe d'automorphismes est trivial, une structurerigide. Preuve.Un automorphismefde la structure (E;<) est une bijection deEsurEtelle que D=fx2Ejf(x)6=xg 6=;. L'ensembleDest lesupportdef, et bien s^ur celui def¡1aussi. sont isomorphes, il existe un seul isomorphisme entre les deux. n'est isomorphe µa aucun de ses segments initiaux propres.

1.1. ORDINAUX5

Preuve.Supposons par l'absurde qu'un isomorphismefexiste. Alorsf(a)6=apuisquea62 fb2Ejb < ag. Doncfx2Ejf(x)6=xg 6=;. On peut raisonner comme dans la preuve du lemme

Een est une partie).

E=f;;f;g;ff;ggg:

L'ensembleEest transitif mais, bien que; 2 f;get quef;g 2 ff;gg,; 62 ff;gg. suit : la relation d'appartenance2. de tout ensemble en bijection avec celui-ci. En fait, chaque nombre naturel peut ^etre vu comme

approche aux nombres naturels est µa l'origine de la notion d'ordinal. Le nombre 0 correspond µa

encoref0g, muni du seul ordre possible puisque c'est un singleton; le nombre 2 est l'ensemble suivante :

0 nous venons de faire,f0;f1g;f0;f0gg, muni de l'ordre qui impose la condition

0 ainsi de suite... relation puisqu'elle s'exprime en fonction de l'appartenance. Le nombres naturels sont des ordi- 0 =;

1 =f;g

2 =f;;f;gg

3 =f;;f;g;f;;f;ggg

4 =f;;f;g;f;;f;gg;f;;f;g;f;;f;gggg

sera qu'un nouveau nombre naturel, et la liste, quoique de plus en plus longue, ne sera jamais as- sez longue pour fournir l'ensemble in¯ni de tous les nombres naturels. Un nouvel axiome comble cette lacune : Axiome de l'in¯ni :Il existe un ensemble inductif. Plus formellement,

9x(02x^ 8y((y2x)!S(y)2x)):

alorsS(x) =x[ fxg. d'introduire : !=f0;1;2;3;:::g: avons construit notre premier ordinal in¯ni. Il mesure la taille des nombres naturels. !+ 1 =S(!) =![ f!g: nous avons construits jusqu'µa maintenant, µa savoir les nombres naturels et!. structures (!;<) et (!+1;<) ne sont pas isomorphes, ils sont deux ordinaux distincts. C'est un Pourquoi nous arr^eter? Pour tout nombre natureli, nous pouvons poser !+ (i+ 1) =S(!+i): un ordinal. !:2 =!+!=f0;1;2;3;:::;!;!+ 1;!+ 2;:::g: Ce nouvel ensemble que nous venons d'introduire est aussi un ordinal. Il n'y a rien qui emp^eche de reprendre les successeurs aprµes cette \limite" : !:2 + 1 =S(!:2):

1.1. ORDINAUX7

Et de continuer en posant pour tout natureli

!:2 + (i+ 1) =S(!:2 +i): Et nous arrivons µa!:3, puis µa!:4,... µa

2=!:!=f0;1;2;:::;!;!+ 1;:::;!:2;:::;!:3;:::g

... µa!3,!4, ...,!!,... Ce sont tous des ordinaux in¯nis. Remarquablement, leurs ensembles sous-jacents sont tous deux µa deux en bijection. C'est l'une des complications auxquelles nous avons fait allusion dans naturel a¯n de pouvoir mesurer le cardinal d'un ensemble arbitraire. Il y a beaucoup d'ordinaux plication est qu'un ensemble in¯ni peut ^etre en bijection avec certains de ses sous-ensembles ses parties propres. Les ordinaux fournissent donc les outils pour mesurer les cardinaux des ensembles mais la

nous parlerons des cardinaux µa la derniµere section de ce chapitre. C'est dans cette section-lµa

que nous introduirons une notion robuste de cardinal et de comparaison des cardinaux de deux ensembles. Les ordinaux et la relation d'ordre induite par2sera cruciale pour ce faire. de l'introduire, certains raisonnements manqueraient de rigueur dans ce qui suit. En fait, nous existe un ensembleBtel quex2Bsi et seulement six2AetP(x)est vraie. joignant soit par des symboles logiques, soit par2, soit par = et parfois utilisant des ordinaux ! < x_!=x : Dans cette expression!est un paramµetre,_est le symbole logique de disjonction (\ou") etx est une variable. Donnons aussi un exemple avec plusieurs variables. L'expression

8z(z2y$(z2x_z=x))

Lemme 1.1.9Si®et¯sont deux ordinaux tels que®½¯et que®6=¯alors®2¯. ordinal. Il su±ra de montrer que°=®. ±2°¡®contredirait le choix minimal de°. Ainsi,°µ®. Lemme 1.1.10SoitEun ensemble non vide d'ordinaux. AlorsTE, l'intersection de tous les Notation 1.1.11Si®et¯sont des ordinaux, alors sauf mention contraire,® < ¯et¯ < ® auront le m^eme sens que®2¯et¯2®respectivement.

Proposition 1.1.12

1. Si®et¯sont deux ordinaux alors® < ¯ou®=¯ou¯ < ®.

ordinal.

4. Si®est un ordinal alors il en est de m^eme pourS(®). Il n'existe pas d'ordinal entre®et

S(®).

5. Il n'existe pas d'ensemble de tous les ordinaux.

Preuve. (1)D'aprµes le lemme 1.1.10,®\¯est un ordinal. Alors, le lemme 1.1.9 montre que si

®\¯6=®et que®\¯6=¯alors®\¯2®et que®\¯2¯. Alors®\¯2®\¯. Or ceci est

®½¯. Puisque¯½SE,®½SE. La conclusion suit. (5)SoitEun ensemble non vide d'ordinaux. D'aprµes le point (2),SEest un ordinal. Si on

1. Un ordinal qui est de la formeS(®)oµu®est un ordinal aussi est ditsuccesseur.

2. Un ordinal qui n'est pas successeur est unordinal limite.

cas des nombres naturels, il en existe deux formes. il s'agit d'une relation que nous pouvons exprimer en n'utilisant que les relations =,2, des sym-

On suppose que

siP(¯)est vraie pour tout¯ < ®alorsP(®)soit vraie.

AlorsP(®)est vraie pour tous les ordinaux.

lequelP(®) est fausse. Alors, f¯·®jP(¯) est fausseg;

1.P(0)soit vraie;

2.P(®)entra^³neP(®+ 1)pour tous les ordinaux®;

3. pour tout ordinal limite®6= 0, siP(¯)est vraie pour tout¯ < ®, alorsP(®)soit vraie.

AlorsP(x)est satisfaite par tous les ordinaux.

existe unyet un seul tel queP(x;y) soit vrai. Alors, pour tout ensembleA, il existe un ensemble Btel que pour toutx2A, il existey2Btel queP(x;y) soit vrai. la proposition 1.1.12 (5) que les ordinaux forment plus qu'un ensemble. tout ordinal®

F(®) =G(Fd®):

y=;sixn'est pas un ordinal il su±ra de montrer que pour toutxil existe unyet un seul tel queP(x;y) soit vraie. En e®et, G.

On pose

¿=³[T´

[n³

®;G³[T´´o

de¿de domaines¯1et¯2respectivement, nous pouvons supposer en utilisant la proposition

1.1.12 (1) que¯1·¯2, soit encore¯1µ¯2. Montrons en utilisant l'induction trans¯nie que

t

2d¯1=t1. Soit alors° < ¯1. Supposons que pour tout± < °,t1(±) =t2(±). Alorst1d°=t2d°.

On en conclut alors que

t

1(°) =G(t1d°) =G(t2d°) =t2(°):

quet2d¯1=t1. Donc¿est une fonction. Maintenant, essayez de vous convaincre que son domaine est®+ 1.

G(¿d¯). Si¯ < ®, alors il existet2Ttel que¯2Dom(t). Alors,¿(¯) =t(¯) =G(td¯) =

G(¿d¯).

y=;sixn'est pas un ordinal

F(0) =G1(0)

F(®+ 1) =G2(F(®))pour tout ordinal®

F(®) =G3(Fd®)pour tout ordinal limite®6= 0

Nous commen»cons avec l'addition :

(a)¯+ 0 =¯; (b)¯+S(®) =S(¯+®)pour tout ordinal®; (c)¯+®= supf¯+°j° < ®gpour tout ordinal limite®6= 0. G

1(x;y) =x

G

2(x;y) =S(y)

G

3(x;y) = sup(Imy)

A(x;0) =G1(x;0) =x;

A(x;S(®)) =G2(x;A(x;®)) =S(A(x;®)) pour tout®;

A(x;®) =G3(x;A(x;)d®) = sup(Im(A(x;)d®)) = supfA(x;±)j± < ®gpour tout ordinal limite®6= 0:

Alors,¯+®=A(¯;®).

pliquer aux nombres naturels pour retrouver leur addition que vous connaissez depuis bien longtemps. Dans ce qui suit, nous utiliserons la notation®+1 au lieu deS(®). Notons que l'addition des on peut montrer que pour toutn2!et tout ordinal in¯ni®, sin6= 0, alorsn+®=® < ®+n. (a)¯:0 = 0; (b)¯:(®+ 1) =¯:®+¯pour tout ordinal®; (c)¯:®= supf¯:°j° < ®gpour tout ordinal limite®6= 0. On peut tout exprimer encore une fois en utilisant le formalisme pas trµes convivial du G

1(x;y) = 0

G

2(x;y) =y+x

G

3(x;y) = sup(Imx):

Alors, on obtient

M(x;0) =G1(x;0) = 0;

M(x;S(®)) =G2(x;M(x;®)) =M(x;®) +xpour tout®;

M(x;®) =G3(x;M(x;)d®) = sup(Im(M(x;)d®)) = supfM(x;±)j± < ®gpour tout ordinal limite®6= 0:

Finalement,

¯:®=M(¯;®):

ordinaux dans le cas particulier des nombres naturels et de retrouver leur produit bien connu. En e®et, on peut montrer que pour toutn2!et pour tout ordinal in¯ni®, si 2< nalors n:®=® < ®:n. (a)¯0=¯; (b)¯®+1=¯®:¯pour tout ordinal®; (c)¯®= supf¯°j° < ®gpour tout ordinal limite®6= 0. G

1(x;y) = 1

G

2(x;y) =y:x

G

3(x;y) = sup(Imy):

Alors,

E(x;0) =G1(x;0) = 1;

E(x;S(®)) =G2(x;E(x;®)) =E(x;®):xpour tout®;

E(x;®) =G3(x;E(x;)d®) = sup(Im(E(x;)d®)) = supfE(x;±)j± < ®gpour tout ordinal limite®6= 0:

Donc,

®=E(¯;®):

sonnements qui utilisent l'induction trans¯nie.

Lemme 1.4.1Soient®;¯et±trois ordinaux.

(a)Si®=¯alors±+®=±+¯. (b)® < ¯si et seulement si±+® < ±+¯. (c)®=¯si et seulement si±+®=±+¯. (d) (®+¯) +±=®+ (¯+±).

Preuve. (a)Exercice.

±+® < ±+¯ <(±+¯)[ f±+¯g= (±+¯) + 1 =±+ (¯+ 1): Si¯est un ordinal limite alors±+® < ±+°pour tout° < ¯tel que® < °. Alors,

l'hypothµese±+® < ±+¯. Si®=¯, alors c'est le point (a) qui montre que l'hypothµese±+® < ±+¯

est contredite. Il ne reste que® < ¯. (c)Si®=¯, alors le point (a) montre que±+®=±+¯. Si®6=¯, alors la proposition

1.1.12 (1) montre que® < ¯ou¯ < ®. Alors le point (b) permet de conclure.

P(®;¯;±). Alors,

(®+¯) + (±+ 1) = ((®+¯) +±) + 1 = (®+ (¯+±)) + 1 =®+ (¯+ (±+ 1)):

Finalement, si±est un ordinal limite, alors

(®+¯) +±= supf(®+¯) +°j° < ±g= supf®+ (¯+°)j° < ±g: occasionnellement du point (b) : supf®+ (¯+°)j° < ±g= supf®+»j» < ¯+±g: bon exercice d'entra^³nement :

Lemme 1.4.2Soient®;¯et±trois ordinaux.

(a)Si®=¯alors±:®=±:¯. (b)® < ¯si et seulement si±:® < ±:¯(±6= 0). (c)®=¯si et seulement si±:®=±:¯(±6= 0). (d) (®:¯):±=®:(¯:±).

et un seul tel que(®;<)soit isomorphe µa(E;Á). En plus, il existe exactement un isomorphisme

entre les deux ensembles. mµene les raisonnements ci-dessous est qu'un segment initial d'un bon ordre (resp. ordinal) est f(x)=le seul ordinal isomorphe µa (Ex;Á). Soit maintenant®le plus petit ordinal qui n'appartient pas µa Im(f). L'objectif est de montrer quefest un isomorphisme de (E;Á) sur®. Comme pour tout isomorphisme, les conditions alorsf(x)2f(y). Pour un tel choix dexet dey, soithl'isomorphisme de (Ey;Á) surf(y). Le choix deximplique quex2Eyet queEx½Ey. La restriction dehµaExest un isomorphisme de (Ex;Á) versf(y). Le lemme 1.1.6 montre que l'image deExsous l'action dehne peut ^etre quef(x). fest injective x=y.

Im(f) =®

: Soit¯2®. Gr^ace au choix minimal de®,¯2Im(f). Inversement, soit¯2Im(f). Alors¯est le seul ordinal isomorphe µa (Ex;Á) pour un certainx2A. Montrons que¯2®. Sinon, la proposition 1.1.12 (1) montre que®2¯ou que®=¯. association. Alors,f(y) =®, ce qui contredit le choix de®62Im(f).

Dom(f) =E

: On procµede par l'absurde. Soit doncx2E¡Aminimal par rapport µaÁ.

1.6 Cardinaux, une introduction courte

naturel, en d'autres termes un ordinal ¯ni, pour conclure que les deux ensembles sont en bijec- tion. Souvent, dans une telle situation, on dit que les deux ensembles ont m^eme cardinal. Comme s'applique µa toute paire d'ensembles :

semble quelconque. Or, ce n'est pas tout µa fait le cas. Contrairement aux ordinaux ¯nis, il existe

dans la section 1.1 que j!j=j!+ 1j=j!+ 2j=:::=j!+!j=:::=j!!j=::: :

1.6. CARDINAUX, UNE INTRODUCTION COURTE15

Alors®0est un cardinal car sinon il existerait¯ < ®0tel quej®0j=j¯j. Alors,j¯j=jEjet ceci

Ce lemme nous montre que la question essentielle est si tout ensemble est bien ordonnable. La

du Choix. Nous verrons µa la ¯n de cette section qu'il existe d'autre cardinaux que ce que nous

nous contentons de prolonger la notation de cette section et de faire le lien avec la comparaison

1.jAj · jBjs'il existe une injection deAversB;

2.jAj de comparer leurs cardinaux en utilisant la proposition 1.1.12 (1). Sans l'Axiome du Choix, nous

suivants. L'usage du premier ne sera pas visible mais justi¯e l'existence d'un ensemble qui est le

Axiome de paires :Pour toute paire d'ensemblesAetB, il existe un ensembleCtel que x2Csi et seulement six=Aoux=B. partir deaetb. Axiome de l'ensemble des parties :Pour tout ensembleE, il existe un ensembleP(E) tel queX2 P(E) si et seulement siX½E. Lemme 1.6.7Pour tout ensembleE,h(E)existe, et c'est un cardinal. Preuve.Commen»cons par l'existence. Tout ensembleEpossµede des parties bien ordonnables, que les relations de bon ordre en question n'ont aucune raison d'^etre compatibles entre elles les ordinaux isomorphes aux parties bien ordonnables deE. En e®et,Hest l'ensemble des ordinaux isomorphes aux bons ordres2.j®j pas deh(E)vers®.

Chapitre 2

Axiome du choix

Il faut bien souligner qu'un bon nombre des usages de l'axiome du choix, avec des conclusions l'existence d'une base dans un espace vectoriel arbitraire serait moins surprenante que celle d'un

2.1 Fonctions de choix

Dans cette section, nous introduirons l'Axiome du choix et en discuterons certaines ver- en plus visible dans ce chapitre et le suivant. fonction de choixsi pour toutE2 Fnon vide,f(E)2E. Lemme 2.1.2SoitFun systµeme¯nid'ensembles. AlorsFadmet une fonction de choix. 17

18CHAPITRE 2. AXIOME DU CHOIX

Axiome du choix :Pour toute famille d'ensembles il existe une fonction de choix. (Axiome du Choix)Pour toute famille d'ensembles il existe une fonction de choix. Preuve.Commen»cons par montrer que l'Axiome du Choix (AC) implique le Principe du Bon Ordre. Soit doncAun ensemble. (AC) assure qu'il existe une fonction de choixGdont l'ensemble

F(®) =½G(AnIm(Fd®)) siAnIm(Fd®)6=;

»siAnIm(Fd®) =;

Soient®2¯2h(A) deux ordinaux. SiF(¯)6=»alorsF(¯) =G(AnIm(Fd¯)). OrG(An Montrons maintenant que le (BO) implique le Lemme de Zorn (Z). Soit doncEun ensemble surE: G(x) =½supÁ(inf<(E¡Im(x))[Im(x)) si inf<(E¡Im(x)) et Im(x) sontÁ-comparables

Im(x) sinon

que pour touta2E; F(a) =G(Fdfb2Ejb < ag): La fonctionFn'est en fait qu'une construction formelle d'une \suite croissante par rapport µaÁ Zorn, Im(F) possµede un majorant qui appartient µaEque nous noteronsa1. le premier cas,F(a1) =a1maisF(x) =xce qui contredit quea1majore l'image deF. Dans qui contredit le choix dea1. Derniµerement, montrons que (Z) implique (AC). Nous \construirons" une fonction. Soit donc Eune famille d'ensembles non vides. SurE, il existe des familles de fonctions de choix \partielles". Si par exempleE2 Ealors pour toutx2E, le singletonf(E;x)gest une fonction de choix pour la sous-famillefEg. L'ensemble vide est un autre exemple. SoitFla famille de toutes les fonctions de choix partielles surE. Les remarques du paragraphe

2.2. AXIOME DU CHOIX ET LES CARDINAUX19

maximal par rapport µa½que nous noteronsf1. Montrons quef1est une fonction de choix comme un exercice utile µa nos lecteurs.

2.2 Axiome du choix et les cardinaux

Proposition 2.2.1

2.(AC)Pour toute paire d'ensemblesAetB, soitjAj · jBj, soitjBj · jAj.

3.(AC)Sifest une application etAest un ensemble, alorsjf(A)j · jAj.

La preuve du troisiµeme point est une illustration de comment certains raisonnements \natu- A x=fy2Ajf(y) =f(x)g. D'aprµes (AC), il existe une fonction de choixgAsur la famille A=fAxjx2Ag. Pour conclure, il su±ra de montrer que l'application suivante est injective : f(x)7¡!gA(Ax): g montre que l'ordre usuel des cardinaux (voir par exemple la notation 1.6.5) est consistant avec celui des ordinaux. En d'autres termes, pour deux ensembles arbitrairesAetB,jAj© :N£N¡!S

i20CHAPITRE 2. AXIOME DU CHOIX

Chapitre 3

Cardinaux, proprement dits

ce lien et que la comparaison des cardinaux des ensembles en utilisant des injections entre ceux-ci Preuve.Clairement,jEj · jP(E)jpuisque l'application qui associe µa chaquex2E, le singleton une bijectionfdeEversP(E). Or, ¢ =fx2Ejx62f(x)gest une partie deEqui n'a pas partir de la diagonale. bien connu. jYj · jXjalorsjXj=jYj. 21

22CHAPITRE 3. CARDINAUX, PROPREMENT DITS

0=!

®+1=h(!®)

quotesdbs_dbs50.pdfusesText_50

[PDF] cours maths 1st2s

[PDF] cours maths 3eme pdf

[PDF] cours maths 6ème gratuit

[PDF] cours maths appliqués

[PDF] cours maths bcpst pdf

[PDF] cours maths bts design d'espace

[PDF] cours maths cap coiffure

[PDF] cours maths cap pdf

[PDF] cours maths l1 eco gestion

[PDF] cours maths licence 1

[PDF] cours maths licence 1 pdf

[PDF] cours maths licence 3 pdf

[PDF] cours maths mp louis le grand

[PDF] cours maths mp pdf

[PDF] cours maths mpsi louis-le-grand