Raisonnement, ensembles & dénombrement

Raisonnement, ensembles & dénombrement — socle

Idée. Avant de calculer quoi que ce soit, il faut savoir ce qu'une phrase mathématique affirme, comment on la démontre et comment on la nie. Ce chapitre fixe le vocabulaire commun à tout le post-bac : les connecteurs et les quantificateurs (partie A), les ensembles et les applications (partie B), puis le premier art de compter (partie E). Presque tout ce qu'il contient est vérifiable de façon exhaustive : une table de vérité se remplit ligne à ligne, une identité entre parties d'un ensemble se teste sur toutes les parties, un compte se recompte en énumérant. C'est le seul chapitre où la machine peut relire à peu près tout — et elle l'a fait.

Note (périmètre de vérification). Chaque équivalence logique de cette leçon a été vérifiée sur toutes ses valuations, chaque identité ensembliste sur toutes les parties d'un ensemble à quatre éléments, chaque nombre de la partie E énuméré par un programme puis comparé à la formule (_verif_raisonnement_denombrement.py). Les démonstrations (contraposée, absurde, récurrence) sont rédigées dans les exercices. Un seul énoncé est admis dans tout le chapitre : le principe de récurrence, propriété fondatrice de $\mathbb{N}$ — on l'accepte, on ne le démontre pas.

A. Logique et raisonnement

• Propositions et connecteurs. Une proposition est un énoncé qui est soit vrai (V), soit faux (F) : « $7$ est premier » (V), « $\sqrt2\in\mathbb{Q}$ » (F). On en fabrique d'autres avec la négation $\lnot P$ (« non $P$ »), la conjonction $P\land Q$ (« $P$ et $Q$ »), la disjonction $P\lor Q$ (« $P$ ou $Q$ », au sens inclusif : les deux à la fois est accepté), l'implication $P\Rightarrow Q$ et l'équivalence $P\iff Q$. La valeur de vérité d'une proposition composée ne dépend que de celles de ses composantes : c'est ce que résume une table de vérité.

• L'implication, à lire trois fois. $P\Rightarrow Q$ n'est fausse que dans un cas : $P$ vraie et $Q$ fausse. Quand $P$ est fausse, l'implication est vraie quoi que dise $Q$ (« si $2=3$, alors je suis le pape » est une implication vraie). Autrement dit $P\Rightarrow Q$ a la même table que $\lnot P\lor Q$, et sa négation est $P\land\lnot Q$ : pour réfuter une implication, on exhibe un cas où l'hypothèse est vraie et la conclusion fausse — un contre-exemple. Vocabulaire : $P$ est une condition suffisante pour $Q$, et $Q$ une condition nécessaire pour $P$.
• Contraposée et réciproque, à ne jamais confondre. La contraposée de $P\Rightarrow Q$ est $\lnot Q\Rightarrow\lnot P$ : elle a exactement la même table de vérité, donc démontrer l'une, c'est démontrer l'autre. La réciproque $Q\Rightarrow P$ est une autre proposition, qui peut être fausse quand la première est vraie : « $n$ multiple de $4$ $\Rightarrow$ $n$ pair » est vraie, sa réciproque est fausse ($n=6$). L'équivalence $P\iff Q$ est la conjonction de l'implication et de sa réciproque ; on la démontre donc en deux temps, ou par une chaîne d'équivalences dont chaque maillon est justifié dans les deux sens.
• Lois de Morgan. $\lnot(P\land Q)\iff\lnot P\lor\lnot Q$ et $\lnot(P\lor Q)\iff\lnot P\land\lnot Q$ : la négation échange « et » et « ou ». « Il n'est pas vrai que $x>0$ et $y>0$ » signifie « $x\leq0$ ou $y\leq0$ ». Retiens aussi les distributivités $P\land(Q\lor R)\iff(P\land Q)\lor(P\land R)$ et $P\lor(Q\land R)\iff(P\lor Q)\land(P\lor R)$ — les mêmes que pour $\cap$ et $\cup$.
• Quantificateurs. « $\forall x\in E,\ P(x)$ » (pour tout $x$ de $E$, $P(x)$) et « $\exists x\in E,\ P(x)$ » (il existe au moins un $x$ de $E$ tel que $P(x)$). Pour démontrer un $\forall$, on prend un $x$ quelconque et on prouve $P(x)$ ; pour démontrer un $\exists$, on exhibe un $x$ qui marche. L'ordre compte : « $\forall x\in\mathbb{R},\ \exists y\in\mathbb{R},\ x<y$ » est vraie ($y=x+1$ : le $y$ a le droit de dépendre du $x$), alors que « $\exists y\in\mathbb{R},\ \forall x\in\mathbb{R},\ x<y$ » est fausse (il faudrait un $y$ plus grand que tous les réels, lui-même compris). On peut permuter deux $\forall$ entre eux, deux $\exists$ entre eux, jamais un $\forall$ et un $\exists$.
• Nier une phrase quantifiée. On passe devant chaque quantificateur en le basculant ($\forall$ devient $\exists$ et inversement), puis on nie le prédicat : la négation de « $\forall x,\ P(x)$ » est « $\exists x,\ \lnot P(x)$ ». Ainsi « $f$ est bornée » ($\exists M,\ \forall x,\ \lvert f(x)\rvert\leq M$) se nie en « $\forall M,\ \exists x,\ \lvert f(x)\rvert>M$ », et « $(u_n)$ converge vers $\ell$ » ($\forall\varepsilon>0,\ \exists N,\ \forall n\geq N,\ \lvert u_n-\ell\rvert<\varepsilon$ — définition du chapitre sur les suites) se nie en « $\exists\varepsilon>0,\ \forall N,\ \exists n\geq N,\ \lvert u_n-\ell\rvert\geq\varepsilon$ ». ⚠️ Nier « tous les élèves ont réussi » donne « au moins un élève a échoué », pas « tous ont échoué ».
• Les modes de raisonnement. Directement : de l'hypothèse à la conclusion par une chaîne d'implications. Par contraposée : pour prouver $P\Rightarrow Q$, on prouve $\lnot Q\Rightarrow\lnot P$ — utile quand $\lnot Q$ est plus maniable que $P$ (« $n^2$ pair $\Rightarrow$ $n$ pair » se prouve en montrant que $n$ impair donne $n^2$ impair). Par l'absurde : pour prouver $P$, on suppose $\lnot P$ et on aboutit à une contradiction (l'irrationalité de $\sqrt2$, l'infinité des nombres premiers). Par disjonction de cas : on couvre toutes les possibilités ($n$ pair ou impair). Par analyse-synthèse pour une existence et une unicité : on suppose l'objet trouvé et on établit sa forme (analyse), puis on vérifie que cette forme convient (synthèse). ⚠️ Un exemple ne prouve jamais un $\forall$ ; un contre-exemple suffit à le réfuter.
• Récurrence — le principe est admis. Si une propriété $P(n)$ vérifie (initialisation) $P(n_0)$ est vraie et (hérédité) pour tout entier $n\geq n_0$, $P(n)\Rightarrow P(n+1)$, alors $P(n)$ est vraie pour tout $n\geq n_0$. C'est le principe de récurrence : une propriété fondatrice des entiers naturels, que ce cours admet (on peut la prendre pour axiome, ou la déduire du fait que toute partie non vide de $\mathbb{N}$ a un plus petit élément — ce qui revient à admettre l'un ou l'autre). Deux erreurs à ne pas commettre : écrire l'hérédité « supposons $P(n)$ vraie pour tout $n$ » (c'est la conclusion, pas l'hypothèse — on suppose $P(n)$ pour un $n$ fixé), et oublier l'initialisation (« $10^n+1$ est divisible par $3$ » est héréditaire et jamais vraie).
• Récurrence forte. Variante où l'hérédité suppose $P(n_0),\dots,P(n)$ toutes vraies pour prouver $P(n+1)$. Indispensable quand $P(n+1)$ ne se déduit pas de $P(n)$ seule : « tout entier $\geq2$ a un diviseur premier », ou les inégalités sur la suite de Fibonacci ($F_{n+1}=F_n+F_{n-1}$ appelle deux rangs). Elle est équivalente au principe de récurrence (appliquer la récurrence simple à « $P(n_0)\land\dots\land P(n)$ »).

B. Ensembles et applications

• Ensembles, éléments, parties. Un ensemble est une collection d'objets, ses éléments ($x\in E$). $A$ est une partie (ou sous-ensemble) de $E$, noté $A\subset E$, si tout élément de $A$ est dans $E$ — convention de ce cours : $\subset$ est l'inclusion large, $E\subset E$. Deux ensembles sont égaux quand ils ont les mêmes éléments : pour prouver $A=B$, on prouve $A\subset B$ et $B\subset A$ (double inclusion). L'ensemble vide $\varnothing$ n'a aucun élément et est inclus dans tout ensemble. $\mathcal P(E)$ est l'ensemble des parties de $E$ : $\mathcal P(\{a,b\})=\{\varnothing,\{a\},\{b\},\{a,b\}\}$. Un ensemble se décrit en extension ($\{1,2,3\}$) ou en compréhension ($\{x\in\mathbb{R}\mid x^2<2\}$ : les éléments $x$ de $\mathbb{R}$ qui satisfont une proposition $P(x)$).
• Opérations. Intersection $A\cap B=\{x\mid x\in A\ \text{et}\ x\in B\}$, réunion $A\cup B=\{x\mid x\in A\ \text{ou}\ x\in B\}$, différence $A\setminus B=\{x\in A\mid x\notin B\}$, complémentaire dans $E$ : $\overline A=E\setminus A$, différence symétrique $A\,\Delta\,B=(A\setminus B)\cup(B\setminus A)$. Les connecteurs logiques se traduisent : « et » devient $\cap$, « ou » devient $\cup$, « non » devient le complémentaire, l'implication $P(x)\Rightarrow Q(x)$ devient l'inclusion $\{x\mid P(x)\}\subset\{x\mid Q(x)\}$. D'où les lois de Morgan ensemblistes : $\overline{A\cup B}=\overline A\cap\overline B$ et $\overline{A\cap B}=\overline A\cup\overline B$, et les distributivités $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$, $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$. Deux façons de les prouver : la double inclusion, ou une table d'appartenance (pour chaque élément, huit cas selon qu'il est ou non dans $A$, $B$, $C$) — c'est la table de vérité, version ensembles.
• Produit cartésien. $E\times F=\{(x,y)\mid x\in E,\ y\in F\}$ est l'ensemble des couples, où l'ordre compte : $(1,2)\neq(2,1)$, et $E\times F\neq F\times E$ en général. Si $E$ et $F$ sont finis, $\lvert E\times F\rvert=\lvert E\rvert\cdot\lvert F\rvert$ — le premier compte de ce chapitre. $E^2=E\times E$, $\mathbb{R}^2$ est le plan.
• Cardinal et parties d'un ensemble fini. Le cardinal $\lvert E\rvert$ (ou $\operatorname{card}E$) est le nombre d'éléments. Une partie de $E=\{e_1,\dots,e_n\}$ se décrit par $n$ choix indépendants « dedans / dehors » : c'est une bijection entre $\mathcal P(E)$ et $\{0,1\}^n$, donc $\lvert\mathcal P(E)\rvert=2^n$ ($8$ parties pour trois éléments, dont $\varnothing$ et $E$). Pour $A,B$ finies, $\lvert A\cup B\rvert=\lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert$ : on retire les éléments comptés deux fois. La fonction indicatrice $\mathbb 1_A$ (qui vaut $1$ sur $A$, $0$ ailleurs) rend ces formules mécaniques : $\mathbb 1_{A\cap B}=\mathbb 1_A\mathbb 1_B$, $\mathbb 1_{\overline A}=1-\mathbb 1_A$, et $\lvert A\rvert=\sum_{x\in E}\mathbb 1_A(x)$.
• Applications. Une application $f:E\to F$ associe à chaque $x\in E$ un unique $f(x)\in F$. $E$ est l'ensemble de départ, $F$ l'ensemble d'arrivée ; l'image de $f$ est $f(E)=\{f(x)\mid x\in E\}\subset F$. Une application est un objet : deux applications sont égales si elles ont même départ, même arrivée et mêmes valeurs — $x\mapsto x^2$ sur $\mathbb{R}$ et sur $\mathbb{R}_+$ sont deux applications différentes.
• Injective, surjective, bijective. $f$ est injective si deux éléments distincts ont des images distinctes : $f(x)=f(x')\Rightarrow x=x'$ (tout élément de $F$ a au plus un antécédent). Elle est surjective si tout $y\in F$ a au moins un antécédent : $f(E)=F$. Elle est bijective si elle est les deux : tout $y$ a exactement un antécédent, ce qui définit la bijection réciproque $f^{-1}:F\to E$. La méthode est toujours la même — résoudre $f(x)=y$ d'inconnue $x$ : zéro solution pour certains $y$ signifie non surjective, deux solutions pour un même $y$ signifie non injective. $n\mapsto2n$ de $\mathbb{N}$ dans $\mathbb{N}$ est injective et non surjective ; $x\mapsto x^3$ est une bijection de $\mathbb{R}$ sur $\mathbb{R}$ ; $x\mapsto x^2$ n'est ni l'une ni l'autre sur $\mathbb{R}$, mais bijective de $\mathbb{R}_+$ sur $\mathbb{R}_+$. ⚠️ Pour une application entre ensembles finis, injective force $\lvert E\rvert\leq\lvert F\rvert$ et surjective force $\lvert E\rvert\geq\lvert F\rvert$.
• Image directe, image réciproque. Pour $A\subset E$, $f(A)=\{f(x)\mid x\in A\}$ ; pour $B\subset F$, $f^{-1}(B)=\{x\in E\mid f(x)\in B\}$ — cette notation ne suppose pas $f$ bijective. L'image réciproque se comporte parfaitement : $f^{-1}(B\cup C)=f^{-1}(B)\cup f^{-1}(C)$, $f^{-1}(B\cap C)=f^{-1}(B)\cap f^{-1}(C)$, $f^{-1}(\overline B)=\overline{f^{-1}(B)}$. L'image directe, moins : $f(A\cup B)=f(A)\cup f(B)$ mais seulement $f(A\cap B)\subset f(A)\cap f(B)$ — avec $f(x)=x^2$, $A=\{-1\}$, $B=\{1\}$, $f(A\cap B)=\varnothing$ tandis que $f(A)\cap f(B)=\{1\}$.
• Composition, réciproque. $g\circ f:x\mapsto g(f(x))$ est définie dès que l'arrivée de $f$ est le départ de $g$ ; elle n'est pas commutative ($f\circ g\neq g\circ f$ en général, même quand les deux existent). La composée de deux injections est injective, de deux surjections surjective, de deux bijections bijective, avec $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ — l'ordre s'inverse, comme pour enfiler puis retirer chaussettes et chaussures. Pour une bijection, $f^{-1}\circ f=\mathrm{id}_E$ et $f\circ f^{-1}=\mathrm{id}_F$, et $f^{-1}$ se calcule en résolvant $y=f(x)$ : pour $f(x)=\dfrac{2x+1}{x-1}$, on trouve $f^{-1}(y)=\dfrac{y+1}{y-2}$.

E. Dénombrement

• Principe multiplicatif. Si une situation se décrit par une suite de $k$ choix indépendants, le premier offrant $n_1$ possibilités, le deuxième $n_2$, …, le nombre total de résultats est $n_1n_2\cdots n_k$. Un menu avec $3$ entrées, $4$ plats et $2$ desserts : $24$ menus. Un code à $4$ chiffres : $10^4=10\,000$. Un mot de $5$ lettres sur un alphabet de $26$ : $26^5$. Plus généralement, le nombre d'applications d'un ensemble à $k$ éléments dans un ensemble à $n$ éléments est $n^k$ — et le nombre de parties d'un ensemble à $n$ éléments, $2^n$, en est le cas $\{0,1\}^n$.
• Arrangements. Choisir $k$ objets distincts parmi $n$, en tenant compte de l'ordre (un podium, un rangement, un code sans répétition) : $A_n^k=n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}$, où $n!=1\times2\times\cdots\times n$ (avec $0!=1$). Un code à $4$ chiffres distincts : $10\times9\times8\times7=5040$. Quand $k=n$, ce sont les permutations : $n!$ façons de ranger $n$ objets ; $5!=120$.
• Combinaisons. Choisir $k$ objets parmi $n$ sans ordre (une main de cartes, un comité, une partie à $k$ éléments) : chaque partie à $k$ éléments correspond à $k!$ arrangements, donc
  $$\binom nk=\frac{A_n^k}{k!}=\frac{n!}{k!\,(n-k)!},\qquad\binom nk=\binom n{n-k},\quad\binom n0=\binom nn=1,\quad\binom n1=n.$$
  Une main de $5$ cartes dans un jeu de $52$ : $\binom{52}5=2\,598\,960$. ⚠️ La question qui décide entre arrangement et combinaison : deux tirages qui ne diffèrent que par l'ordre sont-ils le même résultat ? Si oui, on divise par $k!$.
• Les quatre façons de tirer $k$ objets parmi $n$. C'est le tableau à savoir refaire :

Trois boules parmi cinq : $125$, $60$, $10$ et $35$.

• Formule du binôme et triangle de Pascal. Pour tous $a,b$ et tout $n\in\mathbb{N}$,
  $$(a+b)^n=\sum_{k=0}^n\binom nk a^{n-k}b^k,$$
  parce que développer $(a+b)(a+b)\cdots(a+b)$ revient à choisir, dans chaque facteur, $a$ ou $b$ : le terme $a^{n-k}b^k$ apparaît autant de fois qu'il y a de façons de choisir les $k$ facteurs qui donnent $b$. La formule de Pascal $\binom nk=\binom{n-1}{k-1}+\binom{n-1}k$ se lit par double comptage : parmi les parties à $k$ éléments de $\{1,\dots,n\}$, celles qui contiennent $n$ et celles qui ne le contiennent pas. Elle construit le triangle ligne à ligne ($1$ ; $1\ 1$ ; $1\ 2\ 1$ ; $1\ 3\ 3\ 1$ ; $1\ 4\ 6\ 4\ 1$ ; …). Deux valeurs à connaître, obtenues en posant $a=b=1$ puis $a=1,b=-1$ : $\sum_k\binom nk=2^n$ et $\sum_k(-1)^k\binom nk=0$.

• Compter par le complémentaire, par disjonction, par bijection. « Au moins un » se compte presque toujours par le complémentaire : les nombres à $4$ chiffres ayant au moins un $7$ sont $9000-8\cdot9^3=3\,168$. Quand les cas sont disjoints, on additionne ; quand ils se recouvrent, $\lvert A\cup B\rvert=\lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert$. Et quand deux ensembles sont en bijection, ils ont le même cardinal : les chemins monotones d'une grille $p\times q$ (que des pas « droite » et « haut ») sont en bijection avec les choix des $p$ positions des pas « droite » parmi $p+q$ — il y en a $\binom{p+q}p$, et la figure montre le triangle de Pascal se dessiner de lui-même, nœud par nœud.