Main La théorie des ensembles. Introduction à une théorie de l'infini et des grands cardinaux

La théorie des ensembles. Introduction à une théorie de l'infini et des grands cardinaux

0 / 0
How much do you like this book?
What’s the quality of the file?
Download the book for quality assessment
What’s the quality of the downloaded files?
Year:
2017
Publisher:
Calvage & Mounet
Language:
french
Pages:
668
ISBN 13:
9782916352404
File:
DJVU, 18.95 MB
Download (djvu, 18.95 MB)

You may be interested in Powered by Rec2Me

 

Most frequently terms

 
0 comments
 

To post a review, please sign in or sign up
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
1

Il fondamento teologico del diritto

Year:
2012
Language:
italian
File:
EPUB, 656 KB
0 / 0
2

Jacques Ellul, l'uomo che aveva previsto (quasi) tutto

Year:
2008
Language:
italian
File:
PDF, 6.00 MB
0 / 0
PATRICK DEHORNOY est professeur à l'université de Caen et membre senior de l'Institut Universitaire de France. Ses travaux portent sur la théorie des ensembles, l'algèbre, et la topologie de basse dimension. Il est l'auteur d'une centaine d'articles de recherche et de sept livres. patrick.dehornoy@unicaen.fr https://dehornoy.users.lmno.cnrs.fr/ Mathematics Subject Classification (2010) - Primary : 03 - Exx Set theory 03E10 Ordinal and cardinal numbers 03E25 Axiom of choice and related propositions 03E30 Axiomatics of classical set theory and its fragments 03E35 Consistency and independence results 03E45 Inner models, including constructibility, ordinal definability, and core models 03E55 Large cardinals 03E60 Determinacy principles 03B05 Classical propositionallogic 03B 10 Classical first-order logic 03C07 Basic properties of first-order languages and structures 03D20 Recursive functions and relations, subrecursive hierarchies 03F40 Godel numberings and issues of incompleteness @ Imprimé sur papier permanent @) Calvage & Mounet, Paris, 2017 ISBN 978-2-91-635240-4 11111111 111111 9 782916 352404

à Arlette, une pr'lncesse



Avant- propos



Une théorie magnifique, mais objet de bien des malentendus La théorie des ensembles est l'exploration, à l'aide des outils des mathé- matiques, de la notion d'infini. L'idée de l'infini, partagée par la plupart des humains bien que non évidemment inscrite dans l'univers physique qui nous entoure, est objet de fascination. Développée depuis un siècle et demi, la théorie des ensembles a permis de découvrir de nombreux aspects de l'in- fini, en particulier l'existence d'une multitude d'infinis différents les uns des autres mais entretenant entre eux des liens subtils. C'est une magnifique théorie, qui fait appel à des ressources variées et à des méthodes extrê- mement sophistiquées, une théorie dont les mots eux-mêmes font rêver : hypothèse du continu, argument diagonal, paradoxe de Russell, théorème de non-définissabilité de la vérité, méthode du forcing, ultrapuissanc; es ité- rées, cardinaux inaccessibles, cardinaux géants, cardinaux indescriptibles, réel Oij, modèle L ultime, ... Pour autant, cette théorie est méconnue

t objet de plusieurs malentendus. Le premier, et le plus grave, trouve son origine dans les succès mêmes de l'entreprise. Lors de la crise des fondements qui a secoué les mathématiques au début du xx e siècle, il est apparu que la théorie des ensembles, une fois installée sur une base axiomatique ferme, pouvait également, et même si ce n'était pas sa vocation première, servir de base fondationnelle pour la totalité de l'édifice mathématique: (presque) tout objet mathématique peut être représenté par un ensemble. De ce fait, on a un temps imaginé de faire jouer à la théorie des ensembles le rôle d'une sorte de théorie universelle englobant toutes les autres et à l'intérieur de laquelle toutes les mathématiques, et même peut-être l'enseignement des mathématiques, devraient être pensés. Cette conception réductrice a fait long feu, mais elle a durablement brouillé l'image de la théorie des ensembles: une fois dissipée la fascination pour un formalisme obscur et constatée l'évidence que la théorie des ensembles restait impuissante dans la plupart des domaines, cette vision biaisée a détourné l'attention de ce qui est et reste la vocation première de la théorie, à savoir explorer l'infini. Le second malentendu, lui aussi né des réussites de la théorie des ensembles, est la croyance que celle-ci s'est achevée en 1963, lorsque Paul Cohen a éta- bli que l'hypothèse du continu n'est pas prouvable à partir des axiomes du système de Zermelo-Fraenkel. Certains mathématiciens ont pensé, à tort, que ce résultat magnifique marque la fin de la théorie, et que les questions laissées ouvertes le resteront à jamais, dans un mystérieux statut ni vrai-ni



- vu -



VUl



Avant-propos



faux indiquant peut-être qu'il s'agit de problèmes vides de sens. La théorie des ensembles serait ainsi comme une étoile un temps brillante mais désor- mais éteinte. Quelle erreur! Ce qu'a vérifié Paul Cohen est que le système de Zermelo-Fraenkel est incomplet, contribuant ainsi non pas à fermer, mais à ouvrir la théorie, mise en demeure de compléter une axiomatisa- tion que personne n'avait jamais prétendue exhaustive. Un demi-siècle plus tard, les problèmes ne sont pas tous réglés, mais il est indéniable que l'on en sait beaucoup plus qu'aux temps de Cohen, et a fortiori de Zermelo et Fraenkel.



Les objectifs de ce texte Ce texte est une introduction à la théorie des ensembles d'aujourd'hui. Son but est d'expliquer les bases de cette théorie - tout au moins ce que l'au- teur du texte en a compris! Il n'est évidemment pas question d'offrir un tableau complet: les deux mille pages du Handbook [34] n'y suffisent pas, qui pourtant sont probablement inaccessibles à la plupart des débutants. En pratique, notre ambition sera d'arriver à la compréhension des trois ré- sultats que l'on peut estimer être les plus marquants de la théorie au xx e siècle : . la consistance de l'axiome du choix et de l'hypothèse du continu par rapport au système de Zermelo-Fraenkel, établie par K. Godel en 1938, . la consistance de la négation de l'hypothèse du continu par rapport au système de Zermelo-Fraenkel, établie par P. Cohen en 1963, . l'analyse exhaustive des ensembles de cardinalité dénombrable telle qu'elle résulte des théorèmes sur la détermination projective, établis par D. A. Martin, J. Steel, et H. Woodin en 1985 et 1987. Pour cela, on essaiera de prendre le lecteur par la main depuis le début, pour le mener aux résultats ci-dessus et à un point d'où, ensuite, il pourra facilement continuer dans les textes pour spécialistes. On aimerait combler ici le fossé séparant, d'une part, les nombreux textes existants exclusive- ment élémentaires et destinés aux non-spécialistes, qui souvent reflètent une vision datée et depuis longtemps dépassée, et, d'autre part, des ouvrages spécialisés d'un abord plus difficile comme [58] ou [59]. Chemin faisant, on aura à découvrir bien des outils et des méthodes : théo- rèmes de complétude et d'incomplétude, modèles intérieurs, forcing et ex- tensions génériques, axiomes de grands cardinaux, propriété de détermina- tion... À chaque fois, on essaiera de ne pas rester à un niveau exclusivement technique et de mettre en perspective les résultats avec les objectifs de la théorie, en s'interrogeant sur leur signification et leur portée. La théorie des ensembles est souvent remise en question aujourd'hui en tant que théorie fondationnelle, et c'est une question intéressante à discuter à la lueur de ré- sultats précis. Sans prétendre à une quelconque compétence en philosophie, on a néanmoins inclus quelques remarques naïves dans cette direction. Notre espoir est que des publics variés puissent trouver leur pitance à tra-



Avant-propos



IX



vers le copieux menu qui est proposé. Le lecteur découvrira vite qu'il existe plusieurs niveaux de lecture possibles, suggérés par la typographie : les (abondants) textes en petits caractères sont soit des démonstrations, soit des commentaires, discussions, compléments, non nécessaires à la lecture du texte principal, mais supposés l'éclairer. On espère que la diversité des formats facilitera la navigation.



Organisation du texte Le texte comporte trois parties distinctes tant par leur contenu que par leur style. Dans la partie A (chapitres l à V), on expose la théorie élé- mentaire des ensembles sans supposer aucun prérequis, en particulier de logique. L'objectif est de présenter une approche aussi peu dogmatique que possible de la théorie, en s'efforçant au fur et à mesure de justifier les op- tions adoptées et en évoquant à l'occasion certaines des pistes alternatives non retenues. Comme dans toutes les mathématiques, quelques bribes de logique apparaissent ici ou là, mais uniquement comme une sténographie. Les arguments de cette partie résolument «pré-logique» sont donc princi- palement combinatoires. Malgré ces limitations, on verra que des résultats hautement non triviaux peuvent être établis au prix d'arguments délicats, comme à la fin du chapitre V. Le but de la partie B (chapitres VI à IX) est de fournir, là encore sans supposer de connaissance préalable, les bases de logique mathématique né- cessaires pour le développement ultérieur d'une théorie des ensembles plus avancée. Il s'agit donc d'un cours de logique pour débutants, partant d'une introduction à la logique propositionnelle et aux logiques du premier ordre et cheminant pour donner un accès aussi rapide que possible aux résultats de logique indispensables pour la partie C, à savoir principalement le théo- rème de complétude des logiques du premier ordre et les théorèmes d'in- complétude de Gode!. Des démonstrations complètes sont données, mais l'aperçu présent ne peut prétendre constituer un cours complet de logique mathématique, en particulier parce que le traitement de la théorie des mo- dèles et de la théorie de la démonstration y est indigent. Dans la partie C (chapitres X à XVI), disposant désormais des résultats fon- damentaux de la logique mathématique et d'un cadre précis pour la théorie descriptive, on revient à la théorie des ensembles pour en poursuivre l' éla- boration dans un cadre conceptuel centré sur la notion de modèle de ZFC. Cette partie correspond à ce qui est souvent appelé la théorie axiomatique des ensembles, par opposition à la théorie élémentaire de la partie A. De la même façon que l'on peut étudier des modèles abstraits de l'arithmétique qui ne sont pas nécessairement le modèle standard constitué des vrais en- tiers et de leurs vraies opérations, on peut considérer des modèles abstraits de la théorie des ensembles qui ne sont pas nécessairement constitués des vrais ensembles et de la vraie appartenance. En permettant de considérer simultanément plusieurs modèles et de développer des opérations adaptées,



x



Avant-propos



cette approche, dite sémantique, a révolutionné la théorie, et elle en est le cœur depuis des décennies. On trouvera ici une présentation de notions devenues classiques comme les ensembles constructibles et la méthode du forcing, mais aussi et surtout un aperçu de développements plus récents autour de la hiérarchie des grands cardinaux et des propriétés de détermi- nation, ainsi que quelques ouvertures vers des points de recherche en cours. Globalement, le texte est orienté vers la découverte de nouveaux axiomes susceptibles de compléter le système ZFC, lequel, à l'évidence, n'épuise pas l'intuition de la notion d'infini telle qu'elle se dégage des résultats accu- mulés depuis un siècle et demi. L'idée importante qui, on l'espère, devrait émerger, est que la théorie des ensembles ne se limite pas à des résultats négatifs de non-prouvabilité et d'indépendance, mais qu'elle est principale- ment une théorie structurelle visant à élaborer une conception positive de l'infini mathématique. On espère qu'au-delà des détails techniques, parfois délicats, le lecteur pourra s'imprégner de la philosophie générale de cette démarche et ressentir l'harmonie de la conception qui s'en dégage. Comme on l'a déjà dit, notre objectif ici n'est pas d'offrir un exposé exhaustif ni même toujours des démonstrations complètes, mais plutôt de mettre l'ac- cent sur les notions et les idées fondamentales, de façon à permettre ensuite au lecteur d'accéder, s'il le souhaite, à des textes spécialisés. Les chapitres 1 à VIII sont suivis de quelques exercices. Par ailleurs, on trouvera à la fin de chaque chapitre quelques repères chronologiques : il doit être clair que ceci ne prétend pas fournir une vision complète d'un su- jet par ailleurs très riche, mais simplement de donner quelques dates pour fixer les idées. Sur les aspects historiques du développement de la théorie des ensembles, on pourra consulter [32, 44, 52] pour les origines et, spécia- lement, [60] pour la période plus récente. Pour les aspects philosophiques, on pourra consulter [92]. Le texte a été revu bien des fois, mais il n'est guère douteux que des co- quilles, voire des erreurs, sont encore présentes. Les lecteurs sont invités à les signaler à patrick. dehornoy@unicaen. fr. Une liste des corrections sera tenue à jour à l'adresse "https://dehornoy.users.lmno.cnrs.fr/ens_erratum.html".



Les chapitres La partie A regroupe cinq chapitres. Le chapitre 1 dessine un cadre axio- matique adapté à l'exploration des ensembles. Partant de l'existence de plusieurs infinis distincts, on est rapidement confronté à des problèmes non évidents, comme le problème du continu de Cantor, et ce sont eux qui rendent nécessaire l'élaboration d'une théorie des ensembles et la motivent. Comme il semble difficile de définir les ensembles de façon satisfaisante, on recourt à une approche axiomatique qui, au terme de plusieurs ajustements, aboutit au système de Zermelo, qui est la base axiomatique sur laquelle on propose de développer une théorie -donc d'explorer l'infini.



Avant-propos



Xl



Le chapitre II contient une introduction aux ordinaux, qui sont un prolon- gement transfini de la suite des entiers naturels, et qui jouent le rôle d'une véritable épine dorsale du monde des ensembles. Après quelques résultats généraux sur les bons ordres, on présente la construction des ordinaux de von Neumann, qui fait de ceux-ci des ensembles transitifs particuliers. Cette approche permet d'établir rapidement les propriétés de base des ordinaux, en particulier de développer leur arithmétique. Comme applications, on établit le théorème de Cantor-Bendixson sur la décomposition des fermés de :IR et le théorème de Goodstein sur la convergence des suites éponymes. Dans le chapitre III, utilisant en particulier les ordinaux finis comme contre- parties des nombres entiers, on montre comment la plupart des objets ma- thématiques usuels peuvent être représentés par des ensembles dits purs, puis on vérifie que, pourvu qu'il soit amendé d'axiomes d'infini et de rempla- cement qui en font le système standard ZF de Zermelo-Fraenkel, le système axiomatique obtenu permet de légitimer tous les résultats de représenta- tion par des ensembles purs, ainsi que toutes les propriétés usuelles des ordinaux, dont les définitions récursives. Il apparaît donc raisonnable à ce point de poursuivre le développement sur la base du système ZF. Le chapitre IV est consacré à l'axiome du choix AC. On y établit l'équiva- lence de AC avec ses variantes classiques, théorème de Zermelo et lemme de Zorn, et on introduit deux formes faibles, l'axiome des choix dépendants et l'axiome du choix dénombrable. Ensuite, on passe en revue quelques ap- plications de AC dans des domaines variés, allant de l'algèbre (existence de bases dans les espaces vectoriels, d'idéaux maximaux dans les anneaux) à l'analyse (existence d'ultrafiltres, théorème de Tikhonov) et à la géomé- trie (théorème de Hahn-Banach, décompositions paradoxales de Banach- Tarski). Enfin, anticipant sur les résulats d'indépendance démontrés dans la partie C, on discute brièvement du statut de AC pour conclure qu'il est cohérent avec le point de vue adopté d'inclure celui-ci dans le système de base, qui devient donc ZFC. Dernier de la partie A, le chapitre V regroupe quelques résultats élémen- taires sur les cardinalités (infinies) qui constituent le cœur de la théorie. On y définit la notion de cardinal, avec l'énumération des cardinaux infi- nis par les Na de Cantor et le développement d'une arithmétique cardinale où l'exponentiation pose des problèmes ardus. Comme outil structurant et permettant de mettre un peu de clarté, on introduit la cofinalité, avec les notions dérivées de cardinal successeur et de cardinal limite, et on conclut avec le théorème de Fodor, petit aperçu de combinatoire sur Wl et une de ses applications, le théorème de Silver sur la continuité de l'hypothèse du continu en cofinalité Wl, bon exemple d'un résultat purement élémentaire et néanmoins de démonstration délicate. Viennent ensuite les quatre chapitres de la partie B. Le chapitre VI est consacré au calcul propositionnel, ou booléen. Il n'est pas strictement in- dispensable à la suite, mais il offre l'avantage de présenter sur un exemple simple les notions de cohérence et de complétude pour un système de



Xll



Avant-propos



preuve. Ayant introduit les principales notions dans le cadre d'une logique formelle générale, on les illustre dans celui la logique booléenne, en éta- blissant notamment le théorème de complétude qui montre que l'unique règle de coupure adossée à quelques schémas de preuve simples épuise les possibilités du raisonnement booléen. Le chapitre VII est consacré aux logiques du premier ordre. Après un pas- sage en revue de la syntaxe (inévitablement rébarbatif, comme il se doit...), on passe rapidement à la notion de preuve, avec le théorème de complétude, ici soigneusement démontré et qui ouvre la voie à la notion de modèle d'une théorie, fondement du développement de la théorie des ensembles contem- poraine, et à la méthode sémantique de preuve qui en dérive. En vue des développements du chapitre VIII, il est utile d'appliquer ce qui précède aux modèles de l'arithmétique de Peano faible. Ensuite, le chapitre VIII est consacré aux célèbres résultats de limitation établis dans les années 1930, qui tracent un cadre indépassable pour le pouvoir déductif des systèmes axiomatiques. Le point-clé est un certain ré- sultat technique, dit lemme diagonal. Une fois celui-ci établi, il est rapide de déduire à la fois le théorème d'indécidabilité de Church, le théorème de non-définissabilité de la vérité de Tarski, et les deux théorèmes d'incom- plétude de Godel, le second ici pour les systèmes au moins aussi forts que le système de Zermelo (ce qui est suffisant pour la théorie des ensembles). Mais, pour arriver au lemme diagonal, plusieurs résultats préliminaires sont nécessaires, et on commence par expliquer tout cela: bases sur les fonctions récursives, existence d'une arithmétisation récursive de la prouvabilité en logique du premier ordre, absoluité des formules d'arithmétique de com- plexité El vis-à-vis des modèles de l'arithmétique de Robinson. Le chapitre IX contient des bases de théorie descriptive des ensembles, qui est l'étude spécifique des sous-ensembles de la droite réelle IR, à la fron- tière de la topologie et de la théorie des ensembles. Cette étude, nécessaire en vue du chapitre XV, n'est pas directement partie de la logique, mais ses méthodes et son esprit sont directement réminiscents de ceux du cha- pitre VIII, et il est donc naturel qu'elle soit placée là. Outre les définitions des hiérarchies borélienne, projective, arithmétique, et analytique, on y établit l'universalité de l'espace de Baire parmi les espaces polonais, et la représentatibilité des ensembles :E

comme projections des branches d'un arbre sur w x W1. Enfin viennent les sept chapitres de la partie C. Le chapitre X est introduc- tif et rassemble des résultats élémentaires sur les modèles de Z F, avec en particulier les notions de modèle intérieur et d'absoluité d'une formule pour une famille de structures. Les résultats sont rudimentaires mais permettent de se familiariser avec la notion de modèle de ZF. Comme application facile, on établit l'indépendance de la plupart des axiomes du système ZF les uns par rapport aux autres. Le chapitre XI décrit le modèles des ensembles constructibles qui, à l'in-



Avant-propos



XllI



térieur de tout modèle de référence, est un modèle intérieur minimal, que l'on peut imaginer comme analogue au sous-corps premier d'un corps. On montre en particulier comment l'existence de ce modèle et l'étude de ses propriétés permettent d'établir la consistance relative de l'axiome du choix et de l'hypothèse généralisée du continu, ainsi que celle de la négation de 1 'hypothèse de Souslin. Le chapitre XII est consacré à la méthode du forcing, qui permet, à partir d'un modèle convenable, d'en construire une extension, c'est-à-dire un nou- veau modèle dont le modèle initial est modèle intérieur. On peut cette fois penser à une extension algébrique de corps. On décrit ici le mécanisme des extensions par forcing, et on développe quelques exemples classiques, per- mettant notamment d'établir la consistance de la négation de l'axiome du choix et de l'hypothèse du continu, ainsi que la consistance de l'hypothèse de Souslin via l'axiome de Martin. Les chapitres suivants sont une introduction aux axiomes de grands cardi- naux, qui occupent une place fondamentale dans la plupart des développe- ments de la théorie des ensembles depuis les années 1970. Le chapitre XIII est centré sur les « petits» grands cardinaux, avec notamment ici les car- dinaux inaccessibles et les cardinaux faiblement compacts, et les propriétés d'arbre et de partition associées. Ensuite, un développement approfondi est consacré aux cardinaux mesurables, à la charnière des «petits» et des « grands» grands cardinaux, qui sont fondamentaux à plusieurs titres. On étudie ici la notion-clé d'ultrapuissance d'un modèle de ZF associée à un cardinal mesurable, ainsi que la trace que laisse un tel cardinal sur le modèle intérieur L via une famille d'ordinaux indiscernables. Le chapitre XIV présente quelques «grands» grands cardinaux, cardi- naux forts, cardinaux de Woodin, cardinaux supercompacts, tous définis en termes de l'existence de plongements élémentaires convenables du mo- dèle de référence dans un modèle intérieur. Une place spéciale est accordée aux cardinaux de Laver et à la structure des itérés des plongements élémen- taires associés, qui mène à des applications étonnantes (et, pour le moment, peu connues) en combinatoire finie, avec les propriétés asymptotiques des périodes dans les tables de Laver. Le chapitre XV est consacré à la propriété de détermination d'un sous- ensemble de la droite réelle. On y montre que l'hypothèse que tous les ensembles projectifs sont déterminés (<< axiome de détermination projec- tive DP ») fournit une description optimale de ces ensembles, et qu'elle résulte d'un certain axiome de grand cardinal. On explique alors comment un tel résultat, étendant au monde HNl des ensembles dénombrables la compréhension précédemment acquise pour le monde HNo des ensembles finis, légitime un nouveau consensus dans lequel ZFC amendé en ZFC+DP devient la base axiomatique standard de la théorie des ensembles. Enfin, dans le chapitre XVI, en guise de conclusion, on commence par revenir brièvement sur le rôle fondationnel de la théorie des ensembles pour souligner ce qui devrait apparaître à l'évidence comme des malentendus au lecteur parvenu à ce point, puis on tente une sorte d'évaluation de la théorie



XIV



Avant-propos



au vu des résultats acquis, pour revenir finalement aux mathématiques pour un aperçu de quelques travaux en cours, principalement autour des axiomes de forcing et des modèles canoniques, et des perspectives qu'ils ouvrent pour l'analyse de la structure H N2 et pour une solution du problème du continu, toujours ouvert à ce jour, mais dont le lecteur devrait être désormais d'accord pour penser avec la plupart des spécialistes qu'il n'a nulle vocation à le rester à jamais.



Remerciements Les dix premiers chapitres de ce texte sont issus de cours enseignés pendant des années à l'université de Caen et à l'École normale supérieure de Paris. Je remercie particulièrement les collègues qui m'ont épaulé à cette occasion et ont contribué à enrichir ces notes: Olivier Laurent, Julien Lévy, Claude Sureson, et Philippe Toffin. Je remercie également collectivement les étu- diants qui ont suivi ces cours et les lecteurs connus ou inconnus des diverses versions qui m'ont depuis des années adressé commentaires, questions, cor- rections, suggestions, et en particulier Pierre Ageron, Maxime Bourrigan, Lorenzo Carlucci, Cédric Cessio, Ikram Cherigui, René Cori, Pierre Dehor- noy, Rémi Goblot, Marc Hoyois, Gérard Lang, Serge Leblanc, Marc Mez- zaroba, Simon Pépin-Lehalleur, Vincent Robin, Marc Sage, Pierre Simon, Pierre Simonnet, Lorenzo Tortora, Frédéric Wang. Je remercie mes collègues de la communauté de théorie des ensembles, no- tamment Steve Jackson, Aki Kanamori, Stevo Todorcevic, Friedrich Weh- rung, et Hugh Woodin, pour les nombreuses explications et précisions qu'ils m'ont apportées. Je remercie également Henri Lombardi qui, en jouant le rôle d'un opposant acharné à l'approche ensembliste, m'a aidé à dépasser les a priori dogmatiques. Merci également à Alberto Arabia et Rached Mneimné qui, par leur ex- pertise technique et leur exigence, m'ont aidé à préparer une mise en page soignée et, j'espère, agréable pour le lecteur, malgré sa densité. Et à Arlette Dehornoy et Isabella Bembo pour leur saisissante représentation des grands cardinaux. Enfin et surtout, je remercie Serge Grigorieff qui, par une relecture tout à la fois minutieuse et compétente de l'intégralité de ce texte, a grandement contribué à en améliorer la qualité. J'ajoute mes remerciements aux lecteurs qui, en débusquant fautes et im- précisions du premier tirage, ont permis d'améliorer le deuxième, que voici. Ma gratitude va spécialement à Alexandre Bailleul et à Martial Leroy, deux redoutables et souvent complémentaires chasseurs de coquilles.



Caen, Paris, Arnières-sur-Iton, juin 2017, et mai 2018



Table des matières



Partie A. Théorie élémentaire



1. Le type « ensemble » 1. Pourquoi une théorie des ensembles? 1.1. La notion d'ensemble. . . . . . . 1.2. Utilité des ensembles . . . . . . . . 1.3. Premiers résultats, premiers problèmes. . 2. Opérations ensemblistes . . . . . . . . . . . . . 2.1. Le treillis des parties d'un ensemble ........ 2.2. Les algèbres de Boole comme structures algébriques 2.3. Algèbres de Boole finies . . . . . . . . . . . . 3. Ébauche d'une théorie des ensembles 3.1. Une tentative naïve. . 3.2. Le système de Cantor .. 3.3. Le paradoxe de Berry .. 3.4. Le paradoxe de Russell. . 3.5. Ensembles purs et système de Zermelo



4 4 6 7 14 15 17 19 21 21 23 24 28 32



II. Les ordinaux 1. Les bons ordres ................. 1.1. Relations bien fondées et bons ordres. . . 1.2. Rigidité et comparabilité des bons ordres 1.3. Opérations sur les bons ordres ...... 2. Une construction des ordinaux . . . . . 2.1. Ensembles transitifs et ordinaux 2.2. L'ordre sur les ordinaux . . . . . . . . . . 2.3. Borne supérieure; ordinaux limites 2.4. Le théorème de comparaison 3. L'arithmétique ordinale . . . . . . 3.1. L'addition ordinale . . . . 3.2. La multiplication ordinale 3.3. L'exponentiation ordinale 3.4. Ordinaux non dénombrables. . . 4. Deux applications . . . . . . . . . . 4.1. Le théorème de Cantor-Bendixson 4.2. Le théorème de Goodstein . . . . .



40 41 44 47 54 54 58 61 64 66 66 69 72 74 76 77 79



-xv-



XVI



Table des matières



III. Le système de Zermelo-Fraenkel 1. Représentation par des ensembles purs 1.1. Ensembles purs . . . . . . . . . . . . . 1.2. Représentation des entiers naturels . . . . . . . 1.3. Représentation des couples et des fonctions . . . . 1.4. Représentation de tous les objets mathématiques 2. Axiomatisation des ensembles purs ....... 2.1. Extensions par définition. . . . . . . . . . . . 2.2. Représentation des couples et des fonctions 2.3. Construction des ordinaux. . 2.4. Les axiomes de remplacement 3. Définitions récursives . . . . . 3.1. Récursion sur les entiers . . . 3.2. Récursion ordinale . . . . . . 3.3. Récursion ordinale généralisée. 4. La théorie des ensembles . . . . . . . 4.1. L'axiome de fondation et le système ZF 4.2. La règle du jeu . . . . . . . . . . . . . . .



86 86 90 91 94 96 96 99 101 106 110 110 112 114 120 120 123



IV. L'axiome du choix 1. L'axiome du choix . . . . . . . . . . . . . . . . 1.1. Fonctions de choix . . . . . . . . . . . . . . . . 1.2. Formes alternatives de l'axiome du choix. . . 2. Des applications de l'axiome du choix . 2.1. Dénombrement . . . . . . . . . . . . . 2.2. Ensembles ordonnés et algèbre 2.3. Topologie et analyse . . . . . . . 2.4. Géométrie . . . . . . . . . . . 3. L'axiome du choix est-il vrai? 3.1. Une question ambiguë . . . . . . 3.2. Est-il opportun d'adopter l'axiome du choix? . . . . .



130 130 133 140 140 142 145 150 156 156 157



V. Les cardinaux 1. Cardinaux finis et infinis . . . . . 1.1. La notion de cardinal ...... 1.2. Dénombrements finis . 1.3. Les cardinaux infinis . 2. L'arithmétique cardinale . . . . . 2.1. Opérations à deux arguments 2.2. Sommes et produits infinis. . 2.3. Les cardinaux sans axiome du choix 3. La cofinali té . . . . . . . . . . . . . . . 3.1. Ensembles cofinaux. . . . . . . . . . . 3.2. Cardinaux réguliers et singuliers ... 3.3. Puissance et exponentiation cardinales 4. La combinatoire sur Wl . . . . . . . . . . . 4.1. Ensembles clos cofinaux et le théorème de Fodor 4.2. Le théorème de Silver ................



162 162 165 166 169 169 172 173 176 176 179 180 184 184 187



Table des matières



XVll



Partie B. Un peu de logique mathématique



VI. Logique propositionnelle 1. La logique booléenne . . . . . . . . . . . . . . . . . 1.1. Logiques formelles : syntaxe et sémantique. . 1.2. La logique booléenne . . . . . . . . . . 1.3. Sémantique de la logique booléenne. . 2. Un théorème de complétude ........ 2.1. Preuve par coupure. . . . . . . . . . . 2.2. La forme locale du théorème de complétude 2.3. La forme globale du théorème de complétude



196 196 198 200 202 203 205 208



VII. Logique du premier ordre 1. Logiques du premier ordre . . . . 1.1. Les formules de la logique £L 1.2. Sémantique de la logique £L 1.3. Exprimabilité au premier ordre 2. Le théorème de complétude. . . . 2 .1. Preuves . . . . . . . . . . . . . . . 2.2. Le théorème de la déduction. . 2.3. Théories explicitement complètes . 2.4. La méthode de Henkin . . . . . . . . . . . 3. Applications du théorème de complétude 3.1. La méthode sémantique . . . . . . . . 3.2. Limitations du pouvoir d'expression 3.3. Modèles de l'arithmétique . . . . . . . 4. La logique du premier ordre comme modèle. . 4.1. Modélisation par la logique du premier ordre 4.2. Contexte métamathématique . . . . 4.3. Les logiques du second ordre



216 216 220 223 226 226 229 230 233 236 237 240 244 248 249 252 255



VIII. Théorèmes de limitation 1. Fonctions et relations récursives 1.1. Fonctions primitives récursives . . . . 1.2. Représentation des suites finies . . . . 1.3. Fonctions et relations récursives. 2. Arithmétisation de la syntaxe .. 2.1. Numérotation des formules 2.2. Numérotation des preuves . . 3. L'arithmétique de Robinson ... 3.1. Modèles du système PAfaible . . 3.2. Absoluité des formules El 3.3. Représentabilité. . . . . . . .



260 261 266 269 273 273 276 279 280 284 286



XVlll



Table des matières



4. lndécidabilité et incomplétude . . . . . . . . . . . . 4.1. Le lemme diagonal . . . . . . . . . . . . . . . . . . 4.2. Le théorème d'indécidabilité de Church .... 4.3. Le théorème de non-définissabilité de la vérité de Tarski 4.4. Le premier théorème d'incomplétude de Godel 4.5. Le second théorème d'incomplétude de Godel . . . . . .



IX. Théorie descriptive des ensembles 1. Les boréliens d'un espace polonais . 1.1. Les espaces polonais . . . . . . . 1.2. La hiérarchie borélienne . . . . . 1.3. Classification des espaces polonais 2. La hiérarchie projective . . . . 2.1. Les ensembles analytiques . . . . 2.2. Les ensembles projectifs 2.3. Le théorème de Souslin 3. Les hiérarchies effectives ... 3.1. Les ensembles récursifs. . 3.2. Les hiérarchies arithmétique et analytique . 3.3. Lien avec les ensembles boréliens et projectifs .



Partie C. Théorie axiomatique des ensembles



X. Modèles de ZF 1. La notion de modèle de ZF . . . . . . 1.1. Le modèle d'Ackermann . . . . . . 1.2. Construction de modèles de ZF . . . . 1.3. La méthode sémantique en théorie des ensembles 2. Modèles transitifs . . . . . . . . . . . . . . . . 2.1. Satisfaction des axiomes de ZF . . 2.2. Formules et opérations absolues . 2.3. Absoluité des formules L1î F . . . 2.4. Réduction aux modèles transitifs 3. Exemples et applications . . . . . . . . . . . . 3.1. Les structures (Va, E) et (HK" E) ..... 3.2. Résultats de non-prouvabilité



XI. Les ensembles constructibles 1. La classe L . . . . . . . . . . . . . . . . 1.1. Les opérations de Godel . 1.2. Le schéma de réflexion . . 1.3. La classe des ensembles constructibles 1.4. L'axiome du choix dans L . . . . . . .



292 292 294 296 299 302



312 313 319 324 327 328 330 332 339 340 342 346



354 355 357 361 365 366 368 375 378 383 383 387



394 395 399 403 406



Table des matières



XIX



2. Les ensembles La .... . . . . . . . . 2.1. Définissabilités externe et interne . 2.2. Les ensembles La . . . . . . . . . . . . . . 2.3. L'hypothèse généralisée du continu 2.4. Élimination de AC et HC. . . 3. Propriétés combinatoires de L . . . . . 3.1. Le bon ordre canonique de L . . . 3.2. Les principes combinatoires <> et 0 . . 3.3. L'axiome V =L est-il vrai? 4. D'autres modèles intérieurs . . . . . . . . . 4.1. Constructibilité relative . . . . . . . . . . 4.2. Les modèles HOD et leurs variantes



408 409 413 415 419 422 423 426 431 432 433 434



XII. La méthode du forcing 1. Extensions génériques . . . . . . . 1.1. La méthode sémantique . . . 1.2. Les noms et leur évaluation 1.3. Ensembles génériques et forcing . . 2. Pratique du forcing . . . . . . . . 2.1. Consistance relative de V #L 2.2. Consistance relative de .HC . . 2.3. Consistance relative de .AC . . . 3. Des notions de forcing innombrables . . . . . . 3.1. Changement de cardinalité et de cofinalité . 3.2. L'axiome de Martin ........ 3.3. Valeur booléenne d'une formule. 3.4. Indépendance V8. indécidabilité . . . .



440 441 443 445 452 452 453 457 460 460 464 469 471



XIII. Les grands cardinaux (1) 1. Les « petits» grands cardinaux .... 1.1. Les cardinaux inaccessibles ... . 1.2. Les cardinaux faiblement compacts . 1.3. Les cardinaux indescriptibles 2. Les cardinaux mesurables . . . . . . . . 2.1. Ultrafiltres complets . . . . . . . . . . 2.2. Ultraproduits et théorème de Los . 2.3. Ultrapuissances de modèles de ZFC . . . . 3. Le réel O

. . . . . . . . . . . . . . . . . . . . . 3.1. Cardinaux mesurables et constructibles 3.2. Le réel O

..... . . . . . . . . . 3.3. Le monde sans O

. . . . . . . . . . . . . . . . 3.4. Les grands cardinaux existent-ils?



476 477 480 485 488 488 492 497 503 504 506 511 512



xx



Table des matières



XIV. Les grands cardinaux (II) 1. Les « grands» grands cardinaux . . . . . . . . . . . 1.1. Plongements élémentaires . . . . . . . . . . . . . . . . 1.2. Les cardinaux forts et les cardinaux de Woodin 1.3. Les cardinaux supercompacts 2. Rangs autosimilaires. . . . . . 2.1. La borne de K unen . . . . . . . . 2.2. Les cardinaux de Laver ... 2.3. Itérations d'un plongement élémentaire. . 3. Périodes dans les tables de Laver. ..... 3.1. Les tables de Laver. . . . . . . . 3.2. Quotients finis de Iter(j) . . .. .... 3.3. Deux résultats sur les périodes . . . . 3.4. Un type nouveau d'application de la théorie des ensembles. 3.A. Appendice : propriétés élémentaires des tables de Laver XV. La détermination projective 1. La propriété de détermination 1.1. Jeux infinis . . . . . . . . . . . . . 1.2. Pouvoir d'expression . . . 1.3. La détermination comme moyen d'exploration. . 2. Détermination et grands cardinaux . . . . . 2.1. La détermination nt . . . . . . . . . 2.2. La détermination projective . 2.3. La direction réciproque ... 3. Un nouveau cadre axiomatique. . . . 3.1. Deux approches complémentaires . 3.2. Qu'est-ce qu'un axiome vrai? 3.3. Le système ZFC+DP . . . . . XVI. Un bilan mitigé 1. Une accumulation de malentendus 1.1. Les espoirs déçus . . . . . . . 1.2. Dogmes et errances bourbachiques 1.3. Un système fondationnel parmi d'autres 2. Une théorie de l'infini encore incomplète 2.1. Des réponses .. . . . . . . . . . . . . . . 2.2. Des questions qui résistent. . . . . . . . . 2.3. Des interactions, mais souvent indirectes et limitées 3. Quelques pistes ................. 3.1. Absoluité générique et axiomes de forcing 3.2. Les modèles canoniques 3.3. Une conclusion . . . . . . . . . . . . . . .



Bibliographie Notations Index



516 517 520 525 528 529 531 535 539 540 544 550 554 556



566 566 570 576 580 581 586 592 595 595 597 598



604 604 606 608 610 611 611 613 617 617 623 626



629 635 637



Partie A Théorie élémentaire



-1-



Chapitre 1



Le type « ensemble »



Partant des intuitions de base, et rapidement convaincus que des problèmes difficiles se posent dès que des ensembles infinis sont introduits, nous cher- chons ici les fondements sur lesquels une théorie des ensembles peut être élaborée : que sont les ensembles, quelles opérations et relations s'y rat- tachent, quels principes de base les gouvernent? En nous efforçant de garder l'approche la plus élémentaire possible, nous serons conduits à emprunter le chemin ouvert par Georg Cantor à la fin du XIX e siècle, puis à suivre ses ajustements successifs pour parvenir au système de Zermelo, fondement des développements ultérieurs.



t> On trouvera ici davantage de discussions informelles que de démonstrations, ce qui est naturel puisque l'opportunité de bâtir une théorie et le choix d'un système axiomatique de départ sont affaires de consensus et non de démonstration : sauf à proclamer un dogme que rien ne justifie, la seule chose qui puisse étre recherchée est un accord partagé sur une position du type « Oui, la formalisation proposée est conforme à l'intuition que nous partageons des objets étudiés, ici les ensembles et l'infini» et, de là, «Oui, il est raisonnable d'explorer les problèmes ouverts sur de telles bases et nous jugerons convaincantes les conséquences de celles-ci». Refaire le chemin tracé par les pionniers n'est peut-étre pas la seule manière d'obtenir un tel accord, mais c'est en tout cas une manière commode de procéder pour écarter les approches trop simplistes et comprendre les subtilités du système finalement retenu, lequel pourrait au départ être jugé non intuitif, voire artificiel. Ce que nous verrons vite dans la suite est que la théorie des ensembles est une théorie de l'infini plus qu'une théorie des ensembles au sens propre : pour les ensembles finis, comme on le constatera dans la section 2, (presque) tout est dit quand on a dégagé la structure d'algèbre de Boole. En revanche, dès qu'il est jugé opportun de considérer des ensembles infinis, la situation est radicalement différente et c'est là que la théorie des ensembles aura à se déployer. <]



Le chapitre comporte trois sections. Dans la section 1, on justifie l'oppor- tunité de développer une théorie des ensembles par l'irruption immédiate de problèmes apparemment difficiles dès que des ensembles infinis entrent en jeu. Dans la section 2, on introduit les opérations ensemblistes usuelles,



-3-



4



1. Le type « ensemble»



réunion, intersection, etc., et on montre que la structure d'algèbre de Boole en capture toutes les propriétés dans le cas fini. Dans la section 3, on ébau- che une théorie des ensembles. Comme une définition ex nihilo est malaisée, on recourt à une approche axiomatique, et la nécessité d'échapper aux pa- radoxes de Berry et de Russell mène au système de Zermelo.



1. Pourquoi une théorie des enselllbles?



Après une brève discussion de la notion d'ensemble et de son utilité, on exa- mine les problèmes liés à la comparaison de la taille des ensembles. Dans le cas fini, on établit facilement les résultats combinatoires élémentaires. En revanche, des problèmes surgissent rapidement lorsque l'on passe aux ensembles infinis, au premier plan desquels le problème du continu de Can- tor. L'existence de tels problèmes est la justification la plus naturelle de l'intérêt de développer une théorie des ensembles.



t> Les mathématiques étudient des objets appartenant à des types variés: entiers, réels, points, fonctions, etc., chacun muni d'opérations et de relations qui lui sont spécifiques. Les ensembles constituent un tel type d'objet, et élaborer une théorie des ensembles signifie organiser en une suite cohérente nos connaissances sur ceux des objets mathématiques qui se trouvent étre des ensembles, à la manière dont on développe une théorie des nombres ou une théorie des fonctions réelles. Méme s'il est facile de se convaincre de l'utilité des ensembles en mathématiques, il n'est pas a priori évident qu'il soit utile ou nécessaire d'en développer une théorie. Comme on le verra, ce qui a rendu nécessaire la construction d'une théorie des ensembles, c'est l'apparition, à la fin du XIX e siècle et au début du xx e, de problèmes ouverts difficiles et naturels mettant en jeu les ensembles infinis. On peut alors espérer qu'une théorie cohérente les résoudra ou, au moins, les éclairera. En somme, il y a comme un rendez-vous proposé au lecteur: estimera- t-il, à la fin du livre, qu'il en sait davantage sur ces questions initiales ou, tout au moins, que l'étude ainsi développée lui aura permis de mieux comprendre l'infini en mathématiques et d'en tirer des applications ? <]



Cette section comporte trois sous-sections. Dans la sous-section 1.1, on rappelle la notion d'ensemble de la façon la plus élémentaire possible, avant d'en discuter l'utilité dans la sous-section 1.2, puis de rencontrer dans la sous-section 1.3 les premiers problèmes de dénombrement qui légitiment le développement d'une théorie.



1.1. La notion d'ensemble



Résumé.- Nommer un ensemble, c'est proclamer l'existence d'un nouvel objet rassemblant des objets qui partagent une propriété. .....



1.1.1.- Plutôt que des objets mathématiques isolés, par exemple l'entier 2 ou le réel1r, il arrive que plusieurs objets soient considérés simultanément sans que l'on veuille ou puisse référer à l'un d'entre eux spécifiquement, par



1. Pourquoi une théorie des ensembles?



5



exemple les solutions d'une équation, les entiers pairs ou les réels transcen- dants : l'usage est alors de nommer cette collection d'objets, donc, ce fai- sant, de l'introduire comme un nouvel objet mathématique. Ainsi, lorsque l'on dit: «Soit P l'ensemble des entiers pairs», à côté des entiers 0, 2,4 ... pris individuellement, on introduit, et en particulier on nomme, un nouvel objet référant à tous ces entiers pris collectivement. On déclare alors « n appartient à P », ou encore «n est élément de P », noté n E P, comme une autre façon d'exprimer que n a la propriété définissant P, ici être un nombre pair. En d'autres termes, on remplace un prédicat par son extension ou, tout au moins, on donne un nom à celle-ci. 1.1.2.- La notation traditionnelle 1 pour l'ensemble dont les éléments sont les objets x possédant une certaine propriété P (x) est {x 1 P (x) }, et celle pour l'ensemble dont les éléments sont des objets al, ..., an explicitement énumérés est {al, ... , an}. Par exemple { -1, 1} est l'ensemble dont les deux éléments sont les entiers -1 et 1. Cet ensemble est aussi {l, -1}, et égale- ment {-l,l, 1}, puisque seuls comptent les éléments indépendamment de tout ordre ou multiplicité. Diverses représentations graphiques sont utili- sées, par exemple les diagrammes dits de Venn (figure 1).



1



o



13 o



P



FIGURE 1.- Représentation graphique d'un ensemble par un dia- gramme de Venn, ici l'ensemble P des nombres pairs: un cadre entoure les éléments et les isole des non-éléments; dans le cas présent, la repré- sentation est forcément incomplète puisqu'il existe une infinité d'entiers.



1.1.3.- On pourrait confondre ensemble et propriété en identifiant un en- semble avec la propriété qui le définit. Ce n'est pas le point de vue adopté: l'ensemble ne retient que le résultat final, c'est-à-dire les objets sélection- nés, et non la propriété utilisée pour opérer la sélection. De la sorte, un ensemble est complètement déterminé par ses éléments, et par eux seuls (propriété dite d'extensionnalité) : deux propriétés équivalentes conduisent à sélectionner les mêmes objets, et elles définissent donc un seul ensemble.



[> Par exemple, pour un entier, être le double d'un entier est équivalent à être congru à 0, 2, 4, 6, ou 8 modulo 10 : les deux propriétés sont distinctes, mais l'ensemble qu'elles définissent est le même. Ainsi, un ensemble est associé à une classe d'équivalence de propriétés plutôt qu'à une propriété spécifique 2 .



1. Notation à laquelle on se tiendra ici; on trouve également {x : P(x)} et {x; P(x)}. 2. Comme il n'est pas garanti que l'équivalence des propriétés puisse être reconnue, l'égalité des ensembles ne l'est pas davantage : on introduit comme objets mathéma- tiques abstraits des ensembles dont il peut être impossible en pratique de déterminer les éléments.



6



1. Le type « ensemble»



L'approche qui sera adoptée dans la suite de ce texte est extrémement libérale dans la mesure où les propriétés définissantes seront souvent oubliées, de sorte que des ensembles puissent étre envisagés indépendamment de toute définition. Par exemple, une expression telle que «soit A un ensemble d'entiers» indiquera seulement que A est un objet tel que, pour chaque entier n, l'assertion n E A est soit vraie, soit fausse, et que A est entièrement déterminé par les entiers n qui vérifient n E A, qu'une propriété explicite caractérisant ceux-ci ait été donnée ou non. Une telle approche est qualifiée d'imprédicative, par opposition à l'approche prédicative qui ne considérerait que des objets explicitement définis. Cette étape supplémentaire d'abstraction est une option, et elle est discutable : on peut es- timer n'étre intéressé que par des objets explicitement définis et donc considérer comme vides de sens des énoncés mettant en jeu des objets qui ne le sont pas. Le point de vue de la théorie des ensembles n'exclut pas une telle position, mais ce n'est pas celle qu'il retient - voir plus loin la discussion sur les axiomes de compréhension et des parties dans la sous-section 3.4, ou encore sur l'axiome du choix au chapitre IV. <1



1.2. Utilité des ensembles

Résumé.- Introduire des ensembles est utile pour exprimer des pro- priétés collectives ne faisant pas sens pour des objets individuels.



1.2.1.- La fréquence des termes «ensemble », «famille », «collection» dans les textes mathématiques récents montre que l'introduction d'ensem- bles est au moins une convention commode : séparer les entiers pairs des impairs permet ensuite de travailler avec ceux-ci de manière uniforme, in- dépendamment de la propriété utilisée pour les séparer. De plus, de nom- breux objets mathématiques sont définis comme des domaines, donc des ensembles, munis d'une structure additionnelle, algébrique, topologique ... et il serait donc malcommode, au moins formellement, de se passer d'en- sembles pour définir un groupe, un corps, ou une variété différentiable 3.



1.2.2.- Il Y a plus important : au-delà de la commodité de formula- tion, l'introduction d'ensembles permet surtout de saisir des propriétés glo- bales qui ne font pas sens pour chaque élément pris individuellement. Par exemple, affirmer que les multiples de 5 forment un sous-groupe de Z dit quelque chose de plus 4 que les propriétés individuelles de 10 ou -15.



Exemple. S oit à montrer qu'aucun entier n plus grand que 1 ne divise 3 n - 2 n . Supposons, en vue d'une contradiction, que n divise 3 n - 2 n , et soit p le plus petit facteur premier de n. Si pest 2 ou 3, alors p, donc a fortiori n, ne divise pas 3 n - 2 n . Supposons p

5. Les classes 2 et 3 de 2 et 3 dans Z/pZ sont alors inversibles. L'ensemble {k E Z 1 2 k == 3 k } est un sous-groupe de Z, et est donc de la forme mZ pour un certain m positif. Le petit théorème de Fermat implique l'égalité 2 P - 1 == 3 P - 1 == 1, donc p - 1 E mZ, et m

p - 1. Donc, m ne peut diviser n, puisque p est son plus petit facteur premier. On a donc n r/:. mZ, et p,



3. Mais on ne doit pas oublier que la plupart des résultats mathématiques démontrés avant le xx e siècle l'ont été sans que des ensembles y soient mentionnés formellement. 4. Mais il faut reconnaître qu'au lieu de parler du sous-groupe 5Z, donc d'un ensemble, on pourrait exprimer tous les énoncés en termes de la seule congruence modulo 5.



1. Pourquoi une théorie des ensembles?



7



donc n, ne divise pas 3 n -2 n . Dans la démonstration précédente, le point essentiel est l'introduction de l'ensemble {k E Z 1 2 k = 3 k }, et le fait que tout sous-groupe de Z est de la forme mZ. On pourrait s'en passer en redémontrant le résultat dans le cas particulier, en l'occurrence en considérant le plus petit m vérifiant 2 m = 3 m , puis en montrant par division euclidienne que tout entier k vérifiant 2 k = 3 k est multiple de m. Mais on perdrait ainsi probablement une part de la compréhension et, en tout cas, de l'économie apportées par le résultat structurel sur les sous- groupes de.z, donc par l'introduction d'un ensemble.



1.3. Premiers résultats, premiers problèmes

Résumé.- Comparer les ensembles (infinis) mène au problème du continu sur les tailles intermédiaires entre celles de N et de JR : l'absence d' u ne sol ution évidente motive l' éla boration d' u ne théorie. ......



1.3.1.- Même si l'utilité des ensembles est tenue pour acquise, il ne va pas de soi qu'il faille en construire une théorie générale: par exemple, les suites ou les fonctions sont aussi des outils importants et pourtant la nécessité d'une théorie générale des suites ou des fonctions ne s'est pas fait ressentir 5. Ce qui rend l'élaboration d'une théorie des ensembles nécessaire, ou, au moins, opportune, c'est l'apparition de nombreux problèmes ouverts mettant en jeu des ensembles infinis et leur classification à bijection près. 1.3.2.- La plupart des structures mathématiques vont de pair avec une notion de morphisme. Dans le cas des ensembles, comme aucune structure additionnelle n'est considérée, les morphismes naturels sont les applications, et les isomorphismes sont les bijections 6. Définition (équipotence).- Deux ensembles A et B sont dits en bijec- tion, ou équipotents 7, s'il existe une bijection de A sur B. L'identité, l'inverse d'une bijection, et la composée de deux bijections sont des bijections, donc l'équipotence est une relation d'équivalence. 1> L'existence de bijections ou d'injections entre des ensembles formalise la notion intuitive de nombre d'éléments, donc une notion de taille. Une bijection entre deux ensembles A et B fait se correspondre un à un les éléments de A et de B, et traduit l'intuition que A et B ont la même taille. De même, une injection de A dans B établit une correspondance bijective entre A et un sous-ensemble de B, et elle traduit l'intuition que la taille de A est au plus celle de B. <J



5. Cependant, on pourrait dire que le lambda-calcul évoqué dans la sous- section XV1.1.3 est une théorie générale des fonctions. 6. On rappelle la terminologie usuelle (sur laquelle on reviendra dans la sec- tion 111.1.3) : une fonction de A dans B est une correspondance entre éléments de A et de B dans laquelle chaque élément de A a au plus une image; de plus, elle est dite partout définie, ou appelée application de A dans B, si tout élément de A a une image; une fonction de A dans B est dite injectivesi deux éléments distincts de A ont des images distinctes, et surjective si tout élément de B est image d'au moins un élément de A; enfin une injection (resp., surjection, resp., bijection) de A dans B est une application de A dans B qui est injective (resp., surjective, resp., injective et surjective). 7. Le terme est un peu tombé en désuétude.



8



1. Le type « ensemble»



1.3.3.- Lier la notion intuitive de taille d'un ensemble à l'existence d'une bijection et utiliser un vocabulaire d'ordre en liaison avec l'existence d'une injection est rendu cohérent par le résultat classique suivant.



Démonstration. (Voir aussi l'exercice 1.) Supposons que f : A -t B et g : B -t A sont des injections. Posons A' == Im(f) et B' == Im(g). Alors, f est une bijection de A sur A', et g une bijection de B sur B'. On va construire une bijection h de A sur B'. Pour cela, posons Ao :== A \ B', puis, inductivement, soit Ai l'image de Ai-l par go f pour i

1. L'ensemble Ao est disjoint de Ai pour i

1 car Ao est disjoint de B' et Ai inclus dans B'. Comme la composée (g 0 f)j est injective pour tout j, les ensembles Aj et Aj+i sont disjoints pour tous j

0 et i

1. Par construction, go f envoie Uc

o Ai sur Ui

l Ai, lequel ensemble est inclus dans B'. ?' ?'



gof r+



gof gof r+ r+



A



B



f



t- g



....



"V Im(g 0 f)



....



"V



....



A' == Im(f)



"V B' == Im(g) Définissons alors h par h(a) :== g 0 f(a) si a est dans Ui

O Ai, et h(a) :== a sinon. Par construction, l'image de h est B', et, d'autre part, h est injective car obtenue en recollant deux injections dont les images sont disjointes. Donc, h est une bijection de A sur B', et, finalement, g-l 0 h est une bijection de A sur B. 0



1.3.4.- La notion duale de celle d'injection est celle de surjection. L'exis- tence d'une injection de A dans B entraîne celle d'une surjection de B sur A : si A est non vide et si f : A

B est injective, on définit une surjec- tion 9 : B

A en choisissant un élément a de A et en posant g(b) := f-1 (b) pour b dans Im(f) et g(b) := a sinon.



Question. - L'existence d'une injection de A dans B est-elle équivalente à celle d'une surjection de B sur A ?



Mis à part le cas des ensembles finis (voir 1.3.7 ci-dessous), la réponse n'est pas évidente, on y reviendra au chapitre IV.



1. Pourquoi une théorie des ensembles?



9



1.3.5.- De nombreuses questions apparaissent lorsque les ensembles finis et infinis sont distingués. On définit ici ces notions en partant du principe qu'un ensemble fini est un ensemble dont on peut numéroter les éléments. On rappelle les notations conventionnelles: N désigne l'ensemble des entiers naturels (positifs ou nul), Z celui des entiers relatifs, Q celui des nombres rationnels, :IR celui des nombres réels, et C celui des nombres complexes.



Définition (fini, infini, dénombrable).- Un ensemble est dit fini s'il est vide ou en bijection avec un intervalle de N de la forme {l, 2, ... , p} ; un ensemble qui n'est pas fini est dit infini. Un ensemble en bijection avec N est dit dénombrable.



[> La définition précédente présuppose (bien sûr -0 l'existence des nombres entiers et de l'ensemble N de ces nombres. On se demandera plus loin si une définition plus intrinsèque est possible: on renvoie ici à la sous-section 111.2.3. <1



1.3.6.- Partant de cette définition, il est facile de légitimer les propriétés usuelles des ensembles finis en utilisant le résultat technique suivant. Lemme.- Toute injection d'un ensemble fini dans lui-même est bijective.



Démonstration. Il suffit de montrer le résultat pour les intervalles {l, ...,p}. On raisonne par récurrence sur p

1. Pour p == 1, l'intervalle {l, ...,p} est le single- ton {1}, et la seule application de {1} dans lui-même est l'identité, qui est une bijection. Supposons p

2, et soit f une injection de {l, ...,p} dans lui-même. Posons q :== f(p). On définit une application g de {l, ...,p - 1} dans lui-même en posant g(i) :== f(i) pour f(i) < q et g(i) :== f(i) - 1 pour f(i) > q. 1 2 p-1 p o · J

)1 o J / ' · J



( 0



o



g



q== f (p )y-



( 0

( 0



o



o



.



o



/



o



o



o



o



1 2 p-1 Alors, g est injective puisque q n'appartient pas à l'image de {l, ... ,p-1} par f. Par hypothèse de récurrence, g est surjective. Par construction, Im(f) est Im(g) U {p}, donc on trouve finalement lm(f) == {l, ...,p}. 0



1.3.7.- On en déduit le résultat principal concernant les ensembles finis. Proposition (cardinal). - Tout ensemble fini non vide A est en bijection avec un unique intervalle {l, 2, ..., p} de N. L'entier p est appelé le cardinal de A, noté Il A Il, et 0 est appelé le cardinal de l'ensemble vide.



Démonstration. Par définition, A est en bijection avec un intervalle {l,..., p}. Celui-ci est unique, puisque, pour q < p, une bijection de {l, ...,p} sur {l, ...,q} serait une injection non bijective de {l, ..., p} dans lui-même, qu'exclut 1.3.6. 0



10



1. Le type « ensemble »



On obtient ainsi une classification complète des ensembles finis à l'aide des entiers: deux ensembles finis A, B sont en bijection si l'on a IIAII = IIBII. De même, il existe une injection de A dans B si l'on a IIAII

IIBII.



1.3.8.- Toujours pour les ensembles finis, on déduit une réponse positive à la question 1.3.4.



Corollaire (injectionjsurjection).- Pour A et B finis avec A non vide, l'existence d'une injection de A dans B équivaut à celle d'une surjection de B sur A.



Démonstration. L'existence d'une injection de A dans B équivaut à IIAII

IIBII, celle d'une surjection de B sur A à IIBII

IIAII ... 0



1.3.9.- On passe maintenant aux ensembles infinis, où la situation est beaucoup plus compliquée, et où des bijections, c'est-à-dire des égalités de taille, étonnantes apparaissent.



[> On a vu en 1.3.6 qu'une partie propre d'un ensemble fini est strictement plus petite que celui-ci. Par définition, ce résultat ne s'étend pas aux ensembles infinis: par exemple, l'application «successeur» qui, pour tout entier n, envoie n sur n+ 1 définit une bijection de N sur la partie propre de N composée des entiers non nuls. Autrement dit, N privé de 0 n'est pas plus petit que N. De même, l'application qui, pour tout entier n, envoie n sur 2n définit une bijection de N sur l'ensemble des nombres pairs, ce qui montre que ce dernier, ne contenant pourtant qu'un entier sur deux, n'est pas plus petit que N : la moitié de N n'est pas plus petite que N. <J



Proposition (carré). - Les ensembles N et N x N sont en bijection.



Démonstration. Comme tout entier non nul s'écrit de façon unique comme le produit d'une puissance de 2 et d'un entier impair, l'application (p, q) t-+ 2 P (2q+1) est une bijection de N x N sur N\ {O}, donc (p, q) H- 2 P (2q+ 1) -1 est une bijection de N x N sur N. Une autre bijection classique, qui suit le parcours des diagonales successives du réseau N x N écrit dans un quadrant comme ci-dessous



(2,1) (2,2) (2,3) (2,4) 0 0 0 (1,3) (1,4) 0 0 ...

)............, (0,4) 0 ...... ...... . .



correspond à la formule polynomiale 8 (p, q) H- (p + q)(p + q + 1)/2 + q. 0



8. Polya a montré que le polynôme indiqué et son symétrique sont les seuls polynômes de degré au plus 2 établissant une bijection entre N et N x N.



1. Pourquoi une théorie des ensembles?



Il



1.3.10.- Les résultats suivants relèvent de la même famille.



Corollaire (bijections). - (i) Les ensembles N, Z, et Q sont en bijection. (ii) Les ensembles

(N) et

(N) x

(N) sont en bijection.



Démonstration. (i) Une bijection de N sur Z s'obtient directement en posant 2n H- n, 2n + 1 H- -n - 1. Ensuite, N s'injecte dans Q, tandis que Q s'injecte dans Z x Z, donc, de là, dans N x N, puis, par 1.3.9, dans N. On conclut que Q et N sont en bijection par le théorème de Cantor-Bernstein. (H) Une bijection de

(N) sur

(N) x

(N) s'obtient en posant XH-({pI2pEX},{qI2q+1EX}). 0



1.3.11.- Utilisant ici la notation AB pour l'ensemble des applications de B dans A, nous obtenons de nouvelles bijections. On notera que le théorème de Cantor-Bernstein simplifie les démonstrations en remplaçant la construction d'une bijection par celle de deux injections indépendantes. Proposition (réels).- Les ensembles

(N), IR:, NN, et {O, l}N sont deux à deux en bijection.



Démonstration. Par le théorème de Cantor-Bernstein, il suffit de construire des injections formant un cycle reliant les quatre ensembles. Or, envoyer une partie A de N sur le réel 2:iEA 3- i fournit une injection de

(N) dans IR (le choix de la base 3 plutôt que 2 garantissant l'unicité des développements considérés). Ensuite, pour x réel, notons sgn(x) l'entier 1 pour x

0 et 0 sinon, E(x) la partie entière de Ixl, et posons di (x) :== E(2ilxl). Envoyer x sur la suite (sgn(x), E(x), dl (x), d2(x), ...) définit une injection de IR dans NN. Pour 1 fonction de N dans N, notons S(f) le mot infini 1!C O )Ol!C I )Ol!C 2 )O..., où ln signifie Il...1 avec 1 répété n fois. Envoyer 1 sur la fonction de N dans {O, 1} dont la valeur en i est la iième lettre du mot S(/) définit une injection de NN dans {O, l}N. Enfin, envoyer une fonction 1 de N dans {

1} sur l'ensemble des. entiers i véri- fiant i(i) == 1 définit une injection de {O,l} dans s.p(N). 0



En composant les résultats, on déduit par exemple que le produit IR: x IR: est en bijection avec IR, puis qu'il en est de même de toute puissance finie IRn.



1.3.12.- À ce point, on peut se demander si tous les ensembles infinis sont deux à deux en bijection, c'est-à-dire s'il existe plusieurs infinis distincts. Due à Georg Cantor, la réponse, négative, est le point « zéro» de la théorie des ensembles, l'événement primordial d'où procède toute la suite.



12



1. Le type « ensemble »



Démonstration. Il suffit de montrer que l'intervalle [0,1] n'est pas en bijection avec N. Or, soit A l'ensemble des nombres réels compris entre 0 et 1 dont un développement en base 3 ne contient que des 0 et des 1, et soit f une fonction quelconque de N dans A. On montre qu'il existe au moins un réel dans A dis- tinct de chacun des réels f(O), f(l), ... et donc que f n'est pas surjective, ni a fortiori bijective. Pour cela, écrivons le développement en base 3 de f(i) sous la forme 0, ai,oai,l..., où les chiffres ai,j sont 0 ou 1. Posons a = 1, l = 0, et soit a le réel dont le développement est 0, ao,o al,l a2,2 ... . Alors, a, qui est dans A par construction, ne peut être, quel que soit i, égal à f(i), car le iième chiffre du dé- veloppement de f(i) est ai,i, alors que celui de a est ai,i , et que le développement en base 3 sans chiffre 2 est unique quand il existe. Donc, f n'est pas surjective. 0



[> Conjuguant autoréférence (ici les éléments diagonaux ai,i) et négation (ici l'application «barre»), la démonstration précédente repose sur ce qui est appelé l'argument diagonal. Le recours à la base 3 plutôt que 2 n'est là que pour pallier le défaut d'unicité du développement binaire pour les rationnels dyadiques. <]



1.3.13.- Eu égard à l'existence d'une bijection entre

et s.p(N), une autre démonstration de 1.3.12 est fournie par le résultat suivant, également dû à Cantor et reposant à nouveau sur un argument diagonal.



!



7



;



''':ih,i;\, h:;'

:,

;

'

:T;:P:{

!:j1n;

;



r



s.A.) 1)i::1iî",;1:'z:

j

8t

o:?:',!



,,:

(4 ),i;,>d(jnfj ,'A; ,', en :p,artic'ulier, 'les H?;"'ense,mbles,

i}t'>et;':W{A);).ne':s,6ntpas';:

nbijectîon

;': ' "'" '>"":;:::;;,:;;'::"';:nF<nLr

;m:;;:"!:i:;;:t::!!;:Ei;:;:;;; {)i!:;;:;;;:;;:" :"::':,'," ;'>::,: '>, :',,',' , " ; ';;

;,;ili

t. ;'7

;L

:



,; t1:;.;



j :iriJ :h;

:;J

H k;:'



;



:;;;

';>;:'h::>';;

n* 11i



.

J



i ::;_rt;;b",""L

h! !7 i>., ,;;;"i

;",*

i;;"':;

' ,>,3.iM:r;,,:,< ,,:, ,;,;"".". ....":",,, ,,"., "; :

}i:r,7:;0

;:::;

;



'..,, .,.

;;:;

:m

,,-.j



Démonstration. Soit f : A -t s,p(A) une application quelconque. Posons B := {a E A 1 a

f(a)}. Si un élément a de A est dans B, alors par définition a est dans B \ f(a), donc il est impossible que f(a) soit égal à B. D'un autre côté, si un élément a de A n'est pas dans B, alors par définition a est dans f(a) \ B donc, à nouveau, il est impossible que f(a) soit égal à B. Par conséquent, la seule possibilité est que B n'appartienne pas à l'image de f, et que f ne soit pas surjective. Il n'existe donc pas de surjection de A sur s,p(A), et donc en particulier pas de bijection de A sur s,p(A). Enfin, comme l'application a t-+ {a} définit une injection de A dans s,p(A), s'il existait une injection de s,p(A) dans A, on déduirait du théorème de Cantor-Bernstein l'existence d'une bijection de A sur s.p(A), qui ne se peut. 0



Noter que, clans le cas d'un ensemble fini de cardinal n, le théorème revient à l'inégalité 2 n > n.



1.3.14.- Le résultat de 1.3.13 est plus général que celui de 1.3.12 et, en particulier, il implique l'existence d'une infinité d'ensembles infinis deux à deux non équipotents.



1. Pourquoi une théorie des ensembles?



13



1.3.15.- Revenant à l'ensemble JR, on a vu que sa taille est strictement supérieure à celle de l'ensemble N. Parmi les sous-ensembles infinis de JR, certains sont en bijection avec N, par exemple N lui-même, d'autres sont en bijection avec JR, par exemple JR lui-même. Le problème suivant apparaît donc immédiatement.



Une réponse positive est appelée l' hypothèse du continu, abrégée en HC.



[> Soulevée par Cantor en 1878, la question est celle de l'existence de tailles intermédiaires entre celle de N (le dénombrable) et celle de IR (traditionnellement appelée le continu). Comme on va l'expliquer dans la suite de ce livre, plus de cent quarante ans après que Cantor l'a soulevé, le problème du continu reste non résolu à ce jour. On verra néanmoins qu'un grand nombre de résultats partiels ont été démontrés, et que le problème a joué un rôle fondamental dans le développement de la théorie des ensembles, dont il est le cœur. <1



1.3.16.- Le problème du continu est une question extrêmement naturelle dès que l'existence des ensembles N et JR est posée. L'important ici est qu'il répond à la question qui donne son titre à cette sous-section.



[> Bien entendu, on peut discuter du caractère bien posé ou non du problème du continu, de son importance ou non vis-à-vis du reste des mathématiques, de la signification d'une éventuelle solution : nous y reviendrons plus loin en détail. Pour le moment, on peut dans tous les cas garder en mémoire que des problèmes ardus apparaissent dès que l'on commence à comparer les tailles des ensembles infinis, et considérer que c'est une raison suffisante pour essayer d'élaborer une théorie cohérente de tels objets : la difficulté des problèmes ne garantit pas la pertinence de la théorie, mais, au moins, elle lui fournit une motivation. <1



1.3.17.- On mentionne maintenant quelques questions élémentaires sur lesquelles on reviendra au chapitre IV, et dont on verra plus loin que, contrairement au problème du continu, elles ont trouvé des solutions pou- vant être considé

ées comme optimales. D'abord, l'existence d'une bijection entre N et N x N, et entre JR et JR x JR, rend la question suivante naturelle.



Question.- Tout ensemble infini A est-il en bijection avec A x A ?



14



1. Le type « ensemble»



1.3.18.- Ensuite, s'il existe une injection f de N dans un ensemble A, alors A est nécessairement infini, car l'application envoyant f(n) sur f(n+l) pour tout n et laissant fixes les éléments hors de Im(f) est une injection non surjective de A dans lui-même. Il est naturel de considérer la réciproque.



Question. - Existe-t-il une injection de N dans tout ensemble infini?



1.3.19.- Enfin, on termine avec un problème ne mettant pas en jeu la taille des ensembles, mais simplement le fait de savoir s'ils sont vides ou non. On a utilisé ci-dessus le produit de deux ensembles Al, A 2 , défini comme ensemble des couples (al, a2) avec al E Al et a2 E A 2 . La notion s'étend naturellement à une famille quelconque d'ensembles.



Définition (produit).- Si (Ai)iEI est une famille d'ensembles, le pro- duit TIiEI Ai est l'ensemble des suites (ai)iEI vérifiant Vi (ai E Ai).



1.3.20.- Si Al, ..., An sont des ensembles non vides, le produit Al x ... x An est non vide, car, en choisissant un élément al de Al, puis un élément a2 de A 2 , et ainsi de suite jusqu'à an dans An, on obtient un n- uplet (al, ... , an) qui, par définition, est dans le produit Al x ... x An. Dans le cas d'une famille infinie (Ai)iEI, la répétition du choix d'un élément une infinité de fois est une opération d'un type différent dont la validité n'est pas claire, et l'argument précédent ne s'adapte pas.



Question.- Tout produit d'ensembles non vides est-il non vide?



Aucune des questions ci-dessus n'admet de réponse immédiate, et chacune contribue donc à motiver une étude plus avancée.



2. Opérations ensernblistes



De même que d'une notion de morphisme, chaque type d'objet mathé- matique est accompagné d'opérations et de relations qui lui sont propres. Dans le cas des ensembles, plusieurs opérations et relations s'introduisent naturellement: réunion 9, intersection, différence, inclusion, ... Dans cette brève partie, on étudie les propriétés algébriques, au demeurant simples, de ces opérations dites ensemblistes.



[> Une approche naïve pourrait faire penser que les opérations ensemblistes sont le cœur de la théorie des ensembles, et que cette dernière consiste surtout à ma- nipuler des expressions compliquées à base de U et de n. Ce n'est pas le cas: au moins dans le cas fini, les propriétés des opérations ensemblistes sont complè- tement décrites par le fait qu'elles définissent une algèbre de Boole, c'est-à-dire



9. Utilisé en anglais et plus court, le mot «union» tend souvent à remplacer « réunion», qui est traditionnel en français mais ne se justifie pas.



2. Opérations ensemblistes



15



obéissent à une certaine famille (finie) de lois algébriques explicites qui les carac- térisent de façon exhaustive, et il n'y a guère de mystères à attendre de la seule manipulation de ces opérations. Bien entendu, cela n'est pas dire que la combina- toire des ensembles finis est une affaire triviale, mais c'est dire que, d'un point de vue de théorie des ensembles, les ensembles finis n'offrent pas de grand problème: résolument, la théorie des ensembles sera une théorie des ensembles infinis... <]



Cette section comporte trois courtes sous-sections. Dans la sous-section 2.1, on observe que tout ensemble des parties a une structure de treillis, puis d'algèbre de Boole. Dans la sous-section 2.2, on axiomatise les algèbres de Boole en tant que structures algébriques. Finalement, on établit dans la sous-section 2.3 qu'inversement toute algèbre de Boole finie est de ce type, ce qui, en un sens, clôt, du point de vue de la théorie des ensembles, l'étude des ensembles finis.



2.1. Le treillis des parties d'un ensemble



Résumé.- L'inclusion est une relation d'ordre dont la restnctlon à tout ensemble

(A) est un treillis distributif et complémenté. ...



2.1.1.- Diverses relations et opérations simples dérivent directement de la relation d'appartenance: inclusion, réunion, intersection, différence, etc. On commence par rappeler les définitions usuelles.



Définition (inclusion, parties, opérations ensemblistes).- (i) Si A et B sont des ensembles, on dit que A est inclus dans B, ou encore que A est un sous-ensemble ou une partie de B, noté 10 A C B, si tout élément de B est élément de A. On note

(A) l'ensemble Il des parties de A. (ii) On pose Au B :== {x 1 x E A ou x E B}, An B :== {x 1 x E A et x E B}, A \ B :== {x E A 1 x tt: B}, A

B :== (A\B) U (B\A), différence symétrique de A et B. (iii) Si un ensemble de référence n est fixé, le complémentaire de A est défini par AC :== n \ A.



réunion de A et B, intersection de A et B, différence de A et B,



2.1.2.- On se propose d'étudier les propriétés de la relation C , ainsi que les lois algébriques auxquelles les diverses opérations ensemblistes obéissent.



Lemme.- La relation d'inclusion est une relation d'ordre.



10. La notation « ordre large» est plus cohérente que C, qui suggère un ordre strict. 11. On reviendra plus loin sur l'existence d'un tel ensemble lorsque A est infini; pour le moment, on se contente d'introduire la terminologie et d'explorer les propriétés algé- briques élémentaires des opérations dérivées.



16



1. Le type « ensemble»



AnB



B\A



A



A\B



B



AUB



FIGURE 2.- Opérations ensemblistes représentées à l'aide des dia- grammes de Venn de la figure 1.



Démonstration. La réflexivité et la transitivité sont immédiates. L'antisymétrie provient de ce qui sera appelé plus loin la propriété d'extensionnalité, à savoir l'affirmation que deux ensembles ayant les mêmes éléments coïncident. 0



2.1.3.- La notion de treillis est pertinente pour en dire davantage.



Définition (treillis, algèbre de Boole).- Un treillis est un ensemble ordonné tel que chaque paire d'éléments possède une borne supérieure et une borne inférieure. Un treillis est distributif si l'opération sup est distri- butive par rapport à l'opération inf, et vice versa; il est complémenté s'il possède un minimum 0, un maximum 1 et si, pour tout x, il existe un élé- ment xc, appelé complément de x, vérifiant sup(x, XC) = 1 et inf(x, XC) = o. U ne algèbre de Boole est un treillis distributif et complémenté.



Exemple. L'ensemble des entiers non nuls muni de la relation de divisibilité est un treillis distributif avec un élément minimum 1 mais pas d'élément maximum, et ce n'est donc pas une algèbre de Boole. En revanche, l'ensemble des diviseurs d'un entier fixé n'ayant que des facteurs premiers simples est une algèbre de Boole.



Dans une algèbre de Boole, le complément est unique (exercice 2).



2.1.4.- Le résultat suivant sur l'inclusion est alors classique.



Proposition (algèbre de Boole).- Pour tout ensemble A, l'ensem- ble

(A) muni de C est une algèbre de Boole,. l'opération sup est la réunion, l'opération inf est l'intersection, le minimum est l'ensemble vide, le maxi- mum est A, et le complément est le complémentaire.



Démonstration. U ne vérification directe est facile. Une démonstration alternative plus rapide consiste à remarquer que les algèbres de Boole sont définies par l'obéissance à des lois algébriques (voir paragraphe suivant), d'où il résulte que tout produit d'algèbres de Boole est une algèbre de Boole. Or, définissons un ordre

sur {D, 1} en posant D < 1. Alors, ({D, 1},

) est une algèbre de Boole. Maintenant, l'application F :

(A)

{D, l}A associant à



2. Opérations ensemblistes



17



toute partie X sa fonction indicatrice lx définie par lx (x) :== 1 pour x E X et lx (x) :== 0 pour x rt X induit un isomorphisme entre les structures (

(A), ç, U, n, 0, A, C) et ({O, 1},

, sup, inf, 0,1, x I--t 1 - x)IIAII. La première est donc une algèbre de Boole puisque la seconde l'est. 0



{a,b,c} { a,b } {a} { a,b } 0 l {a} {b} 0 {a} 0 0 0



{a,b,c,d}



{b,c}



{c}



FIGURE 3.- Diagramme de Hasse des algèbres de Boole (s.p(A) , C ) pour IIAII

4 : les sommets sont les éléments, et une arête (ici supposée orientée de bas en haut) relie chaque élément à ses successeurs immédiats. Comme (s.p(A) , C ) est isomorphe à ({O, 1},

) IIAII, le diagramme est un cube de dimension IIAII.



2.2. Les algèbres de Boole comme structures algébriques

Résumé.- Les algèbres de Boole sont axiomatisées par les lois algé- briques auxquelles obéissent leurs opérations sup et inf.



2.2.1.- Définie en termes de relation d'ordre, la structure de treillis peut également être caractérisée par les lois algébriques auxquelles obéissent les opérations de bornes supérieure et inférieure.



Proposition (axiomatisation 1). - (i) Supposons que (T,

) est un treil- lis. Pour a, b dans B, posons a V b :== sup( a, b) et a /\ b :== inf( a, b). Alors, la structure (T, V, /\) obéit aux lois



x V x == x (la) xVy==yVx (Il) x V (y V z) == (x V y) V z (1 2 ) x V (x /\ y) == X (13)



x /\ x == x (16) x/\y==y/\x (If) x/\(y/\z)==(x/\y)/\z (I

) x /\ (x V y) == x (I

)



De plus, a

b est équivalent à a V b == b et à a /\ b == a. (ii) Inversement, supposons que (T, V, /\) obéit aux lois (Il), (1 2 ), (1 3 ), et (If), (I

), (I

). Pour a, b dans T, notons a

b pour a V b == b. Alors, (T,

) est un treillis, et V (resp., /\) en est l'opération sup (resp., inf).



Démonstration. (i) Pour a,b,c dans T, on a sup(a, a) == a, sup(a,b) == sup(b, a) et sup(a, sup(b, c)) == sup(a, b, c), donc sup(a, sup(b, c)) == sup(sup(a, b), c). De plus, a

b équivaut à sup( a, b) == b, et à inf( a, b) == a. Comme on a toujours a

sup(a, b), on a donc inf(a, sup(a, b)) == a, et de même, inf(a, b)

a entraîne sup(a, inf(a, b)) == a. Les lois (la), (Il), (12), (13) et (I

) sont donc obéies, et (16), (If) et (I

) sont obtenues par un argument symétrique.



18



1. Le type « ensemble »



(ii) Notons d'abord que les opérations V et /\ sont idempotentes, c'est-à-dire que les lois (la) et (Ih) sont conséquences de (Il), ..., (1 3 ). Soit a quelconque. Par (13) et (1 3 ), nous avons a == a V (a /\ (a Va)) == a V a, et aussi a /\ (a V (a /\ a)) == a /\ a. On montre d'abord que

est une relation d'ordre. On a en effet a V a == a pour tout a dans T, donc a

a, et

est réflexive. Supposons a

b et b

a. Appliquant la commutativité de V, on obtient a == b V a == a V b == b, et

est antisymétrique. Supposons a

b

c. Appliquant l'associativité de V, on obtient a V c == a V (b V c) == (a V b) V c == b V c == c, donc a

c, et

est transitive. Montrons ensuite que l'élément a V b est borne supérieure de a et b vis-à-vis de

. D'abord on a a V (a V b) == (a Va) V b == a V b, donc a

a V b, et b V (a V b) == b V (b Va) == (b V b) Va == b Va == a V b, donc b

a V b, et a V b est un majorant commun à a et b. Supposons ensuite que c est un majorant commun à a et b. On a donc a V c == c et b V c == c, donc (a V b) V c == a V (b V c) == a V c == c, soit a V b

c, et on conclut que a V b est le plus petit de tous les majorants communs à a et b. Montrons maintenant que a

b, c'est-à-dire a V b == b, est équivalent à a /\ b == a. Supposons aVb == b. Par (I

), nous avons alors a/\b == a/\(aVb) == a. Inversement, supposons a/\b == a. Par (12) et (14), nous avons aVb == (a/\b)Vb == bV(b/\a) == b. Dès lors que V et /\ jouent des rôles symétriques par rapport à l'ordre

, le rai- sonnement montrant que a V b est borne supérieure de a et b montre ipso facto que a /\ b est borne inférieure de a et b, et on conclut que (T,

) est un treillis. 0



2.2.2.- Il existe une semblable axiomatisation pour les algèbres de Boole.



Proposition (axiomatisation II).- (i) Supposons que (B,::() est une algèbre de Boole de minimum 0 et de maximum 1. Pour a, b E B, po- sons a V b :== sup(a, b), a /\ b :== inf(a, b), et notons a l'unique élément vérifiant a V a == 1 et a /\ a == o. Alors, (B, V, /\,0,1, -) obéit aux lois (la), ... , (1 3 ) de 2.2.1 et, de plus, x V (y /\ z) == (x V y) /\ (x V z), (14) X /\ (y V z) == (x /\ y) V (x /\ z), (I

) x V 0 == x, x V 1 == 1, (1 5 ) x /\ 0 == 0, x /\ 1 == x, (I

) x V fi == 1, (1 6 ) x /\ fi == O. (I

) (ii) Inversement, supposons que (B, V, /\, 0,1, -) obéit aux lois (Il), ..., (I

). Notons a ::( b pour a V b == b. Alors, (B,::() est une algèbre de Boole, V (resp., /\) est l'opération sup (resp., inf) associée, 1 (resp., 0) est le maxi- mum (resp., le minimum). Démonstration. D'abord (B,

) est un treillis, donc les lois (10),..., (1 3 ) sont obéies dans B, et, réciproquement, dès lors que (Il),..., (1 3 ) sont obéies, on sait par 2.2.1 que (B,

) est un treillis. Ensuite, (14) et (I

) traduisent directement le fait que le treillis est distributif, (15) et (I

) traduisent le fait que 0 est minimum et 1 est maximum, et (16) et (I

) le fait que ii est un complément pour a. 0



De là, on appelle algèbre de Boole aussi bien un treillis distributif et COffi- plémenté qu'une structure (B, V, /\,0,1, -) obéissant aux lois (la), ..., (I

).



2. Opérations ensemblistes



19



2.2.3.- On conclut avec une autre caractérisation des algèbres de Boole, à nouveau à l'aide de lois algébriques, mais dans le langage des anneaux.



Définition (anneau de Boole).- On appelle anneau de Boole un anneau commutatif et idempotent, c'est-à-dire un anneau dont la multiplication est commutative et où, pour tout x, on a x 2 = x.



2.2.4.- Il est facile de vérifier que, pour tout ensemble A, l'ensemble $(A) muni des opérations 6. et n est un anneau de Boole. Ce résultat est un cas particulier du résultat général d'équivalence entre algèbre de Boole et anneau de Boole. La démonstration est une vérification facile (exercice 7).



Proposition (équivalence).- (i) Si (B, V, A, 0,1, -) est une algèbre de Boole, alors, si l'on pose a 6. b := (a A b) V (a A b), la structure (B, 6., A) est un anneau de Boole. (ii) Inversement, si (B, +,.) est un anneau de Boole, alors, si l'on po- se aVb:= a+b+ab, aAb:= ab, et a:= l+a, la structure (B, V,A,O, 1,-) est une algèbre de Boole.



2.3. Algèbres de Boole finies

Résumé.- Toute algèbre de Boole finie est isomorphe à une algèbre du type (

(A), C ).



2.3.1.- On a vu en 2.1.4 que toute structure du type (

(A), C ) est une algèbre de Boole. On va maintenant établir une réciproque partielle en montrant que toute algèbre de Boole finie est isomorphe à une algèbre du type (

(A), C ), obtenant ainsi une axiomatisation complète des opérations ensemblistes dans le cas fini. Le point de départ est la notion d'atome.



Définition (atome).- Si

est une relation d'ordre sur un ensemble A possédant un minimum 0, un atome de (A,

) est un successeur immédiat de 0, c'est-à-dire un élément a de A vérifiant 12 0 < a, mais tel qu'il n'existe pas d'élément b vérifiant 0 < b < a.



2.3.2.- On peut alors établir le résultat de représentation des algèbres de Boole finies comme algèbres de parties d'un ensemble. 1> Dans une algèbre de Boole de type (S;P(A), Ç), les atomes sont les singletons, et, par conséquent, tout élément est réunion, c'est-à-dire borne supérieure, d'atomes. Si toute algèbre de Boole finie est isomorphe à une algèbre de type S;P(A) , tout élément doit

tre borne supérieure d'atomes, ce qui rend la démonstration ci- dessous naturelle. <]



12. Où a < b signifie « a

b et a =/:. b », voir convention 11.1.1.3 au chapitre II.



20



1. Le type « ensemble »



Proposition (algèbres de Boole finies). - Toute algèbre de Boole finie est isomorphe à une algèbre du type (

(A), C ).



Démonstration. On suppose que (B, V, A, 0,1, -) est une algèbre de Boole finie. Soit A l'ensemble des atomes de B (dont on ne sait pas a priori s'il est non vide). On définit F : B



(A) par F(b) = {a E A 1 a

b}. On va montrer que F établit l'isomorphisme cherché de (B, V, A, 0,1, -) sur (

(A), u, n, 0, A,C). Notons déjà que, par construction, on a F(O) = 0 et F(l) = A. Montrons d'abord que b =1= 0 entraîne F(b) =1= 0. En effet, soit (bo = b, bl, b2, .,,) une chaîne strictement décroissante partant de b et de longueur maximale. Les éléments bi sont deux à deux distincts, donc la longueur de la chaîne est au plus le cardinal de B. Il existe donc n vérifiant b n = O. L'élément bn-l, qui est un minorant de b par construction, est alors un atome de B. En effet, s'il existait c vérifiant 0 < c < bn-l, la chaîne (bo, bl, ... , bn-l, c, b n ) contredirait la maximalité de (bo, bl, ..., bn-l, b n ). Soit b quelconque dans B. Soit a un atome. Si a minorait à la fois b et b, il minorerait b A b, qui est 0, ce qui est impossible, donc F(b) et F(b) sont disjoints. D'un autre côté, supposons a rt F(b), c'est-à-dire a 1:. b. On a a A b

a et a A b =1= a (sinon on aurait a

b), donc, par définition d'un atome, a Ab = O. On obtient a = a A 1 = a A (b V b) = (a A b) V (a A b) = 0 V (a A b) = a A b, donc a

b. Par conséquent, a rt F(b) entraîne a E F(b), et on déduit F(b) = F(b)c. Soient b et c quelconques dans B. Par définition de la borne inférieure, un atome minore bAc si, et seulement si, il minore b et minore c, d'où F(bAc) = F(b) nF(c). Appliquant cela à b et ë, ainsi que l'égalité F(x) = F(x)C, nous obtenons F(b V c) = F( b V c )C = F(b A c)C = (F(b) n F(c))C = F(b)C U F(c)C = F(b) U F(c). À ce point, on a donc montré que F est un homomorphisme de (B, V, A, 0,1, -) dans (

(A), u, n, 0, A, C). Il reste à montrer que F est bijectif. Soient b et c deux éléments distincts de B. L'une au moins des deux relations b

c, c

b est fausse. Supposons par exemple b 1:. c, donc b =1= bAc. Comme on a b = bAl = bA(cVc) = (bAc)V(bAc), on doit avoir bAc =1= 0, donc F(b A c) =1= 0. Il existe donc un atome a minorant b et c, donc ne minorant pas c, c'est-à-dire appartenant à F(b) et non à F(c) : ces ensembles sont donc distincts, et F est injectif. Finalement, soit X un sous-ensemble quelconque de A. Puisque B est fini, A l'est aussi, et on peut écrire X = {al, ...,an}. Posons b = al V... Van (comme V est une opération associative, il n'y a pas d'ambiguïté à supprimer les parenthèses). Soit a un atome quelconque. La distributivité de A vis-à-vis de V implique l'éga- lité a A b = (a A al) V ". V (a A an) : si a est l'un des ai, on obtient a A b = a, soit a

b, ou a E F(b) ; sinon, on obtient a A b = 0, donc a rt F(b). On déduit donc F(b) = X, et F est surjective. 0



2.3.3.- Le résultat de 2.3.2 montre que la notion d'algèbre de Boole cap- ture toutes les propriétés des ensembles

(A) finis: tant que seuls des ensembles finis sont considérés, les lois de 2.2.2 caractérisent complètement les opérations ensemblistes. Il clôt la partie élémentaire de la théorie des ensembles, celle qui se concentre sur les manipulations de la réunion, d'in- tersection et de complémentaire dans le cas fini, et il explique que la partie non triviale de la théorie concerne l'étude des ensembles infinis.



[> La situation est complètement différente avec les algèbres de Boole infinies: un théorème de Stone affirme que toute algèbre de Boole se plonge dans l'algèbre des parties d'un ensemble mais, en général, le plongement n'est pas un isomorphisme et, par exemple, le quotient de

(N) par l'idéal des ensembles finis est une algèbre de Boole infinie extrêmement compliquée, très éloignée d'une algèbre

(A). <]



3. Ébauche d'une théorie des ensembles



21



2.3.4.- Pour terminer, signalons encore l'existence d'autres opérations élé- mentaires sur les ensembles (finis) qui sont bien adaptées à des contextes particuliers, comme le produit de jointure : partant d'une famille d' en- sembles (Zi)iEI et de X := TIiEJ Zi et Y := TIiEK Zi où J et K sont deux sous-ensembles fixés de l, et notant t f S la restriction à S d'une fonction t définie sur J U K, on introduit pour A C X et B C Y A[X)B:= {t E TIiEJUKZi 1 tfJ E A et tfK E B}. (#1) La jointure étend à la fois l'intersection, qui correspond au cas J = K, et le produit cartésien, qui correspond au cas où J et K sont disjoints, et c'est une opération utile pour l'analyse des bases de données (voir exercice 42).



3. Ébauche d'une théorie des ensembles



On a commencé à développer dans les sections précédentes quelques résul- tats et démonstrations concernant les ensembles, mais sans avoir introduit ceux-ci autrement que de façon très informelle. Si l'on veut progresser et développer une théorie élaborée, il est nécessaire de fixer un point de dé- part plus formel, et c'est le but de cette section. Comme il est difficile de définir les ensembles, on recourt à une démarche axiomatique fondée sur les principes d'extensionnalité et de compréhension. Mais la rencontre des paradoxes oblige à refaire le long chemin qui mène au système de Zermelo, point de départ pour la suite du voyage.



[> L'analyse au demeurant restera incomplète, dans la mesure où elle nous mènera à considérer une famille d'ensembles particuliers, les ensembles purs, dont il n'est pas évident que l'étude soit pertinente. Ce sera la tâche des chapitres II et III de montrer que la restriction aux ensembles purs ne limite pas le champ d'application de la théorie, et de légitimer ainsi les options prises dans ce chapitre. <]



Cette section est organisée en cinq sous-sections. Dans la sous-section 3.1, on constate la difficulté de définir naïvement et de façon satisfaisante les ensembles à partir d'autres objets. On passe donc dans la sous-section 3.2 à une axiomatisation basée sur le principe cantorien des définitions par compréhension. Dans la sous-section 3.3, on explique le paradoxe de Berry, qui oblige à restreindre les définitions au cadre d'une logique formelle. Dans la sous-section 3.4, on aborde à son tour le paradoxe de Russell, qui oblige à une nouvelle restriction du cadre. Finalement, on expose le système de Zermelo dans la sous-section 3.5.



3.1. Une tentative naïve



Résumé.- Tenter de définir les ensembles à partir de fonctions indi- catrices tou rne cou rt. .....



22



1. Le type « ensemble »



3.1.1.- Comme pour n'importe quel autre type d'objet mathématique, il est naturel de débuter une théorie des ensembles par une définition des ensembles -et, de fait, c'est l'option prise dans la plupart des langages de programmation. On essaie donc de définir les ensembles en s'appuyant sur d'autres objets supposés plus fondamentaux.



3.1.2.- De façon intuitive et pragmatique, les objets mathématiques re- lèvent de types divers : entiers, points, droites, fonctions, etc. Dans une ap- proche élémentaire, et notamment dans les langages de programmation, les ensembles n'apparaissent pas comme un type de base unique, mais plutôt comme des types dérivés: pour chaque type mathématique T, on introduit un nouveau type Ens r formé par les ensembles d'objets de type T. [> De la même façon, s'introduisent d'autres types voisins comme les suites (ana- logues aux ensembles, mais en tenant compte de l'ordre des facteurs), ou les multi- ensembles (analogues aux ensembles, mais en tenant compte des répétitions). <]



3.1.3.- On cherche donc à définir, pour chaque type T, un type Ens r . Or, il est usuel d'associer à tout ensemble une fonction indicatrice à valeurs dans {O, 1} et une approche naturelle est de définir les ensembles à partir des fonctions. Si le type « fonction» est présent, précisément si, pour chaque paire de types T, T', il existe un type T

T' formé des fonctions allant des objets de type T vers les objets de type T', alors on peut identifier les ensembles à des fonctions indicatrices: se donner un ensemble A d'objets de type T, c'est spécifier, pour chaque objet x de type T, si x est ou non dans A, donc se donner une fonction associant à tout objet de type T soit la valeur VRAI, soit la valeur FAUX.



3.1.4.- Utilisant la notation X:T pour indiquer qu'un objet x est de type T, et notant Booi (comme booléen) le type constitué de ces deux seules valeurs VRAI et FAUX, il est donc naturel de poser la définition suivante.



« Définition» (ensemble).- Pour tout type T, le type T

Bool est noté Ens r ; les objets de type Ens r sont appelés ensembles d'objets de type T. Pour x de type T, et A de type Ens r , on dit que x est élément de A, noté x Er A, si l'on a A(x) == VRAI.



3.1.5.- On peut alors commencer à établir des propriétés des ensembles, et en particulier montrer qu'ils obéissent aux principes informels dégagés dans la première partie de ce chapitre.



« Proposition» (ensembles). - (i) Un objet de type Ens r est déterminé par ses éléments. (ii) Pour tous al, ..., an de type T, il existe un objet de type Ens r ayant pour éléments al, ... , an. (iii) Pour chaque propriété P(X:T) des objets de type T, il existe un objet de type Ens r dont les éléments sont les objets de type T satisfaisant P.



3. Ébauche d'une théorie des ensembles



23



Démonstration. Le point (i) découle de ce que le type Bool ne contient que deux valeurs: si deux ensembles A, A' ont les mêmes éléments, on a A(x) = A' (x) = VRAI pour tout x de type r appartenant à A, et donc A(x) = A'(x) = FAUX pour tout autre x de type r. Les fonctions A et A' coïncident donc (pour autant que deux fonctions prenant les mêmes valeurs partout coïncident). Pour (ii), on définit un objet A de type Ens r en posant A(al) = ... = A(a n ) = VRAI, et A(x) = FAUX pour tout autre objet x de type r. Pour (iii), on définit de même A:r--+Booi par A(x) = VRAI si P(x) est vraie, et A(x) = FAUX sinon. 0



3.1.6.- On doit bien sentir que ce qui précède n'est pas satisfaisant, en tout cas pas suffisant. Même formellement acceptable, la définition de 3.1.4 ne fait que reporter la définition des ensembles sur celle des fonctions, qui n'est pas donnée -et, si l'on se rappelle qu'une fonction est souvent définie comme ensemble de couples, on sent poindre le cercle vicieux. De même, les démonstrations de 3.1.5 ne sont que des vérifications de la cohérence du vo- cabulaire: faute d'avoir indiqué comment spécifier une fonction, l'existence des fonctions mentionnées n'est en rien établie. C'est une fausse piste!



3.2. Le système de Cantor

Résumé.- Suivant l'approche de Cantor, on axiomatise les ensembles par les axiomes d'extensionnalité et de compréhension. ......



3.2.1.- À défaut de définir les ensembles, on va chercher à les axiomati- ser, c'est-à-dire à recenser une liste de principes de base qu'une intuition partagée et un consensus recommandent de tenir pour pertinents et vrais. [> Le problème rencontré ci-dessus est usuel : qu'il s'agisse de débuter l' arithméti- que, la géométrie, ou toute autre théorie concernant des objets basiques, on bute sur la définition des objets premiers. Or, même si la nature en soi des objets mathématiques peut être importante pour le philosophe, elle n'influe pas direc- tement sur les démonstrations et ne concerne donc que peu le mathématicien : peu importe ce que sont les nombres entiers, ce qui lui importe pour établir de nouveaux théorèmes est de savoir comment ils se comportent, c'est-à-dire quelles en sont les propriétés. On peut donc se contenter d'une approche axiomatique, consistant, à défaut de définir les objets que l'on souhaite étudier, à en énumérer des propriétés de base, puis à déduire de celles-ci, utilisées comme axiomes, des conséquences nouvelles. On sait par exemple que le système de Peano constitue un point de départ raisonnable pour l'arithmétique, tout comme le système d'Euclide en constitue un pour la géométrie élémentaire du plan. <]



3.2.2.- Soit donc à développer ce type d'approche axiomatique pour les ensembles. Dans un premier temps, il s'agit de recenser les propriétés de base des ensembles, celles qui seront retenues comme axiomes. On revien- dra dans la section XV.3 sur les questions délicates de choix d'axiomes - questions qui ne peuvent faire l'objet que de consensus et non de démons- trations- mais, pour le moment, il est aisé de débuter en s'appuyant sur l'analyse effectuée dans la première section du chapitre, qui assigne aux ensembles deux types de principes de base (ceux-là même que l'on avait tenté de démontrer en 3.1.5) : le premier est un principe d'unicité, à savoir



24



1. Le type « ensemble »



qu'un ensemble est déterminé par ses éléments; le second est un principe d'existence, à savoir que l'on peut spécifier un ensemble soit en énumérant ses éléments, soit en donnant une propriété caractéristique de ceux-ci.



Définition (extensionnalité, extension, compréhension, système de Cantor).- On appelle axiome d'extensionnalité pour les objets de ty- pe Tl' assertion VA, A':Ens r (A == A' {:> VX:T (x E A {:> x E A')). (Ext r ) Pour n

1, on appelle axiome d'extension (de taille n) l'assertion Val, ..., an:T 3A:Ens r VX:T (XEA{:>(x==alou...oux==a n )). (Exsn,r) Si P(x) est une propriété pertinente pour les objets de type T, on appelle axiome de compréhension pour P l'assertion 3A:Ens r VX:T (x E A {:> P(x) est vraie). (Compp,r) On appelle système de Cantor pour le type T le système formé de tous les axiomes d'extensionnalité, d'extension, et de compréhension relatifs à T.



3.2.3.- En présence de (Ext r ), les ensembles dont (Exsn,r) et (Compp,r) af- firment l'existence sont notés, ainsi que déjà dit, respectivement {al, ..., an} et {X:T 1 P(x)} (Figure 4). On peut s'affranchir des axiomes d'extension, mentionnés seulement pour suivre l'usage: une définition par extension est un cas particulier de définition par compréhension puisque, pour al, ... , an de type T, on a {al,,,., an} == {X:T 1 x == al ou ... ou x == an} .



{al, ..., an}



o



P(X) fausse



o {x 1 P(x)}



FIGURE 4.- Deux façons usuelles de spécifier un ensemble : par ex- tension, en énumérant les éléments (supposés en nombre fini), et par compréhension, en donnant une propriété caractéristique des éléments.



3.2.4.- L'idée à ce point est donc de poser que, pour chaque type T, les objets de type Ens r obéissent aux axiomes d'extensionnalité, (d'extension) et de compréhension, et d'étudier les conséquences de ces axiomes.



3.3. Le paradoxe de Berry

Résumé.- Le paradoxe de Berry rend le système de Cantor intenable. Dans le système de Frege, on restreint la compréhension aux propriétés expri ma bles formellement. ......



3. Ébauche d'une théorie des ensembles



25



3.3.1.- Le système de Cantor n'est pas tenable: le résultat suivant, qui est une variante due à G. Berry d'un énoncé de J. Richard, montre qu'il postule l'existence d'objets contradictoires.



Démonstration. Notons Ent le type « nombre entier » (que toute théorie raison- nable doit inclure), et soit A l'ensemble {n:Ent 1 Pen)}, supposé exister. Il n'y a, en comptant les blancs, qu'au plus 27 100 phrases françaises d'au plus 100 carac- tères, et chaque telle phrase ne définit qu'au plus un entier, puisque dire qu'une phrase définit n signifie que n est le seul entier satisfaisant la propriété exprimée. L'ensemble A a donc au plus 27 100 éléments, et son complémentaire est non vide. L'ordre des entiers est un bon ordre, c'est-à-dire que tout ensemble non vide d'en- tiers possède un plus petit élément (cf. chapitre II), et donc le complémentaire de A possède un plus petit élément, soit no. Puisqu'il n'appartient pas à A, l'en- tier no est non définissable par une phrase française d'au plus 100 caractères. Mais «je suis le plus petit entier non définissable par une phrase française d'au plus cent caractères» est une définition pour no, qui comporte 96 caractères. Cette contradiction montre que l'hypothèse que A existe est à rejeter. 0



3.3.2.- Puisqu'il postule l'existence d'objets impossibles, le point de dé- part qui a été appelé système de Cantor ne peut être conservé, et on est donc amené à le modifier en espérant échapper aux contra

ictions.



[> Renoncer à considérer des ensembles d'entiers est difficile, dans la mesure où le type « entier» est l'un des premiers pour lequel on souhaite construire des ensembles. Renoncer aux définitions par compréhension, et se cantonner aux défi- nitions par extension, est une solution drastique 13 qui ôte à la notion d'ensemble l'essentiel de son intérêt mathématique. Ne reste donc qu'à restreindre le champ des propriétés permises. On sent bien que le paradoxe de Berry tient à ce que la propriété « être définissable par une phrase française d'au plus cent caractères» n'est pas une propriété mathématique en ce qu'elle fait appel à la notion de phrase française, laquelle ne correspond à aucune définition précise. La solution natu- relle est de restreindre le champ de la compréhension à des propriétés exprimables dans un langage assez souple pour laisser le plus de richesse d'expression possible, mais assez restrictif pour échapper au paradoxe de Berry. Par exemple, on tient à l'existence d'un ensemble des entiers qui sont somme de deux carrés. Or, une différence claire entre les propriétés «être définissable par une phrase française d'au plus cent caractères» et « être somme de deux carrés » est que la seconde s'exprime par la formule 3p, q (n = pxp + qxq), (#2) là où une traduction de la première est problématique. L'idée est de se restreindre désormais aux propriétés exprimables par des formules du type (#2). <]



13. C'est plus ou moins le point de vue des langages de programmation impératifs.



26



1. Le type « ensemble »



3.3.3.- Il existe de nombreuses logiques formelles (voir partie B), et donc de nombreuses options sont possibles à ce stade. Pour le moment, on ne va pas entrer dans une discussion précise, mais simplement délimiter un peu le contexte, les définitions formelles étant renvoyées au chapitre VII.



[> Ce qui importe ici est de savoir quelles formules peuvent

tre légitimement utilisées dans des définitions par compréhension. Le principe retenu est de faire appel aux formules dites du premier ordre à un seul type d'objet. Ces formules sont essentiellement les formules mathématiques usuelles, écrites avec des variables et des quantificateurs divers, soumises à quelques contraintes additionnelles que l'on va décrire maintenant. <]



3.3.4.- Le cadre consiste à fixer une liste de symboles (<< signatv,re ») re- présentant des types, et des opérations et des relations susceptibles de relier des objets de ces types, puis à définir inductivement des formules comme des suites finies de symboles qui sont soit des variables avec indication de type, soit des opérations et relations, soit le signe =, soit des connecteurs logiques (non, et, ou, *, {:}), des quantificateurs (3, V), ou des parenthèses.



[> Les règles de construction seront données (ou rappelées : il s'agit ni plus ni moins des usages mathématiques) plus loin. Il est suffisant ici de mentionner que ((V ==== n)))( + + 01 x p2 =>=> n'est pas une formule, parce que les symboles n'y sont pas assemblés dans un ordre correct, alors que Vn:Ent 3p, q:Ent (n == pxp + qxq) (#3) en est une vis-à-vis de la signature LI comportant un unique type d'objet Ent, et deux symboles d'opération binaires + et x. On notera que la formule (#3) est considérée comme légitime alors que la pro- priété qu'elle exprime est fausse : il existe des entiers qui ne sont pas somme de deux carrés. On rencontre là une distinction importante dans la partie B, à savoir qu'une formule est un objet syntaxique (un mot), et que l'éventuelle valeur de vé- rité qui peut lui

tre attachée n'apparaft qu'avec un contexte extérieur d'évaluation non inscrit dans la formule: par exemple, (#3) reçoit la valeur FAUX lorsque Ent est le type «entier», et que + et x réfèrent à l'addition et à la multiplication des entiers. En revanche, on pourra vérifier que la même formule (#3) reçoit la valeur VRAI lorsque Ent réfère aux types «complexe» ou «entier modulo 5 », et + et x aux opérations usuellement associées. <]



3.3.5.- On parle spécifiquement de formules du premier ordre lorsque les seules variables portent sur les éléments des types déclarés dans 2:, à l'exclusion des ensembles de tels éléments.



[> Par opposition, on parle de formules du second ordre lorsque sont autorisées des variables et des quantifications de type T et Ens r et l'usage de Er, du troisième ordre si de m

me on autorise T, Ens r , EnsEns r pour chaque type T de L, etc. Par exemple, la formule (#3) est du premier ordre par rapport à la signature LI, alors que la formule 14 VA:EnSEnt ((0 E A et Vn: