Relations binaires

Une relation binaire sur un ensemble \(E\) décide, pour chaque couple \((x, y)\) d'éléments de \(E\), si \(x\) est en relation avec \(y\). La première idée du chapitre est qu'une telle règle est un objet : la partie de \(E \times E\) formée des couples en relation, comme une application du chapitre Applications est connue par son graphe. Quatre propriétés — réflexivité, symétrie, antisymétrie, transitivité — sont distinctes, une relation pouvant en avoir certaines et pas les autres, et deux de leurs combinaisons donnent les deux grandes familles de relations. La première famille identifie. Une relation d'équivalence dit que deux éléments sont les mêmes à un critère près : la parité d'un entier, le signe d'un réel, un angle à des tours complets près. Son fil est une phrase : une relation d'équivalence est toujours « avoir la même image par une application », ce que le chapitre démontre dans les deux sens. Les classes d'équivalence découpent l'ensemble en morceaux, et relations d'équivalence et partitions sont deux descriptions des mêmes objets. Les congruences, modulo un entier et modulo un réel, en sont le modèle, et chacune de leurs classes a un représentant que la partie entière trouve. La seconde famille compare. Une relation d'ordre peut être totale, comme \(\le\) sur les réels, ou partielle, comme l'inclusion des ensembles ou la divisibilité des entiers ; elle donne un sens au plus grand élément d'une partie, à ses majorants, à sa borne supérieure, et aux applications qui respectent l'ordre.
Notations. Une relation s'écrit \(\mathcal{R}\), et \(x \, \mathcal{R} \, y\) signifie \((x, y) \in \mathcal{R}\) ; la diagonale de \(E \times E\) est \(\Delta_E = \{(x, x) \mid x \in E\}\). Une relation d'équivalence s'écrit \(\sim\), la classe de \(x\) est \(\mathrm{cl}(x)\), aussi notée \(\bar{x}\), et l'ensemble des classes est \(\{\mathrm{cl}(x) \mid x \in E\}\). La congruence de deux entiers \(a\) et \(b\) modulo \(n\) s'écrit \(a \equiv b \ [n]\), et la même notation sert modulo un réel strictement positif \(\alpha\) ; la classe de \(x\) est \(x + n\mathbb{Z}\), ou \(x + \alpha\mathbb{Z}\). Une relation d'ordre quelconque s'écrit \(\preccurlyeq\), le symbole \(\le\) restant réservé aux nombres, et sa version stricte \(\prec\) ; \(\max A\), \(\min A\), \(\sup A\) et \(\inf A\) désignent le plus grand élément, le plus petit élément, la borne supérieure et la borne inférieure d'une partie \(A\). Un ordre qui n'est pas total est dit partiel. Comme dans le chapitre Ensembles, les éléments d'une partition sont ses morceaux, \(\llbracket a, b \rrbracket\) est l'ensemble des entiers de \(a\) à \(b\), et \(\emptyset\) est l'ensemble vide ; \(\lfloor x \rfloor\) est la partie entière d'un réel \(x\) ; \(\mathbb{R}_+^*\) et \(\mathbb{R}_-^*\) sont les ensembles des réels strictement positifs et des réels strictement négatifs, et \(\mathbb{R}^* = \mathbb{R} \setminus \{0\}\). En français, « supérieur à » est large, et l'inégalité stricte s'écrit « strictement supérieur à ». Dans un ensemble listé, un \(n\)-uplet ou un intervalle, le séparateur est la virgule.

Ce chapitre suppose connu le chapitre Ensembles : ensembles, inclusion et ses propriétés (la réflexivité de l'inclusion, les Propositions « Égalité par double inclusion » et « Transitivité de l'inclusion »), réunion, intersection et complémentaire (la Proposition « Propriétés du complémentaire »), la Proposition « Réunion et intersection comme bornes », la Proposition « Lois de la réunion et de l'intersection », la Proposition « L'ensemble vide est inclus dans tout ensemble », la Proposition « Inclusion caractérisée par réunion ou intersection », la Méthode « Lister les parties d'un ensemble fini », familles de parties, partitions (la Définition « Recouvrement disjoint, partition », la Proposition « Partitions élément par élément » et la Méthode « Démontrer qu'un ensemble de parties est une partition »), produit cartésien \(E \times F\), ensemble \(E^2\) et parties d'un produit, ensemble \(\mathcal{P}(E)\), intervalles d'entiers, et description d'un ensemble par un paramètre. Il suppose connu le chapitre Applications : application, graphe, ensemble \(F^E\) des applications de \(E\) dans \(F\) (en particulier \(\mathbb{R}^{\mathbb{R}}\)), restriction, image directe et image réciproque, fibres (la Proposition « Fibres d'une application »), composition, injection, surjection, bijection, la croissance de \(A \mapsto f(A)\) et de \(B \mapsto f^{-1}(B)\) pour l'inclusion (les Propositions « Image directe et opérations ensemblistes » et « Image réciproque et opérations ensemblistes »), et la Proposition « La stricte monotonie implique l'injectivité ». Des chapitres Raisonner et rédiger et Logique : les schémas de démonstration d'un énoncé universel ou existentiel, de l'unicité, par disjonction des cas, par contraposée, par l'absurde, par contre-exemple et par récurrence, les lois des connecteurs et des quantificateurs et leurs négations, et l'irrationalité de \(\sqrt{2}\). Du chapitre Propriétés sur les nombres entiers : divisibilité, division euclidienne dans \(\mathbb{Z}\), nombres premiers, décomposition en facteurs premiers, PGCD et PPCM. Du chapitre Radians et cercle unité : la Proposition « Réels ayant la même image » — deux réels ont la même image sur le cercle trigonométrique si et seulement si leur différence est un multiple de \(2\pi\) — et les valeurs de \(\cos\) et \(\sin\) en \(x + 2k\pi\). Du chapitre Dénombrement : les coefficients binomiaux. Les exemples et les exercices utilisent aussi : le calcul sur les réels (identités, inégalités, valeur absolue, racine carrée) ; les intervalles ; la partie entière \(\lfloor x \rfloor\), l'entier \(k\) tel que \(k \le x < k + 1\), et le fait qu'un entier dépasse tout réel donné ; les fonctions usuelles (puissances, exponentielle, logarithme, cosinus, sinus) et le sens de variation d'une fonction lu sur le signe de sa dérivée ; les nombres complexes sous forme algébrique.