Proposition 7Relations, fonctions

Équipotence et comparaison des ensembles

Deux ensembles $A$ et $B$ sont équipotents, ce qu'on note $A \approx B$ , s'il existe une bijection de $A$ sur $B$ . On note $A \preccurlyeq B$ s'il existe une injection de $A$ dans $B$ .

Énoncé

Pour tous ensembles $A$ , $B$ , $C$ :

(i) $A \approx A$ ; si $A \approx B$ , alors $B \approx A$ ; si $A \approx B$ et $B \approx C$ , alors $A \approx C$ ;

(ii) $A \preccurlyeq A$ ; si $A \preccurlyeq B$ et $B \preccurlyeq C$ , alors $A \preccurlyeq C$ ; si $A \subset B$ , alors $A \preccurlyeq B$ .

Démonstration

(i) L'identité est une bijection. Si $f : A \to B$ est bijective, $f^{-1}$ l'est aussi, et la composée de deux bijections est bijective (Bijection réciproque).

(ii) L'identité et la composée de deux injections sont injectives. Si $A \subset B$ , l'inclusion $A \to B$ , de graphe $\{(a, a) : a \in A\}$ , est injective.

□

Remarque

Ces énoncés ressemblent aux propriétés d'une relation d'équivalence et d'une relation d'ordre, mais $\approx$ et $\preccurlyeq$ ne sont pas des relations au sens de ce graphe : elles portent sur tous les ensembles, qui ne forment pas un ensemble. Ce sont des formules à deux variables libres. Restreintes aux parties d'un ensemble fixé, elles redeviennent des relations.

Remarque

L'antisymétrie de $\preccurlyeq$ , à équipotence près, est le théorème de Cantor-Bernstein, deux nœuds plus loin. La comparabilité, « $A \preccurlyeq B$ ou $B \preccurlyeq A$ pour tous $A$ , $B$ », est en revanche équivalente à l'axiome du choix ; cette équivalence sera établie avec les cardinaux, au nœud Comparabilité.

Repose sur

Bijection réciproque, rétractions et sections

Sert à

Théorème de Cantor Théorème de Cantor-Bernstein