Sauter au contenu

Mathématiques discrètes Version préliminaire

Section 1.3 Les fonctions

Dans un cours de mathématiques discrètes, on étudie les fonctions d’un point de vue différent à celui auquel on est habitué. Pour ce faire, on commence par parler de relations. Étant donné deux ensembles \(A,B\text{,}\) potentiellement égaux, on peut s’intéresser aux relations qui existent entre les éléments de ces ensembles. Par exemple, on peut parler d’un lien de famille entre ensembles de personnes, une catégorisation de produits (un ensemble d’aliments et un ensemble contenant des identifiants comme fruit, légume, viande, etc.) etc.
🔗

Sous-section 1.3.1 Définitions et exemples

Soit \(A\) et \(B\) deux ensembles. Une relation est un sous-ensemble \(R\) du produit cartésien: \(R\subseteq A\times B\text{.}\) On dit parfois que \(R\) est une relation de \(A\) vers \(B\text{.}\) Deux éléments \(a\in A\) et \(b\in B\) sont dits en relation si \((a,b)\in R\text{.}\) On écrit aussi \(a~ R~ b\) ou \(a\sim b\) pour dire que les éléments \(a,b\) sont en relation.
🔗

Exemple 1.3.1. Un exemple de relation.

On considère l’ensemble \(A=B\) formé des provinces canadiennes. On pose
\begin{equation*} R=\{(p,q)\in A\times A~|~\text{il existe une frontière terrestre entre } p \text{ et }q\}\text{.} \end{equation*}
On cherche trois éléments de \(A\times A\) qui sont en relation \(R\) et deux qui ne le sont pas.
🔗
Solution.
On considère le Québec. La province possède une frontière commune avec l’Ontario à l’ouest, avec le Nouveau-Brunswick au sud-est et avec Terre-Neuve par le biais du Labrador à l’est. Ainsi \((\text{Québec},\text{Ontario}),(\text{Québec},\text{Nouveau-Brunswick}),(\text{Québec},\text{Terre-Neuve})\in R\text{.}\)
🔗
Par contre, le Québec n’a pas de frontière terrestre avec l’Alberta ou la Colombie-Britannique alors \((\text{Québec},\text{Alberta}),(\text{Québec},\text{Colombie-Britannique})\notin R\text{.}\)
🔗
🔗
🔗
Le type de relation le plus important et utile en mathématique est certainement la fonction. Une relation est une fonction si elle respecte des conditions additionnelles.
🔗

Définition 1.3.2. Une fonction.

Soit \(A,B\) deux ensembles et \(R\subseteq A\times B\) une relation. On dit que \(R\) est une fonction si chaque élément \(a\in A\) fait partie d’exactement un élément de \(R\text{.}\) En d’autres mots, un élément de \(A\) ne peut être en relation qu’avec un seul élément de \(B\text{.}\)
🔗
Traditionnellement, on dénote les fonctions par les lettres \(f,g,h\text{.}\) On écrit alors
\begin{align*} f&: &A&\to B\\ &&a&\to f(a)=b\text{.} \end{align*}
🔗
Chaque élément \(a\in A\) possède un et un seul élément \(b\in B\) tel que \(f(a)=b\text{,}\) mais un élément de \(B\) peut ne pas être atteint par un élément de \(A\text{.}\) Dans la définition d’une fonction, on spécifie souvent les trois ensembles suivants:
Le domaine:
🔗
L’ensemble \(A\) est appelé le domaine de la fonction.
🔗
Le codomaine:
🔗
L’ensemble \(B\) est appelé le codomaine de la fonction.
🔗
L’image:
🔗
L’image est l’ensemble des \(b\in B\) qui sont atteints par au moins une valeur \(a\in A\text{:}\)
\begin{align*} \text{Ima}(f)=\{b\in B~|~ \text{il existe }\amp a\in A \\ \amp \text{ tel que } f(a)=b\}\text{.} \end{align*}
🔗
Si \(f(a)=b\text{,}\) on dit aussi que \(b\) est l’image de \(a\) et que \(a\) est une préimage de \(b\text{.}\) L’ensemble de toutes les préimages de \(b\) est parfois noté \(f^{-1}(\{b\})\text{.}\) On laisse parfois de côté les accolades, mais il faut alors faire attention de ne pas confondre \(f^{-1}(b)\text{,}\) qui est un ensemble, avec la fonction inverse de \(f\text{,}\) dont il sera question dans la sous-section 1.3.4.
🔗
🔗
🔗
Une fonction est une machine qui associe à chaque entrée exactement une sortie. Le processus par lequel s’effectue la transformation peut souvent être explicite, mais parfois implicite ou inconnu.
🔗
Si \(C\subseteq A\) est un sous-ensemble du domaine d’une fonction \(f\) et qu’on souhaite considérer la fonction restreinte sur ce sous-ensemble, on écrira \(\left. f\right|_C\) (voir l’exercice 1.3.6.3).
🔗

Exemple 1.3.3. Des fonctions.

On cherche parmi les relations suivantes lesquelles sont des fonctions:
  1. La relation définie à l’exemple 1.3.1.
    🔗
    🔗
  2. La relation qui associe à chaque étudiant d’un cours une note à la fin de la session.
    🔗
    🔗
  3. La relation qui associe à un étudiant les langages de programmation qu’il connait.
    🔗
    🔗
  4. La relation de \(\N\) vers \(\N\) qui associe à un nombre \(k\) son carré \(k^2\text{.}\)
    🔗
    🔗
  5. La relation de \(\N\) vers \(\R\) qui associe à un nombre \(k\) les nombres \(r\) tels \(r^2=k\text{.}\)
    🔗
    🔗
  6. La relation \(f:\N\to \N\) définie par \(f(n)=\frac{n}{2}\text{.}\)
    🔗
    🔗
  7. La relation \(f:\N\to \Q\) définie par \(f(n)=\frac{n}{2}\text{.}\)
    🔗
    🔗
  8. La relation de \(\N\backslash\{0\}\) vers \(\N\) qui associe à \(n\) le \(n^{\text{ième}}\) nombre premier.
    🔗
    🔗
🔗
Solution.
  1. La relation entre les provinces de Canada n’est pas une fonction. Une province peut être en relation avec plusieurs autres, comme le Québec. Une province peut aussi ne pas être en relation avec aucune autre, comme l’Île-du-Prince-Édouard.
    🔗
    🔗
  2. À la fin de la session, chaque étudiant aura une note. Deux étudiants auront peut-être la même note, mais ce n’est pas contre l’idée d’une fonction. Par contre, un étudiant aura une et une seule note. C’est donc une fonction.
    🔗
    🔗
  3. Parce qu’un étudiant pourrait connaitre plus d’un langage de programmation, ce n’est pas une fonction. De même, peut-être qu’un étudiant ne sait même pas programmer. Il ne serait donc en relation avec aucun langage de programmation.
    🔗
    🔗
  4. Cette relation est une fonction, car à tout nombre \(k\in \N\text{,}\) il existe une seule valeur pour \(k^2\text{.}\) Par exemple, si on note cette fonction par \(f\text{,}\) alors \(f(4)=16,f(5)=25\) etc.
    🔗
    🔗
  5. Ce n’est pas une fonction, car étant donné \(k\in N\text{,}\) il existe deux nombres dans \(\R\) pour lesquels cela est possible, soit \(\pm \sqrt{k}\text{.}\) Par exemple, le naturel \(4\) serait associé à la fois à \(-2\) et à \(2\) par cette relation.
    🔗
    Si on changeait le codomaine par l’ensemble des réels positifs, \(\R^{+}\text{,}\) alors on aurait une fonction.
    🔗
    🔗
  6. Cette relation n’est pas une fonction, car certaines valeurs du domaine ne possèdent pas d’image. C’est le cas pour \(3\text{,}\) puisque \(f(3)=\frac{3}{2}\notin \N\text{.}\)
    🔗
    🔗
  7. Cette fois-ci, le codomaine est adéquat et on a une fonction puisque la valeur \(\frac{n}{2}\) est unique pour chaque \(n\in \N\text{.}\)
    🔗
    🔗
  8. Cette relation est une fonction, car il n’existe qu’un seul \(n^\text{ième}\) nombre premier et qu’il en existe une infinité. Toutefois, contrairement aux autres fonctions ci-dessus, il n’y a pas de formule explicite pour déterminer \(f(n)\text{.}\) La liste des premiers nombres premiers est \(2,3,5,7,11,13,17,19,23,\ldots\text{.}\)
    🔗
    🔗
🔗
🔗
🔗
Étant donné deux ensembles \(A\) et \(B\text{,}\) combien y a-t-il de fonctions différentes qui vont de \(A\) vers \(B\) ? Si les ensembles ont une cardinalité finie, il sera possible de les compter.
🔗

Exemple 1.3.4. Toutes le fonctions entre deux ensembles.

Soit \(A=\{0,1\}\) et \(B=\{0,1,2\}\text{.}\) On cherche à faire la liste de toutes les fonctions possibles partant de \(A\) vers \(B\text{.}\)
🔗
Il y aura \(9\) fonctions. Avant de poursuivre, tenter de voir pourquoi.
🔗
Solution.
On sait que chaque élément du domaine doit être envoyé sur exactement un élément du codomaine. Comme on a deux éléments dans le domaine et que, pour chacun, on a trois choix dans le codomaine, on devrait trouver \(3\cdot3=9\) fonctions. Elles sont dans la table 1.3.5. L’ordre n’est évidemment pas important, mais remarquer comment elles ont été listées. On est parti avec \(f(0)=0\) pour ensuite faire toutes les valeurs possibles pour \(f(1)\text{.}\) Ensuite, on prend la deuxième option \(f(0)=1\) et on répète, pour finalement arriver avec \(f(0)=2\) et ses variantes pour \(f(1)\text{.}\)
🔗
Table 1.3.5. Les fonctions de \(A\) vers \(B\)
🔗
\(f\) \(f(0)\) \(f(1)\)
\(f_1\) \(0\) \(0\)
\(f_2\) \(0\) \(1\)
\(f_3\) \(0\) \(2\)
\(f_4\) \(1\) \(0\)
\(f_5\) \(1\) \(1\)
\(f_6\) \(1\) \(2\)
\(f_7\) \(2\) \(0\)
\(f_8\) \(2\) \(1\)
\(f_9\) \(2\) \(2\)
🔗
🔗
🔗

Sous-section 1.3.2 Représentation d’une fonction

Pour aider à comprendre une fonction, il peut être pratique de la visualiser à l’aide de différents outils. Selon le domaine ou le codomaine, certains sont plus appropriés que d’autres. À titre d’exemple, on considère les ensembles \(A=\{0,1,2,3\}\) et \(B=\{1,2,3\}\) et la fonction définie comme suit: \(f(0)=1,f(1)=3,f(2)=1,f(3)=2 \text{.}\)
🔗
Une première représentation est celle d’un diagramme sagittal. Cette représentation n’est pratique que si le nombre d’éléments de chaque ensemble est relativement petit. Le diagramme sagittal de la fonction \(f\) est illustré à la figure ci-dessous.
🔗
Figure 1.3.6. Un diagramme sagittal de \(f\)
🔗
Les ellipses autour des éléments sont parfois omises dans cette représentation.
🔗
Une autre méthode consiste à effectuer tout simplement une représentation graphique des valeurs. Cette méthode ne fonctionne que si les ensembles sont numériques bien sûr. Ci-dessous, la représentation de la fonction \(f\) ainsi que d’une fonction \(g:\R\to\R\) sinusoïdale. C’est surtout dans un contexte continue qu’on utilise ce type de représentation, mais à l’occasion aussi dans un contexte discret.
🔗
Figure 1.3.7. Un graphique pour \(f\)
🔗
Figure 1.3.8. Une fonction sinusoïdale
🔗
Une autre manière que l’on considère est de donner une table de valeurs. Celle-ci est utile dans un contexte discret, même lorsque le domaine possède une infinité d’éléments. On peut parfois y déceler une suite logique. Voici la table de valeurs de la fonction \(f\text{.}\)
🔗
Table 1.3.9. La table de valeurs pour la fonction \(f\)
🔗
\(n\) \(f(n)\)
0 1
1 3
2 1
3 2
Une telle table pourrait aussi être horizontale.
🔗
Finalement, une fonction peut-être représentée par une règle algébrique. Selon les cas et en fonction des outils disponibles, cela permet de faire une analyse approfondie du comportement de la fonction. La règle de la fonction sinusoïdale de la figure 1.3.8 est \(g(x)=\sin(3x)\cos(x/2)\text{.}\)
🔗
🔗

Sous-section 1.3.3 La composition de fonctions

On considère trois ensembles \(A,B,C\text{,}\) où \(A\) représente les élèves d’un cours à l’université, \(B\) représente la note de ces élèves (en pourcentage) et \(C\) représente les cotes possibles (\(A^+,A,A^-,\ldots, D,F\)). On peut imaginer une fonction qui à chaque élève associe une note puis, pour chaque note est associée une cote selon un barème préétabli par l’enseignant. Peut-on directement avoir une fonction qui à chaque élève retourne la cote? C’est un exemple de composition de fonctions.
🔗

Définition 1.3.10. La composition de deux fonctions.

Soit \(g:A\to B\) et \(f:B\to C\) deux fonctions. La composition de \(f\) et \(g\text{,}\) notée \(f\circ g\) est une fonction de \(A\) vers \(C\) définie par
\begin{equation*} (f\circ g)(a)=f(g(a)) \end{equation*}
pour tout élément \(a\in A\text{.}\)
🔗
🔗
Cette relation est bel et bien une fonction, car tous les éléments de \(A\) possèdent une image et celle-ci est unique puisque les relations \(f,g\) sont des fonctions. L’image de \(a\) par \(g\) est donc unique, tout comme l’image de \(g(a)\in B\) par \(f\text{.}\) La figure 1.3.11 représente la composition de deux fonctions.
🔗
Trois ensembles A,B,C sont dessinés contenant respectivement les éléments a,g de a et f de g de a. Des flèches illustrant la fonction g partent de l’ensemble A à gauche vers l’ensemble B au centre, des flèches illustrant la fonction f partent de l’ensemble B au centre vers l’ensemble C à droite et des flèches illustrant la composition f rond g partent de l’ensemble A vers l’ensemble C.
Figure 1.3.11. La composition \(f\circ g\)
🔗

Exemple 1.3.12. Composition de deux fonctions.

Soit \(A,B,C\) trois ensembles et \(f,g\) des fonctions telles qu’illustrés à la figure 1.3.13. On veut déterminer
  1. Le domaine, le codomaine et l’image de \(f,g\) et \(f\circ g\text{.}\)
    🔗
    🔗
  2. Les valeurs, si possible de \(f(a),g(a),(f\circ g)(a)\text{.}\)
    🔗
    🔗
  3. Les préimages, si possible, \(f^{-1}(-4),g^{-1}(-4),(f\circ g)^{-1}(-4)\text{.}\)
    🔗
    🔗
🔗
Un graphique sagittal à trois ensembles est illustré. À gauche, les éléments a,b,c de l’ensemble A sont envoyés respectivement sur 1,3 et 1 dans l’ensemble B au centre. L’ensemble B contient les éléments 1,2,3 qui sont envoyés dans l’ensemble C respectivement sur -4,-1,-2. L’ensemble C contient aussi l’élément -3.
Figure 1.3.13. Un diagramme sagittal de \(f,g\) et leur composition
🔗
Solution.
  1. On commence par la fonction \(f\text{.}\) Son domaine est l’ensemble \(B=\{1,2,3\}\text{,}\) son codomaine est l’ensemble \(C=\{-1,-2,-3,-4\}\) et son image est le sous-ensemble de \(C\) contenant les éléments \(-1,-2,-4\text{.}\)
    🔗
    Pour la fonction \(g\text{,}\) son domaine est l’ensemble \(A=\{a,b,c\}\text{,}\) son codomaine est l’ensemble \(B=\{1,2,3\}\) et son image est le sous-ensemble de \(B\) contenant les éléments \(1,3\text{.}\)
    🔗
    Finalement pour la composition \(f\circ g\text{,}\) son domaine est l’ensemble \(A=\{a,b,c\}\text{,}\) son codomaine est l’ensemble \(C=\{-1,-2,-3,-4\}\) et son image est le sous-ensemble de \(C\) contenant les éléments \(-2,-4\text{.}\)
    🔗
    🔗
  2. Comme \(a\notin B=\text{dom}(f)\text{,}\) on ne peut pas déterminer l’image de \(a\) par \(f\text{.}\) Par contre \(a\in A=\text{dom}(g)=\text{dom}(f\circ g)\text{,}\) on a \(g(a)=1\) et \((f\circ g)(a)=-4\)
    🔗
    🔗
  3. La ou les préimages de \(-4\) par la fonction \(f\) est l’ensemble des valeurs \(x\in B=\text{dom}(f)\) telles que \(f(x)=-4\text{.}\) On a \(f^{-1}(-4)=\{1\}\text{.}\) La préimage de \(-4\) par \(g\) n’existe pas, car \(-4\notin \text{Im}(g)\text{.}\)Pour la composition, on cherche l’ensemble des \(x\in A=\text{dom}(f\circ g)\) telles que \((f\circ g)(x)=-4\text{.}\) On trouve \((f\circ g)^{-1}(-4)=\{a,c\}\text{.}\)
    🔗
    🔗
🔗
🔗
🔗
🔗

Sous-section 1.3.4 Fonctions injectives et surjectives

On a vu dans l’exemple 1.3.12 que certaines fonctions envoient plusieurs éléments sur une même image. On a aussi vu que certaines fonctions n’atteignent pas toutes les valeurs de leur codomaine. Ce sont souvent des propriétés qu’il est souhaitable d’avoir ou du moins, elles entrainent d’heureuses conséquences.
🔗

Définition 1.3.14. Fonction injective.

Soit \(f:A\to B\) une fonction. On dit que \(f\) est injective si et seulement si les éléments de l’image ne sont atteints par \(f\) que par exactement un élément du domaine. En langage mathématique, on écrit que si \(f(a_1)=f(a_2)\text{,}\) alors nécessairement \(a_1=a_2\text{.}\)
🔗
🔗
Avec une fonction injective, il n’y a pas de collision dans le codomaine, c’est-à-dire deux valeurs du domaine qui sont envoyées sur le même élément. Dans ce cas, la préimage d’un élément du codomaine est soit l’ensemble vide, soit un élément unique du domaine.
🔗

Exemple 1.3.15. Des fonctions injectives.

On considère les fonctions suivantes et on cherche celles qui sont injectives:
  1. La fonction de \(\R\to \R\) définie par \(f(x)=x^2\text{.}\)
    🔗
    🔗
  2. La fonction de \(\R^{+}\to \R^{+}\)
     1 
    Par \(\R^{+}\text{,}\) on veut dire l’ensemble\(\{x\in \R~|~ x\geq 0\}\)
    🔗
    définie par \(f(x)=x^2\text{.}\)
    🔗
    🔗
  3. La fonction d’un ensemble \(A\) quelconque vers ce même ensemble \(A\) qui associe chaque élément à lui-même.
    🔗
    🔗
  4. Soit \(A=\{0,1,2\}\text{.}\) On pose \(B=A\cup\{3\}\text{.}\) On définit \(f:\mathscr{P}(A)\to B\) comme étant la fonction qui associe à chaque élément de \(\mathscr{P}(A)\) sa cardinalité.
    🔗
    🔗
🔗
Solution.
  1. Cette fonction n’est pas injective puisque pour tout \(x\in \R\text{,}\) on a \(f(x)=f(-x)=^2\text{.}\) En particulier, si \(x\neq 0\text{,}\) on obtient deux valeurs différentes du domaine qui donne la même image, par exemple \(f(-1)=f(1)=1\text{.}\)
    🔗
    🔗
  2. Cette fois, comme le domaine est restreint aux réels positifs, il n’y a plus de \(-x\) possible. Chaque nombre réel positif possède une unique racine carrée et donc, chaque élément de l’image n’est atteint que par un seul élément du domaine. C’est une fonction injective.
    🔗
    🔗
  3. Parce que \(A\) est un ensemble, on sait qu’il n’y a pas de répétitions dans ses éléments. Chaque membre de l’image est atteint par son unique homologue du domaine. C’est donc une injection (on utilise parfois ce terme plutôt que fonction injective).
    🔗
    🔗
  4. On essaie de décortiquer un peu la fonction. L’ensemble de puissances contient \(8\) éléments. La cardinalité de ces éléments varie de \(0\) pour l’ensemble vide à \(3\) pour l’ensemble \(A\) lui-même. On comprend maintenant pourquoi le codomaine ne pouvait pas être que l’ensemble \(A\text{.}\) On a dû lui ajoute l’élément \(3\) afin que \(f\) puisse associer à chaque valeur de \(\mathscr{P}(A)\) une réponse.
    🔗
    On peut évidemment exhiber plusieurs sous-ensembles qui ont la même cardinalité, par exemple \(\{0\},\{1\}\) et \(\{2\}\) ou \(\{0,1\},\{0,2\}\) et \(\{1,2\}\text{.}\) Cette fonction n’est donc pas injective.
    🔗
    🔗
🔗
🔗
🔗

Définition 1.3.16. Fonction surjective.

Soit \(f:A\to B\) une fonction. On dit que \(f\) est surjective si et seulement si tous les éléments du codomaine \(B\) sont atteints par \(f\) par au moins une valeur du domaine \(A\text{.}\)Ceci est équivalent à dire que le codomaine de la fonction \(f\) est l’image de celle-ci. En langage mathématique, on écrit que pour tout \(b\in B\text{,}\) il existe au moins un \(a\in A\) tel que \(f(a)=b\text{.}\)
🔗
🔗
Avec une fonction surjective, personne n’est laissé de côté dans le codomaine. Chaque valeur doit être atteinte.
🔗

Exemple 1.3.17. Des fonctions surjectives.

On considère les fonctions suivantes et on cherche celles qui sont surjectives:
  1. La fonction de \(\R\to \R\) définie par \(f(x)=x^2\text{.}\)
    🔗
    🔗
  2. La fonction de \(\R^{+}\to \R^{+}\)
     2 
    Par \(\R^{+}\text{,}\) on veut dire l’ensemble\(\{x\in \R~|~ x\geq 0\}\)
    🔗
    définie par \(f(x)=x^2\text{.}\)
    🔗
    🔗
  3. La fonction d’un ensemble \(A\) quelconque vers ce même ensemble \(A\) qui associe chaque élément à lui-même.
    🔗
    🔗
  4. Soit \(A=\{0,1,2\}\text{.}\) On pose \(B=A\cup\{3\}\text{.}\) On définit \(f:\mathscr{P}(A)\to B\) comme étant la fonction qui associe à chaque élément de \(\mathscr{P}(A)\) sa cardinalité.
    🔗
    🔗
🔗
Solution.
  1. Cette fonction n’est pas surjective puisque pour tout \(x<0\text{,}\) il n’existe pas de réel qui, mis au carré, donnera \(x\text{.}\) Par exemple, l’équation \(x^2=-1\) n’a pas de solutions dans les réels.
    🔗
    🔗
  2. Cette fois, comme le codomaine est restreint aux réels positifs, il n’y a plus de nombres négatifs. Chaque nombre réel positif possède une unique racine carrée et donc, chaque élément de l’image n’est atteint que par un seul élément du domaine. C’est une fonction surjective.
    🔗
    🔗
  3. Dans la définition de la fonction, on dit que chaque membre du domaine est associé à son homologue du codomaine. C’est donc une surjection (on utilise parfois ce terme plutôt que fonction surjective).
    🔗
    🔗
  4. La cardinalité des éléments de \(\mathscr{P}(A)\) varie de \(0\) pour l’ensemble vide à \(3\) pour l’ensemble \(A\) lui-même, passant par \(1\) et \(2\) avec les sous-ensembles \(\{0\},\{1\}\) et \(\{2\}\) et \(\{0,1\},\{0,2\}\) et \(\{1,2\}\text{.}\) Cette fonction est donc surjective.
    🔗
    🔗
🔗
🔗
🔗
La définition de surjection dit que chaque valeur du codomaine est atteinte par au moins un élément du domaine. On peut reformuler la définition de fonction injective en parlant de codomaine aussi de la manière suivante: chaque valeur du codomaine est atteinte par au plus un élément du domaine. Que se passe-t-il lorsqu’une fonction est à la fois injective et surjective?
🔗

Définition 1.3.18. Fonction bijective.

Une fonction \(f:A\to B\) est dite bijective si elle est à la fois injective et surjective. Une fonction bijective atteint chaque élément du codomaine exactement une fois.
🔗
🔗
Parmi les fonctions des exemples 1.3.15–1.3.17, la fonction \(f:\R^{+}\to \R^{+}\) est une bijection, tout comme la fonction de \(A\) vers \(A\) associant chaque élément à son homologue. Ce dernier exemple est ce qu’on appelle une fonction identité.
🔗
La figure 1.3.19 donne des exemples des différentes combinaisons possibles des propriétés d’injectivité, surjectivité et bijectivité qu’une fonction peut avoir.
🔗
Un ensemble A, à gauche contenant les éléments a,b,c est envoyé vers un ensemble B à droite contenant les éléments 1,2,3. L’élément 1 possède deux préimages et l’élément 2 n’est pas atteint.
(a) Fonction ni injective ni surjective
🔗
Un ensemble A, à gauche contenant les éléments a,b est envoyé vers un ensemble B à droite contenant les éléments 1,2,3. Les éléments a et 1 correspondent, tout comme b et 2. L’élément 3 n’est pas atteint.
(b) Fonction injective, mais pas surjective
🔗
Un ensemble A, à gauche contenant les éléments a,b,c est envoyé vers un ensemble B à droite contenant les éléments 1,2. L’élément 1 possède deux préimages.
(c) Fonction surjective, mais pas injective
🔗
Un ensemble A, à gauche contenant les éléments a,b,c est envoyé vers un ensemble B à droite contenant les éléments 1,2,3. À chaque élément correspond un et un seul élément.
(d) Fonction bijective
🔗
Figure 1.3.19. Différents cas possibles d’injectivité, surjectivité et bijectivité
🔗
On considère une fonction \(f:A\to B\) qui est bijective. Chaque élément du domaine est envoyé vers exactement un élément du codomaine et chaque élément du codomaine est atteint. Il est donc possible de défaire le travail effectué par la fonction et de partir des éléments de \(B\) pour revenir sur les éléments de \(A\text{.}\)
🔗

Définition 1.3.20. Fonction inverse.

Soit \(f:A\to B\) une bijection. La fonction inverse de \(f\text{,}\) notée \(f^{-1}:B\to A\) est la fonction qui associe à chaque \(b\in B\) un élément \(a\in A\) tels que \(f(a)=b\text{.}\) On écrira alors \(f^{-1}(b)=a\text{.}\)
🔗
De manière équivalente, la fonction \(f^{-1}\) est l’unique fonction \(f^{-1}:B\to A\) telle que pour tout élément \(a \in A\text{,}\) on a \(\left(f^{-1}\circ f \right)(a)=a\text{,}\) et pour tout élément \(b \in B\text{,}\) on a \(\left(f\circ f^{-1} \right)(b)=b\text{.}\)
🔗
🔗
La fonction \(f:\R^{+}\to\R^{+}\) des exemples 1.3.15–1.3.17 est bijective. On peut la définir par la règle \(f(x)=x^2\text{.}\) Son inverse est \(f^{-1}(x)=\sqrt{x}\text{.}\) La fonction identité de ces mêmes exemples était aussi bijective. Elle est son propre inverse.
🔗
🔗

En résumé.

Les points importants de cette section sont:
  1. La définition d’une fonction;
    🔗
    🔗
  2. Les notions de domaine, codomaine et image et la différence entre ces deux derniers ensembles, à savoir que l’image est un sous-ensemble du codomaine, mais que celui-ci peut être plus grand;
    🔗
    🔗
  3. La notion de fonction injective;
    🔗
    🔗
  4. La notion de fonction surjective;
    🔗
    🔗
  5. La notion de fonction bijective.
    🔗
    🔗
🔗

Questions de compréhension de la lecture 1.3.5 Questions de compréhension de la lecture

Répondre à ces questions suite à la lecture du texte qui précède pour valider la compréhension.
🔗

1.

Soit \(A=\{0,1,2,3\}\text{,}\)\(B=\{a,b,c,d\}\text{.}\) Déterminer quelles relations ci-dessous sont des fonctions. Expliquer pourquoi.
🔗
(a)
\(R_1\subseteq A\times B\) où \(R_1=\{(0,d),(1,a),(2,b),(3,c)\}\text{;}\)
🔗
🔗
(b)
\(R_2\subseteq A\times B\) où \(R_2=\{(1,a),(2,b),(3,c)\}\text{;}\)
🔗
🔗
(c)
\(R_3\subseteq A\times B\) où \(R_3=\{(0,a),(1,a),(2,b),(3,c)\}\text{;}\)
🔗
🔗
(d)
\(R_4\subseteq A\times B\) où \(R_4=\{(0,a),(1,a),(2,b),(3,c),(1,d)\}\text{;}\)
🔗
🔗
(e)
\(R_5\subseteq A\times A \) où \(R_5=\{(0,0),(1,0),(2,0),(3,0)\}\text{.}\)
🔗
🔗
🔗

2.

Soit \(A=\{n\in \N~|~ 0\leq n\leq 999\}\) les nombres naturels représentés par \(1,2\) ou \(3\) chiffres. On définit \(f:A\to \N\) comme la fonction qui associe à \(a\in A\) la somme des chiffres qui composent \(a\text{.}\) Par exemple, \(f(247)=2+4+7=13\text{.}\)
🔗
(a)
Déterminer \(f(d)\) où \(d\) est le jour de votre anniversaire.
🔗
🔗
(b)
Trouver l’image de cette fonction.
🔗
🔗
(c)
Trouver \(f^{-1}(\{4\})\text{.}\)
🔗
🔗
(d)
Trouver \(f^{-1}(\{2,3\})\)
🔗
🔗
🔗

3.

Soit \(C\) l’ensemble de tous les chiens. Donner un ensemble \(B\) et une relation \(R:C\to B\) tels que
🔗
(a)
\(R\) n’est pas une fonction.
🔗
🔗
🔗

4.

Soit \(A=\{3n-1~|~ n\in \N\ \text{ et }\ 1\leq n \leq 5\}\) et \(B=\{c,d,h,o,q\}\text{.}\) Représenter dans un diagramme sagittal la fonction \(f:A\to B\) qui associe à \(a\in A\) la première lettre de son écriture dans la langue française.
🔗
🔗

5.

Quels énoncés parmi les suivants sont équivalents à dire que \(f:A\to B\) est injective? Justifier.
  1. Le codomaine est égal à l’image.
    🔗
    🔗
  2. Pour tout \(a\in A\) on a \(f(a)\neq \emptyset\text{.}\)
    🔗
    🔗
  3. Si \(a_1\neq a_2\) alors \(f(a_1)\neq f(a_2)\text{.}\)
    🔗
    🔗
  4. \(\displaystyle |A|\leq |B|\)
    🔗
    🔗
🔗
🔗

6.

Quels énoncés parmi les suivants sont équivalents à dire que \(f:A\to B\) est surjective? Justifier.
  1. Le codomaine est égal à l’image.
    🔗
    🔗
  2. Pour tout \(b\in B\text{,}\) on a \(f^{-1}(\{b\})\neq \emptyset\text{.}\)
    🔗
    🔗
  3. Pour tout \(C\subseteq B\) où \(C\neq \emptyset\text{,}\) on a \(f^{-1}(C)\neq \emptyset\text{.}\)
    🔗
    🔗
  4. \(\displaystyle |A|\geq |B|\)
    🔗
    🔗
🔗
🔗

7.

Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
🔗
🔗
🔗

Exercices 1.3.6 Exercices

Exercices.

Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
🔗
1.
Soit \(A=\{0,1,2,3,4,5\}\text{,}\)\(B=\{a,b,c,d,e\}\) et \(C=\{!,@,\#,a\}\text{.}\) On considère les fonctions \(g:A\to B\) et \(f:B\to C\) définies comme suit:
🔗
Déterminer
🔗
(a)
L’image de \(3\) par \(g\text{;}\)
🔗
Réponse.
L’image de \(3\) par \(g\) est \(b\text{.}\) C’est-à-dire que \(g(3)=b\text{.}\)
🔗
🔗
🔗
(b)
La préimage de \(a\) par \(f\text{;}\)
🔗
Réponse.
La préimage de \(a\) par \(f\) est \(\{e\}\text{.}\) C’est-à-dire que \(f^{-1}(a)=\{e\}\text{.}\)
🔗
🔗
🔗
(c)
La préimage de \(a\) par \(g\text{;}\)
🔗
Réponse.
La préimage de \(a\) par \(g\) est \(\{1,4\}\text{.}\) C’est-à-dire que \(g^{-1}(a)=\{1,4\}\text{.}\)
🔗
🔗
🔗
(d)
Le domaine, le codomaine et l’image de \(g\)
🔗
Réponse.
Le domaine de \(g\) est \(A\text{,}\) le codomaine de \(g\) est \(B\text{,}\) et l’image de \(g\) est \(\{a,b,c,d\}\text{.}\)
🔗
🔗
🔗
(e)
Le domaine, le codomaine et l’image de \(f\)
🔗
Réponse.
Le domaine de \(f\) est \(B\text{,}\) le codomaine de \(f\) est \(C\) et l’image de \(f\) est \(C\text{.}\)
🔗
🔗
🔗
(f)
Le domaine, le codomaine et l’image de \(f\circ g\)
🔗
Réponse.
Le domaine de \(f\circ g\) est \(A\text{,}\) le codomaine de \(f\circ g\) est \(C\) et l’image de \(f\circ g\) est \(\{!,@,\#\}\text{.}\)
🔗
🔗
🔗
(g)
L’image de \(0\) par la composition \(f\circ g\text{;}\)
🔗
Réponse.
L’image de \(0\) par \(f\circ g\) est \(\#\text{.}\) C’est-à-dire que \(f\circ g(0)=f(g(0))=f(b)=\#\text{.}\)
🔗
🔗
🔗
(h)
La préimage de \(\#\) par la composition \(f\circ g\text{;}\)
🔗
Réponse.
La préimage de \(\#\) par \(f\circ g\) est \(\{0,3,5\}\text{.}\) C’est-à-dire que \((f\circ g)^{-1}(\#)=\{0,3,5\}\text{.}\)
🔗
🔗
🔗
🔗
2.
Quelle est l’image de la fonction \(f:\emptyset\to B\) où \(B\) est un ensemble quelconque non vide?
🔗
Indice.
Pouvez-vous trouver un élément dans l’image de \(f\text{?}\) Quel est l’ensemble qui ne contient aucun élément?
🔗
🔗
Réponse.
L’image de \(f\) est \(\emptyset\text{.}\)
🔗
🔗
Solution.
On montre qu’il est impossible de trouver un élément dans l’image \(f\) à partir de la définition de l’image d’une fonction.
🔗
On suppose que \(b\in \text{Ima}(f)\text{.}\) Par la définition de l’image, on sait que \(b\) possède une préimage, c’est-à-dire qu’il y a un \(a\in \emptyset\) tel que \(f(a)=b\text{.}\) Or, un tel \(a\) ne peut pas exister, car il serait élément de l’ensemble \(\emptyset\text{.}\)
🔗
Il ne peut donc pas y avoir un élément \(b\in \text{Ima}(f)\text{,}\) c’est-à-dire que \(\text{Ima}(f) =\emptyset\text{.}\) Ceci est un exemple par contradiction. On étudiera cette méthode de preuve en plus de détails plus tard.
🔗
🔗
🔗
3.
Soit \(f:A\to B\) une fonction et \(C\subseteq A\) un sous-ensemble de \(A\text{.}\) On définit la restriction de \(f\) sur \(A\) comme étant le sous-ensemble de \(A\times B\) donné par
\begin{equation*} f|_C=\{(c,f(c))\in A\times B~|~ c\in C\}\text{.} \end{equation*}
On écrit parfois aussi \(f(C)=\{f(c)\in B~|~ c\in C\}\text{.}\) C’est le sous-ensemble des images provenant de \(C\text{.}\) On considère à nouveau les fonctions de l’exercice 1.3.6.1.
🔗
(a)
Déterminer \(g(\{3,4,5\})\text{;}\)
🔗
Réponse.
\(g(\{3,4,5\})=\{a,b,c\}\text{.}\)
🔗
🔗
(b)
Déterminer \(f(\{b,c\})\text{;}\)
🔗
Réponse.
\(f(\{b,c\})=\{\#\}\text{.}\)
🔗
🔗
(c)
Déterminer \((f\circ g)(\{3,4,5\})\text{.}\)
🔗
Réponse.
\((f\circ g)(\{3,4,5\})=\{!,\#\}\text{.}\)
🔗
🔗
🔗
4.
Soit \(h:A\to B, g:B\to C\) et \(f:C\to D\) trois fonctions quelconques. Montrer que
\begin{equation*} (f\circ g)\circ h=f\circ (g\circ h)\text{,} \end{equation*}
soit que le composition est associative.
🔗
Solution.
Pour montrer que deux fonctions sont égales, on doit montrer que si on applique les deux fonctions à n’importe quel élément du domaine, on obtient la même image.
🔗
Soit \(a \in A\) un élément quelconque de \(A\text{,}\) on doit montrer que \((f\circ g)\circ h(a)=f\circ (g\circ h)(a)\text{.}\)
🔗
En utilisant la définition de la composition de fonctions à plusieurs reprises, on a
\begin{align*} ({\color{blue}{f\circ g}}) \circ {\color{red}{h (a)}} \amp = ({\color{blue}{f}}\circ {\color{green}{g}})\left( {\color{red}{h(a)}}\right)\\ \amp = {\color{blue}{f}}\left({\color{green}{g}}{\color{red}{\left(h(a)\right)}}\right)\\ \amp = {\color{blue}{f}}\left({\color{green}{g}}\circ {\color{red}{h\left(a\right)}}\right)\\ \amp = {\color{blue}{f}}\left({\color{red}{g\circ h}}\left(a\right)\right)\\ \amp = {\color{blue}{f}}\circ \left({\color{red}{g\circ h}}\right)(a) \end{align*}
🔗
🔗
🔗
5.
Parmi les énoncées suivants, lesquels représentent une définition équivalente du concept de fonction allant de \(A\) vers \(B\text{.:}\)
  1. Une relation \(f:A\to B\) qui satisfait la propriété que si \(f(a_1)\neq f(a_2)\text{,}\) alors \(a_1\neq a_2\) pour tous les \(a_1,a_2\in A\text{.}\)
    🔗
    🔗
  2. Un ensemble \(\{(a,b)~|~a\in A \text{ et } b\in B\}\text{.}\)
    🔗
    🔗
  3. Un ensemble \(\{(a,f(a))~|~a\in A \}\text{,}\) si pour chaque \(a\text{,}\) \(f(a)\) est un élément de \(B\text{.}\)
    🔗
    🔗
🔗
Réponse.
Les énoncés (a) et (c) sont des définitions équivalentes du concept de fonction.
🔗
🔗
Solution.
L’énoncé (a) est une définition de fonction équivalente. Tout élément de \(A\) possède une image unique dans \(B\text{.}\)
🔗
L’énoncé (b) n’est pas une définition d’une fonction. C’est plutôt le produit cartésien.
🔗
L’énoncé (c) est équivalent au concept de fonction puisqu’il correspond aussi à un sous-ensemble de \(A\times B\) où chaque élément de \(A\) possède un seul élément de \(B\) appelé \(f(a)\text{.}\)
🔗
🔗
🔗
6.
Pour chacune des fonctions suivantes, déterminer
  1. L’image de \(42\text{;}\)
    🔗
    🔗
  2. L’image de la fonction;
    🔗
    🔗
  3. La préimage de \(7\text{.}\)
    🔗
    🔗
🔗
(a)
La fonction \(f_1:\Z\to \Z\) qui associe à \(z\in \Z\) son dernier chiffre (de gauche à droite).
🔗
Réponse.
  1. L’image de \(42\) par \(f_1\) est \(f_1(42)=2\text{.}\)
    🔗
  2. L’image de \(f_1\) est \(\text{Ima}(f_1)= \{0,1,2,3,4,5,6,7,8,9\}\text{.}\)
    🔗
  3. La préimage de \(7\) par \(f_1\text{,}\) \(f_1^{-1}(7)\) est l’ensemble des entiers relatifs ayant \(7\) comme dernier chiffre.
    🔗
🔗
🔗
(b)
La fonction \(f_2:\N\to \N\) qui associe à \(n\in \N\) son premier chiffre (de gauche à droite).
🔗
Réponse.
  1. L’image de \(42\) par \(f_2\) est \(f_2(42)=4\text{.}\)
    🔗
  2. L’image de \(f_2\) est \(\text{Ima}(f_2)= \{0,1,2,3,4,5,6,7,8,9\}\text{.}\)
    🔗
  3. La préimage de \(7\) par \(f_2\text{,}\) \(f_2^{-1}(7)\) est l’ensemble des entiers naturels ayant \(7\) comme premier chiffre.
    🔗
🔗
🔗
(c)
La fonction \(f_3:\R\to \R\) qui associe à un nombre \(r\in\R\) le plus petit entier supérieur ou égal à \(r\text{.}\)
🔗
Réponse.
  1. L’image de \(42\) par \(f_3\) est \(f_3(42)=42\text{.}\)
    🔗
  2. L’image de \(f_3\) est \(\text{Ima}(f_3)= \Z\text{.}\)
    🔗
  3. La préimage de \(7\) par \(f_3\) est \(f_3^{-1}(7)=]6,7]\text{.}\)
    🔗
🔗
🔗
(d)
La fonction \(f_4:\R\to \R\) qui associe à un nombre \(r\in\R\) le plus grand entier inférieur ou égal à \(r\text{.}\)
🔗
Réponse.
  1. L’image de \(42\) par \(f_4\) est \(f_3(42)=42\)
    🔗
  2. L’image de \(f_4\) est \(\text{Ima}(f_4)= \Z\text{.}\)
    🔗
  3. La préimage de \(7\) par \(f_4\) est \(f_4^{-1}(7)=[7,8[\text{.}\)
    🔗
🔗
🔗
🔗
7.
Soit \(f,g,h\) des fonctions définies de \(\Z\) vers \(\Z\) par \(f(n)=n^2,g(n)=n-1\) et \(h(n)=n+1\text{.}\) Donner une formule pour les compositions suivantes.
🔗
(a)
\(f\circ g\circ h\)
🔗
Réponse.
\(f\circ g\circ h (n) = n^2\text{.}\)
🔗
Solution.
On a
\begin{align*} (f\circ g\circ h)(n)&=f(g(h(n)))\\ &=f(g(n+1))\\ &=f(n+1-1)\\ &=f(n)\\ &=n^2 \end{align*}
🔗
🔗
🔗
(b)
\(g\circ f\circ h\)
🔗
Réponse.
\(g\circ f\circ h (n) = n^2+2n\text{.}\)
🔗
Solution.
On a
\begin{align*} g\circ f\circ h&=g(f(h(n)))\\ &=g(f(n+1))\\ &=g((n+1)^2)\\ &=g(n^2+2n+1)\\ &=n^2+2n+1-1\\ &=n^2+2n \end{align*}
🔗
🔗
🔗
(c)
\(h\circ f\circ g\)
🔗
Réponse.
\(h\circ f\circ g (n) = n^2-2n+2\text{.}\)
🔗
Solution.
On a
\begin{align*} h\circ f\circ g&=h(f(g(n)))\\ &=h(f(n-1))\\ &=h((n-1)^2)\\ &=h(n^2-2n+1)\\ &=n^2-2n+1+1\\ &=n^2-2n+2 \end{align*}
🔗
🔗
🔗
🔗
8.
Soit \(A,B\) deux ensembles et \(f:A\to B\) une fonction. Soit \(C,D\subseteq A\) deux sous-ensembles de \(A\text{.}\) Montrer que
🔗
(a)
\(f(C\cup D)=f(C)\cup f(D)\text{;}\)
🔗
Solution.
On montre que \(f(C\cup D)\subseteq f(C)\cup f(D)\text{,}\) et ensuite que \(f(C)\cup f(D)\subseteq f(C\cup D)\text{.}\)
🔗
Soit \(b \in f(C\cup D)\text{,}\) on veut montrer que \(b \in f(C)\cup f(D)\text{.}\) Puisque \(b \in f(C\cup D)\text{,}\) il existe \(a\in C\cup D\) tel que \(f(a)=b\text{.}\) Puisque \(a\in C\cup D\text{,}\) alors soit \(a \in C\text{,}\) ou bien \(a \in D\text{.}\) Si \(a \in C\text{,}\) alors \(b\in f(C)\text{.}\) Si \(a \in f(D)\text{,}\) alors \(b\in f(D)\text{.}\) Ainsi, on a montré que \(b\in f(C)\) ou bien \(b\in f(D)\text{,}\) c’est-à-dire que \(a \in f(C)\cup f(D)\text{.}\) On a donc \(f(C\cup D)\subseteq f(C)\cup f(D)\text{.}\)
🔗
Soit \(b\in f(C) \cup f(D)\text{,}\) on veut montrer que \(b \in f(C\cup D)\text{.}\) Puisque \(b\in f(C) \cup f(D)\text{,}\) alors soit \(b\in f(C)\text{,}\) ou bien \(b\in f(D)\text{.}\) Si \(b\in f(C)\text{,}\) alors \(b=f(a)\) pour un \(a\in C \subseteq C\cup D\text{,}\) et donc \(b\in f(C\cup D)\text{.}\) Sinon, \(b\in f(D)\text{,}\) et alors \(b=f(a)\) pour un \(a\in D \subseteq C\cup D\text{,}\) et donc \(b\in f(C\cup D)\text{.}\) ON a donc montré que \(f(C)\cup f(D)\subseteq f(C\cup D)\text{.}\)
🔗
Puisqu’on a que \(f(C\cup D)\subseteq f(C)\cup f(D)\) et que \(f(C)\cup f(D)\subseteq f(C\cup D)\text{,}\) on a montré que \(f(C\cup D) = f(C)\cup f(D)\text{.}\)
🔗
🔗
🔗
(b)
\(f(C\cap D)\subseteq f(C)\cap f(D)\text{;}\)
🔗
Solution.
Soit \(b \in f(C\cap D)\text{,}\) alors il existe \(a\in C\cap D\) tel que \(f(a)=b\text{.}\) Puisque \(a\in C\) et \(a \in D\text{,}\) on a que \(b \in f(C)\) et \(b \in f(D)\text{.}\) On a donc \(b \in f(C)\cap f(D)\text{,}\) d’où \(f(C \cap D) \subseteq f(C) \cap f(D)\text{.}\)
🔗
🔗
🔗
(c)
Trouver deux ensembles \(A,B\) et des sous-ensembles \(C,D\subseteq A\) tels que
pour lesquels
🔗
(i)
\(f(C\cap D)=f(C)\cap f(D)\)
🔗
Réponse 1.
Soit \(A=\{0,1,2,3\},B=\{0,1,2\},C=\{0,1,2\}\) et \(D=\{2,3\}\) avec \(f(0)=0,f(1)=1,f(2)=1,f(3)=2\text{.}\)
🔗
🔗
Réponse 2.
On prend \(A=\R\text{,}\) \(B=\R\text{,}\) \(C=[1,3]\) et \(D=[2,4]\text{,}\) avec \(f:A \rightarrow B\) définie par \(f(x)=x^2\text{.}\) Ainsi, \(C\cap D= [2,3]\text{,}\) \(f(C\cap D)=[4,9]\text{,}\) \(f(C)=[1,9]\text{,}\) \(f(D)=[4,16]\) et donc \(f(C)\cap f(D) = [4,9]\) .
🔗
🔗
🔗
(ii)
\(f(C\cap D)\subset f(C)\cap f(D)\)
🔗
Réponse 1.
Soit \(A=\{0,1,2,3\},B=\{0,1,2\},C=\{0,1,2\}\) et \(D=\{2,3\}\) avec \(f(0)=0,f(1)=1,f(2)=2,f(3)=1\text{.}\)
🔗
🔗
Réponse 2.
On prend \(A=\R\text{,}\) \(B=\R\text{,}\) \(C=[-1,0]\) et \(D=[0,1]\text{,}\) avec \(f:A \rightarrow B\) définie par \(f(x)=x^2\text{.}\) Ainsi, \(C\cap D= \{0\}\text{,}\) \(f(C\cap D)=\{0\}\text{,}\) \(f(C)=[0,1]\text{,}\) \(f(D)=[0,1]\) et donc \(f(C)\cap f(D) = [0,1]\text{.}\)
🔗
🔗
🔗
🔗
🔗
9.
Soit \(A\) un ensemble et soit \(C\subseteq A\) un sous-ensemble. La fonction caractéristique de \(C\text{,}\) notée \(\mathbb{1}_C\) est une fonction de \(A\) vers \(\{0,1\}\) définie par
\begin{equation*} \mathbb{1}_C(a)=\begin{cases} 1 & \text{ si } a\in C \\ 0 & \text{ si } a\notin C \end{cases} \end{equation*}
.
🔗
(a)
À titre d’exemple, on considère l’ensemble \(A=\{a,b,c\}\) et le sous-ensemble \(C=\{a,b\}\text{.}\) Quels sont les éléments de \(\mathbb{1}_C\text{?}\)
🔗
Réponse.
\(\mathbb{1}_C = \{(a,1),(b,1),(c,0)\}\text{.}\) Ainsi, on a \(\mathbb{1}_C(a)=1\text{,}\) \(\mathbb{1}_C(b)=1\) et \(\mathbb{1}_C(c)=0\text{.}\)
🔗
🔗
🔗
(b)
Pour des ensembles \(C,D\subseteq A\) quelconques, montrer que \(\mathbb{1}_{C\cap D}=\mathbb{1}_C\cdot\mathbb{1}_D\text{.}\)
🔗
Solution.
Soit \(a\in A\text{,}\) on veut comparer \(\mathbb{1}_C(a)\cdot \mathbb{1}_D(a)\) à \(\mathbb{1}_{C\cap D}(a)\text{.}\)
🔗
Si \(a\in C\cap D\text{,}\) alors \(\mathbb{1}_{C\cap D}(a)=1\text{.}\) De plus, on a que \(a\in C\) et \(a \in D\text{.}\) Ainsi, \(\mathbb{1}_C(a)\cdot \mathbb{1}_D(a)=1\cdot 1=1\)
🔗
Si \(a\notin C\cap D\text{,}\) alors \(\mathbb{1}_{C\cap D}(a)=0\text{.}\) De plus, on a que \(a\notin C\) (c’est-à-dire que \(\mathbb{1}_C(a)=0\)) ou \(a \notin D\) (c’est-à-dire que \(\mathbb{1}_D(a)=0\)). Dans les deux cas, on a \(\mathbb{1}_C(a)\cdot \mathbb{1}_D(a)=0\text{.}\)
🔗
🔗
🔗
(c)
Pour des ensembles \(C,D\subseteq A\) quelconques, montrer que \(\mathbb{1}_{C\cup D}=\mathbb{1}_C+\mathbb{1}_D-\mathbb{1}_C\cdot\mathbb{1}_D\text{.}\)
🔗
Solution 1.
Soit \(a\in A\text{,}\) on veut comparer \(\mathbb{1}_C(a)+ \mathbb{1}_D(a)-\mathbb{1}_C(a)\cdot \mathbb{1}_D(a)\) à \(\mathbb{1}_{C\cup D}(a)\text{.}\)
🔗
Si \(a\in C\cup D\text{,}\) alors \(\mathbb{1}_{C\cup D}(a)=1\text{.}\) On veut montrer que \(\mathbb{1}_C(a)+\mathbb{1}_D(a)-\mathbb{1}_C(a)\cdot \mathbb{1}_D(a)=1\text{.}\) Pour ce faire, on doit séparer le cas où \(a\in C\cap D\) du cas où \(a\notin C\cap D\text{.}\)
🔗
Par la partie précédente, on sait que \(\mathbb{1}_{C\cap D}=\mathbb{1}_C\cdot \mathbb{1}_D\text{.}\) Ainsi, si \(a\in C\cap D\text{,}\) alors \(\mathbb{1}_C(a)+\mathbb{1}_D(a)-\mathbb{1}_C(a)\cdot \mathbb{1}_D(a)=1+1-1=1\) .
🔗
Si on a plutôt \(a\notin C\cap D\text{,}\) alors puisqu’on sait que \(a \in C\cup D\text{,}\) on a que \(a \in C\cap D^c\) ou bien \(a\in C^c\cap D\text{.}\) Dans les deux cas, on a \(\mathbb{1}_C(a)+\mathbb{1}_D(a)-\mathbb{1}_C(a)\cdot \mathbb{1}_D(a)=1+0-0=1\)
🔗
Finalement, si \(a\notin C\cup D\text{,}\) alors \(\mathbb{1}_{C\cap D}(a)=0\text{.}\) De plus, on a que \(a\notin C\) et \(a \notin D\text{.}\) Ainsi, \(\mathbb{1}_C(a)+\mathbb{1}_D(a)-\mathbb{1}_C(a)\cdot \mathbb{1}_D(a)=0+0-0\cdot 0=0\text{.}\)
🔗
🔗
Solution 2.
On peut aussi montrer l’égalité à l’aide d’une table d’appartenance, à laquelle on ajoute des colones pour les valeurs des fonctions.
🔗
Table 1.3.21. Table d’appartenance pour l’exercice
🔗
\(C\) \(D\) \(C\cup D\) \(C\cap D\) \(\mathbb{1}_C\) \(\mathbb{1}_D \) \(\mathbb{1}_{C\cup D}\) \(\mathbb{1}_{C}\cdot \mathbb{1}_{D}\) \(\mathbb{1}_C+\mathbb{1}_D-\mathbb{1}_{C}\cdot \mathbb{1}_{D}\)
oui non oui non 1 0 1 0 1
oui oui oui oui 1 1 1 1 1
non non non non 0 0 0 0 0
non oui oui non 0 1 1 0 1
🔗
🔗
(d)
Trouver une expression pour la fonction caractéristique du complément de \(C\) en fonction de celle de \(C\text{.}\)
🔗
Réponse.
\(\mathbb{1}_{C^c}=1-\mathbb{1}_C\text{.}\)
🔗
🔗
🔗
🔗
10.
On considère les ensembles \(A=\{0,1\}\) et \(B=\{a,b,c\}\text{.}\) Dans le chapitre 4, nous verrons des méthodes plus générales pour compter des obtets. Pour l’instant, vous pouvez utiliser un argument intuitif ou énumérer les fonctions demandées.
🔗
(a)
On considère les fonctions de \(A\) vers \(B\text{.}\)
🔗
(i)
Combien y a-t-il de fonctions possibles?
🔗
Réponse.
Il y a \(3^2=9\) fonctions de \(A\) vers \(B\text{.}\)
🔗
🔗
Solution.
Comme chaque élément de \(A\) doit avoir une image dans \(B\) et qu’il y a \(2\) éléments dans \(A\) et \(3\) dans \(B\text{,}\) on a \(3\) choix d’image pour \(0\) et \(3\) choix d’image pour \(1\text{,}\) ce qui donne \(3^2\) fonctions possibles.
🔗
🔗
🔗
(ii)
Combien sont injectives? Si possible, donner un exemple.
🔗
Réponse.
Il y a \(3\cdot 2 = 6\) fonctions injectives de \(A\) vers \(B\text{.}\) Une telle fonction est la fonction définie par \(f(0)=a\) et \(f(1)=b\text{.}\)
🔗
🔗
Solution.
Pour qu’une fonction soit injective, les éléments du domaine doivent avoir des images différentes. On a \(3\) choix pour l’image de \(0\) et, pour chacun de ces choix, \(2\) choix restant pour l’image de \(1\text{,}\) pour un total de \(3\times 2=6\) choix.
🔗
🔗
🔗
(iii)
Combien sont surjectives? Si possible, donner un exemple.
🔗
Réponse.
Il n’y a aucune fonction surjective de \(A\) vers \(B\text{.}\)
🔗
🔗
🔗
(iv)
Combien sont bijectives? Si possible, donner un exemple.
🔗
Réponse.
Il n’y a aucune fonction bijective de \(A\) vers \(B\text{.}\)
🔗
🔗
🔗
🔗
(b)
Répondre aux mêmes questions, mais avec les fonctions de \(B\) vers \(A\text{.}\)
🔗
(i)
Combien y a-t-il de fonctions possibles?
🔗
Réponse.
Il y a \(2^3=8\) fonctions de \(B\) vers \(A\text{.}\)
🔗
🔗
🔗
(ii)
Combien sont injectives? Si possible, donner un exemple.
🔗
Réponse.
Il n’y a aucune fonction injective de \(B\) vers \(A\text{.}\)
🔗
🔗
Solution.
Comme l’image ne contient que deux éléments, mais le domaine en contient trois, il est impossible que chaque élément du domane ait une image différente des autres. Ainsi, il n’y a pas de fonction injective.
🔗
🔗
🔗
(iii)
Combien sont surjectives? Si possible, donner un exemple.
🔗
Réponse.
Il y a \(6\) fonctions surjectives de \(B\) vers \(A\text{.}\) Une telle fonction est la fonction définie par \(f(a)=f(b)=0\) et \(f(c)=1\text{.}\)
🔗
🔗
Solution.
Le problème général de déterminer le nombre de fonctions surjective entre deux ensembles est complexe. Lorsque les cardinalités des ensembles sont petites, on peut les énumérer. En voici une liste:
\begin{align*} f_1&=\{(a,0),(b,0),(c,1)\}\\ f_2&=\{(a,0),(b,1),(c,0)\}\\ f_3&=\{(a,1),(b,0),(c,0)\}\\ f_4&=\{(a,0),(b,1),(c,1)\}\\ f_5&=\{(a,1),(b,1),(c,0)\}\\ f_6&=\{(a,1),(b,0),(c,1)\}\text{.} \end{align*}
Dans ce cas-ci, une autre manière de les compter est de prendre le nombre total de fonctions de \(A\) vers \(B\text{,}\) soit \(8\) et de soustraire les fonctions qui ne sont pas surjectives. Comme l’image ne possède que deux éléments, une fonction qui n’est pas surjective est nécessairement une fonction pour laquelle tous les éléments sont envoyés vers la même image. Il y a deux fonctions ayant cette propriété. Le nombre de fonctions surjective est donc \(8-2=6\text{.}\)
🔗
🔗
🔗
(iv)
Combien sont bijectives? Si possible, donner un exemple.
🔗
Réponse.
Il n’y a aucune fonction bijective de \(B\) vers \(A\text{.}\)
🔗
🔗
🔗
🔗
🔗
11.
Que peut-on dire de la cardinalité des ensembles \(A,B\) s’il existe une fonction \(f:A\to B\) qui est
🔗
(a)
injective? Justifier
🔗
Solution.
Si \(f\) est injective, alors \(|A|\leq |B|\text{.}\) En effet, pour chaque élément \(a\in A\text{,}\) il existe un élément \(b=f(a)\text{.}\) De plus, tous ces éléments sont différents, puisque si \(a_1 \neq a_2\text{,}\) alors \(f(a_1) \neq f(a_2)\text{,}\) par l’injectivité de \(f\text{.}\)
🔗
🔗
🔗
(b)
surjective? Justifier
🔗
Solution.
Si \(f\) est surjective, alors \(|A|\geq |B|\text{.}\) En effet, puisque \(f\) est surjective, pour chaque élément \(b\in B\text{,}\) il existe un \(a\in A\text{,}\) différent pour chaque \(b\text{,}\) tel que \(f(a)=b\text{.}\)
🔗
🔗
🔗
(c)
bijective? Justifier
🔗
Solution.
Si \(f\) est bijective, alors \(|A|= |B|\text{.}\) En effet, si \(f\) est bijective, alors \(f\) est injective et surjective. Par \((a)\text{,}\) on a que \(|A|\leq |B|\text{,}\) alors que par \((b)\text{,}\) on a que \(|A|\geq |B|\text{.}\) Les deux inégalités nous donnent que \(|A|=|B|\text{.}\)
🔗
🔗
🔗
🔗
12.
Donner une fonction de \(\N\) vers \(\N\) qui est
🔗
(b)
surjective, mais pas injective;
🔗
Réponse.
\begin{equation*} f_b(n)=\begin{cases} 0 & \text{ si } n=0 \\ n-1& \text{ sinon } \end{cases}\text{.} \end{equation*}
Cette fonction a deux préimages pour \(0\text{,}\) soit \(0\) et \(1\text{.}\) Elle n’est donc pas injective. Par contre, elle est surjective puisque tout naturel \(n\in \mathbb{N}\) est atteint par \(n+1\text{.}\)
🔗
🔗
🔗
(c)
bijective;
🔗
Réponse 1.
Un exemple simple est d’envoyer chaque naturel sur lui-même, soit \(f_c(n)=n\text{.}\)
🔗
🔗
Réponse 2.
Voici un exemple un peu plus complexe:
🔗
\begin{equation*} g_c(n)=\begin{cases} n+1 & \text{ si } n \text{ est pair.} \\ n-1& \text{ sinon.} \end{cases}\text{.} \end{equation*}
🔗
🔗
(d)
ni injective ni surjective.
🔗
Réponse.
\(f_d(n)=0\) pour tout naturel \(n\in \mathbb{N}\text{.}\)
🔗
🔗
🔗
🔗
13.
Soit \(g:A\to B\) et \(f:B\to C\) des fonctions.
🔗
(a)
Montrer que si \(f,g\) sont injectives, alors \(f\circ g\) l’est aussi.
🔗
Solution.
Pour montrer que \(f\circ g\) est injective, on doit montrer que, soit \(a_1,\ a_2\in A\) deux éléments quelconques de \(A\) tels que \(f\circ g(a_1) = f\circ g(a_2)\text{,}\) alors \(a_1=a_2\text{.}\) Par définition de \(f\circ g\text{,}\) si \(f\circ g(a_1) = f\circ g(a_2)\text{,}\) on a que
\begin{align*} f(g(a_1))& = f(g(a_2)) \amp\\ g(a_1)& = g(a_2)\amp\text{ car } f \text{ est injective} \\ a_1& = a_2\amp\text{ car } g \text{ est injective} \end{align*}
Ainsi, \(f\circ g\) est injective.
🔗
🔗
🔗
(b)
Montrer que si \(f,g\) sont surjectives, alors \(f\circ g\) l’est aussi.
🔗
Solution.
Pour montrer que \(f\circ g\) est surjective, on doit montrer que pour tout élément \(c \in C\text{,}\) on peut trouver un élément \(a \in A\) tel que \(f\circ g(a)=c\text{.}\) Soit \(c \in C\text{,}\) puisque \(f\) est surjective, il existe \(b\in B\) tel que \(\color{red}{f(b)=c}\text{.}\) De plus, puisque \(g\) est surjective, il existe \(a \in A\) tel que \(\color{green}{g(a)=b}\text{.}\) Ainsi,
\begin{equation*} f\circ g(a)=f({\color{green}{g(a)}})=f({\color{green}{b}})={\color{red}{f(b)}}={\color{red}{c}}\text{,} \end{equation*}
et donc \(f\circ g\) est surjective.
🔗
🔗
🔗
🔗
14.
Montrer que si \(g:A\to B\) et \(f:B\to C\) sont deux fonctions inversibles, alors la composition est inversible et
\begin{equation*} (f\circ g)^{-1}=g^{-1}\circ f^{-1} \text{.} \end{equation*}
🔗
Solution.
Par l’exercice 1.3.6.13, on sait que \(f\circ g\) est injective et surjective, et donc bijective et inversible. Il ne reste qu’à montrer que pour tout \(a \in A\text{,}\) et pour tout \(c\in C\)
\begin{equation*} (g^{-1}\circ f^{-1}) \circ (f\circ g) (a) = a \end{equation*}
et
\begin{equation*} (f\circ g)\circ (g^{-1}\circ f^{-1})(c) = c. \end{equation*}
🔗
\begin{align*} (g^{-1}\circ f^{-1}) \circ (f\circ g) (a) &= (g^{-1}\circ f^{-1}) ((f\circ g)(a))\\ &= (g^{-1}\circ f^{-1}) (f(g(a)))\\ &= g^{-1}(f^{-1} (f(g(a))))\\ &= g^{-1}(g(a)) = a \end{align*}
\begin{align*} (f\circ g) \circ (g^{-1}\circ f^{-1}) (c) &= (g\circ f) ((g^{-1}\circ f^{-1})(c))\\ &= (f\circ g) (g^{-1}(f^{-1}(c)))\\ &= f(g (g^{-1}(f^{-1}(c))))\\ &= f(f^{-1}(c)) = c \end{align*}
\begin{equation*} (f\circ g)\circ (g^{-1}\circ f^{-1})(x) = x. \end{equation*}
🔗
🔗
🔗

Exercices supplémentaires.

15.
Dans cet exercice, \(f^{-1}\) fait référence à la préimage de \(f\text{,}\) pas nécessairement à l’inverse.
🔗
Soit \(f:A\to B\) une fonction et soit \(C\subseteq A\) et \(D\subseteq B\) des sous-ensembles. Analyser les égalités suivantes. Sont-elles toujours/jamais vraies ou seulement parfois? Si c’est parfois, quelle propriété doit avoir \(f\) pour garantir qu’elles soient vraies.
🔗
(a)
\(f^{-1}(f(C))=C\)
🔗
Solution.
Si \(A=B=\R\text{,}\) \(f(x)=x^2\) et \(C=[0,1]\text{,}\) alors \(f(C)=[0,1]\) et \(f^{-1}(f(C))=f^{-1}([0,1])=[-1,1]\neq [0,1]\text{.}\) Ainsi, l’égalité ne peut pas être toujours vraie.
🔗
On peut montrer que l’inclusion \(C\subseteq f^{-1}(f(C))\) est vérifiée. En effet, si \(c\in C\text{,}\) alors par définition, \(f(c)\in f(C)\text{,}\) et donc \(c\in f^{-1}(f(C))\text{.}\)
🔗
Supposons maintenant que \(f\) est une fonction injective. On veut montrer que \(f^{-1}(f(C))\subseteq C\text{.}\) Soit \(x \in f^{-1}(f(C))\text{,}\) alors \(f(x)\in f(C)\text{,}\) par définition de \(f^{-1}\text{.}\) Puisque \(f(x) \in f(C)\text{,}\) il existe \(c\in C\) tel que \(f(c)=f(x)\text{.}\) Mais on a supposé que \(f\) est injective, d’où \(c=x\text{,}\) et donc \(x\in C\text{.}\) On a donc bien montré que \(f^{-1}(f(C))\subseteq C\text{.}\)
🔗
Ainsi, l’égalité est parfois vraie, parfois fausse. Elle sera toujours vraie si \(f\) est injective.
🔗
🔗
🔗
(b)
\(f(f^{-1}(D))=D\)
🔗
Solution.
Si \(A=B=\R\text{,}\) \(f(x)=x^2\) et \(D=[-1,1]\text{,}\) alors \(f^{-1}(D)=[0,1]\) et \(f(f^{-1}(D))=f([0,1])=[0,1]\neq [-1,1]\text{.}\) Ainsi, l’égalité ne peut pas être toujours vraie.
🔗
On peut montrer que l’inclusion \(f(f^{-1}(D))\subseteq D\text{.}\) En effet, si \(a \in f(f^{-1}(D))\text{,}\) alors par définition, il existe un élément \(x \in f^{-1}(D)\) tel que \(f(x)=d\text{.}\) Par définition de \(f^{-1}(D)\text{,}\) on a que \(f(x)\in D \text{,}\) et donc \(d=f(x)\in D\text{.}\)
🔗
Supposons maintenant que \(f\) est une fonction surjective. On veut montrer que \(D \subseteq f(f^{-1}(D))\text{.}\) Soit \(d \in D\text{,}\) puisque \(f\) est une fonction surjective, il existe un élément \(a \in A\) tel que \(d=f(a)\text{.}\) Ainsi, on a que \(a \in f^{-1}(D)\text{,}\) et donc \(d=f(a)\in f(f^{-1}(D))\text{.}\) On a donc bien montré que \(D\subseteq f(f^{-1}(D))\text{.}\)
🔗
Ainsi, l’égalité est parfois vraie, parfois fausse. Elle sera toujours vraie si \(f\) est surjective.
🔗
🔗
🔗
🔗
16. La cardinalité et l’infini.
Y a-t-il plus de nombres naturels que de nombres naturels pairs? À priori, cela peut sembler évident puisque les nombres pairs sont inclus dans les naturels et que certains naturels ne sont pas pairs. Dénontant les nombres pairs par \(2\N\text{,}\) on a donc \(2\N\subset \N\text{.}\) Or les deux ensembles contiennent une infinité d’éléments. Ont-ils donc la même cardinalité? Comment la cardinalité de ces deux ensembles se compare-t-elle par rapport à la cardinalité des nombres réels compris entre \(0\) et \(1\text{?}\)
🔗
Ces questions ont longtemps embêté les mathématiciens et c’est la notion de bijection qui est venue trancher le débat.
🔗
On dit que deux ensembles \(A,B\) ont la même cardinalité s’il existe une bijection entre \(A\) et \(B\text{.}\) Le principe est évident et anodin pour les ensembles de cardinalité finie, mais apporte son lot de surprise pour les ensembles infinis.
🔗
(a)
Trouver une bijection entre les nombres naturels et les nombres naturels pairs. Ceci montre que \(|\N|=|2\N|\text{,}\) même si \(2\N\subset \N\text{.}\)
🔗
Un ensemble qui a la même cardinalité que \(\N\) ou qui est de cardinalité finie est dit dénombrable.
🔗
Réponse 1.
\(f(n)=2n\)
🔗
🔗
Réponse 2.
On considère \(f:\N\to 2\N\) la fonction définie par \(f(n)=2n\text{.}\) C’est une bijection. On peut bien le voir dans la table partielle ci-dessous.
🔗
Table 1.3.22. Bijection entre \(\mathbb{N}\) et \(2\mathbb{N}\)
🔗
\(n\) \(f(n)\)
\(0\) \(0\)
\(1\) \(2\)
\(2\) \(4\)
\(3\) \(6\)
\(\vdots\) \(\vdots\)
🔗
🔗
(b)
Trouver une bijection entre \(]0,1[\) et \(\R\text{.}\) Ceci montre que \(\text{Card}\left(]0,1[\right)=\text{Card}\left(\R\right)\text{,}\) même si \(]0,1[ \subset \R\text{.}\)
Indice.
Penser à la fonction \(\tan(x)\text{.}\)
🔗
🔗
Réponse.
La fonction \(f:]0,1[\to \R\) définie par \(f(x)=\tan\left( \pi x - \frac{\pi}{2}\right)\) est une bijection.
🔗
La fonction est illustrée. On voit que c’est une bijection entre les ensembles.
Figure 1.3.23. La fonction \(\tan\left( \pi x - \frac{\pi}{2}\right)\)
🔗
🔗
🔗
(c)
On considère maintenant l’ensemble \(\N\) et l’ensemble \(]0,1[\) des nombres réels compris entre \(0\) et \(1\) (exclusivement, mais ce n’est pas important). On suppose qu’il existe une bijection entre ces deux ensembles. En particulier, on peut déterminer l’image de chaque naturel et lui associer un réel. On peut donc lister les nombres réels. Voici à quoi ressemblerait cette liste:
\begin{align*} f(0)&=0.d_{0,0}d_{0,1}d_{0,2}d_{0,3}d_{0,4}\cdots\\ f(1)&=0.d_{1,0}d_{1,1}d_{1,2}d_{1,3}d_{1,4}\cdots\\ f(2)&=0.d_{2,0}d_{2,1}d_{2,2}d_{2,3}d_{2,4}\cdots\\ f(3)&=0.d_{3,0}d_{3,1}d_{3,2}d_{3,3}d_{3,4}\cdots\\ \vdots&= \vdots\text{.} \end{align*}
🔗
Chaque \(d_{i,j}\) représente un chiffre correspondant à la position décimale. Par exemple, si \(f(2)=0.230984\ldots\text{,}\) alors \(d_{2,0}=2,d_{2,1}=3,d_{2,2}=0\) et ainsi de suite.
🔗
Donc on prétend avoir cette bijection entre les deux ensembles. On considère le nombre réel \(r=0.r_0r_1r_2r_3\cdots\) formé de la manière suivante: \(r_i=1\) si \(d_{i,i}\neq 1\) et \(r_i=2\) si \(d_{i,i}=1\text{.}\) Que peut-on conclure grâce à ce nombre?
🔗
Indice.
Quel nombre naturel a pour image \(r\text{?}\)
🔗
🔗
Solution.
On peut remarquer que le nombre \(r \in ]0,1[\text{,}\) mais \(r\) n’est pas dans l’image de \(f\text{,}\) c’est-à-dire que \(f(n)\neq r\) pour tout \(n \in \N\text{.}\) En effet, si \(r\) était l’image du naturel \(n\text{,}\) alors \(r_n=d_{n,n}\text{.}\) Mais par construction, cela ne peut se produire étant donné que si \(d_{n,n}=1\text{,}\) alors \(r_n=2\) et si \(d_{n,n}\neq 1\text{,}\) on a posé \(r_n=1\text{.}\)
🔗
On dit que \(r\) a été construit en prenant la diagonale de la liste
\begin{align*} f(0)&=0.d_{0,0}d_{0,1}d_{0,2}d_{0,3}d_{0,4}\cdots\\ f(1)&=0.d_{1,0}d_{1,1}d_{1,2}d_{1,3}d_{1,4}\cdots\\ f(2)&=0.d_{2,0}d_{2,1}d_{2,2}d_{2,3}d_{2,4}\cdots\\ f(3)&=0.d_{3,0}d_{3,1}d_{3,2}d_{3,3}d_{3,4}\cdots\\ \vdots&= \vdots \end{align*}
, pour ensuite changer chacun des termes, c’est- a-dire que \(r_i\neq d_{i,i}\text{.}\) Ainsi, \(f\) ne peut pas être une bijection, ce qui est en contradiction avec notre hypothèse initiale. Il n’existe donc pas de bijection entre \(\N\) et \(]0,1[\text{.}\) Par 1.3.6.16.b, il ne peut pas y avoir de bijection entre \(\N\) et \(\R\text{.}\) En fait \(|\N| \lt |\R|\text{.}\)
🔗
🔗
🔗
🔗
17.
Soit \(A=\{n\in\N~|~ 1\leq n\leq 12\}\) et \(B=\{1,2,3,4,6,12\}\text{.}\) On définit la relation \(PGCD_{12}:A\to B\) qui associe à \(a\in A\) le plus grand commun diviseur de \(a\) et \(12\text{.}\)
🔗
(a)
Montrer que cette relation est une fonction.
🔗
Solution.
Pour chaque nombre dans \(A\text{,}\) il n’y a qu’un seul plus grand commun diviseur avec \(12\text{.}\) On a donc bel et bien une fonction.
🔗
🔗
🔗
(c)
Déterminer la préimage de \(3\text{.}\)
🔗
Réponse.
La préimage de \(3\) est \(\{3,9\}\text{.}\)
🔗
🔗
🔗
(d)
Est-ce que la fonction est injective? Surjective?
🔗
Réponse.
Surjective, mais pas injective.
🔗
🔗
🔗
🔗
18.
On considère la fonction caractéristique définie à l’exercice 1.3.6.9 et la différence symétrique de l’exercice 1.2.4.5. Montrer que
\begin{equation*} \mathbb{1}_{A\oplus B}=\mathbb{1}_A+\mathbb{1}_B-2\mathbb{1}_{A\cap B}\text{.} \end{equation*}
🔗
Solution.
On peut construire une table d’appartenance:
🔗
Table 1.3.24. Table d’appartenance pour l’exercice
🔗
\(A\) \(B\) \(A\cap B\) \(A\oplus B\) \(\mathbb{1}_A\) \(\mathbb{1}_B\) \(\mathbb{1}_{A\cap B}\) \(\mathbb{1}_{A\oplus B}\) \(\mathbb{1}_{A}+\mathbb{1}_{B}-2\mathbb{1}_{A\cap B}\)
oui oui oui non \(1\) \(1\) \(1\) \(0\) \(0\)
oui non non oui \(1\) \(0\) \(0\) \(1\) \(1\)
non oui non oui \(0\) \(1\) \(0\) \(1\) \(1\)
non non non non \(0\) \(0\) \(0\) \(0\) \(0\)
Comme les deux dernières colonnes sont identiques, on peut conclure à leur égalité.
🔗
🔗
🔗
19.
(a)
Soit \(A\subseteq \mathbb{N}\text{.}\) Montrer que la cardinalité de \(A\) est finie ou infinie dénombrable.
🔗
Solution.
Si la cardinalité de \(A\) est finie, il n’y a rien à montrer. On considère donc le cas où l’ensemble \(A\) possède une infinité d’éléments et on trouve une bijection entre \(A\) et \(\mathbb{N}\text{.}\)
🔗
On considère la fonction \(f:\mathbb{N}\to A\) définie comme suit:
  1. On pose \(f(0)\) le plus petit naturel dans l’ensemble \(A\text{.}\)
    🔗
    🔗
  2. Soit \(A_1=A-\{f(0)\}\text{.}\) Cet ensemble est non vide puisque la cardinalité de \(A\) est infinie. On pose \(f(1)\) le plus petit naturel de cet ensemble.
    🔗
    🔗
  3. Pour tout naturel \(n\geq 2\text{,}\) on pose \(A_n=A-\{f(0),f(1),\ldots f(n-1)\}\text{.}\) L’image de \(g(n)\) est le plus petit naturel de \(A_n\text{.}\)
    🔗
    🔗
🔗
Il faut montrer que cette fonction est bijective. D’une part, elle est surjective puisque chaque élément de \(A\) est atteint. En effet, si on place les éléments de \(A\) en ordre croissant, l’élément en position \(k\) a comme préimage le naturel \(k-1\text{.}\) De l’autre côté, elle est injective puisque, par construction, deux naturels ne peuvent pas avoir la même image étant donné qu’une fois atteint, un nombre est retiré de l’ensemble \(A\) pour les prochains naturels.
🔗
Puisqu’une bijection entre \(\mathbb{N}\) et \(A\) existe, la cardinalité de \(A\) est infinie dénombrable.
🔗
🔗
🔗
(b)
Soit \(A\subseteq B\) des ensembles avec \(B\) de cardinalité infinie dénombrable. Montrer que \(A\) est aussi dénombrable (finie ou infinie).
🔗
Solution.
Deux cas sont possible, soit \(A\) possède un nombre fini d’éléments, soit il en possède une infinité. Dans le premier cas, il n’y a rien à montrer. On considère donc un sous-ensemble \(A\) de \(B\) qui possède une infinité d’éléments. Parce que \(B\) est de cardinalité infini dénombrable, il existe une bijection entre \(B\) et \(\mathbb{N}\text{,}\) soit \(f:B\to \mathbb{N}\text{.}\) On considère la fonction \(g:A\to f(A)\) donnée par la restriction de \(f\) sur \(A\text{:}\)
\begin{equation*} g(n)=\left.f\right_A(n)\text{.} \end{equation*}
🔗
Parce que \(A\) est de cardinalité infinie et que \(f\) est une bijection, l’ensemble \(f(A)\subseteq \mathbb{N}\) avec cardinalité infinie. De plus, la fonction \(g\) est aussi une bijection entre \(A\) et \(f(A)\text{.}\) Selon la partie précédente, la cardinalité de \(f(A)\) est dénombrable. Ainsi la cardinalité de \(A\) l’est également.
🔗
🔗
🔗
🔗
20.
Soit \(A,B\) deux ensembles de cardinalité infinie dénombrable.
🔗
(a)
Si \(A\cap B=\emptyset\text{,}\) trouver une bijection entre \(\N\) et \(A\cup B\) pour montrer que l’union est aussi dénombrable.
🔗
Solution 1.
Si on est capable de donner une liste de tous les éléments de \(A\cup B\text{,}\) alors l’ensemble est dénombrable. Comme \(A\) et \(B\) sont dénombrables, un telle liste existe pour chacun de ces ensembles. Il suffit d’alterner entre les éléments de \(A\) et ceux de \(B\text{:}\)
🔗
Table 1.3.25. Énumération de \(A\cup B\)
🔗
\(n\) Éléments de \(A\cup B\)
\(1\) \(a_1\)
\(2\) \(b_1\)
\(3\) \(a_2\)
\(4\) \(b_2\)
\(5\) \(a_3\)
\(6\) \(B_3\)
\(\vdots\) \(\vdots\)
🔗
Solution 2.
Si \(A\) et \(B\) sont de cardinalité infinie dénombrable, alors il existe des bijections \(f:\mathbb{N}\to A\) et \(g:\mathbb{N}\to B\text{.}\) On peut créer une nouvelle bijection à partir de ces fonctions de la manière suivante:
\begin{equation*} h(n)=\begin{cases} f\left(\frac{n}{2}\right) & \text{ si } n \text{ est pair}\\ g\left(\frac{n-1}{2}\right) & \text{ si } n \text{ est impair} \end{cases}\text{.} \end{equation*}
On a donc
🔗
Table 1.3.26. bijection entre \(\mathbb{N}\) et \(A\cup B\)
🔗
\(n\) \(h(n)\)
\(0\) \(f(0)\)
\(1\) \(g(0)\)
\(2\) \(f(1)\)
\(3\) \(g(1)\)
\(4\) \(f(2)\)
\(5\) \(g(2)\)
\(6\) \(f(3)\)
\(\vdots\) \(\vdots\)
Puisque \(f,g\) sont des bijections et que les ensembles \(A,B\) sont disoints, on sait que tous les éléments de \(A\) et \(B\) sont présents (la fonction \(h\) est surjective) et qu’il n’y a pas de répétition (elle est aussi injective).
🔗
🔗
🔗
(b)
Montrer que \(A\cup B=(A-B)\cup (B-A)\cup (A\cap B)\text{.}\)
🔗
🔗
(c)
Montrer que \(A\) et \(B\) ne sont pas disjoints, alors \(A\cup B\) est tout de même de cardinalité dénombrable.
🔗
Indice.
Appliquer les parties 1.3.6.20.a et 1.3.6.20.b ainsi que l’exercice 1.3.6.19.
🔗
🔗
Solution.
Par 1.3.6.20.b, l’union de \(A\) et \(B\) s’écrit comme une union de trois ensembles. De plus, par construction, ces trois ensembles sont disjoints. Comme \(A-B\subseteq B, B-A\subseteq B\) et \(A\cap B\subseteq A\) (et \(B\)), l’exercice 1.3.6.19 garantit que ces ensembles sont de cardinalité dénombrable.
🔗
On pose \(C=(A-B)\cup (B-A)\text{.}\) Alors par l’exercice 1.3.6.20.a, l’ensemble \(C\) est dénombrable. Finalement, pour la même raison, l’ensemble \(C\cup (A\cap B)=(A-B)\cup (B-A)\cup (A\cap B)\) est aussi dénombrable.
🔗
🔗
🔗
🔗
21.
Considérer l’ensemble \(A\) des nombres entre \(0\) et \(1\) dont le développement décimal ne contient de que des \(0\) ou des \(1\text{,}\) par exemple \(0.1001000100001\cdots\text{.}\) Montrer que cet ensemble est non dénombrable en modifiant l’argument présenté à l’exercice 1.3.6.16.c.
🔗
Solution.
On imagine qu’une liste de ces nombres existe. On pose \(x=b_1b_2b_3\cdots\) l’un de ces nombres où \(b_i=0\) si le nombre à la ligne \(i\) de cette liste a un \(1\) en position \(i\) et \(b_i=1\) sinon. Par construction, \(x\) n’est pas dans la liste. Or si la cardinalité de \(A\) était dénombrable, il devrait s’y trouver. Ceci est une contradiction, alors \(A\) doit être non dénombrable.
🔗
🔗
🔗
22.
Considérer la table infinie suivante, dans laquelle des nombres rationnels strictement positifs apparaissent.
🔗
Table 1.3.27. Énumération des rationnels
🔗
Numérateur\Dénominateur \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(\cdots\)
\(1\) \(\frac{1}{1}\) \(\frac{1}{2}\) \(\frac{1}{3}\) \(\frac{1}{4}\) \(\frac{1}{5}\) \(\frac{1}{6}\) \(\cdots\)
\(2\) \(\frac{2}{1}\) \(\frac{2}{2}\) \(\frac{2}{3}\) \(\frac{2}{4}\) \(\frac{2}{5}\) \(\frac{2}{6}\) \(\cdots\)
\(3\) \(\frac{3}{1}\) \(\frac{3}{2}\) \(\frac{3}{3}\) \(\frac{3}{4}\) \(\frac{3}{5}\) \(\frac{3}{6}\) \(\cdots\)
\(4\) \(\frac{4}{1}\) \(\frac{4}{2}\) \(\frac{4}{3}\) \(\frac{4}{4}\) \(\frac{4}{5}\) \(\frac{4}{6}\) \(\cdots\)
\(5\) \(\frac{5}{1}\) \(\frac{5}{2}\) \(\frac{5}{3}\) \(\frac{5}{4}\) \(\frac{5}{5}\) \(\frac{5}{6}\) \(\cdots\)
\(6\) \(\frac{6}{1}\) \(\frac{6}{2}\) \(\frac{6}{3}\) \(\frac{6}{4}\) \(\frac{6}{5}\) \(\frac{6}{6}\) \(\cdots\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\ddots\)
(a)
Est-ce que tous les rationnels strictement positifs apparaissent? Justifier
🔗
Solution.
Les rationnels strictement positifs apparaissent tous puisque toutes les combinaisons de numérateur et dénominateur sont présentes. Chaque nombre apparait même plus d’une fois, par exemple \(1/2=2/4=3/6=\cdots\text{.}\)
🔗
🔗
🔗
(b)
Créer une bijection de \(\N\) vers l’ensemble des rationnels strictement positifs afin de montrer que cet ensemble est aussi dénombrable.
Solution.
On va parcourir la table de façon à obtenir une liste de tous les rationnels. On commence au coin supérieur gauche avec l’entrée \(1/1\text{,}\) puis on se déplace vers la droite pour atteindre l’entrée \(1/2\text{.}\) On descend ensuite par la diagonale en bas à gauche pour aller chercher l’entrée \(2/1\text{,}\) on descend pour atteindre l’entrée \(3/1\) et on remonte le long de la diagonale. La figure 1.3.28 illustre le début de ce processus. Lorsque l’on tombe sur un nombre que l’on a déjà rencontré, on l’ignore tout simplement. Ce procédé garantit que tous les rationnels seront touchés puisque, par construction de la grille, chaque combinaison de numérateur et dénominateur est incluse.
🔗
Figure 1.3.28. Énumération des rationnels
🔗
🔗
🔗
🔗
🔗
🔗
🔗
PrécédentTopSuivant