Une bijection est une application particulière $f$ d’un ensemble de départ $E$ sur un ensemble d’arrivée $F$. Comme toute application, elle associe à chaque élément $x\in E$ un élément unique $y=f(x)\in F$. Ce qui est particulier, c’est que chaque élément $y\in F$ est l’image par $f$ d’un seul élément $x\in E$. Bien entendu, deux ensembles étant donnés, il n’existe pas forcément de bijection entre eux, mais si la bijection $f$ existe, il existe aussi une bijection réciproque de $F$ sur $E$ associant à chaque $y=f(x)\in F$ l’élément $x\in E$ dont il est l’image par $f$ : on la note $f^{-1}: F\to E$.
On peut distinguer les bijections entre ensembles finis, qui font l’objet de la Combinatoire, et les bijections entre ensembles infinis. Ces dernières ont été introduites et profondément étudiées par les mathématiciens allemands Georg Cantor (1845-1918) et Richard Dedekind (1831-1916).
Lorsque l’ensemble $E$ est fini, par exemple contenant $n$ éléments, on dit que le cardinal de $E$ est égal à $n$ et l’on note $\#E=n$. Désignons par $\mathbb{N}_n=\{1,2,\ldots,n\}$ l’ensemble des $n$ premiers entiers. Si l’on écrit $E:=\{a_1,a_2,\ldots,a_n\}$, on a déjà numéroté ses éléments, c’est à dire que l’on a défini une bijection $\phi: \mathbb{N}_n\to E$ associant à chaque entier $j$ un élément unique de $E$ que l’on note $a_j=\phi(j)$, sachant que chaque élément a un seul numéro. C’est justement pour cette raison que l’on définit $\#E=n$. Mais on sait très bien que cette numérotation n’est pas unique et que l’on a en fait $n!=1\times2\times\ldots\times n$ bijections possibles entre $\mathbb{N}_n$ et $E$. Si $\phi_1$ et $\phi_2$ sont 2 numérotations de $E$, c’est à dire 2 bijections de $\mathbb{N}_n$ sur $E$, on peut définir l’application suivante de $E$ sur $E$ :\[\forall x\in E, \quad \sigma(x)=(\phi_1\circ\phi_2^{-1})(x)=(\phi_1(\phi_2^{-1}(x))\]Autrement dit, si $x=a_k$ a comme numéro $k\in\mathbb{N}_n$, cela signifie que $\phi_2(k)=x$, donc $\phi_2^{-1}(x)=k$. Maintenant, l’élément $\sigma(x)$ est défini par $\sigma(x)=\phi_1(k)=a_j$, et finalement, on a $\sigma(a_k)=a_j$. Ces applications de $E$ dans lui-même sont appelées les permutations de $E$. Ce sont toutes les bijections de $E$ sur $E$ et il y a $n!$ permutations de $E$. La Combinatoire est la branche des mathématiques qui étudie les cardinaux des ensembles finis, ce qui revient à étudier les applications d’ensembles $\mathbb{N}_p$ sur des ensembles $\mathbb{N}_q$. Ses applications pratiques sont fondamentales car bien entendu les ensembles fournis par la nature sont finis. Cela ne veut pas dire qu’ils sont simples : on sait bien que l’étude d’un génôme ou d’un réseau (par exemple Google sur Internet) est celle d’ensembles finis, mais personne ne trouve cela très simple. Au contraire, cette étude conduit à des développements mathématiques assez théoriques et pas très simples pour le commun des mortels (comme vous et moi).
Considérons maintenant des ensembles infinis, c’est à dire dont le cardinal est supérieur à tout nombre entier. Cantor définit deux ensembles $E$ et $F$ comme équipotents (qui ont la même puissance, ou le même cardinal) lorsqu’il existe une bijection entre $E$ et $F$. Mais comment numéroter un ensemble infini ? On dit qu’un ensemble $E$ est dénombrable} s’il existe une bijection $\phi: \mathbb{N}\to E$. Là encore, on attribue à chaque entier un seul élément de $E$. Ce qui a beaucoup surpris les mathématiciens de l’époque, c’est que Cantor a démontré que $\mathbb{N}$, $\mathbb{Z}$ et $\mathbb{Q}$ sont équipotents, mais que $\mathbb{N}$ et $\mathbb{R}$ ne le sont pas. Aussi surprenant, le segment $I=[0,1]$ est équipotent au carré $Q=[0,1]^2$ ou au cube $C=[0,1]^3$ et tous les trois ont même cardinal que $\mathbb{R}$. Il en est de même des espaces $\mathbb{R}^d$ pour tout $d$ entier. La puissance de $\mathbb{R}$ est strictement supérieure à celle de $\mathbb{N}$. Cette dernière se nomme la puissance du dénombrable} et celle de $\mathbb{R}$ la puissance du continu. On démontre aussi que l’ensemble $\mathcal{P}(\mathbb{N})$ de tous les sous-ensembles de $\mathbb{N}$ (encore appelés les parties de $\mathbb{N}$) a la puissance du continu ! (Essayer d’en commencer la liste). En revanche, on ne sait pas s’il existe une puissance intermédiaire entre le continu et le dénombrable. Plus exactement, on a démontré (1963) que c’était un résultat indémontrable à l’aide de la logique et de la théorie actuelle des ensembles. Une question pour terminer: existe-t-il des puissances supérieures à celle du continu ? La réponse est oui et elle tient dans le théorème suivant: la puissance de $\mathcal{P}(E)$ (l’ensemble de tous les sous-ensembles de $E$) est strictement supérieure à celle de $E$. Bref, c’est pas très simple, mais il y a de quoi bien s’amuser pour passer le temps.
On doit à Richard Dedekind (allemand, 1831-1916) les définitions actuelles d’application, d’image, d’antécédent et de bijection (en tant que correspondance biunivoque, c’est-à-dire tout élément de l’ensemble de départ possède une unique image dans l’ensemble d’arrivée et tout élément de l’ensemble d’arrivée possède un unique antécédent dans l’ensemble de départ).
Intuitivement, grâce à la notion de bijection, nous pouvons comparer le nombre d’éléments de 2 ensembles (deux ensembles sont le même nombre d’éléments s’il existe une bijection entre ces deux ensembles).
Il a approfondi ces notions en particulier par rapport au nombre d’antécédent d’un élément. Ainsi, les notions d’injection, surjection qui seront vu au niveau post-baccalauréat permette de définir de belle manière les ensembles finis et infinis.