[PDF] [PDF] Introduction à la Théorie des En- sembles et nombres cardinaux

[PDF] Ensembles dénombrables

Ensembles dénombrables A 1 Cardinal Lorsque l'on veut dénombrer les éléments d'un ensemble fini (par exemple, si on veut savoir combien de pommes  

[PDF] DENOMBRABILITE

14 mai 2005 · Proposition 4 Soit E un ensemble dénombrable infini Voici un théor`eme qui va aider `a prouver que deux ensembles sont équipotents

[PDF] Introduction à la Théorie des En- sembles et nombres cardinaux

3 3 Ensembles dénombrables pas prouver l'existence d'un ensemble infini à l' aide des autres axiomes, qui à partir d'ensembles finis ne peuvent prouver 

[PDF] Ensembles Finis, infinis, dénombrables

Nous allons démontrer que E est un ensemble infini à l'aide d'un raisonnement par l'absurde Supposons donc E fini D'après la proposition précédente F est fini  

[PDF] MAT-22257 : Exercices COURS 6 Réponses et\ou - ULaval

d) Soit (Ai)i∈N, une famille d'ensembles infinis dénombrables, peut donc considérer un programme comme un mot écrit à l'aide d'un certain alphabet

[PDF] Dénombrabilité, mot et langage - Systèmes Formels Master 1 - LISIC

Que peut-on calculer `a l'aide d'un algorithme ? Savoir montrer qu'un ensemble est non dénombrable Un alphabet Σ est un ensemble dénombrable

[PDF] Université Paris-Dauphine DUMI2E Année 2015-2016 - Ceremade

5 Ensembles finis, ensembles dénombrables 35 démontre qu'elle est vraie, `a l'aide des axiomes, des théor`emes déj`a démontrés, et des r`egles de

[PDF] Peut-on compter les nombres - Zeste de Savoir

12 août 2019 · Cardinaux et ensembles dénombrables j'aurais dû décrire l'ensemble des entiers naturels à l'aide d'une propriété caractéristique Je ne l'ai 

[PDF] Chapitre 1 Ensembles et sous-ensembles

L'objet de ce chapitre est de vous donner quelques éléments pour vous aider Définition 6 10 – Un ensemble E est dénombrable s'il existe une surjec-

[PDF] Introduction 1 Les infinis dénombrables 2 La théorie - Normale Sup

on en déduit que si (An)n∈N est une famille d'ensembles dénombrables alors J n∈N An est dénombrable `A l'aide de ces théor`emes, on prouve de 

[PDF] les ensembles mathématiques

[PDF] les ensembles mathématiques exercices corrigés

[PDF] les ensembles mathématiques pdf

[PDF] les ensembles n z q r

[PDF] les ensembles n z q r pdf

[PDF] les ensembles n z q r tronc commun

[PDF] Les entiers - Mathématiques

[PDF] Les entiers relatifs

[PDF] les entreprise qui pratique le e-commerce au maroc

[PDF] les entreprises (économie)

[PDF] les entreprises en ont elles fini avec le financement externe indirect

[PDF] les envois postaux

[PDF] Les enzymes

[PDF] Les enzymes et leurs propriétés

[PDF] les eoliennes

Introduction à la Théorie des En-

sembles et nombres cardinaux.

Antoine Blanchon

Printemps 2009

Travail effectué dans le cadre optionnel des TIPE de l"université Lyon 1 et sous la direction de M.Altinel de l"Institut Camille Jordan. ii

Table des matières

Introduction v

1 Les fondements 1

1.1 Langage de la Théorie des ensembles et notion de propriétés . . .

1

1.2 Les Axiomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3 Notions et définitions préliminaires . . . . . . . . . . . . . . . . .

5

2 Nombres Naturels 9

2.1 Introduction aux nombres naturels . . . . . . . . . . . . . . . . .

9

2.2 Propriétés des nombres naturels . . . . . . . . . . . . . . . . . . .

11

2.3 Le théorème de récursion . . . . . . . . . . . . . . . . . . . . . .

13

3 Premières classifications des ensembles 15

3.1 Cardinalité des ensembles . . . . . . . . . . . . . . . . . . . . . .

15

3.2 Ensembles finis . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.3 Ensembles dénombrables . . . . . . . . . . . . . . . . . . . . . . .

19

3.4 Ensembles indénombrables . . . . . . . . . . . . . . . . . . . . . .

21

3.5 Définitions alternatives à la finitude, Dedekind infini . . . . . . .

22

4 Nombres Ordinaux 27

4.1 Ensembles bien-ordonnés . . . . . . . . . . . . . . . . . . . . . . .

27

4.2 Nombres ordinaux . . . . . . . . . . . . . . . . . . . . . . . . . .

28

4.3 Induction et récursion transfinie . . . . . . . . . . . . . . . . . . .

31

4.4 Arithmétique des ordinaux . . . . . . . . . . . . . . . . . . . . .

32

5 Nombres Cardinaux 35

5.1 Alephs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

5.2 Arithmétique des cardinaux . . . . . . . . . . . . . . . . . . . . .

38

Bibliographie et remerciements 41

iii ivTABLE DES MATIÈRES

Introduction

Lycéen je me posais déjà certains problèmes sur la densité des infinis, notam- ment le suivant : Soit un segmentSdans l"espace et l"imageIde sa projection sur un plan. Imaginons tout d"abord que le segment soit posé sur le plan. À chacun des points du segmentScorrespond un unique point du plan. On lève maintenant une extrémité du segment, l"autre restant confondue avec le plan. La projection deSsur le plan fait toujours correspondre à chacun des points de Sun unique point deIsur le plan. Or ce segment imageIest plus court queS! Et ceci reste vrai quelle que soit l"inclinaison deS(tant qu"il n"est pas perpen- diculaire au plan car alors la projection se fait sur un point unique), alors que la longueur du segmentIdevient minuscule pour une très forte inclinaison... Ce raisonnement montre qu"il y a le même nombre de points dans deux segments de tailles arbitraires, pour autant que cela ait un sens! Pourtant cela peut pa- raître un peu contradictoire car on a envie de dire qu"il y a plus de points sur le segment le plus grand! Cette contradiction provient du fait que l"on veut traiter le nombre de points des segments comme nous avons l"habitude de la faire avec des quantités finies alors que le nombre de points sur le segment est infini... Mais qu"est ce que l"infini? Avant la seconde moitié du 19èmesiècle et les travaux du mathématicien allemand Georg Ferdinand Ludwig Philipp Cantor, l"infini n"était pas considéré comme une quantité à proprement parler. L"approche de Cantor est révolution- naire dans le sens où après avoir montré qu"il n"existe pas un mais une infinité d"infinis, il va manier ces grandeurs comme des quantités achevées. Sa théorie eut à se confronter à de nombreux détracteurs, dont quelques grands noms de son temps, avant d"être finalement unanimement acceptée. En effet, il s"avère qu"en formalisant de façon précise le cadre de la théorie de Cantor qui met au premier plan la notion d"ensemble, certains mathématiciens vont développer ce que l"on appelle la théorie des ensembles et qui permit de poser les bases de toutes les mathématiques modernes et apporte ainsi une avancée significative à la crise des fondements mathématiques au coeur de tous les débats de l"époque. Parce que ce domaine des mathématiques me paraissait tout aussi intéressant que fondamental, le choix de faire un TIPE

1sur ce sujet à fini par s"imposer de

lui-même. Ce mémoire présente un exposé complet sur la définition des nombres car- dinaux, qui sont en quelque sorte une prolongation de ce que nous connaissons déjà avec les nombres finis, et décrit leur arithmétique.. Cette construction né- cessite bien sur beaucoup de pré-requis, et ce mémoire est donc aussi l"occasion1

Travaux d"Initiative Personnelle Encadrés

v viINTRODUCTION de présenter une synthèse des connaissances que j"ai acquises durant l"étude de mon sujet de TIPE, la théorie des ensembles. Le travail a été effectué en s"appuyant en grande partie sur la lecture active de l"excellent livre de Karel Hrbacek et Thomas Jech "Introduction to Set Theory, Third Edition, Revised and Expanded". Pour cette raison, ce mémoire propose un développement assez similaire à celui-ci et les démonstrations en sont de même souvent inspirées. La plupart des résultats seront démontrés, sauf quelques uns dont la preuve, parfois fastidieuse, n"apporte pas grand intérêt, et pour des raisons de longueur de ce document. Seuls les théorèmes de récursion, finis et tranfinies seront à proprement parler admis.

Chapitre 1

Les fondements

Nul ne doit nous exclure du Paradis que Cantor a créé.

David Hilbert

1.1 Langage de la Théorie des ensembles et no-

tion de propriétés Tout le monde sait intuitivement ce qu"est un ensemble, un regroupement d"objets que nous pensons comme un tout. Pour quelles raison collectionnons nous ces objets ensemble? Nous pouvons distinguer deux raisons à cela : car nous pouvons voir en ces objet une propriété commune (par exemple considérons l"en- semble des êtres vivant sur Terre), ou bien simplement car nous parvenons à regrouper ces objets dans notre esprit sans que ceux-ci n"aient à priori quelque chose en commun(prenons par exemple l"ensemble constitué de la chèvre de mon- sieur Seguin et de la première particule à être entrée en collision dans le LHC du CERN). Cette réflexion, loin d"être inutile nous permet de mieux appréhender ce qu"est un ensemble ce qui est primordial pour construire proprement notre théorie. Premièrement, notons que notre axiomatique devra rendre compte des deux façons qu"a notre esprit de construire un ensemble. Secondement, les en- sembles sur lesquels nous travaillerons devront être parfaitement définis, et nous devons donc donner un moyen de savoir de façon univoque si tel ou tel objet est ou n"est pas dans l"ensemble. On se rend donc compte de la nécessité de clarifier la notion de propriété; en effet, l"exemple donné concernant l"ensemble des êtres vivant sur Terre pourrait être interprété de différentes façons par une personne ou une autre en fonction de sa définition du vivant. On constate que le problème provient de ce que la notion de "vivant" est quelque peu subjective. Nous allons donc pour éviter ce genre de problèmes se fixer un langage formel, exempt de toute ambiguïté, pour décrire les propriétés. Une formule fait référence à des objets d"une théorie, et s"écrit avec une suite de symboles qui appartiennent tous à ce qu"on appelle le langage de la théorie. Autrement dit un langage est une collection de symboles qui permettent d"écrire des formules pour parler des objets de la théorie. Un langage contient toujours les symboles logiques et des symboles de variables pour désigner les objet de la théorie; on distingue en plus les symboles relationnels, fonctionnels, et de constantes. On appelle langage relationnel un langage qui ne contient que des 1

2CHAPITRE 1. LES FONDEMENTS

symboles relationnels. Dans notre cas, le langage de la théorie des ensembles se réduit au sym- bole?d"appartenance, et bien sur au symbole=d"égalité toujours présent, aux symboles logiques, et aux symboles de variables. Il ne comporte aucun symbole fonctionnel, ni de constante, mais seulement les symboles relationnels d"égalité et d"appartenance. On est donc dans le cadre particulier d"une structure rela- tionnelle. Le symbole d"appartenance réfère à une relation binaire, c"est à dire à une relation entre deux objets, qui permet de dire que la première variable est un élément de la deuxième. Remarquons que tous les objets de notre univers sont des ensembles, ainsi les éléments d"un ensemble sont d"autres ensembles! Pour tout ensembleaetb, on aa?boub?a.a?bse lit "aappartient àb", ou "aest un élément deb", ou encore "bcontienta". Ce langage nous permet d"écrire de nombreuses formules, reste maintenant à nous limiter dans leurs constructions pour que celles ci aient un sens (ce qui est bien sur différent de dire qu"elles décriront quelque chose de vrai!). Ici nous nous permettrons uniquement d"écrire des formules du premier ordre, ce que nous définissons maintenant : Définition 1(Formule du premier ordre dans un langage relationnel).La dé- finition est récursive. Premièrement on définit une formule atomique : Si Rest un symbole de relation n-aire, alorsR(x1,x2,...,xn)est une for- mule atomique.

T outeformule atomique est de c etteforme.

Secondement, on donne les règles de construction suivante : Si ΦetΨsont des formules du premier ordre,Φ?Ψet¬Φsont également des formules du premier ordre. (Suffisant pour justifier des autres compo- sitions car par exempleΦ?Ψ =¬(¬Φ? ¬Ψ)etΦ?Ψ =¬(Φ? ¬Ψ)...). Si Φ(x1,x2,...,xn)est une formule du premier ordre, alors?x1,Φ(x1,x2,...,xn) est aussi une formule du premier ordre. Troisièmement, on énonce que réciproquement toute formule du premier ordre s"obtient de la façon décrite précédemment. Notons donc qu"une formule du premier ordre ne quantifie donc que les variables. Nous nous permettrons uniquement d"écrire des formules du premier ordre pour exprimer une proposition ou une propriété. Mais heureusement, même en se donnant cette condition et un langage aussi restreint que le notre nous pourrons décrire tous les objets mathématiques dont nous pourrions avoir besoin et chaque formule ainsi construite avec un ensemble limité d"éléments dont l"agencement ne peut avoir qu"un unique sens, permet d"exprimer toute idée sans ambiguïté. Revenons maintenant munis de ce formalisme sur la notion de propriété. Définition 2.Une variable est dite libre dans une formule si elle n"est pas quantifiée. Dans le cas contraire elle est dite liée. Un énoncé qui ne comporte aucune variable libre est un énoncé, soit vrai soit faux, que l"on appelleproposition. Définition 3.Une propriété pour les variablesx1,x2,...,xnest une formule du premier ordre qui comportex1,x2,...,xncomme variables libres.

1.2. LES AXIOMES3

1.2 Les Axiomes

Nous donnons comme telle la liste des axiomes classiques de la théorie des ensembles. Nous donnons pour chaque axiome son expression dans la langue na- turelle puis dans notre langage formel. Remarquons dès à présent que l"unicité des ensembles construits dans cette section est garantie par l"axiome d"exten- sionnalité, et les notations introduites ont donc bien un sens. Axiome d"existenceIl existe un ensemble qui ne contient pas d"élément. ?X,?x,x /?X Cet axiome prouve que notre univers n"est pas vide, il existe au moins un ensemble : l"ensemble vide, noté∅. Axiome d"extensionnalitéSi tout élément d"un premier ensemble appar- tient à un deuxième et inversement alors ces deux ensembles sont égaux. ?X,?Y,[(x?X?x?Y)?(y?Y?y?X)]?(X=Y) Cet axiome donne la condition d"égalité entre deux ensembles, on constate que seuls les éléments d"un ensemble le caractérisent au final, et non la façon dont il a été construit. Schéma d"Axiomes de compréhensionSoitP(x)une propriété de x. Pour tout ensembleA, il existe un ensembleBtel quex?Bsi et seulement six?A etP(x). ?A,?B,(x?B)?(x?A?P(x)) C"est un schéma d"axiomes, c"est à dire qu"il y a en fait un axiome pour chaque propriétéP. Notation 1.{x?A|P(x)}est l"ensemble des éléments deAqui possède la propriétéP. Axiome de la pairePour chaque ensembleAetB, il existe un ensemble qui contient comme unique élémentAetB. ?A,?B,?C,x?C?(x=A?x=B) Notation 2.{A,B}est l"ensemble qui contient A et B comme unique éléments. Cet axiome nous permet de commencer à construire des ensembles contenant de plus en plus d"éléments, on procède comme suit : D"après l"axiome de la paire il existe un ensembleE={∅,∅}, qui est égal à l"ensemble qui ne contient que l"ensemble vide par l"axiome d"extentionnalité, on note doncE={∅}. Et donc toujours d"après l"axiome de la paire,{E,∅}={{∅},∅}est bien un ensemble...

4CHAPITRE 1. LES FONDEMENTS

Axiome de l"unionPour tout ensembleZ, il existe un ensembleXtel que xappartient àXsi et seulement si il existeY?Ztel que quex?Y. ?Z,?X,x?X?(?Y?Z,x?Y) Notation 3.L"union du système d"ensembleZest noté?Z. Introduisont maintenant une définition pratique que nous utiliserons constam- ment par la suite. Définition 4.On dit queXest un sous ensemble deY, ou queXest une partie deYsi tous les éléments deXsont aussi des éléments deY. On dit queXest un sous ensemble strict (ou une partie stricte, ou un sous ensemble propre) de YsiXest un sous ensemble deY, et queYpossède des éléments queXne possède pas. Notation 4.On note respectivementX?YouX?YsiXest un sous ensemble ou un sous ensemble strict deY.

On remarque queX?Ysi et seulement siX?YetX?=Y.

Axiome de l"ensemble des partiesPour tout ensembleA, il existe un ensemble qui contient comme éléments toutes les parties deA. ?A,?B,(X?B)?(X?A) Notation 5.On appelle ensemble des parties deAet on noteP(A)l"ensemble construit de cette façon.

Axiome de l"infiniIl existe un ensemble inductif.

Nous verrons dans le chapitre 2 ce qu"est un ensemble inductif. Schéma d"Axiome de remplacementSoitP(x,y)une propriété telle que pour chaquex, il existe un uniqueypour lequelP(x,y)est vérifiée. Pour tout ensembleA, il existe alors un ensembleBtel que pour chaquex?A, il existe y?Bpour lequelP(x,y)est vérifiée. ?A,?B,(y?B)?(x?A?P(x,y)) C"est aussi un schéma d"axiomes. Il justifie que la collection des objets qui

sont liés un à un par une propriété à des éléments d"un ensemble, est également

un ensemble. Axiome du choixIl existe une fonction de choix pour chaque système d"en- sembles. ParZF, on fait référence au système de ces axiomes sans l"axiome de choix, du nom des mathématiciens Zermelo et Fraenkel, premiers à proposer une vé- ritable axiomatisation de la théorie des ensembles, etZFCavec l"axiome de choix. L"axiome du choix est ainsi distingué des autres dans le sens où il pos- tule de l"existence d"un ensemble d"une façon totalement non constructive par

1.3. NOTIONS ET DÉFINITIONS PRÉLIMINAIRES5

rapport aux autres axiomes. Ces implications apportent une certaine cohérence pratique à la théorie comme nous aurons l"occasion de le mentionner, mais aussi quelques résultats contre-intuitifs. Pour ces raisons il rencontra et rencontre d"ailleurs toujours des opposants à son utilisation. On peut rajouter à cette liste certains autres axiomes supplémentaires qui ne sont généralement pas admis comme étant part du systèmeZFC, sauf peut être l"axiome de fondation qui stipule que tout ensemble non vide contient un élément qui ne possède aucun élément en commun avec lui. Cet axiome permet d"éliminer de notre univers les ensembles qui sont éléments d"eux même ce qui permet d"éviter certains paradoxes. Soulignons le fait que l"existence d"un ensemble ne peut être justifiée que par les axiomes donnés précédemment. Certains regroupements d"ensembles ne sont pas des ensembles au sens d"objets de notre univers! C"est par exemple le cas de "l"ensemble de tous les ensembles" : Démonstration.SoitVl"ensemble de tous les ensembles. Alors le Schéma de Compréhension permet d"affirmer queA={x?V|x /?x}est un ensemble, donc il appartient àV. On constate alors que siA?AalorsA /?A, et siA /?A, alorsA?A; contradiction dans les deux cas. Or la seule hypothèse (tacite) que

nous avions faite est queVest un ensemble.Les objets de notre théorie sont donc en fait regroupés dans ce qu"on appelle

une classe. Notons que l"axiome de la paire permet de justifier de l"existence d"ensembles même si les éléments n"ont à priori aucune propriété commune selon la remarque faite en introduction du chapitre. Nous ne préciserons pas quand nous aurons recours à un axiome par la suite car cela est constamment le cas! Néanmoins les trois derniers axiomes ne seront pas utilisés tout de suite et nous préciserons donc à quel moment nous en ferons un premier usage. Pour ce qui concerne l"axiome de choix, nous mentionnerons au fil de ce mémoire les implications qu"il pourrait avoir, mais nous effectuerons tout notre travail indépendamment de celui ci ne l"utiliserons donc à aucun moment.

1.3 Notions et définitions préliminaires

Opérations sur les ensembles

Nous sommes maintenant en mesure d"introduire quelques opérations élé- mentaires sur les ensembles. L"axiome de compréhension permet de définir l"intersection de deux en- sembles : Définition 5.On appelle intersection deAetB, et on noteA∩Bl"ensemble {x?A|x?B}des éléments qui appartiennent à la fois àAet àB. L"axiome de la paire et de l"union permettent de définir l"union de deux ensembles : Définition 6.On appelle union deAetB, et on noteA?Bl"ensemble des

éléments qui appartiennent àAou àB.

6CHAPITRE 1. LES FONDEMENTS

L"axiome de compréhension nous permet également de définir la différence de deux ensembles : Définition 7.On noteA-Bl"ensemble des éléments deAqui n"appartiennent pas àB.

Relations

Un ensemble à deux éléments est une paire non-ordonnée (d"après l"axiome d"extensionnalité{A,B}={B,A}). Pour définir une relation, notion fonda- mentale en mathématiques, dans le cadre de notre théorie il va falloir introduire la notion de couple,iede paire ordonnée. Définition 8.On définit le couple d"élémentsaetbpar(a,b) ={a,{b}}. Définition 9.Un ensembleRest une relation siRest un ensemble de couples. Si(x,y)?R, on écritxRy, et on dit quexetysont en relation relativement à R. Cette définition très simple permet néanmoins de définir tout ce que nous savons sur les relations, fonctions, applications et leurs propriétés en imposant des conditions surR. Nous ne détaillerons pas tout cela ici car ces constructions ne font pas parties des objectifs du mémoire et ne nous serviront pour la plupart pas pour la suite même si nous utiliserons bien sur constamment la notion de relation et de fonction. Néanmoins redonnons ici la définition d"une relation d"ordre et d"ordre strict, puis la définition générale de ce qu"est un isomorphisme car ces notions vont être fondamentales pour la suite. Définition 10.Une relation d"ordreRsur un ensembleEest une relation qui possède les propriétés suivantes :

R éflexivité: Si x?E, alors(x,x)?R.

T ransitivité: Si (x,y)?Ret(y,z)?R, alors(x,z)?R.

A ntisymétrie: Si (x,y)?Ret(y,x)?R, alorsx=y.

Définition 11.Une relation d"ordre stricteR?sur un ensembleEest une relation qui possède les propriétés suivantes : T ransitivité: Si (x,y)?R?et(y,z)?R?, alors(x,z)?R?. A symétrie: (x,y)?R?et(y,x)?R?ne peuvent pas être simultanément vraies. Un ensemble muni d"une relation d"ordre est dit ensemble ordonné. Définition 12.Soit un ensembleAmuni d"une famille de relationRi, et un ensembleBmuni d"une famille de relationSioùi?Eun ensemble quelconque. Supposons de plus que siRiest une relation n-aire surAalors la relationSi surBest également une relation n-aire. Alors on dit qu"une bijectionfdeAdansBest un isomorphisme entreA etBsifpréserve la structure de ces ensembles,ie: ?i?E, Ri(x1,x2,...,xn)si et seulement siSi(f(x1),f(x2),...,f(xn))

1.3. NOTIONS ET DÉFINITIONS PRÉLIMINAIRES7

Par exemple si8CHAPITRE 1. LES FONDEMENTS

Chapitre 2

Nombres Naturels

Dieu fit le nombre entier, le reste est l"oeuvre de l"Homme...

Léopold Kronecker

2.1 Introduction aux nombres naturels

Qu"est ce qu"un nombre naturel? Nous ne prétendons pas bien sur répondre à cette question philosophique, mais pour développer notre théorie nous allons devoir en donner une définition ensembliste. On voudrait par exemple que le nombre naturel2soit défini par un ensemble comportant "2" éléments confor- mément à notre intuition. Or si on peut facilement dire si un ensemble possède un, deux ou trois éléments, nous pouvons donner beaucoup d"exemples de tels ensembles. Nous allons voir qu"il existe une façon naturelle de faire un choix. La construction suivante est dûe à John von Neumann, un mathématicien et physicien américain d"origine hongroise. Pour définir0nous nous tournons naturellement vers le seul ensemble qui ne possède aucun élément, et on pose donc

0 =∅

Les ensembles contenant un seul élément sont les ensembles de la forme{x} oùxest un ensemble (les singletons). Comment choisir un représentant? Le seul objet de notre théorie que nous avons défini pour l"instant étant l"ensemble

0 =∅il semble naturel de poser

1 ={∅}

Et dès lors que nous avons deux objets particuliers différents de défini (0et

1), il semble encore une fois naturel de poser

2 ={0,1}={∅,{∅}}

Nous allons continuer de cette façon ce qui nous donne

3 ={0,1,2}={∅,{∅},{∅,{∅}}}

4 ={0,1,2,3}={∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}}

9

10CHAPITRE 2. NOMBRES NATURELS

L"idée est intéressante mais pas encore totalement satisfaisante. car nous pouvons avec cette méthode définir des nombres naturels aussi grands que nous le voulons, mais pas le concept de nombre naturel lui-même. En effet, nous ne pouvons pas définir un nombre naturel comme étant l"ensemble des nombres naturels plus petits car une telle définition fait appel au concept qu"elle essaie justement de définir! Pour contourner cet obstacle nous allons en fait d"abord définir l"ensemble des entiers naturels, et donc en suite simplement dire que les nombres naturels sont les éléments de cet ensemble. Pour cela remarquons que chacun des nombres naturels que nous avons construit est égal à l"union de son prédécesseur et du singleton qui contient son prédécesseur, par exemple2 = 1?{1}. On pose alors les définitions suivantes. Définition 13.On appelle successeur dexet on noteS(x)l"ensemblex?{x}. Sinest un entier naturel,S(n)est l"entier qui le succède immédiatement, on utilise alors la notation suggestiven+ 1pour désignerS(n). Notons bien qu"il ne s"agit pour l"instant que d"une notation, même si nous verrons qu"elle est compatible avec l"opération d"addition des nombres naturels qui sera définie

à la fin du chapitre.

Définition 14.Un ensembleIest dit inductif si il possède les deux propriétés suivantes : -0?I.

Si n?I, alors(n+ 1)?I.

Nous sommes proches de notre but maintenant que nous avons défini les en- sembles inductifs. En effet nous savons que tout ensemble inductif doit contenir l"ensemble des nombres naturels. En fait l"ensemble des nombres naturels tel que nous voulons le construire est précisement le plus petit, au sens de l"inclusion, des ensembles inductifs, c"est à dire celui qui ne contient pas d"autre ensemble que0et ceux construit par l"opération successeur. On pose donc la définition suivante : Définition 15.On appelle ensemble des nombres naturels l"ensemble

N={n|n?I,pour tout ensemble inductifI}

Les éléments deNsont appelésnombres naturels. Ainsi un ensemble est un nombre naturel si et seulement si il appartient à tout ensemble inductif. Remarquons que nous devons justifier l"existence de cet ensemble. Cela est facile avec le schéma d"axiome de compréhension. Démonstration.Si on noteP(n)la propriété den: "n?I, pour tout ensemble inductifI." et si E est un ensemble inductif quelconque alors on a :

N={n?E|P(n)}

2.2. PROPRIÉTÉS DES NOMBRES NATURELS11

Il reste néanmoins une question primordiale! Existe-il un ensemble inductif? Sans l"axiome de l"infini la réponse serait non dans le sens où on ne pourrait pas prouver l"existence d"un ensemble infini à l"aide des autres axiomes, qui à partir d"ensembles finis ne peuvent prouver que l"existence d"autres ensembles finis (voir chapitre suivant pour plus de détails sur ce point). Nous utilisons donc ici cet axiome comme une sorte de porte d"entrée pour l"infini, ce qui est la motivation première de la théorie des ensembles.

2.2 Propriétés des nombres naturels

Le théorème d"inductionLe théorème d"induction est une conséquence im- médiate de notre construction des nombres naturels, il en est donc l"outil fon- damental pour leur étude. Théorème 2.1(Théorème d"Induction).SoitP(x)une propriété dexqui peut éventuellement dépendre d"autres paramètres. (1)P(0)est vraie. Si : (2) Pour tout entier natureln,P(n)?P(n+ 1). alorsPest vraie pour tous les entiers naturels. Démonstration.Soit l"ensembleA={n?N|P(n)}.Aest un ensemble inductif d"après les deux hypothèses. DoncN?A. Et comme par constructionA?N ces deux ensembles sont égaux, c"est à dire quePest vraie pour toutn?N.L"ordre dansN On remarque en observant la façon dont nous les avons construits que chaque entier naturel appartient à ceux qui lui sont plus grands, et aussi qu"un entier naturel contient tout ceux qui lui sont plus petits. En fait les entiers naturel sont ordonnés par l"appartenance. Définition 16.La relation d"ordre usuelle dansNest définie par :m?nsi et seulement sim?n. Montrons d"abord ce petit lemme qui sera utile par la suite et qui fournit un bon exemple de démonstration à l"aide du principe d"induction. Démonstration.La preuve se fait avec l"aide du principe d"induction et en consi- conditions d"application du théorème ce qui prouvera la véracité de la proposi- tion pour tout nombre naturel.

chaque cas0?n? {n}=n+ 1, donc0?n+ 1. AinsiP(n)?P(n+ 1).Nous allons maintenant démontrer le résultat important de cette partie qui

montre que l"ordre que nous avons défini dansNpossède bien les propriétés que nous pouvons attendre de lui. Théorème 2.2.(N,?)est un ensemble totalement ordonné.

12CHAPITRE 2. NOMBRES NATURELS

Démonstration.Preuve de la transitivité : Soitm,n,ptrois entiers naturels tels quem?netn?p. Nous devons montrer quem?p. Nous allons raisonner par induction sur p. Soit[?m,n?N,(m?n?n?x)?(m?x)]une propriété dexque nous nommeronsP(x). P(0): affirme que?m,n?N,m?netn?0implique quem?0. Or d"après le lemme 2.1 il n"existe pas d"entier naturelntel quen?0donc l"affirmation est trivialement vraie. P(p)?P(p+ 1): Nous devons montrer quem?netn?p+ 1implique m?p+ 1. Orn?p+ 1signifie par définition quen?p+ 1 =p? {p}donc quen?pou quen=p. Sin?p, ien?palorsP(p)qui est notre hypothèse d"induction nous permet de dire quem?p, et donc quem?p? {p}=p+ 1. Sin=p, alors commem?n,m?pet doncm?p+ 1. Dans les deux cas on a bienm?p+ 1. DoncP(p)est vraie quel que soitp?N, ce qui est précisement l"énoncé de la transitivité. Preuve de l"asymétrie : Nous devons montrer que pour toutm,n?N,m?n etn?mne peuvent pas être vraies conjointement. Si c"était le cas, d"après la transitivité de?on auraitm?m. Il nous faut maintenant montrer que celaquotesdbs_dbs46.pdfusesText_46