Retrouver l’étudiant à partir de sa salle
Une fonction associe à chaque élément d’un ensemble de départ un seul élément d’un ensemble d’arrivée. Dire si elle est injective, surjective ou bijective, c’est dire si l’on peut retrouver l’entrée à partir de la sortie.
Une université affecte chaque étudiant à une salle d’examen. Si deux étudiants ont la même salle, la salle seule ne dit pas qui est dedans. Les trois mots de cette leçon décrivent ces situations.
À la fin de cette leçon
Remarque
Je peux dire si une application est injective, surjective ou bijective.
Mots-clés
| Mot | Ce que ça veut dire |
|---|---|
| Domaine | l’ensemble de départ : les entrées permises |
| Image | la sortie associée à une entrée donnée |
| Relation | une liste de couples qui relient des éléments |
| Injective | deux entrées différentes ont toujours des sorties différentes |
| Surjective | chaque élément de l’ensemble d’arrivée est atteint |
| Bijective | à la fois injective et surjective |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une fonction donne une seule sortie par entrée
Une relation est une liste de couples. Une fonction est une relation où chaque élément du domaine apparaît exactement une fois comme entrée.
Pas deux sorties pour la même entrée, et pas d’entrée oubliée. On dit aussi une application.
Exemple travaillé : trois relations étudiant-salle
| Couples | Fonction ? | Pourquoi |
|---|---|---|
| Lina-A1, Hugo-A1, Jade-B1 | Oui | Chaque étudiant a une seule salle |
| Lina-A1, Lina-B1, Hugo-A1, Jade-B1 | Non | Lina a deux salles |
| Lina-A1, Hugo-A1 | Non | Jade n’a pas de salle |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une fonction : le carré
python3 -c "print({x: x * x for x in range(-2, 3)})"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Injective : jamais deux entrées pour une sortie
Une fonction est injective si deux entrées différentes donnent toujours deux sorties différentes.
Avec le carré, 2 et -2 ont la même sortie 4. Ce n’est donc pas injectif. Une astuce de comptage : si le nombre de sorties distinctes est plus petit que le nombre d’entrées, il y a une collision.
Exemple travaillé : les carrés de -3 à 3
| Entrée | -3 | -2 | -1 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|---|---|---|
| Sortie (le carré) | 9 | 4 | 1 | 0 | 1 | 4 | 9 |
| Déjà vue ? | Non | Non | Non | Non | Oui | Oui | Oui |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Compter les sorties distinctes
python3 -c "print(len({x * x for x in range(-3, 4)}))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Chercher une collision
# Un entier a-t-il son image en double ?
entrees = [-2, -1, 0, 1, 2]
sorties = []
for x in entrees:
sorties.append(x * x)
print("Sorties :", sorties)
doublons = 0
for i in range(len(sorties)):
for j in range(i + 1, len(sorties)):
if sorties[i] == sorties[j]:
doublons = doublons + 1
print("Paires qui se ressemblent :", doublons)
# Remplacez x * x par x + 10 puis relancez : le nombre de paires tombe à 0.
Surjective : toute l’arrivée est atteinte
Une fonction est surjective si chaque élément de l’ensemble d’arrivée est la sortie d’au moins une entrée.
Une fonction à la fois injective et surjective est bijective. Chaque sortie correspond alors à une seule entrée, et l’on peut revenir en arrière.
Trois fois x, modulo 7
python3 -c "print(sorted(set((3 * x) % 7 for x in range(7))))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Deux fois x, modulo 6
python3 -c "print(sorted(set((2 * x) % 6 for x in range(6))))"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup pensent qu’injective et surjective veulent dire la même chose. Ce n’est pas le cas. Injective parle des entrées qui ne se rencontrent pas. Surjective parle des sorties que rien n’oublie. Une fonction peut avoir l’une, l’autre, les deux ou aucune.
Une relation d’équivalence range en classes
Une relation d’équivalence regroupe des éléments qui « se ressemblent » : ils forment des classes, sans reste et sans recouvrement.
Exemple : deux entiers sont liés s’ils ont le même reste dans la division par 3. Les restes de 0 à 8 forment trois classes.
Les restes de 0 à 8 par 3
python3 -c "print([n % 3 for n in range(9)])"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Pour aller plus loin
Dans le terminal, essayez trois fois x modulo 9 sur les entiers de 0 à 8 : python3 -c "print(sorted(set((3 * x) % 9 for x in range(9))))". Dites avant de lancer si le résultat compte neuf valeurs.
Puis cherchez pourquoi trois fois x modulo 7 est bijective et trois fois x modulo 9 ne l’est pas. Pensez aux diviseurs communs de 3 et de 9.