Ensembles, relations et fonctions

Le langage du cours

La leçon suivante définit les entiers naturels au moyen d’une fonction, le successeur, qui est injective et n’atteint pas $1$. L’unité suivante construit les entiers relatifs et les nombres rationnels comme classes d’une relation d’équivalence ; la leçon de combinatoire définit le nombre d’éléments au moyen de bijections ; l’ordre des entiers naturels est une relation d’ordre ; et la troisième unité compose et inverse des fonctions réelles. Tous ces mots appartiennent à un même langage, qu’il convient de fixer avant de l’utiliser, avec les premiers théorèmes que le cours invoquera ensuite.

Il convient de signaler ce qui est anticipé. Les exemples utilisent de petits entiers naturels avec leur ordre, leur addition, leur multiplication, la divisibilité et le reste d’une division, tels qu’on les apprend à l’école. La leçon suivante définit les entiers naturels au moyen des axiomes de Peano, et les leçons de l’unité définissent ces opérations et démontrent leurs propriétés sans utiliser aucun exemple de celle-ci, de sorte qu’il n’y a pas de cercle. Aucun théorème de cette leçon ne dépend des exemples : les nombres ne servent qu’à voir les théorèmes à l’œuvre.

Ce que l’on admet

Un ensemble est une collection d’objets, ses éléments ; on écrit $a \in A$ pour dire que $a$ appartient à $A$, et $a \notin A$ pour le nier. Ensemble et appartenance ne se définissent pas : ce sont des notions primitives, comme $1$ et le successeur en arithmétique. Or toute propriété ne définit pas un ensemble. S’il existait l’ensemble $R$ de tous les ensembles qui ne s’appartiennent pas à eux-mêmes, la question de savoir si $R$ appartient à $R$ n’aurait pas de réponse, car par la définition de $R$ on aurait $R \in R \leftrightarrow R \notin R$. Cette contradiction, découverte par Russell en 1901, oblige à restreindre la formation des ensembles : une propriété ne fait que sélectionner des éléments d’un ensemble déjà donné.

Fait admis (règles de la théorie naïve des ensembles). On admet sans démonstration les règles de la théorie naïve des ensembles que cette leçon utilise : deux ensembles qui ont les mêmes éléments sont égaux ; à partir d’un ensemble donné $A$ et d’une propriété $P$, on forme l’ensemble $\{ x \in A : P(x) \}$ des éléments de $A$ qui la vérifient ; et il existe l’ensemble vide, l’ensemble $\{a, b\}$ dont les seuls éléments sont $a$ et $b$, la réunion des éléments d’un ensemble d’ensembles et l’ensemble des sous-ensembles d’un ensemble. L’existence d’un ensemble ayant les propriétés de l’ensemble des entiers naturels est admise dans la leçon suivante.

Ces règles font partie des axiomes de Zermelo et Fraenkel, dont l’étude relève de la théorie des ensembles et dépasse ce cours ; c’est pourquoi on les admet, et on les énonce pour que l’on sache exactement ce qui est utilisé.

Logique des quantificateurs

Les démonstrations combinent des énoncés au moyen des connecteurs $\neg$, $\wedge$, $\vee$, $\rightarrow$ et $\leftrightarrow$, dont les lois sont étudiées dans le cours complémentaire Logique mathématique I : logique propositionnelle, à partir de son langage ; ici, il suffit de rappeler que l’implication $p \rightarrow q$ n’est fausse que lorsque $p$ est vraie et $q$ fausse, qu’elle équivaut à sa contraposée $\neg q \rightarrow \neg p$, et que les lois de De Morgan nient une conjonction ou une disjonction :

Pour parler d’ensembles, il faut en outre des énoncés portant sur tous les éléments ou sur certains d’entre eux. Si $P(x)$ est une propriété des éléments de $A$, l’énoncé $(\forall x \in A)\,P(x)$, qui se lit « pour tout $x$ de $A$, $P(x)$ », affirme que tous les éléments de $A$ la vérifient ; l’énoncé $(\exists x \in A)\,P(x)$, « il existe un $x$ de $A$ tel que $P(x)$ », affirme qu’au moins un la vérifie ; et $(\exists! x \in A)\,P(x)$ affirme qu’exactement un la vérifie. Les symboles $\forall$ et $\exists$ s’appellent des quantificateurs, universel et existentiel.

Fait admis (négation des quantificateurs). Nier que tous les éléments vérifient une propriété, c’est affirmer que l’un d’eux ne la vérifie pas, et nier que l’un d’eux la vérifie, c’est affirmer qu’aucun ne la vérifie :

Ces règles, propres à la logique du premier ordre, sont admises ; elles prolongent les lois de De Morgan, car si $A = \{a, b\}$, l’énoncé universel est $P(a) \wedge P(b)$ et l’énoncé existentiel est $P(a) \vee P(b)$. L’ordre des quantificateurs importe : l’énoncé $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ dit que tout entier naturel admet un entier naturel strictement plus grand, et il est vrai ; l’énoncé $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ dit qu’il existe un entier naturel strictement plus grand que tous, y compris que lui-même, et il est faux.

La forme logique d’un énoncé dicte la manière de le démontrer. Les stratégies que cette leçon utilise sont les suivantes ; leur justification logique est étudiée dans la leçon sur les techniques de déduction.

• Pour démontrer $(\forall x \in A)\,P(x)$, on prend un élément $x$ quelconque de $A$, sans rien supposer de lui sinon son appartenance à $A$, et l’on démontre $P(x)$.
• Pour démontrer $(\exists x \in A)\,P(x)$, on exhibe un élément concret de $A$ qui vérifie $P$ ; pour réfuter $(\forall x \in A)\,P(x)$, il suffit d’un contre-exemple, un élément qui ne la vérifie pas.
• Pour démontrer $p \rightarrow q$, on suppose $p$ et l’on en déduit $q$ ; ou bien on démontre la contraposée $\neg q \rightarrow \neg p$ ; ou bien on suppose $p \wedge \neg q$ et l’on aboutit à une contradiction.
• Pour démontrer $p \leftrightarrow q$, on démontre les deux implications $p \rightarrow q$ et $q \rightarrow p$.

Ensembles

Appartenance, égalité et inclusion

Un ensemble se décrit en extension, en énumérant ses éléments entre accolades, comme $\{1, 2, 3\}$, ou en compréhension, au moyen d’une propriété, comme $\{ n \in \mathbb{N} : n \leq 3 \}$, qui est le même ensemble. La règle d’extensionnalité dit qu’un ensemble est déterminé par ses éléments :

Il s’ensuit que, dans une description en extension, ni l’ordre ni les répétitions n’importent : $\{1, 2, 2\}$ et $\{2, 1\}$ sont le même ensemble, car ils ont les mêmes éléments. Il s’ensuit aussi qu’il n’existe qu’un seul ensemble sans éléments, l’ensemble vide $\emptyset$ : deux ensembles sans éléments ont les mêmes éléments, à savoir aucun.

Définition (inclusion). Un ensemble $A$ est inclus dans un ensemble $B$, ou est un sous-ensemble de $B$, lorsque tout élément de $A$ est un élément de $B$ :

Si de plus $A \neq B$, on dit que $A$ est un sous-ensemble strict de $B$.

L’ensemble vide est inclus dans tout ensemble $A$, car l’implication $x \in \emptyset \rightarrow x \in A$ a toujours un antécédent faux et est donc vraie. Il convient de distinguer l’appartenance de l’inclusion : $1 \in \{1, 2\}$ et $\{1\} \subseteq \{1, 2\}$ sont vrais, tandis que $\{1\} \in \{1, 2\}$ est faux, car les seuls éléments de $\{1, 2\}$ sont $1$ et $2$, et l’ensemble $\{1\}$ n’est égal à aucun d’eux : $\{1\} \neq 1$, car l’ensemble dont le seul élément est $1$ ne se confond pas avec $1$, et $\{1\} \neq 2$.

Réunion, intersection et différence

Définition (opérations sur les ensembles). La réunion de $A$ et $B$ est l’ensemble des éléments qui appartiennent à l’un d’eux au moins ; l’intersection, celui des éléments qui appartiennent aux deux ; et la différence $A \setminus B$, celui des éléments qui appartiennent à $A$ et non à $B$ :

Si $B \subseteq A$, la différence $A \setminus B$ s’appelle le complémentaire de $B$ relatif à $A$. Deux ensembles sont disjoints lorsque leur intersection est vide.

Chaque opération traduit un connecteur : la réunion, la disjonction ; l’intersection, la conjonction ; la différence, la conjonction avec une négation. S’il en est ainsi, chaque loi logique produit une loi des ensembles : la réunion et l’intersection sont commutatives, associatives et distributives l’une par rapport à l’autre parce que les connecteurs le sont, et toutes ces lois se démontrent comme le théorème suivant. Le complémentaire se prend toujours relativement à un ensemble de référence, car un ensemble de tout ce qui n’est pas dans $B$ reconstruirait le paradoxe de Russell.

L’ensemble des parties

Les sous-ensembles d’un ensemble forment à leur tour un ensemble, dont l’existence a été admise au début. L’ensemble des parties de $A$, noté $\mathcal{P}(A)$, est l’ensemble dont les éléments sont les sous-ensembles de $A$ :

Par exemple, l’ensemble des parties de $\{1, 2, 3\}$ a huit éléments : l’ensemble vide, trois ensembles à un élément, trois à deux éléments et $\{1, 2, 3\}$ lui-même.

Pour tout ensemble $A$, l’ensemble vide et $A$ lui-même sont des éléments de $\mathcal{P}(A)$, et pour chaque $a$ de $A$ on a $\{a\} \in \mathcal{P}(A)$, tandis que $a$ n’est pas, en général, un élément de $\mathcal{P}(A)$. Dans la leçon sur la combinatoire, on démontrera qu’un ensemble à $n$ éléments a $2^n$ sous-ensembles.

Couples et produit cartésien

Un point du plan, une fraction ou une soustraction en attente se décrivent par deux objets dans un ordre déterminé : le couple $(3, 5)$ n’est pas le couple $(5, 3)$. L’ensemble $\{3, 5\}$ ne peut pas le représenter, car il est égal à $\{5, 3\}$. La seule chose que l’on exige d’un couple est sa propriété caractéristique : deux couples sont égaux si et seulement s’ils ont la même première composante et la même seconde composante. Kuratowski a observé en 1921 que la notion d’ensemble suffit pour construire un objet ayant cette propriété.

Définition (couple). Le couple de première composante $a$ et de seconde composante $b$ est l’ensemble

Une fois la propriété caractéristique démontrée, la construction de Kuratowski peut être oubliée : tout ce que le cours dit des couples s’en déduit.

Définition (produit cartésien). Le produit cartésien de $A$ et $B$ est l’ensemble des couples dont la première composante appartient à $A$ et dont la seconde composante appartient à $B$ :

L’écriture $\{ (a, b) : a \in A \wedge b \in B \}$ n’est pas à elle seule l’une des règles admises, qui ne permettent que de séparer des éléments d’un ensemble déjà formé. Or cet ensemble existe : si $a \in A$ et $b \in B$, les ensembles $\{a\}$ et $\{a, b\}$ sont inclus dans $A \cup B$, et sont donc des éléments de $\mathcal{P}(A \cup B)$ ; il s’ensuit que le couple $(a, b) = \{ \{a\}, \{a, b\} \}$ est inclus dans $\mathcal{P}(A \cup B)$, c’est-à-dire qu’il est un élément de $\mathcal{P}(\mathcal{P}(A \cup B))$. Le produit cartésien se forme donc par séparation à l’intérieur de cet ensemble, qui existe par les règles admises : $A \cup B$ est la réunion des éléments de $\{A, B\}$, et l’on prend deux fois l’ensemble des parties.

Le nom rappelle Descartes : le plan de la géométrie analytique est $\mathbb{R} \times \mathbb{R}$. Le produit n’est pas commutatif : $\{1\} \times \{2\}$ ne contient que $(1, 2)$, et $\{2\} \times \{1\}$ que $(2, 1)$, qui est distinct par la propriété caractéristique.

Relations

Dire que $2$ divise $6$, que $3$ est strictement inférieur à $5$ ou que deux jours tombent le même jour de la semaine, c’est affirmer que certains couples d’objets sont en relation. S’il en est ainsi, une relation est déterminée par les couples qu’elle met en relation, et elle peut se définir comme un ensemble de couples.

Définition (relation). Une relation de $A$ dans $B$ est un sous-ensemble $R$ du produit $A \times B$ ; une relation sur $A$ est une relation de $A$ dans $A$. Si $(a, b) \in R$, on dit que $a$ est en relation avec $b$ par $R$.

Par exemple, la relation « inférieur ou égal à » sur $\{1, 2, 3\}$ est l’ensemble de couples $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$. Pour les relations d’usage courant, on écrit un symbole entre les termes, comme $a \leq b$ ou $a \mid b$, au lieu de $(a, b) \in R$. Quatre propriétés d’une relation sur un ensemble reviennent dans tout le cours.

Définition (propriétés des relations). Une relation $R$ sur $A$ est réflexive, symétrique, antisymétrique ou transitive lorsqu’elle vérifie, respectivement, les conditions suivantes.

• Elle est réflexive si tout élément est en relation avec lui-même : $(\forall a \in A)\,((a, a) \in R)$ ;
• Elle est symétrique si la relation de $a$ avec $b$ implique celle de $b$ avec $a$ : $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$ ;
• Elle est antisymétrique si deux éléments en relation dans les deux sens sont égaux : $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$ ;
• Elle est transitive si la relation de $a$ avec $b$ et celle de $b$ avec $c$ impliquent celle de $a$ avec $c$ : $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$.

Sur le quadrillage de $A \times A$, une relation est un ensemble de points. Elle est réflexive lorsqu’elle contient toute la diagonale, celle des couples $(a, a)$ ; elle est symétrique lorsque son dessin est symétrique par rapport à la diagonale ; et elle est antisymétrique lorsqu’aucun point hors de la diagonale n’a son symétrique dans la relation. Antisymétrique ne signifie pas « non symétrique » : l’égalité est les deux à la fois, et le problème proposé 1 demande une relation qui ne soit ni l’un ni l’autre.

Relations d’équivalence

La relation « avoir la même parité » se comporte comme une égalité partielle : elle identifie les nombres qui coïncident sous un aspect, leur parité, et oublie les autres. Les trois propriétés qui la font se comporter ainsi reçoivent un nom.

Définition (relation d’équivalence). Une relation sur $A$ est une relation d’équivalence lorsqu’elle est réflexive, symétrique et transitive. On écrit alors $a \sim b$, et l’on dit que $a$ est équivalent à $b$. La classe de $a$ est l’ensemble des éléments équivalents à $a$, et chacun d’eux est un représentant de la classe :

L’ensemble de toutes les classes s’appelle l’ensemble quotient et se note $A/{\sim}$.

Sont des relations d’équivalence l’égalité, dont les classes n’ont qu’un seul élément ; la même parité, avec deux classes ; avoir le même reste dans la division par $3$, avec trois ; et tomber le même jour de la semaine, avec sept, ce qui fait l’objet du problème résolu 3. En général, si $g$ est une fonction définie sur $A$, la relation $g(x) = g(y)$ hérite de l’égalité les trois propriétés, et le problème résolu 5 montre que toute équivalence est de cette forme.

Les classes divisent donc l’ensemble en blocs qui ne se chevauchent pas. Cette manière de diviser un ensemble mérite une définition propre.

Définition (partition). Une partition d’un ensemble $A$ est un ensemble de sous-ensembles de $A$, appelés blocs, qui ne sont pas vides, qui sont disjoints deux à deux et dont la réunion est $A$ ; de manière équivalente, chaque élément de $A$ appartient à exactement un bloc.

Se donner une équivalence sur $A$ et se donner une partition de $A$ sont donc deux manières de dire la même chose ; le problème résolu 4 en tire parti pour dénombrer des équivalences. L’ensemble quotient est la partition vue comme un ensemble nouveau : en passant de $A$ à $A/{\sim}$, les éléments équivalents se fondent en un seul.

De même, dans la leçon sur les nombres rationnels, deux fractions $(p, q)$ et $(r, s)$ sont équivalentes lorsque $ps = qr$, et un nombre rationnel est une classe ; et dans la leçon sur les congruences, les restes modulo $n$ sont les classes d’une équivalence entre entiers relatifs.

Relations d’ordre

La divisibilité de l’exemple précédent n’est pas symétrique mais antisymétrique : au lieu d’identifier des éléments, elle les ordonne. Les relations de ce type reçoivent un nom propre.

Définition (ordre). Une relation sur $A$ est une relation d’ordre, ou ordre partiel, lorsqu’elle est réflexive, antisymétrique et transitive ; on écrit alors $a \preceq b$, et l’on dit que $a$ précède $b$. L’ordre est total lorsque deux éléments quelconques sont comparables, c’est-à-dire lorsque pour tous $a$ et $b$ on a $a \preceq b$ ou $b \preceq a$.

Sont des ordres la relation $\leq$ entre entiers naturels, qui est totale par la trichotomie démontrée dans la leçon sur les opérations sur les entiers naturels ; l’inclusion, par le théorème sur ses propriétés, qui n’est pas totale, car $\{1\}$ et $\{2\}$ ne sont pas comparables ; et la divisibilité entre entiers naturels, dont l’antisymétrie est démontrée dans la leçon sur la divisibilité, qui n’est pas totale, car on n’a ni $2 \mid 3$ ni $3 \mid 2$. Un ordre fini se dessine au moyen d’un diagramme de Hasse : un point par élément, avec $b$ plus haut que $a$ lorsque $a$ précède $b$, et un segment lorsqu’il n’y a aucun autre élément entre les deux ; la transitivité permet d’omettre les autres segments.

Définition (minorants, majorants et éléments extrémaux). Soient $\preceq$ un ordre sur $A$ et $X$ un sous-ensemble de $A$. Les minorants, les majorants et les éléments extrémaux de $X$ se définissent comme suit.

• Un élément $c$ de $A$ est un minorant de $X$ s’il précède tous les éléments de $X$, et un majorant si tous les éléments de $X$ le précèdent.
• Un plus petit élément de $X$ est un minorant de $X$ qui appartient à $X$, et un plus grand élément est un majorant qui appartient à $X$.
• Un élément $m$ de $X$ est minimal si aucun élément de $X$ distinct de lui ne le précède, et maximal s’il ne précède aucun élément de $X$ distinct de lui-même.
• La borne inférieure de $X$ est le plus grand élément de l’ensemble de ses minorants, et la borne supérieure est le plus petit élément de l’ensemble de ses majorants, lorsqu’ils existent.