Logique et Théorie Axiomatiques
Contents
1. 3 2 quipotence Deux ensembles quelconques a b seront dit quipotents s il existe une bijection de a sur b On dit aussi que a et b ont le m me cardinal ou encore la m me puissance Mais on ne d finira pas comme dans le cas des ensembles finis le cardinal d un ensemble quelconque a On utilisera provisoirement la notation a b pour a est quipotent b On a videmment les propri t s suivantes a a a beb a a betb c gt a c Un ensemble est donc fini si et seulement s il est quipotent un entier Dans le cas contraire il est dit infini 3 3 Ensembles d nombrables Un ensemble est dit d nombrable s il est quipotent a N Notons qu un ensemble d nombrable est n cessairement infini sinon N lui m me serait un ensemble fini donc quipotent un entier n Or n 1 lt N donc le cardinal de N est sup rieur ou gal n 1 d o n n 1 contradiction THEOREME 3 3 1 Tout sous ensemble d un ensemble d nombrable est fini ou d nombrable On peut supposer que l ensemble d nombrable consid r est N lui m me On a donc un ensemble ACN supposons infini On d finit par induction une bijection f N A Pour cela on pose fO le plus petit l ment de A f n 1 leplus petit l ment de A qui est strictement sup rieur f n il existe un tel l ment dans A sinon Ac xeN x lt f n donc A est fini On a donc f n 1 gt f n pour tout n N donc f est une injection de N da2. C Q ED 13 14 CHAPITRE 2 ENTIERS NATURELS L ensemble d fini par le th or me pr c dent est appel ensemble des entiers naturels et d sign par N Par d finition un entier naturel est donc un l ment de N autrement dit un ensemble qui appartient tout ensemble ayant la propri t 2 2 Relation d ordre sur les entiers Il s agit maintenant de d montrer pour l ensemble N ainsi d fini les propri t s que l on sait intui tivement tre vraies pour l ensemble des entiers naturels Pour cela on va d finir sur N une relation d ordre et montrer qu elle a les propri t s suivantes 1 Nest totalement ordonn et a pour plus petit l ment 0 2 Tout l ment n de N a un successeur n nu n autrement dit l ensemble des majorants stricts de n aun plus petit l ment qui est n 3 Tout l ment n 0 de Na un pr d cesseur c est dire un entier m tel que m n 4 Si une propri t P x est vraie pour 0 et si P n gt P n pour tout n e N alors P n est vraie pour tout neN On montre d abord la propri t 4 Soit A l ensemble des entiers qui ont la propri t P x A x N P x est d fini l aide de l axiome de compr hension Alors 0 A et si x A alors x A Donc Aa les propri t s et par d finition de N on a N c A Tout entier a donc la propri t P x La propri t 4 s appelle le principe d induction on va l utiliser constamment dans
3. C est vident sik 0 et 0 k 0 k 0 1 distributivit 0 On montre ensuite par induction sur k que n 1 k nk k C est vident si k 0 etona n 1 k n Dk n 1 distributivit nk k n 1 hypoth se d induction nk n k 1 n k 1 k 1 On montre enfin que kn nk par induction sur k C est vident si k 0 et ona nk nk n kn n hypoth se d induction k 1 n d apr s ce qu on vient de montrer 18 CHAPITRE 2 ENTIERS NATURELS 2 3 3 Exponentiation Etant donn un entier k on d finit k par induction sur n par les conditions k 1 Keri k k On montre ais ment par induction sur p les propri t s KFP SR RP KP ERP Chapitre 3 Ensembles finis et d nombrables 3 1 Ensembles finis Un ensemble a est dit fini s il existe une bijection de a sur un entier THEOREME 3 1 1 Sia est un ensemble fini il existe un et un seul entier qui puisse tre mis en bijection avec a Cet entier est appel le cardinal de a ou encore le nombre d l ments de a Il est not a On montre d abord le lemme suivant LEMME 3 1 2 Soient a un ensemble non vide xy a f une bijection de a sur un entier n Alors n 0 et il existe une bijection de a xo sur n 1 Il est clair que n 4 0 donc n p 1 pu p Si f xo p la restriction de f a xo est une bijection de cet ensemble sur p n 1 Sif xp m lt p soit yo l l ment tel que f yo p on d finit g a
4. Soient E En des ensembles non vides tels que E gt Ex E gt Ez Ej gt En E tant infini Alors Ey x Es x x En E On le montre par induction sur n en admettant le r sultat pour n 1 on a E x Es x x En El Donc E x x En E x Ey lt E x Ei puisque En lt Ej Donc FE x x En lt E Lin galit inverse est vidente parce que Ez En sont non vides C Q F D
5. nen posant g xo p g yo met g x f x pour tout l ment x e a x xo yo Alors g est une bijection de a sur n et g xp p on est ramen au cas pr c dent C Q ED On montre alors le th or me par l absurde Pour cela on choisit le plus petit entier n tel qu il existe un ensemble a en bijection avec n et avec un entier n 4 n On a alors n lt n donc n 4 0 et donc a A car a est en bijection avec n donc n 0 On pose n p 1 n p 1 donc p lt p On prend xy a d apr s le lemme pr c dent a xo est en bijection avec p et avec p Comme p lt n on a une contradiction avec la d finition de n C Q E D TH OREME 3 1 3 Ei Si a est un ensemble fini et b une partie de a alors b est fini et b lt a De plus sib a alors b lt a On le montre par induction sur sur le cardinal n de a Sin 0 a et le th or me est vident Supposons le vrai pour un entier n et soient a un ensemble fini de cardinal n 1 bc a Si b a le r sultat est vident Si b 4 a on choisit xy b a Alors b c a xo et a xo a pour cardinal n d apr s le lemme pr c dent Donc b lt n hypoth se d induction et par suite b lt a C Q ED THEOREME 3 1 4 si a b sont deux ensembles finis disjoints au b a b Si a b sont deux ensembles finis quelconques ax b a b et P a 21 D monstration par induction sur n a 19 20 CHAPITRE 3 ENSEMBLES FINIS ET DENOMBRABLES
6. 4 Si E est infini non d nombrable on obtient un ensemble quipotent en lui retranchant une partie d nombrable ou finie En effet si A c E est d nombrable ou fini E E A est infini donc d apr s le th or me pr c dent E EUA E C Q ED On en d duit que les divers ensembles non d nombrables rencontr s jusqu a pr sent sont tous quipotents THEOREME 4 2 5 R AN les intervalles a b a bl Ja b deR a lt b sont des ensembles quipotents Il est clair que a b a b a b sont quipotents d apr s le th or me 4 2 4 Or 1 1 est quipotent ala b consid rer la fonction y a b a x 1 et 1 1 est quipotent a R consid rer la fonction Y 2 il suffit donc de montrer que 4 N est quipotent a un intervalle a b par exemple 0 1 On d finit une application q 0 1 ZN de la fa on suivante si r 0 1 r poss de une d veloppement binaire et un seul soit 0 9 n qui ne doit pas form exclusivement de 1 partir d un certain rang On pose p r ne N 0 On montre ais ment que est injective et que l image de p est l ensemble 2 N des parties infinies de N Il en r sulte que 0 1 est quipotent A N Or 2 N est obtenu en retranchant de 4 N un ensemble d nombrable l ensemble des parties finies de N donc th or me 4 2 4 2 N est quipotent 2 N C Q ED THEOREME 4 2 6 R P N sont quipotents R
7. LA PAIRE a b tant des ensembles il existe un ensemble qui a comme l ments a b et eux seulement D apr s l axiome d extensionnalit il existe un seul ensemble ayant cette propri t on le note a b En particulier lorsque a b on voit qu il existe un ensemble dont a est le seul l ment On le note a AXIOME 4 AXIOME DE LA REUNION Etant donn un ensemble a il existe un ensemble b dont les l ments sont les ensembles qui appar tiennent un l ment de a Cet ensemble b unique d apr s l axiome d extensionnalit est appel r union des l ments de a et not J x xea tant donn deux ensembles a b on appelle r union de a et b et on note au b la r union des l ments de l ensemble fa b Pour tout ensemble x on a donc xeaub o xeaouxeb A l aide de l axiome d extensionnalit on voit ais ment que aub bua au buc aub uc Ce dernier ensemble est note au bu c et est appel r union des ensemble a b c On d finit de m me la r union de quatre ensemble a b c d etc Etant donn trois ensemble a b c il existe un ensemble qui a comme l ments a b c et eux seule ment c est a u b U c On le note a b c On d finit de m me l ensemble a b c d etc Etant donn deux ensembles a b on appelle intersection de a et b et on note an b l ensemble xe a x b d fini grace l axiome de compr hension On a donc pour tout ensemble x xeanb
8. b est d termin de fa on unique Remarque On a pens a noncer l axiome suivant tant donn une propri t P x il existe un en semble b dont les l ments sont les ensembles qui ont la propri t P x Mais cela m ne a une contradiction quand on prend comme propri t P x x x autrement dit la 8 CHAPITRE 1 ENSEMBLES RELATIONS FONCTIONS propri t pour un ensemble de ne pas s appartenir lui m me En effet l noncer pr c dent donne alors un ensemble b tel que pour tout ensemble x on ait x b x x En particulier pour x bon obtient be b b bce qui est videmment faux Cette remarque a t faite par B Russell d o son nom le paradoxe de Russell et a impos l axiome de compr hension tel que nous l avons nonc Ensembles et propri t s L ensemble des l ments de l ensemble a qui ont la propri t P x est not xe a P x Il existe un ensemble et un seul qui ma aucun l ment on le note 9 et on l appelle ensemble vide Pour montrer son existence on prend nimporte quel ensemble a et on consid re x a x x cet ensemble n a aucun l ment L unicit est due l axiome d extensionnalite Il n existe aucun ensemble qui ait tous les ensembles comme l ments en effet si a est un tel ensemble on pose b x a x x Alors pour tout ensemble x on a xe b xg x d o une contra diction comme pour le paradoxe de Russell AXIOME 3 AXIOME DE
9. ce m aurait pas t la peine de lui donner un nom Les ensembles d crivent donc un certain domaine que nous nous pro posons d tudier Chapitre 1 Ensembles relations fonctions 1 1 Axiomes de Zermelo Il y a deux relations fondamentales entre les ensembles l galit et l appartenance Nous ne les d finissons pas on consid re que chacun sait ce que veut dire les ensembles a b sont gaux ou identiques ce qu on crit a b bien entendu et l ensemble a appartient l ensemble b ce qu on crit a b on dit aussi a est un l ment de b Toutes les autres relations seront elles d finies partir de ces deux la Par exemple on dira que l ensemble a est une partie ou un sous ensemble de l ensemble b ou encore que a est contenu dans b si chaque l ment de a est aussi l ment de b La notation est ac b Nous allons dans ce qui suit noncer certaines propri t s des ensembles sous forme de r gles comme on ne peut pas d finir les ensembles on se contente de dire ce qu on peut faire et ce qu on ne peut pas faire avec eux Ces r gles constituent donc le mode d emploi de la notion d ensemble On les appelle axiomes de la th orie des ensembles ou axiomes de Zermelo A part le premier tous ces axiomes ont l allure g n rale suivante certains ensembles tant donn s il existe un ensemble ayant telle et telle propri t vis vis des ensemble
10. et nous utiliserons la notation k 1 pour le successeur de l entier k Associativit de l addition k n p k n p ce qu on montre par induction sur p C est vident sip 0 etona k n p k n p k n p D apr s l hypoth se d induction k n p k n p et donc k n p k n pl k n p 2 3 FONCTION SUR LES ENTIERS 17 Commutativit de l addition On montre d abord par induction sur k que0 k k 0 k C est vident si k 0 eton a O k 0 Kt k k 40 On montre ensuite 1 k k 1 c est vident si k 0 et on a 1 k 1 0 k D k k 1 On montre alors par induction sur k que k n n k c est d j fait si k 0 etona n k 1 n 1 k n 1 k n 1 n k kt k k k k 1 n k n l k n l k n k 2 3 2 Le produit de deux entiers Il est aussi d fini par induction Etant donn un entier k on d finit n k par induction sur k par les conditions suivantes n 0 0 n k 1 n k n Distributivit du produit par rapport l addition On montre par induction sur k que n m k n m n Kk C est vident si k 0 etona n m k n m k 1 n m k n nm nk n hypoth se d induction nm nk associativite du produit On montre par induction sur k que n mk nm k C est vident si k 0 et ona nm k nm k nm n mk nm hypoth se d induction n mk m distributivit n mk Commutativit du produit On montre d abord par induction sur k que 0 k k 0 0
11. qui n est d finie que lorsque f est biunivoque Elles sont d finies de la fa on suivante si X A A fi y B il existe x X tel que y f x si Y P B fY x A fe Y f X est appel l image de X par la fonction f et f Y l image r ciproque de Y par la fonction f En particulier f A est appel l image de la fonction f Soient X X c A et Y Y c B on a les propri t s suivantes f xXux ADUA YUY fur Y Tanne PLOT Enr FACE Ah Caf M 1 2 6 Familles d ensembles tant donn un ensemble J une fonction de domaine T valeur dans un ensemble quelconque A est aussi appel e famille d ensembles index e par I On la note alors ai icz I est appel l ensemble d indices de la famille 1 On appelle r union de la famille a er et on la note U ez ai la r union d l ments de l image de la fonction f on utilise ici l axiome de la r union En particulier si I on a f L image de f est donc et donc aussi la r union des l ments de l image de f Donc il n y a qu une seule famille dont l ensemble d indices est vide on l appelle la famille vide Sa r union est Supposons maintenant I Alors il existe un ensemble C dont les l ments sont les ensembles qui appartiennent tous les l ments de l image de f En effet puisque I 4 on prend ig I Un ensemble qui appartient tous les a appartient en particulier a On peu
12. signifient respectivement il existe une injection de E dans F et il existe une bijection de E sur F se comportent comme une relation d ordre c est a dire ESE E lt FetF lt E o E F E lt FetF lt G gt E lt G Il serait maintenant int ressant de montrer qu on peut comparer les puissances de deux ensembles quelconques Autrement dit tant donn deux ensembles E et F ou bien E lt F ou bien F lt E Ce r sultat sera obtenu comme application d un th or me tr s important de th orie des ensembles attribu a Zorn 5 1 Th or me de Zorn THEOREME 5 1 1 ZORN Soit E un ensemble ordonn qui a la propri t suivante tout sous ensemble de E qui est totalement ordonn a un majorant Alors E a un l ment maximal Rappelons que si E est un ensemble ordonn et X une partie de E un majorant de X est un l ment m de E tel que m gt x pour tout x e X Si de plus m g X on dit que m est un majorant strict de X Un l ment maximal de E est un l ment a de E qui n a pas de majorant strict pour aucun x de E onnax gt a Avant de prouver le th or me de Zorn donnons l application indiqu e la comparaison des puis sances de deux ensembles TH OR ME 5 1 2 Quels que soient les ensembles E F il existe ou bien une injection de E dans F ou bien une injection de F dans E Th or me 5 1 2 Soit amp l ensemble des applications f injectives donc le domaine est une partie
13. une injection de E dans A D apr s le lemme 4 2 9 E est quipotent A donc F C Q ED Lemme 4 2 9 Pour chaque x E on d finit par induction y x pour tout ne N 0 pp x p x ert x On d signe par B l ensemble des l ments de E de la forme p x n d crivant N et x d crivant E A on obtient cet ensemble l aide de l axiome de compr hension B y E il existe xe E Aetne N tels que y p x videmment B gt E A puisque p x x De plus p envoie B dans B et comme est une injection de E dans A on voit que la restriction pg de y B est une injection de B dans Bn A En fait tout l ment de Bn A est atteint par pg si u BN A on a u o x xe E A donc n 0 sinon ug A soit n p 1 et u p v v o x donc v B On a ainsi montr que pg est une bijection de B sur BN A 4 2 ENSEMBLES NON DENOMBRABLES 27 Donc B est quipotent a Bn A Il en r sulte que E B UB est quipotent E B u B N A car E B et B sont disjoints ainsi que E B et Bn A Comme E B UB E on aura le r sultat cherch si on montre que E B U BnN A A Or B gt E A donc E B c A et comme Bn Ac A ona E B u BN A Cc A Inversement si x A ou bien x B d o x ANB oubienx Bet xe E B Donc E B U BN ADA C Q ED A titre d application du th or me de Cantor Bernstein notons le th or me suivant THEOREME 4 2 10 L ensemble NN des fonction
14. xeaetxeb On voit imm diatement l aide de l axiome d extensionnalit que anb bna an bnc anb nc Ce dernier ensemble est not an bn c et appel intersection des ensemble a b c On d fini de m me l intersection de quatre ensemble a b c d etc Toujours l aide de l axiome d extensionnalite on voit que au bnc aub n auc et an bUc anb U anc Etant donn un ensemble A et une partie X de A l ensemble x A xg X d fini gr ce l axiome de compr hension est appel compl mentaire de X par rapport A et not C4X ou encore A X On voit ais ment l aide de l axiome d extensionnalit que si X Y c A on a Cx Xu Y C XnC1Y et CaA Xn Y CyxulaY 1 2 QUELQUES NOTIONS L MENTAIRES 9 AXIOME 5 AXIOME DE L ENSEMBLE DES PARTIES Pour tout ensemble a il existe un ensemble b dont les l ments sont les sous ensembles de a Cet ensemble b unique d apr s l axiome d extensionnalit est appel ensemble des parties de a et not A A Nous noncerons plus tard les deux derniers axiomes de la th orie des ensembles l axiome de l infini et l axiome du choix 1 2 Quelques notions l mentaires 1 2 1 Couple ordonn tant donn deux ensembles a b on appelle couple ordonn dont le premier l ment est a et le second b l ensemble a a b On le note a b TH OR ME 1 2 1 Si a b a b alors a a et b b On a en effet a La
15. Af de E et l image une partie Bf de F On met sur amp une relation d ordre en posant fsg Ar C Ag et f est la restriction de ga Af autrement dit f lt g si et seulement si g est un prolongement de f L hypoth se du th or me de Zorn est alors satisfaite en effet soit X une partie de amp totalement ordonn e On pose A Urey Af et on d finit une fonction p de domaine A en posant pour chaque XE A y x f x pour n importe quel f X tel que xe Af 29 30 CHAPITRE 5 LE THEOREME DE ZORN En effet si x Ar Ar avec f f X comme Y est totalement ordonn on a par exemple f lt f donc f x f x y est le prolongement commun de tous les l ments de X donc est un majorant de X Soit fo Ap Bo un l ment maximal de amp il en existe d apr s le th or me de Zorn Si Ap E fo est une injection de E dans F Si Bo F f est une injection de F dans E Supposons alors que Ay E Bo F On prend xy E Ap y F Bo et on d finir go Ag U xo Bo U yo comme le prolongement de f qui donne a xp la valeur y On a alors go et go gt fo ce qui contredit la maximalit de fo C Q ED D monstration du th or me de Zorn Soient E un ensemble ordonn X une partie de E Si l ensemble des majorants de X a un plus petit l ment on l appelle borne sup rieure de X et on le d signe par sup X De m me si l ensemble des minorants de X a un plus grand l ment o
16. E et E sont des ensembles disjoints ainsi que F et F et si E lt F et F lt F alors EU F lt Fu F TH OR ME 4 2 7 Soient E et F deux ensembles tel que E Alors E lt F si et seulement s il existe une surjection de F sur E Si E lt F on a une injection f E F Comme E on prend a E on d finit g F E en posant g y le seul l ment x de E tel que y f x s il existe g y a sinon Alors g est une surjection de F sur E Inversement soit g F E surjective D apr s l axiome du choix il existe une application P E E telle que p X X pour toute partie X non vide de E On d finit alors f E F en po sant f x og xp e xp y F g y x est non vide puisque g est surjective Alors f est une injection de E dans F C Q E D ty TH OR 1E ME 4 2 8 CANTOR BERNSTEIN SiE lt et F lt E alors E est quipotent F ll Ce th or me justifie qu on emploie partir de maintenant la notation E F au lieu de E F Le symbole lt se comporte alors comme une relation d ordre Pour montrer le th or me il suffit de montrer le lemme suivant LEMME 4 2 9 Si ACE et s il existe y E A injective alors A E Th or me 4 2 8 En effet en admettant le lemme consid rons deux ensembles E F tels que E lt F et F lt E On a donc deux injections f E F et g F E Si ACE est l image de g F est quipotent A Or go f est
17. Logique et Th orie Axiomatiques mise a jour le 10 d cembre 2014 J L Krivine Ce document est issu d un polycopi de licence actuelle L3 de l universit Paris 7 crit dans les ann es 1970 par Jean Louis Krivine et distribu sous sa forme originale jusqu a tr s r cemment Il en reprend la premi re partie consacr e la th orie des ensembles avec quelques tr s peu de modifica tions de l auteur Rapha l Giromini en a produit une premi re version au format BIFX en ao t 2004 version compl t e et corrig e par Jean Louis Krivine Yves Legrandg rard et Paul Rozi re N h sitez pas a envoyer les corrections de coquilles ou autres erreurs que vous pourriez rep rer a roziere pps univ paris diderot fr ou l auteurkrivine pps univ paris diderot fr Table des mati res I l ments de Th orie des Ensembles 1 Ensembles relations fonctions LA Sommes US LETRA us coc A a Rk dat a ar mets A Bo 1 2 Quelques nations l mentaires o o bg eu ara ke eg 12 1 Baupleamenne lt a A ea lee sr ss sas 1 2 2 Ensemble prod oes ces ue e dis on eee ane a Me 123 Relations DIRA TES oe ccce cecina aa ie ou nue ir a a 124 PONCIIONAS s enoa 4 a8 oo wat hw de baton wh ee 1 2 5 Applications COMPOSERS oco caci in ee ROA ET eee re ren 12 6 Familles d ensembles oa cucus 388 2820 eus a date es 2 Entiers Naturels 2 1 D hnthiondes enter naturels coo ae ete eur be ee MUR RS 2 2 Relation d ordre
18. N en posant m lt n si et seulement si m c n D apr s le lemme 2 2 4 ona m lt nsietseulement si m e n D apr s le lemme 2 2 6 cette relation d ordre est totale D apr s le lemme 2 2 5 elle a 0 pour plus petit l ment propri t 1 Sim n sont entiersonam lt n lt gt menetm lt n lt emcmn doncm lt n lt menetmc mn c est dire m lt n amp mu m cn et donc m lt n gt mu m lt n Lensemble des majorants stricts de m a donc un plus petit l ment qui est mu m On a ainsi termin la d monstration des propri t s 1 2 3 et 4 C Q F D Dans toute la suite nous ne nous servirons plus explicitement de la d finition de N mais seulement du fait que N satisfait les propri t s 1 2 3 et 4 TH OR ME 2 2 7 Sim neN etm n alors m nm En effet si m 4 n on a par exemple m lt n Donc m lt n par d finition du successeur Comme n lt n on a m lt n ce qui contredit l hypoth se C Q ED THEOREME 2 2 8 Tout ensemble d entier qui est non vide a un plus petit l ment Soit X un sous ensemble de N qui n a pas de plus petit l ment On considere la propri t P n n est un entier et aucun entier m lt n n est l ment de X Comme X n a pas de plus petit l ment en particulier 0 X et donc P 0 De plus P n gt P n pour tout entier n car n n tant pas le plus petit l ment de X si aucun entier inf rieur ou gal n n est l ment de X aucun en
19. Z puisque Zc Q C Q F D D finition Une famille d ensembles an nen index e par N autrement dit une fonction de domaine N est aussi appel e une suite d ensembles Au lieu d crire la suite d ensembles an nen on crit souvent la suite d ensembles do a1 An On a donc trois noms et trois notations diff rents pour la m me notion une fonction de domaine N not e f N E une famille d ensembles index e par N not e an nen une suite d ensembles not e do a Ap Lorsqu on a un ensemble d nombrable E on choisit souvent une bijection f N E qui est donc aussi une suite Go 41 An On dit que cette suite num re E et on crit E 1ap 4 An J 22 CHAPITRE 3 ENSEMBLES FINIS ET DENOMBRABLES Chapitre 4 Comparaison des ensembles infinis 4 1 Axiome du choix A l aide des axiomes de la th orie des ensembles nonc s jusqu ici on ne parvient pas rendre compte correctement des propri t s intuitives des ensembles infinis Par exemple on n arrive pas a prouver que tout ensemble infini contient un sous ensemble d nombrable Nous non ons donc main tenant le dernier axiome de la th orie des ensembles AXIOME 7 AXIOME DU CHOIX Pour toute famille Aj ice d ensembles non vides il existe une fonction f de domaine I telle que f i A pour toutie I Autrement dit le produit d une famille d ensemble non vides est non vide Etant don
20. ar la relation d quivalence R et on le note E R On appelle partition de E un sous ensemble P de 4 E tel que XeP gt X X YePetXZY gt XnY UxepX E Alors E R est une partition de E comme on le voit imm diatement Inversement si P est une partition de E on lui associe une relation d quivalence R sur E d finie par x y Re il existe un l ment X de P tel que x ye X Les relations d quivalence sur l ensemble E correspondent donc canoniquement aux partitions de E 1 2 4 Fonctions Une application de l ensemble A dans l ensemble B ou encore une fonction d finie sur l ensemble A valeurs dans B est par d finition un sous ensemble f de Ax B qui a la propri t suivante pour tout l ment x A il existe un l ment y e B et un seul tel que x y f On crit alors y f x au lieu de x y f On crit f A B pour f est une application de A dans B Il existe un ensemble C dont les l ments sont les applications de dans B En effet si f est une application de A dans B alors f c Ax B donc f A x B On peut donc au moyen de l axiome de compr hension d finir l ensemble C f P Ax B f est une application de A dans B qui est l ensemble cherch L ensemble des applications de A dans B est not B4 Par exemple si A BA 8 est une fonction de domaine et c est la seule Si B et A Z ona B4 il n y a aucune fonction de
21. b a a b et il y a donc deux possibilit s 1 a a et a b a b d o a a et b b 2 a a b et a a b dota b a et a b b donc a a b b C Q F D tant donn trois ensembles a b c on appelle triplet ordonn dont le premier l ment est a le second b et le troisi me c l ensemble a b c On le note a b c TH OR ME 1 2 2 Si a b c a b c alors a a b b etc c En effet on a a b c a b c donc a a et b c b c d apr s le th or me pr c dent D ot b b etc c C Q E D On d finit de m me le quadruplet ordonn a b c d en posant a b c d a b c d Donc si a b c d a b c d alors a a b b c c etd d Et ainsi de suite 1 2 2 Ensemble produit Etant donn deux ensembles A B il existe un ensemble P donc les l ments sont les couples ordonn s x y avecxe Aet ye B En effet si x A y B alors x x y appartiennent A AU B Donc x fx y AU B et donc x x y A P AU B On d finit alors P l aide de l axiome de compr hension en posant P z 2 2 AuB z est un couple x y avec x A y B et il est clair que P est l ensemble cherch Cet ensemble P est appel produit de A et B et not Ax B tant donn trois ensemble A B C l ensemble des triplets x y z avec x A ye BetzeC est
22. domaine A 9 valeur dans 9 Une application f B est dite injective si x x A xix f x f x surjective si pour tout y B il existe x A tel que y f x bijective ou biunivoque de A sur B si elle est la fois injective et surjective Si f est une application biunivoque de A sur B l ensemble des couples y x avec x A ye Bet x y f est alors une application de B sur A qu on note f et qu on appelle application inverse ou r ciproque de f 1 2 5 Applications compos es Soit f A B et g B C D signons par l ensemble des couples x z avec x A z C tels qu il existe y B avec x y f et y z g Il est facile de montrer que est alors une application de A dans C On l appelle application compos e de f et de g et on la note go f Pour tout x e on a donc go f x gfx 1 2 QUELQUES NOTIONS ELEMENTAIRES 11 Soient f A B g B gt C h C D on a alors ho gof hog of En effet ona x t ho go f e il existe ze C tel que x z go f et z h il existe ze Cet y B tels que x y f y g et z h e il existe y B tel que x y f et y t hog x He hog of C Q ED Soit f une application de A dans B on lui associe deux applications f P A P B et f P B A ne pas confondre malgr la notation identique avec l application r ciproque de f
23. emble U NP est d nombrable peN L ensemble P des polyn mes une variable coefficient dans Z est d nombrable si Pz est l en semble des polyn mes de degr lt k P est quipotent Z un polyn me de degr lt k est une suite de k 1 entiers relatifs donc est denombrable L ensemble consid r est P Uken Pr donc est d nom brable L ensemble des nombres alg briques r els nombres r els qui est racine d un polyn me une va riable coefficient dans Z est d nombrable En effet chaque polyn me u P associons l ensemble fini R de ses racines r elles L ensemble tudi est U lt p Ru Comme P est d nombrable c est la r union d une suite d ensemble finis donc un ensemble d nombrable d apr s le th or me pr c dent ce n est videmment pas un ensemble fini 4 2 Ensembles non d nombrables Tous les ensembles infinis rencontr s jusqu ici se sont r v l s d nombrables Les deux th or mes suivants dus Cantor montrent qu il existe des ensembles infinis non d nombrables TH OR ME 4 2 1 P N west pas d nombrable Supposons qu il existe une application surjective f N A N On d finit x e A N en posant X neN ng f n Puisque f est surjective il existe ng N tel que f no X Par d finition de X ona no E X ng f no Autrement dit ny X gt ny Z X ce qui est une contradiction C Q ED THEOREME 4 2 2 Lintervalle 0 1 deR west pas d nombrab
24. ensemble est infini si et seulement s il est quipotent une partie propre On a vu que si E est un ensemble fini et F une partie propre de E F c E FA E alors le cardinal de F est strictement inf rieur celui de E donc E rest pas quipotent F Soit maintenant E un ensemble infini on prend une partie D d nombrable de E D ao 41 dy On d finit f E E en posant fo xsixeE D fa ain pourienN Il est clair que f est une bijection de E sur E ag donc une bijection de E sur une partie propre de E C Q ED THEOREME 4 1 4 La r union d une suite d ensemble d nombrables ou finis est un ensemble d nombrable ou fini Soit An nen une suite d ensemble d nombrables ou finis Il suffit de trouver une application surjective de N sur Unen An Pour chaque n e N soit S l ensemble des applications surjectives de N sur A Par hypoth se Sn pour chaque n N D apr s l axiome du choix il existe une fonction y de domaine N telle que p n SA pour tout n N Autrement dit p n est pour chaque entier n une surjection de N sur Ap On d finit Y Nx N Unen An en posant n p p n p Alors O est surjective car si x yen An ona x Am donc x p m a pour un certain entier q puisque y m est surjective Comme N x N est d nombrable on a le r sultat cherch C Q ED On en d duit imm diatement que l ensemble des suites finies d entiers autrement dit l ens
25. est non vide car E X On v rifie imm diate ment que Xy amp Xo est donc le plus petit l ment de Y c est dire qu il est inclus dans tout l ment de X Si on montre que Xp est une cha ne on aura la contradiction cherch e en effet d apr s les pro pri t s d finissant les l ments de Y on aura alors sup Xo a Xy d o a Xp Or a est un majorant strict de sup Xo donc de Xo et ne peut tre l ment de Xo Soit x Xo x tant comparable tout l ment de Xo alors pour tout y Xo ona y lt x ou y gt u x Soit X y Xo y lt x ou y gt u x On montre que X Y et donc X gt Xp ce qui est le r sultat cherch En effet soit Y c X Y tant une cha ne Si tout l ment de Y est inf rieur ou gal x onasup Y lt x donc sup Y X si l un des l ments de Y est sup rieur ou gal u x on a sup Y gt u x donc sup Y X Soit y X Si y gt u x on a u y gt y gt u x donc u y X Si y lt x on remarque que u y Xo car y Xo donc u y est comparable a x si u y lt xon a y X si u y x on a y lt x lt u y et donc y x ou x u y Donc u y u x ou u y x Dans les deux cas u y X On a ainsi montr que 5 2 APPLICATIONS DU THEOREME DE ZORN 31 si x Xo est comparable tout l ment de Xo il en est de m me de u x Soit alors Z x Xo x est comparable tout l men
26. ha ne qui contient strictement A ce qui est impossible Donc a est maximal C Q F D 5 2 Applications du th or me de Zorn Les th or mes suivants qui sont des applications du th or me de Zorn permettent d valuer la puissance de la r union et du produit de deux ensembles infinis TH OR ME 5 2 1 Soient E Ez deux ensembles quipotents un ensemble infini E Alors E UB E Supposons d abord Ej Ez disjoints On prend des bijections fi E E1 fo E E2 Pour chaque partie X de E on d signera par X resp X2 l image de X par fi resp f2 Soit l ensemble des bijections X X1 U X2 X d crivant Z E Si p y on pose y lt y si y est un prolongement de w L ensemble amp est alors ordonn non vide car E est infini donc il y a une partie d nombrable X alors X et X2 sont d nombrables aussi donc aussi X U X et il existe une bijection de X sur X U X2 L ensemble amp satisfait l hypoth se du th or me de Zorn en effet si X est une partie totalement ordonn e de amp on voit ais ment que les p X ont un prolongement commun qui est un majorant et m me la borne sup rieure de X Soit alors u A U A un l ment maximal de X Comme u est bijective on a A AU A On va montrer que E A est un ensemble fini donc aussi E A1 E2 Aa Il en r sulte d apr s le th or me 4 2 4 que E A E U Ey A U A d o le r sultat cherch Suppo
27. i m c n alors m n 0u men C est vident si n 0 car m c n gt m 0 Supposons que l on ait P n et soit m c nu n si ng m alors m c n et donc hypoth se d induction m n ou me n dans ce cas m nu n Sine mona n c m lemme 2 2 2 et n c m car cela quivaut n m Donc nu n c m et comme par hypoth se on a l inclusion inverse m nu n C Q F D 2 3 FONCTION SUR LES ENTIERS 15 LEMME 2 2 5 Sim est un entier non nul alors 0 m On montre par induction sur m que m 0 ou 0 e m C est vident si m 0 si c est vrai pour m on a n cessairement 0 e m U m car ou bien m 0 et on sait que me mu m ou bien m 40 donc 0 m hypoth se d induction et 0 mu m C Q ED LEMME 2 2 6 Sim n sont entiers alors un et un seul de trois cas suivants est r alis ne m n m0u me mn Montrons d abord l unicit si n m et n m ona me m ce qui est impossible lemme 2 2 3 si ne m etmenonancm lemme 2 2 2 et comme m n ona me m ce qui est impossible On montre alors par induction sur n la propri t P n pour tout entier m men m n ou nem Si n 0 c est vrai d apr s le lemme 2 2 4 Supposons P n et consid rons n U n et un entier quelconque m Par hypoth se on a donc men m nounem Simenoum nalors menufn Sinemonancm lemme 2 2 2 et n c m donc nu n c m Par suite lemme 2 2 4 nu n m ou nu n E m C Q ED On d finit alors une relation d ordre sur
28. l ensemble A x B x C On le note A x B x C et on l appelle produit des ensembles A B C 1 2 3 Relations binaires Une relation binaire R sur un ensemble E est par d finition un sous ensemble de E c est dire un ensemble de couples x y avec x y E Rest dite r flexive si x x R pour tout x R R est dite sym trique si x y R gt yx ER Rest dite antisym trique si x ye Ret y x R D X y 10 CHAPITRE 1 ENSEMBLES RELATIONS FONCTIONS Rest dite transitive si x y R et y z R gt x DER Rest dite totale si x y E gt x y R ou y x R Si R est une relation binaire sur E r flexive antisym trique et transitive on dit que R est une relation d ordre sur E Si de plus R est totale on dit que R est une relation d ordre total sur E Si R est une relation binaire sur E r flexive sym trique et transitive on dit que R est une relation d qui valence sur E Si a E l ensemble x E x a R est appel classe d quivalence de a mod R Notons la classe d quivalence de a Il existe un ensemble E qui a comme l ments les classes d qui valence des l ments de E En effet si a E alors ac E donc e E Donc si on pose F X P E il existe a E tel que X E est d fini gr ce l axiome de compr hension E est l ensemble cherch On l appelle ensemble quotient de E p
29. le 4 2 ENSEMBLES NON DENOMBRABLES 25 Soit f une application surjective de N sur 0 1 Le r el f n poss de une repr sentation d cimale 0 aa DE a et une seule o ak 0 1 9 la suite ak ken n tant pas form e de 9 partir d un certain rang On d finit alors une suite bx ken d entiers 0 lt by lt 9 en posant b 0 si ak A0etb 1 si ak 0 La suite by n est pas form e de 9 partir d un certain rang elle ne contient en fait pas de 9 Le r el 0 b ba by est donc un l ment de 0 1 et comme f est surjective il existe un entier no tel que f No 0 b b2 by Onadonc 1 2 k 0 Any An Ang 0 bib2 be En particulier bj ao ce qui contredit la d finition de bng C Q ED Bien entendu il en r sulte que R lui m me n est pas d nombrable puisque R gt 0 1 Comme on a d montr plus haut que l ensemble des nombres alg briques r els est d nombrable on a ainsi prouv il existe un nombre r el transcendant c est dire non alg brique et m me l ensemble des nombres r els transcendants est non d nombrable car la r union de deux ensembles d nombrables est d nombrable TH OR ME 4 2 3 Si E est infini et F est d nombrable ou fini alors EU F est quipotent E En effet on a un ensemble d nombrable D c E Donc EUF E D u Du F Mais DUF est quipotent D tous deux sont d nombrables donc Eu F E D UE E C Q ED THEOREME 4 2
30. n un ensemble E on appelle fonction de choix sur E une application f dont le domaine est l ensemble des parties non vides de E c est dire Z E a valeur dans E telle que f X X pour toute partie non vide X de E COROLLAIRE 4 1 1 Sur tout ensemble E il existe une fonction de choix En effet il suffit d appliquer l axiome du choix la famille des parties non vide de E c est a dire l appli cation identique dont le domaine est l ensemble des parties non vides de E C Q E D TH OREME 4 1 2 Tout ensemble infini possede un sous ensemble d nombrable Soit E un ensemble infini Il s agit de trouver une application injective p N E soit f P E E une fonction telle que f X X pour toute partie X non vide E il en existe d apr s ce qui pr c de On d fini N Z E par induction D 0 FO P n 1 D nMUIFE D M n 1 est donc une partie de E obtenue en ajoutant n un l ment de E Il en r sulte que D n est fini pour tout n N Comme E rest pas fini E n donc par d finition de f f E D n g n et par suite n 1 n poss de un l ment et un seul On peut alors d finir y N E en posant p0 f g n 1 le seul l ment de D n 1 O n Il est clair que est injective C Q F D Le corollaire suivant donne une caract risation des ensembles infinis 23 24 CHAPITRE 4 COMPARAISON DES ENSEMBLES INFINIS COROLLAIRE 4 1 3 Un
31. n l appelle borne inf rieure de X et on le d signe par inf X Un l ment minimal de X est par d finition un l ment de X qui n a pas de minorant strict dans X Une partie de E qui est totalement ordonn e est appel e une chaine de E Deux l ments x y de E sont dits comparables si on a x lt y ou y lt x Une cha ne de E est donc une partie de E dont les l ments sont deux a deux comparables On montre d abord ce th or me TH OR ME 5 1 3 Soit E un ensemble ordonn ayant les propri t s suivantes toute cha ne de E a une borne sup rieure sixe E a un majorant strict l ensemble des majorants stricts de x a un l ment minimal Alors E a un l ment maximal On raisonne par l absurde en supposant que tout l ment de E a un majorant strict En utilisant l axiome du choix on consid re une fonction f A E E telle que f X X pour toute partie non vide X de E Pour chaque x E soit My l ensemble des majorants stricts minimaux de x Par hypoth se My 4 pour tout x E On d finit application u E E en posant u x f Mx il en r sulte que u x est un majorant strict minimal de x autrement dit x lt u x et si y E est tel que x lt y lt u x on a x y ou y u x Soit X l ensemble de toutes les parties X de E ayant les propri t s suivantes si Yc X est une cha ne alors sup Y X si xE X x EX On d signe par Xo l intersection de tous les X X qui
32. ns A La fonction f est surjective En effet soit x le plus petit l ment de A non atteint par f s il en existe l ensemble x A x lt xo a un plus grand l ment x f n il est atteint par f Mais x est le plus petit l ment de A qui est strictement sup rieur a f n donc xy f n 1 C Q ED THEOREME 3 3 2 S il existe une injection de A dans N ou bien une surjection deN dans A alors A est fini ou d nombrable Si f est une injection de A dans N l image de f est un sous ensemble de N qui est quipotent A Donc A est fini ou d nombrable d apr s le th or me pr c dent Soit g une surjection de N sur A On d finit une injection h A N en posant h x le premier entier n tel que g n x C Q ED THEOREME 3 3 3 N x N est d nombrable Comme N x N n est pas fini il suffit d apr s le th or me pr c dent de trouver une injection f Nx N N On peut poser par exemple f x y 2 3 unicit de la d composition d un nombre en facteurs premiers C Q ED COROLLAIRE 3 3 4 Le produit de deux ensembles d nombrables est d nombrable 3 3 ENSEMBLES DENOMBRABLES 21 COROLLAIRE 3 3 5 NP est d nombrable pour tout entier p gt 1 D monstration par induction sur p COROLLAIRE 3 3 6 Z et Q sont des ensembles d nombrables On d finit une surjection f N Q en posant f x y z y siz 0 avece l si x est paire 1sinon f x y 0 0 z Donc Q est d nombrable ainsi que
33. ocie l ensemble x u x c est dire l ensemble dont les l ments sont x et les l ments de x En effet on a par exemple 12 0 1 2 11 et 13 0 1 2 11 12 donc 13 12U 12 Dans la suite de ce chapitre on utilisera la notation x pour d signer l ensemble x u x On se propose de d finir l ensemble des entiers Cet ensemble A doit avoir les propri t s suivantes DEA sixe Aalorsx e A On ne peut pas d duire des axiomes d j nonc s l existence d un ensemble A ayant les propri t s On nonce donc un nouvel axiome AXIOME 6 AXIOME DE L INFINI Il existe un ensemble A tel que A et si x A alors xu x A On montre alors le th or me suivant TH OR ME 2 1 1 Il existe un ensemble et un seul qui a les propri t s et qui est contenu dans tout ensemble A qui a les propri t s On consid re un ensemble A qui a les propri t s il en existe un d apr s l axiome de l infini Soit B l intersection de tous les sous ensembles de A qui ont les propri t s x Il est imm diat que B a encore les propri t s Soit C un ensemble quelconque ayant les propri t s alors Cn A a encore cette propri t et c est un sous ensemble de A donc B c CN A par d finition de B Par suite B c C ce qui montre que B est l ensemble cherch Si B a la propri t et est inclus dans tout ensemble ayant la propri t alors B lt B et B c B donc B B
34. p Sig ye amp on pose y lt y si y est un prolongement de L ensemble amp est alors ordonn non vide car amp tant infini il a une partie denombrable X alors X1 X sont d nombrables aussi donc aussi X x X2 et il existe une bijection de X sur X x X2 L ensemble amp satisfait l hypoth se du th or me de Zorn en effet si X est une partie totalement ordonn e de on voit ais ment que les p X ont un prolongement commun qui est un majorant de E Soit alors u A x Az un l ment maximal de Y Comme y est bijective on a A A x A2 On va montrer que E A lt A Il en r sultera que E E A U A A th or me pr c dent Donc A A Ap E E E Comme A A x Ap on aura bien montr que E E x Supposons alors que E A gt A Il en r sulte qu il existe B c E A B A On a alors B c E Aj B2 c E2 A donc sion pose C AUB ona C1 x C2 A1 x A2 U A1 x Bo U A2 x By U By x Ba Les ensembles A Aj Az Aj X Aa By B2 sont quipotents Donc ils sont aussi quipotents A x Bo As x By By x Bo D apr s le th or me pr c dent ils sont aussi quipotents A x B2 U A2 x By U B x B2 Soit alors v une bijection de B sur ce dernier ensemble La fonction u de domaine C qui est gale u sur A et v sur B est donc une bijection de C sur C x Ca Donc p amp et u est un majorant strict de u ce qui est une contradiction C Q F D COROLLAIRE 5 2 4
35. pour tout n N On montre d abord que PIN est quipotent Z N soient A B deux ensembles d nombrables disjoints Il est clair que A N est quipotent A A P B A AU B car AUB est aussi d nom brable Or se donner une partie de AU B revient se donner une partie de A et une partie de B donc P A x P B P AU B Il en r sulte que P N ZN Il en r sulte que R est quipotent R On montre alors imm diatement par induction sur n que R R pour tout nE N C Q ED 26 CHAPITRE 4 COMPARAISON DES ENSEMBLES INFINIS D finition On dit qu un ensemble a la puissance du continu s il est quipotent a R Les ensembles infinis rencontr s jusqu ici se rangent en deux classes ceux qui sont d nombrables ceux qui ont la puissance du continu Nous allons voir qu il existe des ensembles infinis qui ne se rangent dans aucune de ces classes Pour pouvoir comparer entre eux les divers ensembles infinis on introduit la d finition suivante D finition On dit que le cardinal ou la puissance de l ensemble E est inf rieur ou gal celui de F s il existe une injection de E dans F On crit alors E lt F On a imm diatement les propri t s suivantes SiE lt FetF lt G alors E lt G Si E F alors E lt F et F lt E La r ciproque est vraie mais non vidente et sera d montr e un peu plus loin th or me 4 2 8 de Cantor Bernstein Si E lt F et F lt F alors E x F lt F x F Si
36. r tout entier n si n y Mo et n z Mo alors y z On raisonne par l absurde et on consi dere le premier entier m tel qu il existe y z E y A z m y Mo m z Mo Si m 0 on a par exemple y a soit M l ensemble obtenu en tant 0 y de Mo Mj Mj 1 0 y Alors M a les deux propri t s ci dessus et est strictement inclus dans Mo ce qui contre dit la d finition de Mo On a donc m 0 et par suite m pt D apr s la d finition de m il existe un l ment et un seul de E tel que p t Mo alors p H p t Mo et on a par exemple y H p t On pose M Mo m y Mo p y Alors M a les deux propri t s ci dessus car 0 a My et 0 a 4 m y donc 0 a M Si n u Mj alors n H n u Mo et n H n u A m y c est vident si n 4 metsin m alors n p donc u t et y H p t Donc n H n u Mp Comme M est strictement inclus dans M on a encore contredit la d finition de Mo Mo est donc le graphe d une application f de N dans E et on a bien f 0 a f n H n f n pour chaque entier n C Q ED Quand on utilise ce th or me pour d finir une fonction f on dit que f est d finie par induction sur les entiers 2 3 1 Laddition des entiers Elle est d finie par induction tant donn un entier k on d fini k n par induction sur n par les conditions k 0 k ktnt k n D apr s cette d finition on a k 1 k
37. s d finies sur les entiers valeur enti res a la puissance du continu Si chaque partie de N on associe sa fonction caract ristique on obtient une injection de A N dans NN D autre part une fonction f N N est un ensemble de couples d entiers donc NY c N Comme PIN est quipotent a A N puisque N est d nombrable on en d duit une injection de NN dans PN D apr s le th or me de Cantor Bernstein NN est quipotent A N C Q ED On dira que l ensemble E a une puissance strictement inf rieure celle de F ce qu on crit E lt F si E lt F et E 4 F Autrement dit s il existe une injection de E dans F mais pas d injection de F dans E Par exemple R a une puissance strictement sup rieure a celle de N Le th or me suivant montre que pour tout ensemble il en existe un de puissance strictement sup rieure THEOREME 4 2 11 CANTOR _ Pour tout ensemble E P E gt E L application x x de E dans A E est injective Donc E lt Z E Si f est une bijection de E sur Z E on d finit X A E en posant X xe E xg f x Alors il existe Xo E tel que f xo X Par d finition de X on a xo X xo f xo soit xo X xp g X ce qui est une contradiction C Q F D 28 CHAPITRE 4 COMPARAISON DES ENSEMBLES INFINIS Chapitre 5 Le th or me de Zorn Gr ce au th or me de Cantor Bernstein on a montr que les notations E lt F et E F qui rappelons le
38. s donn s Traditionnellement ils portent les noms sui vants axiome d extensionnalit axiome de compr hension ou s paration axiome de la paire axiome de la r union axiome de l ensemble des parties axiome de l infini axiome du choix Ils expriment des propri t s plus ou moins videntes de la notion d ensemble ce qui fait qu a pre mi re vue on ne voit pas au moins pour plusieurs d entre eux l int r t qu il y a les noncer L int r t existe n anmoins pour la raison suivante les axiomes de Zermelo expriment de fa on exhaustive les propri t s des ensembles Ce qui fait que chaque fois que l on aura un doute sur la validit de la construction de tel ou tel ensemble c est aux axiomes qu il faudra se r f rer pour voir s ils permettent de faire cette construction Or en math matiques en toute rigueur il faudrait avoir un doute chaque pas en avant qu on se propose de faire AXIOME 1 AXIOME D EXTENSIONNALITE Pour que l ensemble a soit gal l ensemble b il faut et il suffit que tout l ment de a soit l ment de b et inversement Autrement dit a b o acbetbc a AXIOME 2 AXIOME DE S PARATION OU DE COMPR HENSION Etant donn un ensemble a et une propri t P x portant sur un ensemble variable x il existe un en semble b dont les l ments sont ceux parmi les l ments de a qui ont la propri t P x Notons que d apr s l axiome d extensionnalit un tel ensemble
39. sons que E A soit infini et soit D une partie d nombrable de E A On pose B AUD on a B A UD B2 Aa U D2 Comme D D et Dz sont d nombrables il existe une bijection v D gt Di U D2 La fonction y B B U Bo gale u sur A et v sur D est bijective donc u et y est un majorant strict de u ce qui est une contradiction Le cas o E et E ne sont pas disjoints est cons quence du corollaire suivant C Q E D 32 CHAPITRE 5 LE THEOREME DE ZORN COROLLAIRE 5 2 2 a Soient E En des ensembles tels que E gt E gt EL gt E3 1 gt En E tant infini Alors ty E UEzU UE E On le montre d abord lorsque n 2 On choisit un ensemble E quipotent E et disjoint de Ej D apr s le th or me pr c dent Ey U E est quipotent a Ej Comme E lt E E il existe une surjection de ES sur Ez donc une surjection de E U ES sur E U E2 Donc F UE lt EL U E E Comme E lt E U E gt de fa on vidente on a bien E UE E On montre alors ais ment le r sultat par induction sur n C Q F D TH OR ME 5 2 3 Soient E un ensemble infini E Ex deux ensembles quipotents E Alors E E x Es On choisit deux bijections fi E Ej fo E E2 pour chaque partieX de E on d signera par X resp X gt l image de X par fi resp f2 Soit amp l ensemble des bijections X X x Xa X d crit l ensemble des parties de am
40. sur les entiers 23 Ponchon BUT ESCOCIA eee on ee 2 3 1 Ladditiondes entiers es so o eo 44 vue de ou ou vase due ni i e du 232 eproudit dede 5 420 ee edo etes h aD a 2 33 EXPOREOCIADON 00 er BAW SOE dd REE ESS 3 Ensembles finis et d nombrables 31 Ensembles finis ese saar terre 2 Tau ee ae en EN UPN ia te le a 3 3 Ensembles d nombrables 4 Comparaison des ensembles infinis LL Adome AI das Ae ew ee AEE Se ale es 4 2 Ensembles non denombrables 5 Le th or me de Zorn ek TR re 8 rare Dee Matte re Due a ew time 52 Applications du th or me de ZG eaa secreet aaa basses a us 13 13 14 15 16 17 18 19 19 20 20 23 23 24 TABLE DES MATIERES Premi re partie El ments de Th orie des Ensembles En math matique toutes les notions ou presque sont d finies a partir de la notion d en semble On ne peut donc pas esp rer d finir ce qu est un ensemble N anmoins on voudrait pouvoir utiliser les ensembles et faire des d monstrations avec eux sans avoir de doute sur la rigueur Pour cela on va se baser sur l id e intuitive que chacun poss de plus ou moins sur les ensembles en la pr cisant quelque peu On peut admettre sans difficult que certaines choses m ritent d tre appel es ensemble et certaines non si la notion d ensemble recouvrait nimporte quoi
41. t de Xp On a donc x Z u x Z D autre part soit Y une cha ne incluse dans Z et u Xp Tout l ment de Y est comparable a u Si y lt u pour tout y Y on a sup Y lt u Si l un des ye Y v rifie y gt u on a sup Y gt u Dans les deux cas sup Y est comparable u Comme u est un l ment quelconque de Xy on a sup Y Z Finalement on a montr que Z Y donc Z gt Xo Cela prouve que tous les l ments de Xy sont comparables autrement dit que Xy est une cha ne C Q ED THEOREME 5 1 4 HAUSDORFF Soit C un ensemble ordonn Alors l ensemble des cha nes de C ordonn par inclusion a un l ment maximal Soit E l ensemble des cha nes de C Il suffit de prouver que E satisfait aux hypoth ses du th or me pr c dent Soit X c E une cha ne de E donc si A B X A et B sont des cha nes de CetonaAcCBouBcA il est alors imm diat de voir que U xe x A est une cha ne de C qui est la borne sup rieure de X Soit A E A ayant un majorant strict B On a donc Ac B AZ B A B tant des cha nes de C On choisit a B A alors AU a est un majorant strict minimal de A C Q ED On peut alors montrer le th or me de Zorn th or me 5 1 1 Soit E un ensemble ordonn dont toute cha ne est major e Soit A lt E une cha ne maximale de E obtenue l aide du th or me pr c dent a un majorant a E Si a n est pas maximal on prend be E b gt a Alors bg A et AU b est une c
42. t donc d finir C en posant C x aj x appartient tous les l m nts de l image de f on utilise ici l axiome de compr hension Cet ensemble C est appel intersection de la famille a i iez et not N a Notons que cette intersec el tion n est d finie que pour une famille non vide tant donn une famille d ensemble a jer il existe un ensemble C dont les l ments sont les fonctions q de domaine telle que i e a pour tout i I En effet une telle fonction p est une application de J dans J a donc un l ments de a On peut iel el donc poser en utilisant l axiome de compr hension C pe U ai p i e aj pour tout i I ie Cet ensemble est appel produit de la famille a er et not I Qj ie 12 CHAPITRE 1 ENSEMBLES RELATIONS FONCTIONS Chapitre 2 Entiers Naturels 2 1 D finition des entiers naturels On commence par d finir chacun des entiers naturels 0 1 2 L id e de la d finition est la sui vante l entier 5 par exemple doit tre un ensemble qui a cing l ments Si on a d j d fini 0 1 2 3 4 il est alors naturel de poser 5 0 1 2 3 4 On d finit donc successivement 0 9 1 0 2 0 1 3 0 1 2 Onadonc 1 G 2 198 181 3 H 1 OH Lop ration qui permet de passer d un entier au suivant est une op ration tr s simple sur les en sembles celle qui l ensemble x ass
43. tier inf rieur ou gal n ne peut tre l ment de X D apr s le principe d induction P n est donc vrai pour tout entier n mais cela implique que X est vide On en d duit le r sultat par contrapos e C Q ED 2 3 Fonction sur les entiers On consid re un ensemble quelconque E 8 un l ment a de E et une application H N x E gt E 16 CHAPITRE 2 ENTIERS NATURELS THEOREME 2 3 1 Il existe une application f de N dans E et une seule telle que f 0 a et f n H n f n pour tout entier n Unicite Consid rons deux fonctions f g ayant cette propri t Si f 4 g l ensemble n N f n 4 g n est non vide donc a un plus petit l ment m m 0 car f 0 g 0 a Donc m a un pr d cesseur p on a f p g p donc H p f p H p g p soit f p g p c est dire f m g m ce qui contredit la definition de m Existence On considere les sous ensembles M de N x E qui ont les propri t s suivantes 0 a e M si n y M alors n H n y M Il est clair que l intersection Mp de tous ces ensembles M de N x E a encore ces propri t s C est donc le plus petit sous ensemble de N x E qui a ces propri t s On va en d duire que c est le graphe d une application de N dans E Pour tout entier n il existe y E tel que n y Mo C est vrai pour n 0 puisque 0 a Mo si c est vrai pour n c est vrai pour n d apr s la deuxi me propri t satisfaite par Mo Pou
44. toutes les d monstrations sur N Montrons maintenant la propri t 3 Soient B neN il existe m N tel que m n et A Bu 0 Alors 0 A six A on a videment x B donc x A Donc A a les propri t s et par suite Nc A cela veut dire que tout entier non nul a un pr d cesseur LEMME 2 2 1 SineNetme n alors meN tous les l ments d un entier sont des entiers On le montre par induction sur n La propri t est vraie si n 0 n n a pas d l ment Supposons la vraie pour n Si m e n comme n nu n on a ou bien me n donc m est entier hypoth se d induc tion ou bien m n et m est encore entier C Q ED LEMME 2 2 2 Sin est entier etsi m n alorsmcn Par induction sur n C est vident si n 0 On suppose que c est vraie pour n et soit m nu n Alors ou bien me n donc mc n hypoth se d induction donc mc nu n ou bien m n donc mc nu n C Q F D LEMME 2 2 3 Sin est entier ng n C est vident si n 0 n ma pas d l ment Supposons que ng n et que nu n nu n On a alors ou bien nu n n ou bien nu n n Dans le premier cas on a n n car n NU n ce qui contredit l hypoth se Dans le second on a nu n c n lemme 2 2 2 Or n nu n donc n n contrairement l hypoth se C Q E D LEMME 2 2 4 Sim n sont entiers et mc n alors m n ou bien me n On le montre par induction sur n la propri t P n est alors pour tout entier m s
Download Pdf Manuals
Related Search