Exercices Alternatifs

Parties d’un ensemble et procédé diagonal

\begin{matrix}c \\ ◯ \end{matrix}2002 Vincent Guirardel (copyleft LDL : Licence pour Documents Libres).

     Source: parties et procede diagonal.tex.
     Version imprimable: parties et procede diagonal.pdf

Théorie des ensembles, et structures de base. DEUG première année. Angle pédagogique : Langage.

Objectifs et commentaires. L’exercice commence par introduire le codage des parties d’un ensemble par leur fonction caractéristique, puis leur montre le procédé diagonal de Cantor. L’exercice fait manipuler aux étudiants les notions de bijections, injections, applications, complémentaire. C’est volontairement qu’on parle d’ensemble quelconque (sans preciser que cela signifie fini ou infini), et c’est la derniere question qui doit leur faire realiser que la construction marche aussi pour un ensemble infini. On peut alors les faire réfléchir sur l’existence d’infinis plus grand que d’autres...

Question 1. Codage des parties d’un ensemble fini

Dans tout l’exercice, on notera B = {0, 1} (ensemble des ”bits”).

Soit E = {a_{1}, …, a_{n}} un ensemble à n éléments (n ≥ 1). À toute partie A de E, on associe son application caractéristique :

χ_{A} : \begin{cases}E → B \\ x ↦ \begin{cases}1 si x ∈ A \\ 0 si x ∉ A \end{cases} \end{cases}

On peut coder l’application χ_{A} par un vecteur de bits (”bit vector”) V_{A} = (ϵ_{1}, …, ϵ_{n}), où ϵ_{i} = χ_{A}(a_{i}). Autrement dit, le i-ème bit ϵ_{i} est mis à 1 si a_{i} est élément de A, sinon, il est mis à 0 ^{1}.

a. On prend ici n = 3 et E = {1, 2, 3}. Enumérer toutes les parties de E. Pour chacune, expliciter son application caractéristique ainsi que le vecteur de bits associé. On présentera les résultats sous forme de tableau.

b.

(i). — On se replace dans le cas général (n quelconque). Montrer que l’application de P(E) dans F(E, B) qui à une partie A de E associe sa fonction caractéristique χ_{A} est bijective. Pour cela, on explicitera son application réciproque.

(ii). — Montrer de même que l’application P(E) dans B^{n} qui à une partie A de E associe son vecteur de bits V_{A} est bijective.

La bijectivit’e de cette application a-t-elle un intérêt, en termes du codage mentionné au dessus ?

1C’est la méthode utilisée dans le langage Pascal (par exemple) pour coder le type de données ensemble.

(iii). — En déduire le cardinal de P(E).

c.

(i). — On note \overline{0} = 1 et \overline{1} = 0 (bit complémentaire) ; autrement dit, ∀ϵ ∈ B , \overline{ϵ} = 1 − ϵ. Pour tout vecteur de bits V = (ϵ_{1}, …, ϵ_{n}) ∈ B^{n}, on note \overline{V} = (\overline{ϵ_{1}}, …, \overline{ϵ_{n}}). A quelle partie de E correspond le vecteur de bits \overline{V_{A}}?

(ii). — Décrire de même le vecteur de bits associé à A ∪ A′, à A ∩ A′.

Question 2. Le procédé diagonal de Cantor

a. Montrer que pour tout entier naturel n, 2^{n} > n. En déduire que, pour tout ensemble fini E, il n’existe aucune application surjective de E sur P(E).

b. On prend maintenant E = {1, …, n}. On considère n parties de E, notées A_{1}, …, A_{n}. Pour tout i ∈ {1, …, n}, on note V_{A_{i}} = (ϵ_{i,1}, …, ϵ_{i,n}) le vecteur de bits associé. Puis, pour tout i ∈ \{1, …, n\}, on note ϵ′_{i} = \overline{ϵ_{i,i}}. On note enfin V′ = (ϵ′_{1}, …, ϵ′_{n}) et A′ l’unique partie de E dont le vecteur de bits associé est V′.

(i). — Donner un exemple de ces constructions, sous forme de tableau, lorsque n = 10.

(ii). — En général, montrer que A′ n’est égal à aucune des parties A_{i}. On raisonnera par l’absurde : si l’on avait A′ = A_{i} pour un certain i ∈ {1, …, n}, quelle serait la valeur du i-ème bit du vecteur associé à cette partie ?

(iii). — Retrouver ainsi le résultat de la question a. Indication : si f est une application de E dans P(E), on note A_{1} = f(1), …, A_{n} = f(n) ; on constate alors que la partie A′ construite ci-dessus n’appartient pas à l’ensemble image de f.

(iv). — Vérifier que A′ = {i ∈ E / i ∉ A_{i}}.

c. On s’inspire ici de la question b pour démontrer le théorème suivant : E étant un ensemble quelconque, il n’existe aucune application surjective de E sur P(E). Supposons donc que f est une application de E dans P(E). Posons :

A′ = {x ∈ E / x ∉ f(x)}.

(i). — Vérifier que cette définition a bien un sens.

(ii). — Montrer qu’il n’existe aucun élément x de E tel que A′ = f(x). On raisonnera par l’absurde : si l’on avait A′ = f(x), aurait-on x ∈ A′ ou x ∉ A′?

(iii). — Conclure.

(iv). — Pourquoi, dans l’énoncé du théorème, a-t-on précisé que l’ensemble E était ”quelconque” ?