Ce chapitre constitue un premier contact avec la notion d'ensemble.
A la section 1 on donne un très bref aperçu historique sur la façon dont les ensembles ont été perçus au cours des âges. Ce qu'on pourrait appeler la préhistoire de la théorie des ensembles commence avec Euclide (IIIème Siècle av. J.C.) et finit avec Dedekind (1831-1916), en passant par quelques précurseurs comme Leibniz, Bolzano et Riemann.
Dans la section 2 on essaie de formaliser de façon maladroite ce qu'on appelle de nos jours la théorie naïve des ensembles. On introduit le vocabulaire, les notations et les opérations usuelles : intersection, réunion, complémentaire, ensemble des parties d'un ensemble. On définit dans ce cadre les notions d'application, injection, surjection, bijection.
La section 3 est consacrée à une étude plus particulière des ensembles finis, qui longtemps ont été considérés comme les seuls ensembles admissibles. On les présente de façon totalement intuitive avant de dégager la notion de cardinal et les quelques propriétés qui y sont liées. On observe comment opèrent les notions d'injection, surjection, bijection dans le cas fini, et on retrouve de façon un peu plus systématique le principe des tiroirs et le lemme des bergers qui ont été évoqués dans l'introduction.
Ce chapitre pourrait très bien s'intituler L'histoire de Georg Cantor, puisque c'est à ce grand mathématicien allemand, né à Saint-Petersbourg en 1845 et mort à Halle en 1918, que sont dus la plupart des résultats qui y sont présentés. Toutefois, suivre à la lettre l'ordre historique aurait probablement posé des problèmes techniques et de commodité de présentation. Nous avons donc choisi de commencer par examiner les toutes premières propriétés de l'infini avec nos mots à nous, et de reporter au chapitre suivant la description historique de ces grandes découvertes.
Dans la section 1 on donne la définition de l'infini actuel selon Dedekind, ainsi que quelques caractérisations. On rappelle les définitions naïves des ensembles ℕ, ℤ , 𝔻, ℚ, ℝ, ℂ, et on profite de l'occasion pour discuter de façon informelle du statut de la notion de fonction.
A la section 2 on découvre l'existence de deux sortes d'infinis : le dénombrable et le continu. Un ensemble est dénombrable s'il peut être mis en bijection avec ℕ. On montre que ℤ et ℚ sont dénombrables, ainsi que l'ensemble des nombres algébriques. Par contre ℝ n'est pas dénombrable, et on va voir que ce phénomène s'inscrit dans une généralité. En attendant, l'existence de deux ou plusieurs sortes d'infinis nous incite à donner une définition naïve de la cardinalité dans le cas infini.
La section 3 est consacrée au célèbre théorème de Cantor-Bernstein, dont on donne 2 démonstrations élémentaires, ainsi que 2 applications fondamentales : ℝ est en bijection avec ℝ² (il y a en un certain sens autant de points sur une droite que dans le plan), et aussi avec l'ensemble des parties de ℕ.
A la section 4 on démontre le théorème de Cantor, qui dit que pour tout ensemble X on a Card(𝓟(X))>Card(X) . Cet état de fait nous donne une autre démonstration de la non-dénombrabilité de ℝ, et prouve l'existence d'une infinité de sortes d'infinis. Mais le théorème de Cantor-Bernstein nous conduit à hiérarchiser l'infini en décrétant que Card(X)≤Card(Y) ssi il existe une injection de X dans Y . Se posent alors 2 problèmes : celui du continu et celui de la totalité de l'ordre sur les cardinaux.
La section 5 est consacrée à prouver que, pour l'essentiel, ce dernier problème revient à se poser la question de l'existence d'un bon ordre sur tout ensemble. On y dégage la notion d'ensemble bien ordonné, et on définit naïvement ce qu'est un ordinal, avant de donner quelques exemples. On termine cet exposé en constatant que la théorie naïve ainsi construite est contradictoire, à cause du paradoxe de Burali-Forti, ce qui semble imposer une certaine nécessité à la méthode axiomatique.
Dans ce chapitre on abandonne définitivement la théorie naïve pour tenter de donner les premiers rudiments de ce que pourrait être une axiomatisation effective de la théorie des ensembles. L'essentiel de l'exposé consiste en une démonstration informelle du fait que la méthode choisie ici est la bonne.
Dans la section 1, on montre qu'il est impossible de définir correctement le mot ensemble et on se résout, à défaut d'une définition rigoureuse, à essayer de cerner les ensembles à travers ce qui semble être leurs propriétés.
La section 2 est consacrée à un bref historique de la théorie des ensembles moderne. On raconte en quelques lignes l'histoire du mathématicien allemand Georg Cantor qui, pour avoir enfin donné un vrai visage à l'infini actuel, peut être considéré comme le grand précurseur de cette théorie. Puis on explique très rapidement comment la découverte magistrale de Cantor concernant l'existence de plusieurs sortes d'infinis, ainsi que les problèmes qui en ont résulté, ont peu à peu incité les mathématiciens de cette époque à envisager une axiomatisation progressive de la théorie des ensembles.
Dans la section 3 on essaie de développer une axiomatique primaire basée sur des observations courantes : deux ensembles sont égaux si et seulement si ils ont les mêmes éléments (c'est l'axiome d'extensionnalité), et d'autre part un ensemble paraît bien n'être rien d'autre que la collection des éléments x qui vérifient une certaine propriété P(x) (schéma de compréhension). On se heurte alors inévitablement à 2 écueils : d'abord le paradoxe de Berry (le plus petit entier qui n'est pas définissable en moins de quarante mots) nous montre qu'il va falloir développer une logique formelle pour préciser clairement la notion de propriété. Ensuite le paradoxe de Russel (le barbier du village rase tous les hommes qui ne se rasent pas eux-mêmes) nous incite à restreindre le schéma de compréhension.
A la section 4 on évoque le désir de construire une axiomatique avancée dans laquelle les axiomes écrits devront obéir à certaines règles syntaxiques, et où le schéma de compréhension (appelé aussi, dans ce cas, schéma de séparation) sera restreint aux sous-ensembles d'un ensemble donné a priori. S'impose alors la nécessité d'introduire de nouveaux axiomes pour permettre la construction d'ensembles ex nihilo.
Enfin, à la section 5 on donne un rapide aperçu du plan des chapitres suivants, et on montre en particulier comment on va introduire au fur et à mesure les nouveaux axiomes dont on a besoin.
Le but de ce chapitre est de présenter un cadre logique formel adéquat pour faire de la théorie des ensembles. On a vu au Chapitre 3 (paradoxe de Berry) qu'une partie des ennuis auxquels on est confrontés quand on essaie de faire une théorie axiomatique simplifiée des ensembles provient du fait qu'on n'a pas défini clairement la notion de propriété. Il s'agit donc de donner un sens à la formule ϕ(x) , et d'expliquer ce que signifie ϕ(x) est vraie quand on remplace x par tel ou tel objet.
A la section 1 on précise quelles sont nos exigences par rapport à une logique formelle. Il y a essentiellement 3 points : adéquation des règles énoncées avec l'intuition que l'on a acquise de par la pratique mathématique usuelle, cohérence de la logique (que les règles ne permettent de démontrer que des propriétés universellement vraies) et, ce qui est plus difficile à réaliser, la propriété de complétude : qu'une propriété vraie dans tous les modèles d'une théorie T admette une démonstration à partir des axiomes de T et des règles élémentaires de la logique considérée. Il existe plusieurs méthodes pour réaliser nos exigences, selon le type de quantifications que l'on s'autorise. Nous en présentons essentiellement trois dans cet ouvrage (dont deux dans ce chapitre), en allant de la plus simple à la plus sophistiquée.
La section 2 est consacrée au calcul propositionnel. On décrit rapidement le langage, puis les règles de constitution des formules. C'est là l'aspect syntaxique. Le côté sémantique consiste en la satisfaisabilité et en l'universelle validité d'une formule. On propose ensuite une axiomatisation du calcul propositionnel, couplée avec des règles de démonstration. Les nouvelles formules obtenues par application stricte de ces règles sont appelées des théorèmes. On montre que tout théorème est une tautologie (ou formule universellement valide), ce qui prouve au passage la cohérence (en anglais : soundness) du calcul propositionnel, puis on donne quelques exemples canoniques de tautologies. On termine par l'énoncé du théorème de complétude, dont la démonstration est reportée au Chapitre 14.
A la section 3 on découvre les bases du calcul des prédicats du premier ordre. La syntaxe y est plus complexe que dans le cas du calcul propositionnel. Il faut d'abord définir le langage. En plus des symboles logiques habituels (connecteurs et quantificateurs), ce dernier comporte des symboles spécifiques à chaque théorie : symboles de constante, de fonctions et de relations. Viennent ensuite les termes, qui sont les objets sur lesquels va porter notre étude, puis la notion générale de formule. Dans chaque formule interviennent un certain nombre de variables, dont certaines sont libres et d'autres liées. Une formule sans variable libre est appelée un énoncé, ou une formule close, et une théorie est un ensemble (fini ou infini) d'énoncés. Du point de vue de la sémantique, une structure, ou réalisation du langage, est un ensemble non vide sur lequel on a privilégié certains éléments, fonctions et relations qui vont servir d'interprétations aux symboles du langage. On est alors en mesure de définir la satisfaction des formules dans une structure. Un modèle d'une théorie T sera une structure dans laquelle tous les axiomes de T sont satisfaits. On précise alors le vocabulaire de base de la théorie des modèles, puis on donne les principes de démonstration en logique du premier ordre : il y a des tautologies, des axiomes logiques, des axiomes extra-logiques et des règles. Cette section se termine par l'énoncé du théorème de complétude, et par quelques exemples de théories axiomatiques.
Enfin, à la section 4 on donne, à titre de complément, une introduction à la logique intuitionniste, variante de la logique classique dans laquelle on refuse la loi du tiers exclu, ou, ce qui revient au même, le raisonnement par l'absurde. On explique qu'une légère modification de l'axiomatique du calcul propositionnel conduit à la logique intuitionniste (LI), puis on montre, dans le cadre de LI, l'équivalence entre un certain nombre de principes.