Mathématiques pour l’Informatique 2 2016–17                  http://www.lri.fr/~blsk/MathInfo2


Mathématiques pour l’Informatique 2

Thibaut Balabonski, d’après Christine Paulin
http://www.lri.fr/~blsk/MathInfo2

2  Théorie naive des ensembles

La théorie naive des ensembles formalise la notion de collection d’objets. Les ensembles eux-mêmes sont des objets que l’on peut organiser dans d’autres ensembles.

2.1  Constructions de base

Propriétés des ensembles.

Notations.

On écrira xA,P pour x, xAP et xA,P pour x, xAP.

Ensembles de base.

Exemple 1   L’ensemble des parties d’un ensemble X contient toujours l’ensemble vide et l’ensemble X lui-même.

Définition par compréhension.

Soit une formule P et un ensemble X, on peut définir par compréhension un nouvel ensemble {xX  | P} qui est le sous-ensemble de X des objets qui vérifient P. On a:

x ∈ {x ∈ X  | P} ⇔ x ∈ X ∧ P
Exemple 2   On suppose définie la relation usuelle d’ordre strict sur les entiers x<y. On définit l’ensemble [0,n[ comme {x ∈ ℕ  | x < n}

Le schéma de compréhension introduit une correspondance entre une formule logique P(x) portant sur une variable x désignant un objet dans l’ensemble A et le sous-ensemble de A des objets qui satisfont P.

Exemple 3 (Paradoxe de Russel)   Que se passe-t-il si on peut construire l’ensemble P suivant des ensembles qui n’appartiennent pas à eux mêmes. P  =def  {x  |  xx}.

Si P est un ensemble, on se pose la question: est-ce que PP? On remarque que PPPP, d’où une contradiction. On en déduit que P n’est pas un ensemble ou encore que l’ensemble de tous les ensembles n’existe pas (sinon le schéma de compréhension permettrait de définir P).

Intersection, union, différence.

Des opérations usuelles sur les ensembles sont l’union, l’intersection et la différence. Soient A et B deux ensembles, on peut construire les ensembles suivants:

Exercice 1   Montrer que si XA et XB alors XAB

Pour définir l’union de manière similaire, il faut identifier un ensemble W tel que A,BW et définir:
AB  =def  {xW  | xAxB}.

La théorie des ensembles comporte une règle spécifique qui garantit l’existence de W. C’est la règle de l’union qui est généralisée à une famille quelconque d’ensembles. Plus précisément, si on a un ensemble X qui est formé d’ensembles, alors il existe un ensemble X qui correspond à l’union de tous les ensembles YX. C’est-à-dire que :

x ∈ X ⇔ ∃ Y ∈ Xx ∈ Y

Dans le cas de l’union de deux ensembles A et B, on pose X={A,B } (définition par extension) on a YXY=AY=B. On pose AB  =def  ∪{A,B } et on vérifie que xAB ⇔ (xAxB).

Intersection.

Soit X un ensemble non vide d’ensembles. On définit l’intersection X de tous les éléments de X, c’est-à-dire que x appartient à X s’il appartient à tous les ensembles YX.

Comme X est non vide, il existe X0X et on définit X  =def  {xX0  | ∀ YX, xY}.

2.2  Relations

La notion de relation est importante en informatique en particulier pour modéliser des systèmes d’information, c’est-à-dire des ensembles d’objets qui ont des relations entre elles. De plus parmi les relations, nous distinguerons celles qui ont la propriété d’être des fonctions qui vont être utilisées pour représenter des transformations de données.

Définition 1 (Relation binaire)   Une relation binaire sur A× B est un sous-ensemble de A× B, c’est-à-dire un élément de ℘(A × B).
Exemple 4   On considère l’ensemble A des étudiants et l’ensemble B des cours ainsi qu’une relation suit entre étudiants et cours qui capture le fait qu’un étudiant suit un cours. Le même étudiant peut suivre plusieurs cours (éventuellement zéro). De même un cours peut être suivi par zéro ou plusieurs étudiants.

Le schéma de compréhension introduit une correspondance entre les formules logiques R(x,y) portant sur une variable x désignant un objet dans l’ensemble A et une variable y désignant un objet dans l’ensemble B et les sous-ensembles de A × B. La formule R(x,y) correspond à l’ensemble défini par compréhension {pA × B  | R(fst(p),snd(p))} que l’on notera aussi {(x,y) ∈ A × B  | R(x,y)}. Inversement, si R est une relation binaire, on pourra écrire R(x,y) la propriété (x,y) ∈ R.

Exemple 5   Soient R et S deux relations binaires sur A× B, on introduit les relations suivantes:
Exercice 2   Soit R la relation binaire sur les entiers xy.

Le domaine d’une relation est le sous-ensemble de A des objets qui ont un correspondant dans la relation et l’image d’une relation est le sous-ensemble de B des objets qui ont un correspondant dans la relation.

dom(R
def
=
 
  {x ∈ A  | ∃ y,R(x,y)}     img(R
def
=
 
  {y ∈ B  | ∃ x,R(x,y)}

2.3  Fonctions

Une fonction d’un ensemble A dans un ensemble B est une manière d’associer à un élément de A, un unique élément d’un ensemble B.

Les fonctions sont des cas particuliers de relations binaires, à savoir l’ensemble des couples (x,y), telle que la fonction f associe y à x. La relation est parfois appelée le graphe de la fonction.

On introduit l’ensemble des fonctions totales de A dans B comme un sous-ensemble des relations, celles qui sont fonctionnelles et totales.

Définition 2 (Ensemble AB des fonctions totales de A dans B)   L’ensemble AB des fonctions totales de A dans B (appelées aussi applications) est défini par compréhension:
A→ B  
def
=
 
  {f ∈ ℘(A × B)  | Fun(f)}

Notation fonctionnelle.

Une fonction totale f associe exactement un élément de B à chaque élément aA et on note cet élément f(a).

On peut définir une fonction à partir d’une expression e qui représente un objet dans l’ensemble B qui dépend d’une variable x dans l’ensemble A. On note fun  xe cette fonction.

fun  x ⇒ e 
def
=
 
  {(x,y) ∈ A × B  | y=e}

Soit f le nom donné à cette fonction on pourra aussi écrire f(x) =def  e.

Définition 3 (Fonction partielle)   Une relation fonctionnelle f qui n’est pas totale est appelée une fonction partielle. On utilise encore la notation f(a) lorsque a appartient au domaine de la fonction.
Exercice 3   Si A est l’ensemble vide, existe-t-il des fonctions dans AB. Même question si A est non vide mais B est vide.
Définition 4 (Restriction)   Si f est une application de AB et CA alors il existe une application fC de CB qui coincide avec f sur C. On dira que fC est la restriction de f à C.
Définition 5 (Application injective)   Une application fAB est injective si elle ne relie pas deux éléments différents au même résultat.
Inj(f)  
def
=
 
  ∀ x1 x2 ∈ Af(x1)=f(x2) ⇒ x1=x2
Définition 6 (Application surjective)   Une application fAB est surjective si tous les éléments de B sont accédés.
Surj(f)  
def
=
 
  ∀ y ∈ B, ∃ x ∈ Af(x)=y
Définition 7 (Application bijective)   Une application qui est injective et surjective est dite bijective. Elle met en correspondance exacte les objets de A et les objets de B.
Définition 8 (Application réciproque)   Soit f une application dans AB. Si f est bijective alors la relation réciproque f−1 est une application (dite application réciproque) et on a
∀ x∈ Af−1(f(x))=x      ∀ y ∈ Bf(f−1(y))=y
Exercice 4   On note n/2 la division entière.

Image d’un ensemble par une application.

Soit f une application dans AB et X un sous-ensemble de A. On note f(X), l’image de l’ensemble X par f l’ensemble des éléments de B qui peuvent être atteints par f à partir d’un élément de X.

f(X)={y ∈ B  | ∃ x ∈ Xf(x)=y}

On définit également l’image inverse d’un ensemble par une application. Si Y est un sous-ensemble de B, on note f−1(Y), l’image inverse de l’ensemble Y par f l’ensemble des éléments de A qui atteignent par f un élément de Y.

f−1(Y)={x ∈ A  | f(x)∈ Y}
Exercice 5  

Application à plusieurs arguments.

Une relation F(x1,…,xn,y) dans A1 × … × An× B est fonctionnelle si

∀ x1… xn y z,F(x1,…,xn,y) ⇒ F(x1,…,xn,z) ⇒ y=z

On notera F(x1,…,xn) l’unique y tel que F(x1,…,xn,y) lorsqu’il existe.

Une application à plusieurs arguments peut se voir comme une application à un seul argument qui est un n-uplet dans le produit cartésien A1 × … × An.

On notera A1 × … × AnB l’ensemble des applications à n arguments.

Exercice 6   On s’intéresse à une relation entre des entiers naturels et des booléens {V;F}
R 
def
=
 
 {(1,F);(2,V);(3,V);(4,F)}
  1. Cette relation définit-elle une fonction partielle ? une application ?
  2. Quelle est son domaine, son image ?
  3. Quelle est l’image par cette relation de l’ensemble {2;3} ?
  4. Quelle est l’image inverse par cette relation de l’ensemble {F} ?
  5. La relation est-elle injective ? surjective ? bijective ?

2.4  Ensemble fini

Définition 9 (Ensemble fini)   L’ensemble A est fini s’il existe un entier n∈ℕ et une application (fonction totale) injective f de A dans l’ensemble [0,n[.

Propriétés des ensembles finis.

Proposition 1    Preuve:
Proposition 2 (Lemme du tiroir)   Soit n, m ∈ ℕ, si n < m alors il n’existe pas d’application injective dans [0,m[→ [0,n[.

Preuve: La preuve est par récurrence sur n. On peut se ramener au cas où m=n+1 en effet s’il y a une application injective de [0,m[→ [0,n[ avec n+1≤ m alors par restriction il en existe aussi une de [0,n+1[→ [0,n[.

Définition 10 (Cardinal d’un ensemble fini)   Soit A un ensemble fini, il existe un unique entier n tel qu’il existe une bijection dans A → [0,n[. Cet entier est appelé le cardinal de l’ensemble A et est noté |A|.
Preuve: L’entier est unique car s’il existe une bijection f de A → [0,n[ et une bijection g de A → [0,m[ alors il existe une bijection fg−1 de [0,m[ → [0,n[, une bijection est injective donc le principe des tiroirs nous dit que mn. De même gf−1 est une application injective de [0,n[ → [0,m[, et donc nm et donc n=m.

Montrons l’existence de n. Comme A est fini, il existe une injection g de A → [0,m[. On va montrer par récurrence sur m que l’existence d’une injection g de A → [0,m[ implique l’existence de nm et d’une bijection f de A → [0,n[.

La notion de finitude et de cardinal est préservée par la relation pour deux ensembles d’être en bijection.

Proposition 3   Soient A et B deux ensembles tels qu’il existe une bijection de A dans B. Si A est fini alors B est fini et |A|=|B|.
Preuve: La preuve est immédiate par composition de la bijection de A dans [0,n[ et l’application réciproque de la bijection de A dans B.
Proposition 4   Preuve:
Exercice 7   Soient A et B deux ensembles finis tels que |A|=|B| et fAB. Montrer que les 2 propriétés suivantes sont équivalentes:
  1. f est injective
  2. f est bijective
Preuve: On suppose que f est injective donc f est bijective de A dans Img(f) donc |B|=|A|=|Img(f)| et Img(f) ⊆ B donc Img(f)=B et donc f est surjective et donc f est bijective.
Exercice 8   Soit A un ensemble de cardinal n et B un ensemble de cardinal m
Exercice 9   Jean a élaboré une fonction z de compression de données qui permet de traiter des suites finies de 0 et de 1.

2.5  Ensemble dénombrable

Définition 11 (Ensemble dénombrable)   L’ensemble A est dénombrable s’il existe une bijection de A → ℕ.

Si un ensemble est dénombrable, alors il est possible d’énumérer ses éléments, c’est-à-dire de construire une suite (un)n∈ ℕ qui parcourt l’ensemble des éléments de A en passant exactement une fois par chaque élément. Il suffit d’utiliser l’application réciproque d’une bijection de A→ ℕ.

Proposition 5   Un ensemble A est dénombrable si et seulement si il existe un ensemble B dénombrable et une application bijective dans AB.
Proposition 6   Preuve:
Proposition 7   L’ensemble ℘(ℕ) des parties de n’est pas dénombrable.
Preuve: La preuve utilise l’argument de la diagonale de Cantor. On suppose qu’il existe une application bijective f:℘(ℕ)→ ℕ et donc une application réciproque g:ℕ → ℘(ℕ) qui permet d’énumérer tous les ensembles de ℘(ℕ). On va construire un nouvel ensemble d’entiers qui ne pourra être aucun de ceux-là. On définit A  =def  {k ∈ ℕ  | kg(k)} et on pose n =def  f(A). On a alors
n ∈ A ⇔ n ∉g(n)⇔ n ∉g(f(A))⇔ n ∉A
d’où une contradiction.

Dans le cas des ensembles finis, un sous-ensemble strict d’un ensemble fini a un cardinal plus petit. Cela n’est pas le cas des ensembles infinis. Par exemple l’ensemble A des nombres pairs est en bijection avec l’ensemble des entiers. Il suffit de prendre l’application correspondant à la division par 2.

Cette propriété caractérise les ensembles infinis.

Définition 12 (Ensemble infini)   Un ensemble A est infini s’il existe un sous-ensemble B de A qui est différent de A et une application injective de AB.
Proposition 8   Tout sous-ensemble d’un ensemble dénombrable est fini ou dénombrable.
Preuve: Soit A un ensemble dénombrable et f une bijection dans A → ℕ. Soit B un sous-ensemble de A et f|B la restriction de f à B. On regarde l’image de f|B. C’est un sous-ensemble C de . Si cet ensemble est borné alors il existe n tel que xB, f(b)<n et donc f|B est une injection de B dans [0,n[. et donc B est fini. Dans le cas contraire, on sait que pour tout n∈ ℕ, il existe xB tel que nf(x). A chaque n on peut donc associer h(n) le plus petit k∈ ℕ tel que f−1(k) ∈ B. On peut alors énumérer les éléments de B par une fonction g. On pose g(0)=f−1(h(0)) et g(x+1)=f−1(h(g(x)+1)). Le fait que ces deux équations définissent bien une fonction sera justifié plus tard.
Proposition 9   L’union dénombrable d’ensembles dénombrables est dénombrable.
Preuve: On se donne un ensemble d’ensembles X. On suppose que cet ensemble est dénombrable, c’est-à-dire que l’on peut énumérer les éléments de X : X0,X1,…. De plus chaque ensemble Xi est dénombrable, soit fi la bijection associée. A chaque élément x∈ ∪X on associe le couple (i,fi(x)) avec i le plus petit entier tel que xXi. On vérifie que cette application est injective de X dans ℕ× ℕ. C’est donc une bijection de X dans un sous-ensemble de ℕ× ℕ. L’ensemble X est donc fini ou dénombrable. Comme cet ensemble contient X0 qui est infini dénombrable, on en déduit que X est dénombrable.
Exercice 10  
  1. Dire si les ensembles suivants sont dénombrables
    • ℕ×ℕ : dénombrable
    • ℕ→ℕ : non dénombrable, contient ℕ→ {0;1} qui est isomorphe à ℘(ℕ)
    • ℘(ℕ) : non dénombrable
    • : non dénombrable
    • L’ensemble des suites finies de {0;1} : dénombrable, union dénombrable d’ensembles finis
    • L’ensemble des suites infinies de {0;1} : non dénombrable, isomorphe à ℘(ℕ)
  2. Existe-t-il une partie X de différente de , telle que X est en bijection avec .

Ce document a été traduit de LATEX par HEVEA