M04 - Ensembles, fonctions et relations

M04 - Ensembles, fonctions (injection, surjection, bijection) et relations binaires

---

1. Ensembles

Notation	Lecture	Exemple
$x\in E$	$x$ appartient à $E$	$3\in \{1,2,3\}$
$F\subset E$	$F$ est inclus dans $E$	$\{1,2\}\subset \{1,2,3\}$
$\varnothing$	ensemble vide
$A\cup B$	union (OU)	$\{1,2\}\cup \{2,3\}=\{1,2,3\}$
$A\cap B$	intersection (ET)	$\{1,2\}\cap \{2,3\}=\{2\}$
$\bar{A}$	complémentaire
$A\times B$	produit cartésien (couples)	$\{0,1\}\times \{a,b\}=\{(0,a),(0,b),(1,a),(1,b)\}$
$\text{Card}(E)$ ou $|E|$	nombre d’éléments

Lien direct avec la logique : $\cup \leftrightarrow +$, $\cap \leftrightarrow \cdot$, complémentaire $\leftrightarrow$ NON ; et avec SQL : UNION, INTERSECT, EXCEPT.

2. Injective, surjective, bijective

flowchart LR
  subgraph INJ["Injective (≤ 1 flèche arrive)"]
    a1((a)) --> x1((1))
    b1((b)) --> y1((2))
    z1((3))
  end
  subgraph SURJ["Surjective (≥ 1 flèche arrive)"]
    a2((a)) --> x2((1))
    b2((b)) --> x2
    c2((c)) --> y2((2))
  end
  subgraph BIJ["Bijective (exactement 1)"]
    a3((a)) --> x3((1))
    b3((b)) --> y3((2))
  end

Type	Chaque élément de l’arrivée a…	Test pratique
Injective	au plus un antécédent	Deux éléments différents ont toujours des images différentes
Surjective	au moins un antécédent	Toute l’arrivée est « touchée »
Bijective	exactement un antécédent	Injective et surjective → admet une réciproque $f^{-1}$

Entre ensembles finis : bijection possible seulement si $\text{Card}(E)=\text{Card}(F)$. Si $\text{Card}(E)>\text{Card}(F)$ → jamais injective ; si $\text{Card}(E)<\text{Card}(F)$ → jamais surjective.

Exemples :

• $f(x)=x^2$ de $\mathbb{R}$ dans $\mathbb{R}$ : ni injective ($f(2)=f(-2)$), ni surjective ($-1$ n’a pas d’antécédent). De $[0,+\infty [$ dans $[0,+\infty [$ : bijective, réciproque $\sqrt{x}$.
• BTS : $f:\{a,b,c,d\}\to \{1,2,3\}$, $a\mapsto 2,b\mapsto 1,c\mapsto 3,d\mapsto 2$ → surjective, non injective (2 a deux antécédents).
• Chiffrement affine avec clé valide : bijection de l’alphabet sur lui-même (c’est pour ça qu’on peut déchiffrer) → M01 - Arithmétique et chiffrement affine.
• Informatique : une fonction de hachage n’est pas injective (collisions possibles) ; une clé primaire définit une injection ligne → identifiant.

3. Relations binaires

Propriété	Définition	Exemples
Réflexive	$\forall a,a\mathcal{R}a$	$=$, $\le$, « divise »
Symétrique	$a\mathcal{R}b\Rightarrow b\mathcal{R}a$	$=$, « est dans le même VLAN que »
Antisymétrique	$a\mathcal{R}b$ et $b\mathcal{R}a\Rightarrow a=b$	$\le$, « divise » (sur ${\mathbb{N}}^{\ast }$)
Transitive	$a\mathcal{R}b$ et $b\mathcal{R}c\Rightarrow a\mathcal{R}c$	$=$, $<$, « divise »

• Relation d’équivalence = réflexive + symétrique + transitive (ex. « même reste modulo 26 », « même sous-réseau »).
• Relation d’ordre = réflexive + antisymétrique + transitive (ex. $\le$, « divise », inclusion $\subset$).

BTS 2018 : « divise » sur ${\mathbb{N}}^{\ast }$ est réflexive, antisymétrique, transitive, non symétrique (2 | 6 mais 6 ∤ 2) → relation d’ordre.

Une relation se représente par un graphe (arc de $a$ vers $b$ si $a\mathcal{R}b$) ou une matrice → M07 - Graphes et plus court chemin.

Voir aussi

• M03 - Logique booléenne et Karnaugh · M07 - Graphes et plus court chemin
• Retour : 00 - Index général