Eclats de vers : Matemat : Bijections
Table des matières
\( \newcommand{\parentheses}[1]{\left(#1\right)} \newcommand{\crochets}[1]{\left[#1\right]} \newcommand{\accolades}[1]{\left\{#1\right\}} \newcommand{\ensemble}[1]{\left\{#1\right\}} \newcommand{\identite}{\mathrm{Id}} \newcommand{\indicatrice}{\boldsymbol{\delta}} \newcommand{\dirac}{\delta} \newcommand{\moinsun}{{-1}} \newcommand{\inverse}{\ddagger} \newcommand{\pinverse}{\dagger} \newcommand{\topologie}{\mathfrak{T}} \newcommand{\ferme}{\mathfrak{F}} \newcommand{\img}{\mathbf{i}} \newcommand{\binome}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\canonique}{\mathfrak{c}} \newcommand{\tenseuridentite}{\boldsymbol{\mathcal{I}}} \newcommand{\permutation}{\boldsymbol{\epsilon}} \newcommand{\matriceZero}{\mathfrak{0}} \newcommand{\matriceUn}{\mathfrak{1}} \newcommand{\christoffel}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\lagrangien}{\mathfrak{L}} \newcommand{\sousens}{\mathfrak{P}} \newcommand{\partition}{\mathrm{Partition}} \newcommand{\tribu}{\mathrm{Tribu}} \newcommand{\topologies}{\mathrm{Topo}} \newcommand{\setB}{\mathbb{B}} \newcommand{\setN}{\mathbb{N}} \newcommand{\setZ}{\mathbb{Z}} \newcommand{\setQ}{\mathbb{Q}} \newcommand{\setR}{\mathbb{R}} \newcommand{\setC}{\mathbb{C}} \newcommand{\corps}{\mathbb{K}} \newcommand{\boule}{\mathfrak{B}} \newcommand{\intervalleouvert}[2]{\left] #1 , #2 \right[} \newcommand{\intervallesemiouvertgauche}[2]{ \left] #1 , #2 \right]} \newcommand{\intervallesemiouvertdroite}[2]{\left[ #1 , #2 \right[ } \newcommand{\fonction}{\mathbb{F}} \newcommand{\bijection}{\mathrm{Bij}} \newcommand{\polynome}{\mathrm{Poly}} \newcommand{\lineaire}{\mathrm{Lin}} \newcommand{\continue}{\mathrm{Cont}} \newcommand{\homeomorphisme}{\mathrm{Hom}} \newcommand{\etagee}{\mathrm{Etagee}} \newcommand{\lebesgue}{\mathrm{Leb}} \newcommand{\lipschitz}{\mathrm{Lip}} \newcommand{\suitek}{\mathrm{Suite}} \newcommand{\matrice}{\mathbb{M}} \newcommand{\krylov}{\mathrm{Krylov}} \newcommand{\tenseur}{\mathbb{T}} \newcommand{\essentiel}{\mathfrak{E}} \newcommand{\relation}{\mathrm{Rel}} \DeclareMathOperator*{\strictinferieur}{\ < \ } \DeclareMathOperator*{\strictsuperieur}{\ > \ } \DeclareMathOperator*{\ensinferieur}{\eqslantless} \DeclareMathOperator*{\enssuperieur}{\eqslantgtr} \DeclareMathOperator*{\esssuperieur}{\gtrsim} \DeclareMathOperator*{\essinferieur}{\lesssim} \newcommand{\essegal}{\eqsim} \newcommand{\union}{\ \cup \ } \newcommand{\intersection}{\ \cap \ } \newcommand{\opera}{\divideontimes} \newcommand{\autreaddition}{\boxplus} \newcommand{\autremultiplication}{\circledast} \newcommand{\commutateur}[2]{\left[ #1 , #2 \right]} \newcommand{\convolution}{\circledcirc} \newcommand{\correlation}{\ \natural \ } \newcommand{\diventiere}{\div} \newcommand{\modulo}{\bmod} \DeclareMathOperator*{\pgcd}{pgcd} \DeclareMathOperator*{\ppcm}{ppcm} \newcommand{\produitscalaire}[2]{\left\langle #1 \vert #2 \right\rangle} \newcommand{\scalaire}[2]{\left\langle #1 \| #2 \right\rangle} \newcommand{\braket}[3]{\left\langle #1 \vert #2 \vert #3 \right\rangle} \newcommand{\orthogonal}{\bot} \newcommand{\forme}[2]{\left\langle #1 , #2 \right\rangle} \newcommand{\biforme}[3]{\left\langle #1 , #2 , #3 \right\rangle} \newcommand{\contraction}[3]{\left\langle #1 \odot #3 \right\rangle_{#2}} \newcommand{\dblecont}[5]{\left\langle #1 \vert #3 \vert #5 \right\rangle_{#2,#4}} \DeclareMathOperator*{\major}{major} \DeclareMathOperator*{\minor}{minor} \DeclareMathOperator*{\maxim}{maxim} \DeclareMathOperator*{\minim}{minim} \DeclareMathOperator*{\argument}{arg} \DeclareMathOperator*{\argmin}{arg\ min} \DeclareMathOperator*{\argmax}{arg\ max} \DeclareMathOperator*{\supessentiel}{ess\ sup} \DeclareMathOperator*{\infessentiel}{ess\ inf} \newcommand{\dual}{\star} \newcommand{\distance}{\mathfrak{dist}} \newcommand{\norme}[1]{\left\| #1 \right\|} \newcommand{\normetrois}[1]{\left|\left\| #1 \right\|\right|} \DeclareMathOperator*{\adh}{adh} \DeclareMathOperator*{\interieur}{int} \newcommand{\frontiere}{\partial} \DeclareMathOperator*{\image}{im} \DeclareMathOperator*{\domaine}{dom} \DeclareMathOperator*{\noyau}{ker} \DeclareMathOperator*{\support}{supp} \DeclareMathOperator*{\signe}{sign} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\unsur}[1]{\frac{1}{#1}} \newcommand{\arrondisup}[1]{\lceil #1 \rceil} \newcommand{\arrondiinf}[1]{\lfloor #1 \rfloor} \DeclareMathOperator*{\conjugue}{conj} \newcommand{\conjaccent}[1]{\overline{#1}} \DeclareMathOperator*{\division}{division} \newcommand{\difference}{\boldsymbol{\Delta}} \newcommand{\differentielle}[2]{\mathfrak{D}^{#1}_{#2}} \newcommand{\OD}[2]{\frac{d #1}{d #2}} \newcommand{\OOD}[2]{\frac{d^2 #1}{d #2^2}} \newcommand{\NOD}[3]{\frac{d^{#3} #1}{d #2^{#3}}} \newcommand{\deriveepartielle}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\PD}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dblederiveepartielle}[2]{\frac{\partial^2 #1}{\partial #2 \partial #2}} \newcommand{\dfdxdy}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}} \newcommand{\dfdxdx}[2]{\frac{\partial^2 #1}{\partial #2^2}} \newcommand{\gradient}{\mathbf{\nabla}} \newcommand{\combilin}[1]{\mathrm{span}\{ #1 \}} \DeclareMathOperator*{\trace}{tr} \newcommand{\proba}{\mathbb{P}} \newcommand{\probaof}[1]{\mathbb{P}\left[#1\right]} \newcommand{\esperof}[1]{\mathbb{E}\left[#1\right]} \newcommand{\cov}[2]{\mathrm{cov} \left( #1 , #2 \right) } \newcommand{\var}[1]{\mathrm{var} \left( #1 \right) } \newcommand{\rand}{\mathrm{rand}} \newcommand{\variation}[1]{\left\langle #1 \right\rangle} \DeclareMathOperator*{\composante}{comp} \DeclareMathOperator*{\bloc}{bloc} \DeclareMathOperator*{\ligne}{ligne} \DeclareMathOperator*{\colonne}{colonne} \DeclareMathOperator*{\diagonale}{diag} \newcommand{\matelementaire}{\mathrm{Elem}} \DeclareMathOperator*{\matpermutation}{permut} \newcommand{\matunitaire}{\mathrm{Unitaire}} \newcommand{\gaussjordan}{\mathrm{GaussJordan}} \newcommand{\householder}{\mathrm{Householder}} \DeclareMathOperator*{\rang}{rang} \newcommand{\schur}{\mathrm{Schur}} \newcommand{\singuliere}{\mathrm{DVS}} \newcommand{\convexe}{\mathrm{Convexe}} \newcommand{\petito}[1]{o\left(#1\right)} \newcommand{\grando}[1]{O\left(#1\right)} \)
\( \newenvironment{Eqts} { \begin{equation*} \begin{gathered} } { \end{gathered} \end{equation*} } \newenvironment{Matrix} {\left[ \begin{array}} {\end{array} \right]} \)
\label{chap:bijections}
1. Dépendances
- Chapitre \ref{chap:fonctionsEtOrdre} : Fonctions et ordre
2. Inverse à gauche
Soit \(f : A \mapsto B\). Si \(l : B \mapsto A\) est une fonction telle que :
\[l \circ f = \identite\]
on dit que \(l\) est un inverse à gauche de \(f\).
2.1. Unicité
Soit \(y \in B\). Si \(f\) admet un inverse à gauche, on peut trouver au plus un seul \(x \in A\) tel que \(f(x) = y\). En effet, supposons que \(x_1, x_2 \in A\) avec \(f(x_1) = f(x_2) = y\). On a :
\[l(y) = (l \circ f)(x_1) = (l \circ f)(x_2)\]
mais comme \(l \circ f = \identite\), et que \(\identite(x) = x\) pour tout \(x \in A\), on a :
\[l(y) = x_1 = x_2\]
ce qui prouve l'unicité de la solution.
3. Inverse à droite
Soit \(f : A \mapsto B\). Si \(r : B \mapsto A\) est une fonction telle que :
\[f \circ r = \identite\]
on dit que \(r\) est un inverse à droite de \(f\).
3.1. Existence
Soit \(y \in B\). Si \(f\) admet un inverse à droite \(r\), on peut trouver au moins un \(x \in A\) tel que \(f(x) = y\). En effet, si l'on choisit \(x = r(y)\), on a :
\[f(x) = (f \circ r)(y) = \identite(y) = y\]
ce qui prouve l'existence de la solution.
4. Fonction inverse
Soit \(f : A \mapsto B\). Supposons que \(f\) admette à la fois un inverse à gauche \(l\) et un inverse à droite \(r\). Ces deux inverses sont dès lors identiques :
\[l = l \circ \identite = l \circ f \circ r = \identite \circ r = r\]
4.1. Existence et unicité
Soit \(y \in B\). On déduit des résultats précédents que l'on peut trouver un unique \(x \in A\), donné par \(x = r(y)\), tel que \(f(x) = y\). Nous pouvons dès lors définir la fonction inverse, notée \(f^{-1} : B \mapsto A\), par :
\[f^{-1}(y) = r(y)\]
pour tout \(y \in B\). On a donc :
\[f^{-1} = r = l\]
et :
\[f^{-1} \circ f = f \circ f^{-1} = \identite\]
4.2. Bijection
Lorsque \(f\) admet un inverse \(f^{-1}\), on dit que \(f\) est inversible ou que \(f\) est une bijection. On note :
\[\bijection(A,B) = \{ f \in B^A : \exists f^{-1} \in A^B \}\]
l'ensemble des bijections de \(A\) vers \(B\).
5. Relation
Lorsque \(f\) est inversible, l'image inverse de \(y \in B\) se réduit à un ensemble contenant un unique \(x \in A\). Soit \(R\) la relation associée à \(f\). On a :
\[R^{-1}(y) = \{ f^{-1}(y) \}\]
6. Inverse d'une composée
Soit \(f \in \bijection(A,B)\) et \(g \in \bijection(B,C)\). Nous allons essayer de trouver une expression de l'inverse \(h\) de la composée de ces deux fonctions. On part de la relation \(h \circ g \circ f = \identite\) et on compose à droite par l'inverse de \(f\) puis l'inverse de \(g\), ce qui nous donne :
\[h \circ g \circ f \circ f^{-1} \circ g^{-1} = \identite \circ f^{-1} \circ g^{-1} = f^{-1} \circ g^{-1}\]
Mais comme :
\[h \circ g \circ f \circ f^{-1} \circ g^{-1} = h \circ g \circ \identite \circ g^{-1} = h \circ g \circ g^{-1} = h \circ \identite = h\]
on a :
\[h = f^{-1} \circ g^{-1}\]
Partant de la relation \(g \circ f \circ h = \identite\) et composant à gauche par l'inverse de \(g\) puis par l'inverse de \(f\), on arrive au même résultat \(h = f^{-1} \circ g^{-1}\). Donc :
\[(g \circ f)^{-1} = f^{-1} \circ g^{-1}\]
On généralise par récurrence à \(n\) fonctions :
\[(f_n \circ ... \circ f_2 \circ f_1)^{-1} = f_1^{-1} \circ f_2^{-1} \circ ... \circ f_n^{-1}\]
7. Puissances négatives
Si \(f\) est inversible, on peut également définir les puissances négatives par :
\[f^{-n} = \left( f^{-1} \right)^n = f^{-1} \circ ... \circ f^{-1}\]
pour tout \(n \in \setN\).
8. Inverse d'une puissance
En considérant le cas particulier de fonctions identiques (\(f_1 = ... = f_n = f\)), l'expression de l'inverse d'une composition de fonctions nous montre que :
\[\left( f^{-1} \right)^n = f^{-n} = \left( f^n \right)^{-1}\]
L'inverse de la puissance est identique à la puissance de l'inverse.
9. Idempotence
On dit que deux ensembles \(A\) et \(B\) sont idempotents si il existe une bijection inversible de \(A\) vers \(B\) :
\[\bijection(A,B) \ne \emptyset\]
9.1. Equivalence
Soit les ensembles \(A\) et \(B\). Supposons qu'il existe une bijection \(f \in \bijection(A,B)\). On peut alors définir une équivalence sur \(A \cup B\) en disant que \(x \equiv y\) si \(x \in A\) avec \(y = f(x) \in B\), ou si \(x \in B\) avec \(y = f^{-1}(x) \in A\). Dans les autres cas, \(x\) ne sera pas équivalent à \(y\). Les classes d'quivalences seront donc de la forme :
\[\mathcal{E}(a) = \{ a , f(a) \}\]
pour tout \(a \in A\) et de la forme :
\[\mathcal{E}(b) = \{ b , f^{-1}(b) \}\]
pour tout \(b \in B\). Il y a donc une « équivalence » entre les éléments de \(A\) et les éléments de \(B\). Dans ce cas, on confond souvent les éléments \(x\) de \(A\) avec les éléments de \(\hat{x}\) de \(B\), et on note abusivement \(x = \hat{x}\).
9.2. Ensembles finis
Dans le cas d'ensembles finis, l'idempotence revient à dire que \(A\) et \(B\) ont le même nombre d'éléments.
10. Inverse des fonctions monotones
10.1. Théorème
Soit la fonction \(f : A \mapsto B\) avec \(B = f(A)\). Si \(f\) est strictement croissante (ou décroissante), alors la fonction \(f\) est inversible.
10.2. Démonstration
Choisissons \(y \in B\) et considérons l'ensemble de solutions :
\[S(y) = \{ x : f(x) = y \}\]
Comme \(B = f(A)\), cet ensemble est non vide. Supposons \(x_1,x_2 \in S(y)\) avec \(x_1 \strictinferieur x_2\). On a alors, soit \(f(x_1) \strictinferieur f(x_2)\) (si \(f\) est strictement croissante), soit \(f(x_1) \strictsuperieur f(x_2)\) (si \(f\) est strictement décroissante). Or, par définition de \(S(y)\), on doit avoir \(f(x_1) = f(x_2) = y\). Il ne peut donc y avoir d'éléments distincts dans \(S(y)\), et cet ensemble est de la forme :
\[S(y) = \{ g(y) \}\]
relation qui définit implicitement la fonction \(g : B \mapsto A\). On peut trouver un unique \(g(y)\) tel que \(f(g(y)) = y\). La fonction \(f\) est donc inversible et :
\[f^{-1} = g\]