Application (mathématiques)/Application caractéristique

Début de la boite de navigation du chapitre

Nous avons défini au premier chapitre, pour toute partie A d'un ensemble E, la fonction indicatrice de A (ou « application caractéristique de A ») :

fin de la boite de navigation du chapitre

${\begin{matrix}\chi _{A}&:&E&\to &\{0,1\}\\&&x&\mapsto &{\begin{cases}1&{\text{si }}&x\in A\\0&{\text{si }}&x\notin A.\end{cases}}\end{matrix}}$.

La bijection $\chi$

Grimpons à l'étage supérieur : l'ensemble E restant fixe, faisons maintenant varier A dans l'ensemble ${\mathcal {P}}(E)$ des parties de $E$.

Début d’un théorème

Théorème

L'application

${\begin{matrix}\chi &:&{\mathcal {P}}(E)&\to &\{0,1\}^{E}\\&&A&\mapsto &\chi _{A}\end{matrix}}$

est une bijection.

Fin du théorème

Démonstration

Pour toute application $f:E\to \{0,1\}$, une partie $A$ de $E$ vérifie $f=\chi _{A}$ si et seulement si $\forall x\in E\quad \left(x\in A\Leftrightarrow f(x)=1\right)$, c'est-à-dire si et seulement si $A=f^{-1}(\{1\})$. Donc $f$ a un unique antécédent par $\chi$ : l'image réciproque par $f$ du singleton $\{1\}$.

 

Corollaire

Deux parties de E sont égales si et seulement si leurs fonctions indicatrices sont égales.

Traduction arithmétique des opérations ensemblistes

On peut combiner des fonctions à valeurs entières en utilisant les opérations arithmétiques usuelles. Le résultat est une fonction à valeurs entières. Mais si les fonctions de départ ne prennent que les valeurs 0 ou 1 alors, certaines combinaisons arithmétiques produisent une fonction qui, elle aussi, ne prend que ces deux valeurs. En particulier :

Proposition

Pour toutes parties A et B de E :

• $\chi _{\overline {A}}=1-\chi _{A}$ ;
• $\chi _{A\cap B}=\min(\chi _{A},\chi _{B})=\chi _{A}\chi _{B}$ ;
• $\chi _{A\cup B}=\max(\chi _{A},\chi _{B})=\chi _{A}+\chi _{B}-\chi _{A}\chi _{B}$ (en particulier, si $A\cap B=\varnothing$ alors $\chi _{A\cup B}=\chi _{A}+\chi _{B}$) ;
• $\chi _{A\backslash B}=\chi _{A}(1-\chi _{B})$ ;
• $\chi _{A\Delta B}=\chi _{A}+\chi _{B}-2\chi _{A}\chi _{B}=(\chi _{A}-\chi _{B})^{2}=\left|\chi _{A}-\chi _{B}\right|$.

Démonstration

Les deux premières lignes sont immédiates et les trois suivantes s'en déduisent.

 

Transformation des formules entières en formules modulo 2

Identifions l’ensemble {0, 1} à l'ensemble des deux classes de congruence modulo 2 (0 = Pair, 1 = Impair) et munissons cet ensemble de l'addition et de la multiplication correspondantes. Sur {0, 1}, la multiplication modulo 2 est la même que la multiplication usuelle, mais l'addition modulo 2 correspond au OU exlusif, ou XOR, noté ici $\oplus$ :

$\oplus$	0	1
0	0	1
1	1	0

Avec ces nouvelles opérations, par construction, n'importe quelle combinaison de fonctions à valeurs dans {0, 1} sera automatiquement à valeurs dans {0, 1}. Les formules précédentes deviennent :

Corollaire

Pour toutes parties A et B de E, on a :

• $\chi _{\overline {A}}=1\oplus \chi _{A}$ ;
• $\chi _{A\cap B}=\chi _{A}\chi _{B}$ ;
• $\chi _{A\cup B}=\chi _{A}\oplus \chi _{B}\oplus \chi _{A}\chi _{B}$ ;
• $\chi _{A\backslash B}=\chi _{A}(1\oplus \chi _{B})$ ;
• $\chi _{A\Delta B}=\chi _{A}\oplus \chi _{B}$.