Ensembles et fonctions

Contenu

Ensembles et fonctions#

Nul ne nous sortira du paradis que Cantor a créé pour nous.

David Hilbert

La théorie des ensembles est le langage universel des mathématiques modernes. Elle permet de formaliser tous les objets mathématiques et leurs relations.

Ensembles#

Définition 10 (Ensemble par extension ou par compréhension)

Un ensemble peut être défini par extension, en énumérant tous ses éléments, ou par compréhension, par un prédicat caractérisant ses éléments :

\[E = \{x \in F \mid P(x)\}\]

Exemple 9

Par extension : \(E = \{1, 2, 3\}\)
Par compréhension : \(E = \{n \in \mathbb{N} \mid 1 \leq n \leq 3\}\)
Ces deux écritures définissent le même ensemble.

Remarque 8

Un ensemble n’est pas ordonné (\(\{x, y\} = \{y, x\}\)), et ses éléments sont distincts (\(\{x, x\} = \{x\}\)). L’ensemble vide \(\varnothing\) est l’unique ensemble ne contenant aucun élément. Un ensemble à un seul élément est un singleton ; à deux éléments, une paire.

Remarque 9 (Paradoxe de Russell)

La définition naïve « un ensemble est une collection quelconque d’objets » conduit à des paradoxes. Soit \(R = \{E \mid E \notin E\}\). Alors \(R \in R \iff R \notin R\), une contradiction.

La théorie axiomatique des ensembles (ZFC — Zermelo-Fraenkel avec axiome du choix) résout ce problème en restreignant les ensembles admissibles. En pratique, on travaille dans un « univers » fixé.

Inclusion et égalité#

Définition 11 (Sous-ensemble — Inclusion)

Soient \(E\) et \(F\) des ensembles. \(F\) est un sous-ensemble (ou partie) de \(E\), noté \(F \subseteq E\) (ou \(F \subset E\)), si

\[\forall x,\ x \in F \implies x \in E\]

On dit que \(F\) est inclus dans \(E\), ou que \(E\) contient \(F\).

On note \(F \subsetneq E\) si \(F \subseteq E\) et \(F \neq E\) (inclusion stricte).

Proposition 10 (Caractérisation de l’égalité)

\[E = F \iff (E \subseteq F) \land (F \subseteq E)\]

Proof. \((\implies)\) Si \(E = F\), tout élément de \(E\) est dans \(F\) et réciproquement.

\((\impliedby)\) Supposons \(E \subseteq F\) et \(F \subseteq E\). Soit \(x \in E\) : alors \(x \in F\). Soit \(x \in F\) : alors \(x \in E\). Donc \(E\) et \(F\) ont exactement les mêmes éléments, soit \(E = F\).

Ensemble des parties#

Définition 12 (Ensemble des parties)

L”ensemble des parties de \(E\), noté \(\mathcal{P}(E)\), est l’ensemble de tous les sous-ensembles de \(E\) :

\[\mathcal{P}(E) = \{F \mid F \subseteq E\}\]

Proposition 11 (Cardinal de \(\mathcal{P}(E)\))

Si \(E\) est fini avec \(|E| = n\), alors \(|\mathcal{P}(E)| = 2^n\).

Proof. Chaque sous-ensemble de \(E = \{x_1, \ldots, x_n\}\) correspond à un mot binaire de longueur \(n\) (le \(i\)-ème bit indique si \(x_i\) est inclus). Il y a donc \(2^n\) sous-ensembles.

Alternativement, par récurrence : si \(|\mathcal{P}(E)| = 2^n\), ajouter un élément \(x_{n+1}\) double le nombre de parties (chaque partie de \(E\) donne deux parties de \(E \cup \{x_{n+1}\}\) : avec ou sans \(x_{n+1}\)).

Exemple 10

\(\mathcal{P}(\{a, b, c\}) = \{\varnothing,\ \{a\},\ \{b\},\ \{c\},\ \{a,b\},\ \{a,c\},\ \{b,c\},\ \{a,b,c\}\}\), soit \(2^3 = 8\) éléments.

Opérations sur les ensembles#

Définition 13 (Opérations ensemblistes)

Soient \(E\), \(F\) des sous-ensembles d’un ensemble ambiant \(\Omega\).

Complémentaire : \(\bar{F} = \Omega \setminus F = \{x \in \Omega \mid x \notin F\}\)
Union : \(E \cup F = \{x \mid x \in E \lor x \in F\}\)
Intersection : \(E \cap F = \{x \mid x \in E \land x \in F\}\)
Différence : \(E \setminus F = \{x \mid x \in E \land x \notin F\}\)
Différence symétrique : \(E \triangle F = (E \setminus F) \cup (F \setminus E)\)

Proposition 12 (Propriétés algébriques)

Les opérations \(\cup\), \(\cap\) vérifient :

Commutativité : \(E \cup F = F \cup E\), \(E \cap F = F \cap E\)
Associativité : \((E \cup F) \cup G = E \cup (F \cup G)\)
Distributivité : \(E \cap (F \cup G) = (E \cap F) \cup (E \cap G)\)
Éléments neutres : \(E \cup \varnothing = E\), \(E \cap \Omega = E\)
Éléments absorbants : \(E \cup \Omega = \Omega\), \(E \cap \varnothing = \varnothing\)
Lois de De Morgan : \(\overline{E \cup F} = \bar{E} \cap \bar{F}\), \(\overline{E \cap F} = \bar{E} \cup \bar{F}\)
Involution : \(\bar{\bar{E}} = E\)

Proof. Montrons la loi de De Morgan \(\overline{E \cup F} = \bar{E} \cap \bar{F}\).

\(x \in \overline{E \cup F} \iff x \notin E \cup F \iff \lnot(x \in E \lor x \in F)\) \(\iff x \notin E \land x \notin F\) (De Morgan logique) \(\iff x \in \bar{E} \land x \in \bar{F} \iff x \in \bar{E} \cap \bar{F}\).

Show code cell source

Hide code cell source

# Diagrammes de Venn : toutes les opérations binaires
fig, axes = plt.subplots(4, 2, figsize=(10, 16))
axes = axes.flatten()

def set_venn_full(ax, which, title, color='#3498db'):
    """Colore les régions spécifiées d'un diagramme de Venn."""
    v = venn2(subsets=(1, 1, 1), ax=ax)
    regions = {'10': v.get_patch_by_id('10'),
               '01': v.get_patch_by_id('01'),
               '11': v.get_patch_by_id('11')}
    for region_id, patch in regions.items():
        if patch:
            if region_id in which:
                patch.set_facecolor(color)
                patch.set_alpha(0.7)
            else:
                patch.set_facecolor('white')
                patch.set_alpha(0.5)
    ax.set_title(title, fontsize=11, fontweight='bold')
    # Labels
    if v.get_label_by_id('A'):
        v.get_label_by_id('A').set_text('$A$')
    if v.get_label_by_id('B'):
        v.get_label_by_id('B').set_text('$B$')

set_venn_full(axes[0], ['10', '01', '11'], r'$A \cup B$', '#3498db')
set_venn_full(axes[1], ['11'],             r'$A \cap B$', '#e74c3c')
set_venn_full(axes[2], ['10'],             r'$A \setminus B$', '#2ecc71')
set_venn_full(axes[3], ['01'],             r'$B \setminus A$', '#f39c12')
set_venn_full(axes[4], ['10', '01'],       r'$A \triangle B$', '#9b59b6')

# Complémentaire de A : région hors des deux cercles + région de B seul
v5 = venn2(subsets=(1, 1, 1), ax=axes[5])
if v5.get_patch_by_id('10'): v5.get_patch_by_id('10').set_alpha(0.1)
if v5.get_patch_by_id('11'): v5.get_patch_by_id('11').set_alpha(0.1)
if v5.get_patch_by_id('01'): v5.get_patch_by_id('01').set_facecolor('#e74c3c'); v5.get_patch_by_id('01').set_alpha(0.5)
# Colorier le fond pour représenter le complémentaire
axes[5].set_facecolor('#ffcdd2')
axes[5].set_title(r'$\bar{A}$ (complémentaire)', fontsize=11, fontweight='bold')

# Loi de De Morgan illustrée
v6 = venn2(subsets=(1, 1, 1), ax=axes[6])
for rid in ['10', '01', '11']:
    p = v6.get_patch_by_id(rid)
    if p: p.set_alpha(0.1)
axes[6].set_facecolor('#d5e8d4')
axes[6].set_title(r'$\overline{A \cup B} = \bar{A} \cap \bar{B}$' '\n(région extérieure)', fontsize=10, fontweight='bold')

# Ensembles disjoints
v7 = venn2(subsets=(5, 5, 0), ax=axes[7])
if v7.get_patch_by_id('10'): v7.get_patch_by_id('10').set_facecolor('#3498db'); v7.get_patch_by_id('10').set_alpha(0.6)
if v7.get_patch_by_id('01'): v7.get_patch_by_id('01').set_facecolor('#e74c3c'); v7.get_patch_by_id('01').set_alpha(0.6)
axes[7].set_title(r'$A \cap B = \varnothing$' '\n(ensembles disjoints)', fontsize=11, fontweight='bold')

fig.suptitle('Opérations sur les ensembles', fontsize=14, fontweight='bold', y=1.01)
plt.tight_layout()
plt.show()

_images/d21b6ad1da444828e326b47bf6e612718c18936b4f18af9c78ee834d2a709124.png

_images/e3ed4a6218626cec88cd76f8ca6aba86153cb119ae13a13d9d754c016a2f5a3e.png

Produit cartésien et famille d’ensembles#

Définition 14 (Produit cartésien)

Soient \(E\) et \(F\) des ensembles non vides. Le produit cartésien \(E \times F\) est l’ensemble des paires ordonnées :

\[E \times F = \{(x, y) \mid x \in E,\ y \in F\}\]

On note \(E^n = E \times E \times \cdots \times E\) (\(n\) fois).

Proposition 13 (Cardinal du produit cartésien)

Si \(E\) et \(F\) sont finis, \(|E \times F| = |E| \cdot |F|\).

Définition 15 (Famille d’ensembles)

Soit \(I\) un ensemble d’indices. Une famille \((E_i)_{i \in I}\) est une application \(i \mapsto E_i\).

\[\bigcup_{i \in I} E_i = \{x \mid \exists i \in I,\ x \in E_i\}, \qquad \bigcap_{i \in I} E_i = \{x \mid \forall i \in I,\ x \in E_i\}\]

Le produit cartésien généralisé est \(\prod_{i \in I} E_i = \{(x_i)_{i \in I} \mid \forall i,\ x_i \in E_i\}\).

Remarque 10

L”axiome du choix affirme que \(\prod_{i \in I} E_i \neq \varnothing\) pour toute famille d’ensembles non vides. Cet axiome, indépendant des autres axiomes de ZF, est équivalent au lemme de Zorn et au théorème de bonne-ordination.

Relations#

Définition 16 (Relation binaire)

Une relation binaire \(\mathcal{R}\) de \(E\) dans \(F\) est un sous-ensemble \(G \subseteq E \times F\) (son graphe). On note \(x \mathcal{R} y\) si \((x, y) \in G\).

Définition 17 (Propriétés d’une relation sur \(E\))

Soit \(\mathcal{R}\) une relation de \(E\) dans \(E\).

Réflexive : \(\forall x \in E,\ x \mathcal{R} x\)
Symétrique : \(\forall x, y \in E,\ x \mathcal{R} y \implies y \mathcal{R} x\)
Anti-symétrique : \(\forall x, y \in E,\ (x \mathcal{R} y \land y \mathcal{R} x) \implies x = y\)
Transitive : \(\forall x, y, z \in E,\ (x \mathcal{R} y \land y \mathcal{R} z) \implies x \mathcal{R} z\)
Totale : \(\forall x, y \in E,\ x \mathcal{R} y \lor y \mathcal{R} x\)

Définition 18 (Relations d’équivalence et d’ordre)

\(\mathcal{R}\) est une relation d’équivalence si elle est réflexive, symétrique et transitive.
\(\mathcal{R}\) est une relation d’ordre si elle est réflexive, anti-symétrique et transitive. L’ordre est total si la relation est de plus totale.

Définition 19 (Classes d’équivalence et quotient)

Soit \(\sim\) une relation d’équivalence sur \(E\), et \(x \in E\). La classe d’équivalence de \(x\) est

\[[x] = \{y \in E \mid y \sim x\}\]

L’ensemble quotient \(E/{\sim}\) est l’ensemble de toutes les classes d’équivalence. Les classes forment une partition de \(E\) : elles sont deux à deux disjointes et leur union est \(E\).

Exemple 11

L’égalité \(=\) est la relation d’équivalence la plus fine (chaque classe est un singleton).
La congruence modulo \(n\) : \(a \equiv b \pmod{n}\) si \(n \mid (a-b)\). Exemple : \(\mathbb{Z}/3\mathbb{Z} = \{\bar{0}, \bar{1}, \bar{2}\}\).
Sur \(\mathbb{R}^2 \setminus \{(0,0)\}\), la relation \((x,y) \sim (x', y')\) si \((x', y') = \lambda(x, y)\) pour un \(\lambda > 0\) donne le plan projectif.

Show code cell source

Hide code cell source

# Visualisation des classes d'équivalence et partitions
fig, axes = plt.subplots(2, 1, figsize=(9, 9))

# Classes modulo 3 dans {0,...,11}
n = 12
elements = np.arange(n)
classes = [elements[elements % 3 == r] for r in range(3)]
colors_cls = ['#e74c3c', '#3498db', '#2ecc71']
labels_cls = ['$\\bar{0}$ : mult. de 3', '$\\bar{1}$ : reste 1', '$\\bar{2}$ : reste 2']

ax = axes[0]
for i, (cls, col, lbl) in enumerate(zip(classes, colors_cls, labels_cls)):
    y = [i] * len(cls)
    ax.scatter(cls, y, s=300, color=col, zorder=5, label=lbl)
    for x0 in cls:
        ax.text(x0, i, str(x0), ha='center', va='center', fontsize=9, color='white', fontweight='bold')
    # Boite autour de chaque classe
    ax.add_patch(FancyBboxPatch((cls[0]-0.5, i-0.35), cls[-1]-cls[0]+1, 0.7,
                 boxstyle='round,pad=0.1', facecolor=col, alpha=0.15, edgecolor=col, lw=2))

ax.set_xlim(-1, 12)
ax.set_ylim(-0.8, 2.8)
ax.set_yticks([0, 1, 2])
ax.set_yticklabels([r'Classe $\bar{0}$', r'Classe $\bar{1}$', r'Classe $\bar{2}$'])
ax.set_xlabel('Éléments de $\\{0, 1, \\ldots, 11\\}$')
ax.set_title('Partition de $\\{0,\\ldots,11\\}$\npar la congruence modulo 3', fontsize=11)
ax.legend(loc='upper right', fontsize=9)
ax.grid(True, axis='x', alpha=0.3)

# Relation d'ordre : divisibilité sur {1,...,12}
ax2 = axes[1]
# Diagramme de Hasse pour la divisibilité sur {1,2,3,4,6,12}
nodes = [1, 2, 3, 4, 6, 12]
pos = {1: (2, 0), 2: (1, 1), 3: (3, 1), 4: (0.5, 2), 6: (2.5, 2), 12: (1.5, 3)}
edges = [(1,2), (1,3), (2,4), (2,6), (3,6), (4,12), (6,12)]

for (a, b) in edges:
    xa, ya = pos[a]
    xb, yb = pos[b]
    ax2.annotate('', xy=(xb, yb), xytext=(xa, ya),
                arrowprops=dict(arrowstyle='->', color='#555', lw=1.5))

for n_node, (x, y) in pos.items():
    ax2.scatter([x], [y], s=500, color='#3498db', zorder=5)
    ax2.text(x, y, str(n_node), ha='center', va='center', color='white', fontsize=12, fontweight='bold')

ax2.set_xlim(-0.5, 4)
ax2.set_ylim(-0.5, 3.8)
ax2.axis('off')
ax2.set_title('Diagramme de Hasse\n(divisibilité sur $\\{1,2,3,4,6,12\\}$)', fontsize=11)

plt.tight_layout()
plt.show()

_images/0254d44654f725907617c92200ad2b5892db3261d0af3d1a2dec3cfba051f800.png

Fonctions et applications#

Définition 20 (Fonction et application)

Soient \(E\), \(F\) des ensembles. Une fonction \(f : E \to F\) est une relation de \(E\) dans \(F\) telle que tout \(x \in E\) admet au plus un antécédent. Si tout \(x \in E\) admet exactement un antécédent, \(f\) est une application.

Le domaine de définition est \(D_f = \{x \in E \mid \exists y \in F,\ f(x) = y\}\). L”image est \(\text{Im}(f) = \{f(x) \mid x \in D_f\} \subseteq F\).

Définition 21 (Image directe et image réciproque)

Soient \(f : E \to F\), \(A \subseteq E\), \(B \subseteq F\).

Image directe : \(f(A) = \{f(x) \mid x \in A\}\)
Image réciproque : \(f^{-1}(B) = \{x \in E \mid f(x) \in B\}\)

Proposition 14 (Propriétés des images)

\[f(A \cup A') = f(A) \cup f(A'), \quad f(A \cap A') \subseteq f(A) \cap f(A')\]

\[f^{-1}(B \cup B') = f^{-1}(B) \cup f^{-1}(B'), \quad f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')\]

\[f^{-1}(\bar{B}) = \overline{f^{-1}(B)}\]

Proof. Montrons \(f^{-1}(\bar{B}) = \overline{f^{-1}(B)}\) : \(x \in f^{-1}(\bar{B}) \iff f(x) \in \bar{B} \iff f(x) \notin B \iff x \notin f^{-1}(B) \iff x \in \overline{f^{-1}(B)}\).

Remarque : l’inclusion \(f(A \cap A') \subseteq f(A) \cap f(A')\) est en général stricte. Si \(f\) est injective, on a égalité.

Injection, surjection, bijection#

Définition 22 (Injective, surjective, bijective)

Soit \(f : E \to F\).

\(f\) est injective si \(\forall x, y \in E,\ f(x) = f(y) \implies x = y\).
\(f\) est surjective si \(\forall y \in F,\ \exists x \in E,\ f(x) = y\).
\(f\) est bijective si elle est à la fois injective et surjective.

Proposition 15 (Caractérisations équivalentes)

\(f\) injective \(\iff f^{-1}(\{y\})\) a au plus un élément pour tout \(y \in F\).
\(f\) surjective \(\iff f^{-1}(\{y\}) \neq \varnothing\) pour tout \(y \in F\).
\(f\) bijective \(\iff \exists g : F \to E,\ g \circ f = \text{Id}_E \land f \circ g = \text{Id}_F\).

Proof. Montrons la troisième. Si \(f\) est bijective, pour chaque \(y \in F\) il existe un unique \(x \in E\) tel que \(f(x) = y\) ; posons \(g(y) = x\). Alors \(f(g(y)) = y\) et \(g(f(x)) = x\).

Réciproquement, si \(g \circ f = \text{Id}_E\), alors \(f\) est injective (si \(f(x) = f(y)\), appliquer \(g\)). Si \(f \circ g = \text{Id}_F\), alors \(f\) est surjective (pour tout \(y\), \(f(g(y)) = y\)).

Remarque 11

Pour des ensembles finis de même cardinal \(n\) : \(f\) injective \(\iff\) \(f\) surjective \(\iff\) \(f\) bijective. Ce résultat est faux en dimension infinie.

Show code cell source

Hide code cell source

# Illustration injection / surjection / bijection
fig, axes = plt.subplots(3, 1, figsize=(9, 16))

def plot_function_map(ax, E, F, arrows, title, subtitle=''):
    """Dessine un schéma de fonction avec flèches."""
    ax.axis('off')
    ax.set_xlim(0, 4)
    ax.set_ylim(-0.5, max(len(E), len(F)) + 0.5)
    n = max(len(E), len(F))

    # Fond des deux ensembles
    for label, x_center, elements in [('$E$', 0.8, E), ('$F$', 3.2, F)]:
        y_positions = np.linspace(n-1, 0, len(elements))
        rect = FancyBboxPatch((x_center-0.55, -0.3), 1.1, n+0.1,
                                   boxstyle='round,pad=0.05',
                                   facecolor='#ecf0f1', edgecolor='#bdc3c7', lw=2)
        ax.add_patch(rect)
        ax.text(x_center, n+0.1, label, ha='center', va='bottom', fontsize=14, fontweight='bold')
        for i, (elem, y) in enumerate(zip(elements, y_positions)):
            ax.scatter([x_center], [y], s=200, color='#3498db', zorder=5)
            ax.text(x_center, y, str(elem), ha='center', va='center',
                    color='white', fontsize=10, fontweight='bold')

    # Flèches
    E_pos = {e: n - 1 - i * (n-1)/(len(E)-1) if len(E) > 1 else n/2
             for i, e in enumerate(E)}
    F_pos = {f: n - 1 - i * (n-1)/(len(F)-1) if len(F) > 1 else n/2
             for i, f in enumerate(F)}

    for (e, f) in arrows:
        y_e = E_pos[e]
        y_f = F_pos[f]
        ax.annotate('', xy=(3.2-0.15, y_f), xytext=(0.8+0.15, y_e),
                   arrowprops=dict(arrowstyle='->', color='#e74c3c', lw=2))

    ax.set_title(title + '\n' + subtitle, fontsize=11, fontweight='bold')

# Injection non surjective : f(1)=a, f(2)=b, f(3)=c, d non atteint
E1 = [1, 2, 3]; F1 = ['a', 'b', 'c', 'd']
plot_function_map(axes[0], E1, F1,
                  [(1,'a'), (2,'b'), (3,'c')],
                  'Injection (non surjection)',
                  r'$f(1)=a, f(2)=b, f(3)=c$')

# Surjection non injective : f(1)=a, f(2)=a, f(3)=b, f(4)=c
E2 = [1, 2, 3, 4]; F2 = ['a', 'b', 'c']
plot_function_map(axes[1], E2, F2,
                  [(1,'a'), (2,'a'), (3,'b'), (4,'c')],
                  'Surjection (non injection)',
                  r'$f(1)=f(2)=a$')

# Bijection
E3 = [1, 2, 3]; F3 = ['a', 'b', 'c']
plot_function_map(axes[2], E3, F3,
                  [(1,'a'), (2,'b'), (3,'c')],
                  'Bijection',
                  r'(injection + surjection)')

plt.suptitle('Injection, surjection, bijection', fontsize=14, fontweight='bold', y=1.02)
plt.tight_layout()
plt.show()

_images/86e496fb8eb1b51c50757c79577555ba7327ee2b1c3d774db68334008e700d4f.png

Composition et bijection réciproque#

Définition 23 (Composition)

Soient \(f : E \to F\) et \(g : F \to G\). La composée \(g \circ f : E \to G\) est définie par \((g \circ f)(x) = g(f(x))\).

Proposition 16 (Propriétés de la composition)

La composition est associative : \((h \circ g) \circ f = h \circ (g \circ f)\).
\(\text{Id}_F \circ f = f\) et \(f \circ \text{Id}_E = f\).
Si \(f\) et \(g\) sont injectives (resp. surjectives, bijectives), alors \(g \circ f\) l’est aussi.
\((g \circ f)^{-1} = f^{-1} \circ g^{-1}\) si \(f\) et \(g\) sont bijectives.

Proof. Injectivité de \(g \circ f\) : Supposons \((g \circ f)(x) = (g \circ f)(y)\), i.e. \(g(f(x)) = g(f(y))\). Par injectivité de \(g\) : \(f(x) = f(y)\). Par injectivité de \(f\) : \(x = y\).

Surjectivité de \(g \circ f\) : Soit \(z \in G\). Par surjectivité de \(g\), \(\exists y \in F\) tel que \(g(y) = z\). Par surjectivité de \(f\), \(\exists x \in E\) tel que \(f(x) = y\). Alors \((g \circ f)(x) = z\).

Cardinalité et dénombrabilité#

Définition 24 (Équipotence et cardinalité)

Deux ensembles \(E\) et \(F\) sont équipotents (notés \(E \sim F\)) s’il existe une bijection \(f : E \to F\). Leur cardinal est le même, noté \(|E| = |F|\).

Un ensemble est dénombrable (ou infini dénombrable) s’il est équipotent à \(\mathbb{N}\).

Proposition 17 (Dénombrabilité de \(\mathbb{Z}\) et \(\mathbb{Q}\))

\(\mathbb{Z}\) et \(\mathbb{Q}\) sont dénombrables.

Proof. Pour \(\mathbb{Z}\) : La bijection \(f : \mathbb{N} \to \mathbb{Z}\) définie par \(f(n) = \frac{n}{2}\) si \(n\) est pair, \(f(n) = -\frac{n+1}{2}\) si \(n\) est impair est une bijection.

Pour \(\mathbb{Q}\) : On énumère les fractions \(\frac{p}{q}\) avec \(p \in \mathbb{Z}\), \(q \in \mathbb{N}^*\), \(\text{pgcd}(|p|, q) = 1\) par la diagonale de Cantor. C’est une injection de \(\mathbb{Q}\) dans \(\mathbb{N}\), et comme \(\mathbb{N} \subseteq \mathbb{Q}\), par le théorème de Schröder-Bernstein, \(|\mathbb{Q}| = |\mathbb{N}|\).

Proposition 18 (Indénombrabilité de \(\mathbb{R}\) (Cantor, 1874))

\(\mathbb{R}\) n’est pas dénombrable.

Proof. Par l”argument diagonal de Cantor. Supposons par l’absurde qu’il existe une surjection \(f : \mathbb{N} \to \: ]0, 1[\), i.e. une énumération \(f(0) = 0.a_{00}a_{01}a_{02}\ldots\), \(f(1) = 0.a_{10}a_{11}a_{12}\ldots\), etc.

Construisons \(x = 0.b_0 b_1 b_2 \ldots\) avec \(b_n \neq a_{nn}\) (et \(b_n \notin \{0, 9\}\) pour éviter les ambiguïtés des développements décimaux).

Alors \(x \in \: ]0, 1[\) et \(x \neq f(n)\) pour tout \(n\) (car ils diffèrent au \(n\)-ième rang décimal). Contradiction avec la surjectivité de \(f\).

Remarque 12

Le théorème de Cantor montre que \(|\mathcal{P}(E)| > |E|\) pour tout ensemble \(E\) : il n’existe pas de « plus grand ensemble ». La hiérarchie des infinis est \(\aleph_0 = |\mathbb{N}| < \mathfrak{c} = |\mathbb{R}| = 2^{\aleph_0} < 2^{\mathfrak{c}} < \cdots\)

Show code cell source

Hide code cell source

# Visualisation de l'argument diagonal de Cantor
fig, axes = plt.subplots(2, 1, figsize=(9, 9))

# Grille des chiffres decimaux
n_show = 8
np.random.seed(42)
digits = np.random.randint(1, 9, size=(n_show, n_show))

ax = axes[0]
im = ax.imshow(digits, cmap='Blues', vmin=1, vmax=8, aspect='auto')

for i in range(n_show):
    for j in range(n_show):
        color = 'red' if i == j else 'black'
        weight = 'bold' if i == j else 'normal'
        ax.text(j, i, str(digits[i, j]), ha='center', va='center',
                fontsize=12, color=color, fontweight=weight)

# Diagonale en rouge
for i in range(n_show):
    ax.add_patch(plt.Rectangle((i-0.5, i-0.5), 1, 1,
                 fill=False, edgecolor='red', linewidth=2))

ax.set_xticks(range(n_show))
ax.set_xticklabels([f'rang {i}' for i in range(n_show)], rotation=45, ha='right')
ax.set_yticks(range(n_show))
ax.set_yticklabels([f'$f({i})$' for i in range(n_show)])
ax.set_title('Argument diagonal de Cantor\n(chiffres sur la diagonale sont modifiés)', fontsize=11)

# Construction du nombre x diagonal
diagonal = digits[range(n_show), range(n_show)]
modified = (diagonal % 8) + 1  # != diagonal et dans {1,...,8}
ax.text(n_show + 0.1, n_show/2 - 0.5,
        f'$x = 0.{"".join(map(str, modified))}\\ldots$\n$\\neq f(n)$ pour tout $n$',
        fontsize=10, color='red', va='center')

# Cardinalités comparées
ax2 = axes[1]
sets = ['$\\mathbb{N}$', '$\\mathbb{Z}$', '$\\mathbb{Q}$', '$\\mathbb{R}$', '$\\mathcal{P}(\\mathbb{R})$']
cards = [r'$\aleph_0$', r'$\aleph_0$', r'$\aleph_0$', r'$\mathfrak{c} = 2^{\aleph_0}$', r'$2^{\mathfrak{c}}$']
heights = [1, 1, 1, 2, 3]
colors_card = ['#3498db', '#3498db', '#3498db', '#e74c3c', '#9b59b6']

bars = ax2.bar(sets, heights, color=colors_card, edgecolor='black', alpha=0.8)
for bar, card, h in zip(bars, cards, heights):
    ax2.text(bar.get_x() + bar.get_width()/2, h + 0.05, card,
             ha='center', va='bottom', fontsize=11, fontweight='bold')

ax2.set_ylabel('Niveau de cardinalité (schématique)')
ax2.set_title('Hiérarchie des infinis\n($\\aleph_0 < \\mathfrak{c} < 2^\\mathfrak{c} < \\cdots$)', fontsize=11)
ax2.set_ylim(0, 3.8)

# Accolade pour les dénombrables
ax2.annotate('', xy=(2.4, 1.1), xytext=(2.4, 0.9),
             arrowprops=dict(arrowstyle='<->', color='#3498db', lw=2))
ax2.text(2.6, 1.0, 'dénombrables', color='#3498db', fontsize=9, va='center')

plt.tight_layout()
plt.show()

_images/be201710ee66ca10d6a88a6bf72af327a4c228102fb1bee5cd3034e22739dedc.png

Fonction caractéristique et indicatrice#

Définition 25 (Fonction indicatrice)

Soient \(\Omega\) un ensemble et \(A \subseteq \Omega\). La fonction indicatrice (ou caractéristique) de \(A\) est

\[\begin{split}\mathbf{1}_A : \Omega \to \{0, 1\}, \quad \mathbf{1}_A(x) = \begin{cases} 1 & \text{si } x \in A \\ 0 & \text{si } x \notin A \end{cases}\end{split}\]

Proposition 19 (Propriétés)

Pour tous \(A, B \subseteq \Omega\) :

\[\mathbf{1}_{\bar{A}} = 1 - \mathbf{1}_A, \quad \mathbf{1}_{A \cap B} = \mathbf{1}_A \cdot \mathbf{1}_B, \quad \mathbf{1}_{A \cup B} = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \cdot \mathbf{1}_B\]

\[\mathbf{1}_{A \triangle B} = \mathbf{1}_A + \mathbf{1}_B - 2\mathbf{1}_A\mathbf{1}_B = |\mathbf{1}_A - \mathbf{1}_B|\]

Proof. \(\mathbf{1}_{A \cap B}(x) = 1 \iff x \in A \cap B \iff x \in A \text{ et } x \in B \iff \mathbf{1}_A(x) = 1 \text{ et } \mathbf{1}_B(x) = 1 \iff \mathbf{1}_A(x)\mathbf{1}_B(x) = 1\).

Pour l’union : \(\mathbf{1}_{A \cup B} = 1 - \mathbf{1}_{\overline{A \cup B}} = 1 - \mathbf{1}_{\bar{A} \cap \bar{B}} = 1 - (1-\mathbf{1}_A)(1-\mathbf{1}_B) = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A\mathbf{1}_B\).

Remarque 13

La formule \(\mathbf{1}_{A \cup B} = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_{A \cap B}\) est la version ensembliste de la formule d’inclusion-exclusion. En général :

\[\left|\bigcup_{i=1}^n A_i\right| = \sum_i |A_i| - \sum_{i < j} |A_i \cap A_j| + \cdots + (-1)^{n+1}|A_1 \cap \cdots \cap A_n|\]

_images/3430339562e8dee4ea08da247c1b3f438a4dd6eb5c84ca0ec8fb42a577aae814.png