Exercice 8 / 9Moyen
Injection, surjection ou bijection ?
À toi
On note E₂₆ = {0 ; 1 ; … ; 25}, les rangs des lettres. Pour chaque application, dis si elle est injective seulement, surjective seulement, bijective, ou ni l'une ni l'autre.
- f : ℕ → ℕ, n ↦ n + 1.
- g : E₂₆ → E₂₆, x ↦ le reste de 2x modulo 26.
- h : E₂₆ → E₂₆, x ↦ le reste de 7x + 3 modulo 26.
- k : {Inès ; Léo ; Maya ; Noé} → {Compta ; Info ; RH}, le service de chaque salarié : Inès → Info, Léo → Compta, Maya → Info, Noé → RH.
- Combien d'antécédents 0 a-t-il par g ?
Ensembles, relations et applications
Notations
Un ensemble s'écrit entre accolades, éléments séparés par des points-virgules : {1 ; 2 ; 3}. x ∈ E se lit « x appartient à E », A ⊂ B « A est inclus dans B ». card(E) est le nombre d'éléments de E. Un couple s'écrit entre parenthèses : (a ; b).
Les opérations
Dans E = {1 ; 2 ; … ; 8}, avec A = {1 ; 2 ; 3 ; 4} et B = {3 ; 4 ; 5} :
| Opération | Se lit | Contient | Exemple |
|---|---|---|---|
| A ∪ B | A union B | les éléments de A ou de B | {1 ; 2 ; 3 ; 4 ; 5} |
| A ∩ B | A inter B | les éléments de A et de B | {3 ; 4} |
| A \ B | A privé de B | les éléments de A qui ne sont pas dans B | {1 ; 2} |
| Ā | complémentaire de A | les éléments de E hors de A | {5 ; 6 ; 7 ; 8} |
| A Δ B | différence symétrique | les éléments d'un seul des deux | {1 ; 2 ; 5} |
Lois de De Morgan : ∁(A ∪ B) = Ā ∩ B̄ et ∁(A ∩ B) = Ā ∪ B̄.
Cardinal d'une réunion : card(A ∪ B) = card(A) + card(B) − card(A ∩ B). Dans un groupe, 12 étudiants font du Python, 9 du PHP et 4 les deux : 12 + 9 − 4 = 17 font au moins l'un des deux. Sans la soustraction, les 4 seraient comptés deux fois.
Produit cartésien et dénombrement
E × F est l'ensemble des couples (x ; y) avec x ∈ E et y ∈ F. L'ordre compte : (x ; y) n'est pas (y ; x). card(E × F) = card(E) × card(F) : 3 systèmes et 4 navigateurs donnent 3 × 4 = 12 configurations de test. Une suite de k éléments pris dans un ensemble de n éléments est un élément de Eᵏ : il y en a nᵏ. Un code de 3 lettres majuscules : 26³ = 17 576 possibilités.
L'ensemble des parties
P(E) est l'ensemble de toutes les parties de E, ∅ et E compris. Si card(E) = n, card(P(E)) = 2ⁿ : chaque élément est dans la partie ou n'y est pas. Pour E = {x ; y} : P(E) = {∅ ; {x} ; {y} ; {x ; y}}, 4 parties.
Ne confonds pas : x ∈ E (un élément dans un ensemble), {x} ⊂ E (une partie dans un ensemble), {x} ∈ P(E) (une partie est un élément de P(E)).
Les propriétés d'une relation sur E
| Propriété | Définition | Pour la réfuter |
|---|---|---|
| Réflexive | x R x pour tout x | un (x ; x) manquant |
| Symétrique | x R y ⇒ y R x | un (x ; y) sans son retour |
| Antisymétrique | x R y et y R x ⇒ x = y | un aller-retour entre deux éléments différents |
| Transitive | x R y et y R z ⇒ x R z | un enchaînement sans son raccourci |
- Relation d'équivalence : réflexive, symétrique, transitive. Elle range E en classes disjointes. « A le même reste dans la division par 3 » sur {1 ; … ; 6} : classes {1 ; 4}, {2 ; 5}, {3 ; 6}.
- Relation d'ordre : réflexive, antisymétrique, transitive. L'ordre est total si deux éléments sont toujours comparables, partiel sinon. Le diagramme de Hasse ne garde que les liens directs, sans boucles ni raccourcis dus à la transitivité.
Les applications
f : E → F est injective si chaque élément de F a au plus un antécédent, surjective s'il en a au moins un, bijective s'il en a exactement un. Entre deux ensembles finis de même cardinal, injective, surjective et bijective reviennent au même. Si card(E) > card(F), aucune application de E vers F n'est injective (principe des tiroirs).
En SQL
| Opérateur | Opération | Lignes renvoyées |
|---|---|---|
UNION | réunion, doublons supprimés | card(A ∪ B) |
UNION ALL | réunion, doublons gardés | card(A) + card(B) |
INTERSECT | intersection | card(A ∩ B) |
EXCEPT | différence A \ B | card(A \ B) |
CROSS JOIN | produit cartésien | card(A) × card(B) |
Tu es bloqué ?
Ouvre les indices un par un, le corrigé en dernier.
Indice 1
Injective : deux éléments différents n'ont jamais la même image. Surjective : tout élément d'arrivée a au moins un antécédent.
Indice 2
Pour g, compare g(0) et g(13).
Indice 3
Entre deux ensembles finis de même cardinal, injective et surjective vont ensemble. h est un chiffrement affine avec PGCD(7, 26) = 1.
Voir le corrigé
Connecte-toi pour voir le corrigé
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données
Pour revoir la notion : chapitre 2 du cours Ensembles, Union, intersection, complémentaire et diagrammes de Venn.
Tes réponses
Connecte-toi pour faire cet exercice
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données