Aller au contenu

Chapitre 2 - Ensembles - Applications⚓︎

Let's talk about sets⚓︎

D'après Salt N Pepa

Placeholder

Let's talk about sets, baby

Let's talk about you and me

Let's talk about all the good things

And the bad things that may be

Let's talk about sets

La théorie des ensembles a bouleversé les mathématiques à partir des travaux de Georg CANTOR. dès la fin du XIXe siècle. Nous aborderons certains de ses aspects basiques à travers nos explorations cette année. Cette section n'est qu'une très courte introduction. Les curieux pourront, outre CANTOR, aller découvrir qui était RUSSELL que nous avons déjà évoqué.

Nous nous contenterons de la définition donnée par CANTOR lui-même:

Définition 2-1 - Ensemble

Par ensemble, nous entendons toute collection \(M\) d'objets \(m\) de notre intuition ou de notre pensée, définis et distincts, ces objets étant appelés les éléments de \(M\).

Appartenance⚓︎

On note \(m ∈M\) qu'on lit « \(m\) appartient à \(M\) »

Ou encore \(M ∋ m\) qu'on lit « \(M\) contient \(m\) »

Appartenance

En Python on dispose de in pour vérifier qu'un élément appartient à une collection.

In [1]: 3 in [1, 2, 3]
Out[1]: True

In [2]: 'a' in 'papa'
Out[2]: True

In [5]: 42 in range(100)
Out[5]: True

Inclusion⚓︎

Définition 2-2 - Inclusion

Si \((∀x)(x ∈ A ⟹ x ∈B)\) alors on note cela \(A \subseteq B\) ou \(B \supseteq A\) et on lit « \(A\) est inclus dans \(B\) »

Inclusion en Python

On pourrait tenter d'utiliser encore in :

In [4]: [1, 2] in [1, 2, 3]
Out[4]: False

Pourquoi cela ne fonctionne-t-il pas ? Comment y remédier ?

Le type set

Python possède une structure de données dénommée set (ensemble en anglais). Les éléments, comme pour les ensembles définis juste au-dessus, ne sont pas ordonnés : on ne s'occupe que de l'appartenance.

On les construit avec des accolades ou bien set :

In [12]: ens = {1, 2, 3}

In [13]: 2 in ens
Out[13]: True

In [15]: ens2 = set([2, 1, 3, 2, 3, 1, 2])

In [16]: ens2
Out[16]: {1, 2, 3}

In [17]: ens3 = set([3,2,1])

In [18]: ens3
Out[18]: {1, 2, 3}

Commentez....

Pour l'inclusion, on pourrait procéder comme ci-dessus ou bien utiliser un opérateur réservé aux ensembles :

In [19]: {1, 2, 1, 2, 2, 2, 2, 1} <= {1, 2, 3}
Out[19]: True

In [20]: {1, 2, 1, 2, 2, 2, 2, 1}.issubset({1, 2, 3})
Out[20]: True

Enlever les doublons

On utilise souvent dans les projets les sets pour enlever des doublons et donc compter les éléments distincts :

In [22]: {k%2  for k in range(100)}
Out[22]: {0, 1}

In [23]: {k%3  for k in range(100)}
Out[23]: {0, 1, 2}

Comment interpréter ces résultats ?

Remarque

On devrait distinguer \(⊂\), l'inclusion stricte, et \(\subseteq\), l'inclusion au sens large. Dans la plupart des textes de concours cependant, on utilise \(⊂\) pour les deux cas.

Recherche

Pour dire qu'un ensemble n'est pas inclus dans un autre, on utilise le symbole \(\not\subset\). Comment démontrer qu'un ensemble n'est pas inclus dans un autre?

Égalité⚓︎

Définition 2-3 - Égalité d'ensembles

On dit que deux ensembles \(A\) et \(B\) sont égaux et on note \(A=B\) si, et seulement si:

\[ (∀x)(x ∈A ⟺ x∈B) \]

Cela signifie en fait que deux ensembles sont égaux si, et seulements si, ils ont les mêmes éléments : on appelle cette définition l'axiome d'extensionalité.

Égalité de deux ensembles en Python

Interprétez :

In [24]: [1, 2, 3] == [3, 2, 1]
Out[24]: False

In [25]: {1, 2, 3} == {3, 2, 1}
Out[25]: True

In [26]: [1, 2, 3] == [1, 1, 1, 2, 3]
Out[26]: False

In [27]: {1, 2, 3} == {1, 1, 1, 2, 3}
Out[27]: True

Double inclusion

Pour démontrer que deux ensembles sont égaux, on procède souvent par double inclusion (à rapprocher de la démonstration par double implication puisqu'il y a une équivalence dans la définition de l'égalité de deux ensembles).

Plus formèlement cela se note :

\[ (∀ X)(∀ Y)(((X \subseteq Y) ∧ (Y \subseteq X)) ⟹ (X=Y)) \]

Définition par extension / compréhension⚓︎

Quand on peut nommer tous les éléments d'un ensemble, on dit qu'on donne la définition en extension de cet ensemble. Par exemple \(\bigl\{1,2,3\bigr\}\)

Parfois il est beaucoup trop long voire impossible de donner une définition par extension. On peut alors donner une propriété qui caractérise cet ensemble. Par exemple

\[ P=\bigl\{p ∈ \mathbb Z \mid (∃k∈\mathbb Z )(x=2×k)\bigr\} \]

caractérise l'ensemble des entiers pairs. On aurait pu aussi écrire:

\[ P=\bigl\{2×k\mid k∈\mathbb Z \bigr\} \]

On dit qu'on définit l'ensemble par compréhension.

C'est un moyen qui a inspiré de nombreux langages de programmation dont Python.

In [1]: ns1 = {2*n for n in range(10)}

In [2]: ns1
Out[2]: {0, 2, 4, 6, 8, 10, 12, 14, 16, 18}

In [3]: ns2 = {n for n in range(20) if n%2 == 0}

In [4]: ns2
Out[4]: {0, 2, 4, 6, 8, 10, 12, 14, 16, 18}

Recherche 2-1

Comment expliquer :

In [6]: {lettres for lettres in "abracadabra"}
Out[6]: {'a', 'b', 'c', 'd', 'r'}

In [7]: [lettres for lettres in "abracadabra"]
Out[7]: ['a', 'b', 'r', 'a', 'c', 'a', 'd', 'a', 'b', 'r', 'a']

Recherche 2-2

On note \(E=\bigl\{x\mid x\in\mathbb Z \wedge x^2=1\bigr\}\) et \(F=\bigl\{x\mid x \in\mathbb R\wedge\left| x\right|=1\bigr\}\).

Que dire de E et F ?

Ensembles de nombres⚓︎

Un petit rappel ?

  • \(\mathbb N\) comme entiers Naturels: \(0\), \(1\), \(2\), \(3\),...
  • \(\mathbb Z\) comme les (Z)entiers (relatifs): ...\(-3\), \(-2\), \(-1\), \(0\), \(1\), \(2\), \(3\),...Il s'agit de la réunion de \(\mathbb N\) avec l'ensemble de toutes les solutions des équations \(x+n=0\) avec \(n\) un entier naturel.
  • \(\mathbb D\) comme Décimal.Il s'agit des nombres dont l'écriture en base 10 est \og finie\fg{}. Plus rigoureusement:

    \[ x\in\mathbb D ⟺ (∃p∈\mathbb Z)(∃k ∈\mathbb Z)(x = k×10^p) \]
  • \(\mathbb Q\) comme rationnel.Il s'agit de l'ensemble de toutes les solutions des équations \(n×x=p\) avec \(n\) un entier et p un entier naturel non nul:

    \[ x\in\mathbb Q ⟺ (∃p∈\mathbb Z)(∃n ∈\mathbb N^*)(n×x = p) \]

    On note l'unique solution de \(n×x=p\) sous la forme \(\frac{p}{n}\)

  • \(\mathbb R\) comme Réel. Là les choses se compliquent. Une définition rigoureuse de ce qu'est un nombre réel n'est pas à notre programme (demandez à vos camarades de MPSI). On se contentera de ce qu'on vous a dit en classe de 2\up{nde}: c'est l'ensemble des abscisses des points d'une droite. Il y a bien sûr beaucoup de choses à dire sur les réels. Nous en reparlerons plus tard.

  • \(\mathbb C\) comme Complexe. \(\mathbb C=\bigl\{a + \mathbf{i} b \mid a∈\mathbb R, b∈\mathbb R\bigr\}\) avec i l'unique nombre vérifiant \(\mathbf{i}^2=-1\). Nous consacrerons tout un chapitre à l'étude de cet ensemble.

Intervalles entiers

L'ensemble des nombres entiers compris entre \(k\) et \(\ell\) se note \( [\![k,\ell]\!]\)

Recherche 2-3

Écrivez \( [\![2, 10]\!]\) en extension et en compréhension.

Et voici un premier théorème :

Théorème 2-1 - Transitivité de l'inclusion

Soit A, B et C trois ensembles. Alors :

\[ (A \subseteq B ∧ B \subseteq C)⟹ A\subseteq C \]

:)

Cardinal d'un ensemble fini⚓︎

Définition 2-4 - Cardinal d'un ensemble fini

Un ensemble fini \(E\) est un ensemble comportant un nombre fini d'éléments. Ce nombre est appelé cardinal de l'ensemble \(E\) et noté \(|E|\) ou \({\rm card}(E)\) ou \(\# E\).

Recherche 2-4

Quel est le cardinal de \(E=\bigl\{1, \frac{2}{2}, {\rm e}^0, \cos(2π)\bigr\}\) ?

Définition 2-5 - Singleton

Un singleton est un ensemble de cardinal 1.

Définition 2-6 - Ensemble vide

L'ensemble vide est l'ensemble de cardinal 0. On le note \(\emptyset\) ou \(\bigl\{\bigr\}\).

  • l'ensemble vide...est un ensemble

-il est inclus dans tous les ensembles (en particulier lui-même!)

Ensemble des sous-ensembles d'un ensemble !⚓︎

Soit maintenant E un ensemble, \(\Bigl\{ X\mid X\subseteq E\Bigr\}\) est alors lui-même un ensemble. C'est l'ensemble des solutions de \(X\subseteq E\) d'inconnue \(X\).

Recherche 2-5

Cet ensemble admet toujours au moins deux éléments: lesquels?

On appelle cet ensemble l'ensemble des parties de E.

Une partie d'un ensemble est un autre terme pour désigner un sous-ensemble.

Théorème 2-2 - Ensemble des parties d'un ensemble

Nous admettrons que si \(E\) désigne un ensemble alors l'ensemble des parties de \(E\) est un ensemble noté \(\mathscr P\left( E\right) \)

\[ \mathscr P\left( E\right) =\Bigl\{ X\mid X\subseteq E\Bigr\} \]

Recherche 2-6

On a donc:

\[ X \subseteq E ⟺ X ∈ ?? \]

Par exemple, si \(E\) est un singleton, alors \(\mathscr P(E)=\bigl\{\ \ ??\ \ \bigr\}\)

Recherche 2-7

Soit \(E=\{b,c,p,s,t\}\). Déterminez quelques éléments de \(\mathscr P(\mathscr P(E))\)...

Attention !

Attention à la nature des objets manipulés !

On écrit : \(3∈\mathbb R\) , \(\{3\}\subseteq \mathbb R\) et \(\{3\}∈\mathscr P(\mathbb R)\).

\(\varnothing\subset E\) donc \(\varnothing\in\mathscr P(E)\) et on a aussi \(\varnothing\subset \mathscr P(E)\) car \(\varnothing\) est inclus dans tous les ensembles.

Opérations sur les ensembles⚓︎

Intersection⚓︎

Définition 2-7 - Intersection de deux ensembles

L'intersection des ensembles \(A\) et \(B\) est l'ensemble \(A\cap B\) constitué des éléments communs à \(A\) et \(B\).

\[ A\cap B=\Bigl\{ x\mid (x\in A)\land (x\in B)\Bigr\} \]

C'est une partie de \(E\). De plus \((x\in A\cap B)\Longleftrightarrow ( x\in A\land x\in B)\).

Recherche 2-8

Démontrez que \((A\cap B=B)\Longleftrightarrow (B\subseteq A)\).

On peut généraliser l'intersection à plus de deux ensembles.

In [8]: A = {1, 2, 3, 4, 5}

In [9]: B = {2, 4, 6, 8}

In [10]: C = {2, 4, 8, 16, 32}

In [11]: {x for x in A if x in B and x in C}
Out[11]: {2, 4}

In [12]: {x for x in range(1000)  if x in A and x in B and x in C}
Out[12]: {2, 4}

Définition 2-8 - Intersection d'une famille d'ensembles

\(\displaystyle\bigcap_{i∈I}A_i=\bigl\{x∈E\mid (∀i ∈I)(x∈A_i)\bigr\}\)

Réunion⚓︎

Définition 2-9 - Réunion de deux ensembles

L'union ou la réunion des ensembles \(A\) et \(B\) est l'ensemble :

\[ A\cup B=\Bigl\{ x\mid (x\in A)\lor (x\in B)\Bigr\} \]

C'est une partie de \(E\). De plus \((x\in A\cup B)\Longleftrightarrow ( x\in A\lor x\in B)\).

On doit se persuader que le « ou » intervenant dans cette définition est un « ou inclusif (i.e. non exclusif) » et par conséquent on a \(A\subseteq \left( A\cup B\right) ,B\subseteq \left( A\cup B\right) \) et \(\left( A\cap B\right) \subseteq \left( A\cup B\right) .\)

Recherche 2-9

Reprenez le code python précédent et adaptez-le pour l'union des trois ensembles.

On peut généraliser la réunion à plus de deux soit ensembles.

Définition 2-10 - Réunion d'une famille d'ensembles

Soit \((A_i)_{i∈I}\) une famille de sous-ensembles de \(E\),

\[ \bigcup_{i∈I}A_i=\bigl\{x∈E\mid (∃i ∈I)(x∈A_i)\bigr\} \]

Différence de deux ensembles⚓︎

Définition 2-11 - Différence de deux ensembles

La différence des ensembles \(A\) et \(B\) est l'ensemble

\[ A\setminus B=\Bigl\{ x\mid (x\in A)\land (x\notin B)\Bigr\} \]

Recherche 2-10

Écrivez par compréhension en Python la différence entre les entiers pais inférieurs à 20 et les multiples de 3 inférieurs à 20.

Complémentaire⚓︎

Définition 2-12 - Complémentaire d'un ensemble dans un autre ensemble

\(A\) désignant une partie de \(E,\) le complémentaire de \(A\) par rapport à \(E\) ou le complémentaire de \(A\) dans \(E\) est l'ensemble noté \(\complement_{E}A\) défini par

\[ \complement_{E}A=E\setminus A=\Bigl\{ x\mid (x\in E)\land (x\notin A)\Bigr\} \]

S'il n'y a pas d'ambiguïté sur le référentiel \(E\), \(% \complement _{E}A\) est noté \(\overline{A}\) et \(\overline{\overline{A}}=A\).

Recherche 2-11

Quel est le complémentaire dans \(\mathbb N\) des entiers pairs ?

Remarque

\(A\setminus B=A\cap \overline{B}\)

Lois de De Morgan⚓︎

Définition 2-13 - Lois de De Morgan

\[ \overline{\left( \bigcup\limits_{i=1}^{n}A_{i}\right) }=\bigcap% \limits_{i=1}^{n}\overline{A_{i}} \qquad \qquad\text{et}\qquad \qquad \overline{\left( \bigcap\limits_{i=1}^{n}A_{i}\right) }=\bigcup% \limits_{i=1}^{n}\overline{A_{i}}% \]

Ceci s'exprime en français courant de la façon suivante:

  • Le complémentaire d'une union est égale à l'intersection des complémentaires.

  • Le complémentaire d'une intersection est égale à la réunion des complémentaires.

Recherche 2-12

Placeholder

Quel est le contraire d'être « beau et con à la fois » comme en rêvait Jacques Brel ?

Commentez le code suivant :

In [1]: A = {1, 2, 3, 4}

In [2]: B = {2, 4, 6, 8}

In [3]: {x for x in range(10) if x in A or x in B}
Out[3]: {1, 2, 3, 4, 6, 8}

In [4]: {x for x in range(10) if not(x in A or x in B)}
Out[4]: {0, 5, 7, 9}

In [5]: {x for x in range(10) if x not in A and x not in B}
Out[5]: {0, 5, 7, 9}

In [6]: {x for x in range(10) if not(x in A and x in B)}
Out[6]: {0, 1, 3, 5, 6, 7, 8, 9}

In [7]: {x for x in range(10) if x not in A or x not in B}
Out[7]: {0, 1, 3, 5, 6, 7, 8, 9}

Dualité⚓︎

Regroupons les lois algébriques vues précédemment dans un tableau. On considère des parties A, B et C d'un ensemble E.

Nom de la propriété Propriété Duale
Idempotence \(A\cup A= A\) \(A\cap A = A\)
Associativité \((A\cup B)\cup C=A\cup(B\cup C)\) \((A\cap B)\cap C=A\cap(B\cap C)\)
Commutativité \(A\cup B=B\cup A\) \(A\cap B=B\cap A\)
Distributivité \(A\cup(B\cap C)= (A\cup B)\cap (A\cup C)\) \(A\cap(B\cup C)= (A\cap B)\cup (A\cap C)\)
Identité \(A\cup \emptyset=A\) \(A\cap E= A\)
Involution \(\overline{\overline{A}}=A\)
Complémentaire \(A\cup \overline{A}=E\) \(A\cap \overline{A}=\emptyset\)
\(\overline{E}=\emptyset\) \(\overline{\emptyset}=E\)
De Morgan \(\overline{A\cup B} = \overline{A} \cap \overline{B}\) \(\overline{A\cap B} = \overline{A} \cup \overline{B}\)

Soit \(e\) une équation algébrique définie sur \({\mathscr P} (E)\). La duale \(e^\star\) de \(e\) est l'équation obtenue en remplaçant \(\cap\), \(\cup\), E et \(\emptyset\) respectivement par \(\cup\), \(\cap\), \(\emptyset\) et \(E\).

Le principe de dualité affirme que si \(e\) est vérifiée pour tout élément de \({\mathscr P} (E)\), alors sa duale \(e^\star\) aussi: ça se démontre...

Partition d'un ensemble⚓︎

Vous avez déjà rencontré ce genre de découpage d'un ensemble lors de l'étude des probabilités (dans quel contexte ?)

Définition 2-14 - Partition d'un ensemble

\(E\) désignant ici un ensemble non vide. Soit \(P\), une partie non vide de \({\mathscr P} (E)\) (on a donc \(P\subseteq {\mathscr P} \left( E\right) \) et \(% P\neq \emptyset )\) \(P\) est un ensemble non vide de parties de \(E\). On dit que \(P\) est une partition de \(E\) si, et seulement si,

  1. tout élément de \(P\) est non vide,

  2. deux éléments distincts quelconques de \(P\) sont disjoints,

  3. tout élément de \(E\) appartient à l'un des éléments de \(P.\)

Si \(E\) est fini, toute partition \(P\) de \(E\) est du type \(P=\left\{ A_{1},A_{2},\ldots ,A_{k}\right\} \) avec

\[ A_{i}\subseteq E,A_{i}\neq \emptyset ,A_{i}\cap A_{j}=\emptyset \text{ si }% i\neq j\text{ et }\bigcup\limits_{i=1}^{k}A_{i}=E \]

On peut imaginer une partition de \(E\) comme un découpage de \(E,\) aucun des morceaux étant non vide, les morceaux étant tous disjoints deux à deux. Par exemple \( \left\{ \left\{ \beta \right\} ,\left\{ \alpha ,\delta \right\} \left\{ \varepsilon ,\gamma \right\} \right\} \) est une partition de l'ensemble \(\left\{ \alpha ,\beta ,\gamma ,\delta ,\varepsilon \right\} \)

Pour vous distraire, voici un exercice extrait de mon livre de CE1:

CE1_partition

Produit cartésien⚓︎

Exemple⚓︎

Cette partie va nous permettre d'introduire des notions informatiques fondamentales, notamment dans le traitement des bases de données.

Vous êtes embauché(e) dans un restaurant. Vous disposez de trois ensembles:

  • l'ensemble des entrées: E = { Cuisses de sauterelles panées, œuf mou, huîtres de l'Erdre }

  • l'ensemble des plats de résistance : P = {Turbot à l'huile de ricin, Chien à l'andalouse, Soupe d'orties }

  • l'ensemble des desserts: D = {Pomme, Banane, Noix }

Vous avez envie de créer un nouvel ensemble, celui des menus possibles. Une première idée consiste à regrouper tout le monde en prenant \(E\cup P \cup D\).

Je sais bien que la gastronomie n'est pas la principale préoccupation des jeunes au palet perverti par les tristes fastefoudes mais en général on commande UNE entrée SUIVIE D'UN plat de résistance SUIVI D'UN dessert or la simple union que vous avez proposée peut vous faire choisir un menu totalement différent: cinq desserts et vingt entrées, dans n'importe quel ordre, par exemple.

Nous avons besoin de créer un « objet » ordonné de trois composantes, chacune étant choisie respectivement dans \(E\), \(P\) et \(D\).

Par exemple, (œuf mou, chien à l'andalouse, pomme) est un menu. C'est un triplet, à ne pas confondre avec l'ensemble \(\bigl\{\)œuf mou, chien à l'andalouse, pomme \(\bigr\}\) qui n'est pas ordonné.

On peut avoir une vision de tous les menus possibles avec un arbre:

arbre

n-uplets⚓︎

couple

Comme je l'ai appris jadis en CE1, un couple est une collection ordonnée de deux éléments.

On retrouve cette notion sur Python :

In [1]: a = (1, 2)

In [2]: b = (2, 1)

In [3]: a == b
Out[3]: False

In [4]: A = {1, 2}

In [5]: B = {2, 1}

In [6]: A == B
Out[6]: True

In [7]: type(a)
Out[7]: tuple

In [8]: type(A)
Out[8]: set

On peut former des ensembles de couples :

In [10]: { (lettre, nb) for lettre in {'a', 'b', 'c'} for nb in {1,2,3,4,5} }
Out[10]: 
{('a', 1),
 ('a', 2),
 ('a', 3),
 ('a', 4),
 ('a', 5),
 ('b', 1),
 ('b', 2),
 ('b', 3),
 ('b', 4),
 ('b', 5),
 ('c', 1),
 ('c', 2),
 ('c', 3),
 ('c', 4),
 ('c', 5)}

Cet ensemble s'appelle le produit cartésien de l'ensemble \(\{a, b, c\}\) par l'ensemble \(\{1,2,3,4,5\}\).

Définition 2-15 - Produit cartésien de deux ensembles

\[ A\otimes B = \bigl\{(a,b)\mid (a\in A) \land (b\in B)\bigr\} \]

Pour se représenter le produit cartésien \(E\otimes F\) avec \(% E=\left\{ a,b,c\right\} \) et \(F=\left\{ 1,2,3,4,5\right\} ,\) on peut évidemment l'écrire en extension: il possède \(3\times 5=15\) éléments.

\[ E\otimes F=\bigl\{ \left( a,1\right) ,\left( a,2\right) ,\cdots ,\left( c,5\right) \bigr\} \]

mais il est souvent préférable de faire appel à un tableau du type de celui présenté dans le livre de CE1.

Remarque

\[ u ∈ E ⊗ F ⟺ (∃x ∈ E)(∃y ∈ F)(u = (x, y)) \]

Notation

\(E⊗E\) se note le plus souvent \(E^2\)

Danger !

Les ensembles \(E\otimes F\) et \(F\otimes E\) sont en général différents. À ne pas confondre avec la multiplication de nombres réels.

Mais comment faire avec notre menu qui a trois plats ordonnés, voire plus?

n-uplets - Produit d'un nombre quelconque d'ensembles⚓︎

Définition 2-16 - Produit cartésien de plusieurs ensembles

Soit \(n∈ℕ^*\) et \(( A_i )_{1\leqslant i \leqslant n}\) une famille de sous-ensembles d'un ensemble \(E\),

\[ \bigotimes_{i=1}^n A_i = A_1 ⊗ A_2 ⊗ \dots ⊗ A_n = \left\{(x_1, x_2, \dots, x_n ) |(∀i ∈ [\![1, n]\!])(x_i ∈ A_i) \right\} \]

Recherche 2-13

Est-ce que \(A⊗B⊗C=(A⊗B)⊗C=A⊗(B⊗C)\)?

Est-ce que \(E⊗E⊗E=(E⊗E)⊗E=E⊗(E⊗E)\)?

Relations, Fonctions, Applications⚓︎

Relations binaires⚓︎

rel_ce1

Définition 2-17 - Relation binaire

Une relation binaire entre deux ensemble E et F est la donnée d'un triplet \((E, F,\cal G_{\cal R})\)\(\cal G_{\cal R}\) est un sous-ensemble du produit cartésien \(E\otimes F\). On l'appelle graphe de la relation.

\(E\) est l'ensemble de départ de la relation et \(F\) son ensemble d'arrivée.

Si \((x,y)\in {\cal G}_{\cal R},\) on dit que \(y\) est UNE image de \(x\) par la relation \(\cal R\) et que \(x\) est UN antécédent de \(y\).

L'ensemble des éléments de E qui admettent une image par \(\cal R\) est le domaine de \(\cal R\) : on le note \({\rm dom}(\cal R)\).

Reprenons la figure de mon vieux livre de CE1.

La relation \(\cal R\) est définie par « ...est sur le (la)... » avec un ensemble de départ qui est en fait l'ensemble des élèves: \(E=\bigl\{A, B, C, D, E, F, G\bigr\}\) et un ensemble d'arrivée qui est en fait l'ensemble des jeux: \(J=\bigl\{T, M, B\bigr\}\)

Son graphe est:

\[ G_\cal R=\bigl\{\hspace{10cm}\bigr\} \]

Complétez le diagramme sagittal associé.

On remarque que de chaque élément de l'ensemble de départ, il ne part au maximum qu'une seule flèche: on dit dans ce cas que la relation est une fonction. Plus fort: on remarque que de tous les éléments de l'ensemble de départ il part une et une seule flèche: on dit que la relation est une fonction totale souvent appelée traditionnellement en France application même si ce dernier terme est moins parlant.

Fonctions⚓︎

Définition 2-18 - Fonction

On dit que la relation \(f=(E,F,G_{f})\) est une fonction de \(E\) vers (ou dans) \(F\) si, et seulement si, tout élément de \(E\) a au plus (cela veut dire : soit zéro ou une) une image dans \(F\).

Si \(x\) a au moins une image, c'est-à-dire s'il existe \(y\in F\) tel que \(\left( x,y\right) \in G_{f},\) \(y\) est forcément unique et est noté \(f(x).\) Lorsque la relation \(f=(E,F,G_{f})\) est une fonction on préfère le plus souvent utiliser la notation:

\[ f\colon \begin{array}{rll} E & \to & F\\ x & \mapsto & f(x)=y \end{array} \]

qui se lit « \(f\) est une fonction de \(E\) dans \(F\) qui à \(x\) associe \(f(x)\) ». On note \({\cal F}(E,F)\) ou \(F^{E}\) l'ensemble des fonctions de \(E \) dans \(F\).

Lorsque \(E\) est de la forme \(U=U_1\otimes U_2\otimes \ldots \otimes U_n,\) on dit que la fonction de \(U\) dans \(F\) est une fonction de \(n\) variables

\[ f\colon \begin{array}{rll} U & \to & F\\ (u_1,u_2,...,u_n) & \mapsto & f(u_1,u_2,...,u_n) \end{array} \]

et \(u_{i}\) est appelée la \(i^{\grave{e}me}\) variable de \(f.\)

Par exemple, en CM1 vous avez vu la fonction :

\[ f\colon \begin{array}{rll} \mathbb N^2 & \to & \mathbb N\\ (\ell, L) & \mapsto & 2(\ell + L) \end{array} \]

Que vous permettait-elle de calculer ?

Définition 2-19 - Fonction totale

Si la fonction \(f=(E,F,G)\) vérifie \({\rm dom}\left( f\right) =E\) on dit que \(f\) est une fonction totale (ou une application) de \(E\) dans \(F\).

Une application en anglais se dit map, comme un plan de ville.

Pensez à une application comme une fonction qui aux points de la ville de Nantes associe les points correspondant sur le plan de la ville de Nantes. Une bonne carte est une application...

Recherche 2-14

Parmi les deux relations représentées, y a-t-il une fonction? une fonction totale?

fonc_tota fonc_tota

Définition 2-20 - Fonction identité

C'est la fonction totale définie sur \(E\) par

\[ {\rm Id}_E\colon \begin{array}{rll} E & \to & E\\ x & \mapsto & x \end{array} \]

Images directe et réciproque par une application⚓︎

Définition 2-21 - Image directe

Soit \(f:E\longrightarrow F\) une application et \(I\subset E\)

On note \(f(I)\) l'ensemble des images par \(f\) des éléments de \(I\).

\[ f(I)=\bigl\{f(x)\mid x\in I \bigr\} \]

C'est l'image directe de \(I\) par \(f\).

On note parfois \({\rm Im}(f)=f(E)\) l'ensemble image de l'ensemble de départ.

Par exemple, l'image directe de \(\{1,2,3,4\}\) par la fonction carré est :

In [3]: { x**2 for x in {1, 2, 3, 4} }
Out[3]: {1, 4, 9, 16}

Danger !

La notation peut être trompeuse. \(f(I)\) est un ensemble!

Définition 2-22 - Ensemble stable par une application

Soit \(f:E\rightarrow E\) et \(A\subset E\). On dit que A est stable par f si \(f(A)\subseteq A\), c'est à dire si

\[ (\forall x)(x\in A ⟹.......) \]

Recherche 2-15

L'intervalle \([0,1]\) est-il stable par la fonction carrée ?

Définition 2-23 - Image réciproque

Soit \(f:E\rightarrow F\) et \(B\subset F\). On note

\[ f^{-1}(B)=\bigl\{x\in E \mid f(x)\in B\bigr\} \]

l'ensemble des antécédents des éléments de \(B\).

\(f^{-1}(B)\) est appelé image réciproque de \(B\) par \(f\).

On parle parfois de contre-image.

Commentez la figure suivante en utilisant notre nouveau vocabulaire:

contri

Par exemple, si \(f:I\rightarrow \mathbb R\) est une fonction, \(f^{-1}(\{0\})\) est l'ensemble des solutions de l'équation \(f(x)=0\).

\(f^{-1}(\mathbb R_+^*)\) est l'ensemble des éléments dont l'image par \(f\) est strictement positive, ou l'ensemble des solutions de l'inéquation \(f(x)>0\)

On peut avoir \(f^{-1}(B)=\varnothing\).

Attention !

Attention! \(f^{-1}\) ne désigne pas forcément une fonction! (Pourquoi?) \(f^{-1}(I)\) est juste une abréviation trompeuse pour désigner l'ensemble des antécédents par \(f\) des éléments de \(I\).

Composée de deux fonctions⚓︎

Définition 2-24 - Composée de 2 fonctions

\(f=(E,F,G_f)\) et \(g=(U,V,G_g)\) sont deux fonctions. La composée de \(f\) et \(g\) est la fonction \((E,V,G_{g\circ f})\) avec

\[ G_{g\circ f}=\left\{\left(x,z\right) \in E\otimes V\mid\exists y\in F,\ \left( x,y\right) \in G_f \land \left(y,z\right) \in G_g\right\}\]

ou, de manière plus synthétique:

\[ x\xrightarrow{f} f(x)\xrightarrow{g} (g\circ f)(x) \]

ou plus schématique:

cd

Attention !

Il faudra bien faire attention: on doit avoir \(F=U\)!

Attention !

Attention à l'ordre! Dans \((g\circ f)(x)\), on commence par prendre l'image par \(f\) puis par \(g\).

Théorème 2-3 - Calcul effectif

Avec les mêmes notations que la définition, si \(x\) appartient au domaine de \(g\circ f\) alors

\[ (g\circ f)(x)=g \bigl( f(x) \bigr) \]

Recherche 2-16

Soit \(f:E\to F\) une application. Quid de ses compositions avec des applications \(\Id_X\)?

Injections, surjections, bijections⚓︎

Définition 2-25 - Fonction injective

La fonction \(f:E\longrightarrow F\) est injective (ou est une injection) si, et seulement si, tout élément de \(F\) a au plus un antécédent.

inj

En pratique

Cette définition équivaut à dire que :

  • \(f^{-1}\) est une fonction.

  • il n'existe pas deux éléments différents de \(E\) qui ont la même image dans \(F.\) En d'autres termes deux éléments différents ont toujours des images différentes.

  • il n'existe pas d'élément de \(F\) ayant plus d'un antécédent.

\[ \begin{eqnarray*} f\text{ injective} &\equiv &\forall (x,x^{\prime })\left( (x,x')\in E^2\land x\neq x^{\prime }⟹ f(x)\neq f(x^{\prime })\right) \\ f\text{ injective} &\equiv &\forall (x,x^{\prime })\left((x,x')\in E^2\land f(x)=f(x^{\prime })⟹ x=x^{\prime }\right) \end{eqnarray*} \]

Recherche 2-17

Injection ?

inj2

Définition 2-26 - Fonction surjective

La fonction \(f:E\longrightarrow F\) est surjective (ou est une surjection de \(E\)) sur \(F\) si, et seulement si, tout élément de \(F\) a au moins un antécédent.

sur

Cela équivaut à écrire que \({\rm Im}(f)=F \) ou que \(f\left( E\right) =F\) ou encore que la relation (pas forcément une fonction...pourquoi?) réciproque de \(f \) est une relation totale.

Définition 2-27 - Fonction bijective

La fonction \(f:E\longrightarrow F\) est bijective ou biunivoque ou est une bijection si, et seulement si, elle est à la fois injective et surjective.

Remark"

En anglais, une application bijective est appelée one to one function : c'est plus parlant!

Recherche 2-18

Soit \(f:A\to B\) et \(g: B\to C\) deux applications. Démontrer que :

  • Si \(f\) et \(g\) sont injectives, alors \(g\circ f\) est injective;

  • Si \(f\) et \(g\) sont surjectives, alors \(g\circ f\) est surjective;

  • Si \(f\) et \(g\) sont bijectives, alors \(g\circ f\) est bijective;

Définition 2-28 - Inversibilité pour la loi \(\circ\)

Soit \(f:E\to F\) une application. On dit qu'elle est inversible (pour la loi \(\circ\)) si, et seulement si, il existe une application \(g:F\to E\) telle que:

\[ f\circ g= {\rm Id}_F \quad \text{ et} \quad g\circ f={\rm Id}_E \]

La fonction \(g\) s'appelle alors application réciproque de \(f\)

Est-ce que cette notion d'inverse vous dit quelque chose? Pouvez-vous en abstraire un motif général ?

Recherche 2-19

Démontrer que Si \(f\) est inversible (pour la loi \(\circ\)) alors son application réciproque est unique (on la note \(f^{-1}\))

Théorème 2-4 - Bijectivité et inversibilité

\(f\) est bijective de \(E\) sur \(F\) si, et seulement si, \(f\) est inversible pour \(\circ\).

Recherche 2-20

Démontrer ce théorème :)

Théorème 2-5 - Bijection réciproque de la composée

Soit \(E\xrightarrow{f}F\xrightarrow{g}G\) des fonctions bijectives. Alors \(g\circ f\) est bijective et

\[ (g\circ f)^{-1}=f^{-1}\circ g^{-1} \]

Attention à l'ordre !