Complément sur la théorie des ensembles

Notation des opérations sur les ensembles

En mathématique, il est fréquent d'utiliser plusieurs notations différentes pour un même concept. A l'image du dicton chinois selon lequel il ne faut pas confondre le doigt qui pointe la lune avec la lune, il ne faut pas confondre une notation avec le concept qu'elle représente. Par exemple, en théorie des ensembles U-A, U\A et Ac, représentent le même concept de complément de A, qui dépend toujours de l'univers U.

Opérations sur une suite d'ensembles

Considérons un ensemble fini de n ensembles: X = { X1,X2,...,Xn }, on note ∪i=1,nXi, ou simplement ∪X, l'ensemble:

X1∪X2∪...∪Xn

On définit de la même manière ∩X.

Ces notations peuvent s'étendre naturellement au cas d'une suite infinie d'ensembles.

Partition d'un ensemble fini

Intuitivement, une partition est un découpage d'un ensemble en sous-ensembles couvrant tout l'ensemble, mais disjoints 2 à 2. De manière précise, on a:

Partition d'un ensemble fini
Soit A un ensemble fini et soit E ⊂ ℘(A). On dit que E est une partition de A si :
  1. A=∪E
  2. ∀ X ∈ E on a X≠∅
  3. ∀ X,Y ∈ E on a X∩Y=X ou X∩Y=∅

Paradoxe de Russell

Il s'agit d'un paradoxe simple de la théorie des ensembles, mis en lumière au début du 20 ième siècle par le mathématicien Russell. Il a stimulé les efforts de formalisation de la théorie des ensembles.

On dit qu'un ensemble est anormal si il est lui-même membre de l'ensemble, sinon il est dit normal. Par exemple, soit K l'ensemble de tous les carrés, puisque K n'est pas un carré, il est normal. Cependant, si on considère plutôt le complémentaire de K, Kc, de tous les ensembles qui ne sont pas des carrés. Or, Kc étant un ensemble qui n'est pas un carré, il est dans lui-même... donc anormal.

Considérons maintenant l'ensemble N de tous les ensembles normaux. Puisque N ne contient que des ensembles normaux, il ne contient pas N lui-même, ce qui implique que N est anormal, ce qui est contradictoire car dans ce cas il contiendrait N lui-même ce qui est faux par hypothèse.

La racine de ce paradoxe est l'axiome de spécification: toute propriété P peut-être utilisée pour définir un ensemble via E = { x | P(x) }. Afin d'éliminer le paradoxe, l'approche retenue en théorie des ensembles est de restreindre cet axiome. Une façon de le faire a été proposée par les mathématiciens Zermelo et Freankel via l'axiome de régularité. Celui-ci impose qu'un ensemble ne peut pas se contenir lui-même, i.e. E ∉ E. Ceci induit une hiéarchie des ensembles: les atomes sont les éléments qui ne sont pas des ensembles, les ensembles de premier niveau contiennent des atomes, les ensembles de second niveau des ensembles, etc.

Cardinalité

Définitions:

Cardinalité d'un ensemble fini
c'est le nombre d'éléments de l'ensemble.
Cardinalité égale
2 ensembles ont la même cardinalité si il existe une correspondance 1-1 (i.e. une fonction bijective) entre leurs éléments respectifs.
Ensemble infini
un ensemble est infini si il a la même cardinalité qu'un de ses sous-ensembles propres.
Ensemble infini dénombrable
un ensemble est infini mais dénombrable si il est de même cardinalité que l'ensemble des entiers.

Théorèmes 1: L'ensemble des nombres rationels est infini dénombrable. En effet, les rationels sont de la forme i/j où i et j sont des entiers. Si on traite i et j comme les indices de ligne et de colonne d'une matrice, chacun des nombres rationels est une entrée de la matrice. La correspondance avec les entiers est alors obtenue en balayant diagonalement la matrice:

Théorèmes 2: L'ensemble des nombres réels est infini non-dénombrable. Preuve: voir le document sur l'argument de la diagonale de Cantor.

Définition récursive d'un ensemble

En mathématique, on travaille souvent avec des ensembles infinis. Dans le cas des nombres entiers on utilise { 0, 1, 2, 3, ... } pour caractériser ses éléments. Ceci fonctionne bien parce que nous sommes habitué à cette séquence. Si on considère l'ensemble infini { 4, 10, 22, 46, ... }, il est beaucoup plus difficile de construire le reste de l'ensemble.

Une définition récursive d'un ensemble donne une méthode pour construire ses éléments. Elle est toujours composé d'un ensemble d'éléments explicites, la base, et d'un algorithme pour générer les autres éléments de l'ensemble. Le plus souvent, l'algorithme contient une formule récursive, i.e. définissant les prochains éléments en fonction des précédents, et une règle de fermeture.

Par exemple, si on appelle s(n) la fonction successeur d'un entier, définie par la règle s(n)=n+1, on peut donner une définition récursive de l'ensemble des entiers naturels:

  1. base: 0 ∈ ℕ
  2. règle récursive: si n ∈ ℕ, alors s(n) ∈ ℕ
  3. fermeture: n ∈ ℕ seulement si n peut être obtenu par un nombre fini d'application de la règle récursive à la base, i.e. 0

Un autre exemple est la suite des nombres de Fibonaci { 1, 2, 3, 5, 8, ... }, on peut en donner une définition récursive via:

  1. base: 1, 2 sont les 2 premiers nombres de Fibonaci, respectivement noté f1 et f2
  2. règle récursive: pour n>2, fn=fn-1+fn-2
  3. fermeture: un entier n est un nombre de Fibonaci seulement si n peut être obtenu par un nombre fini d'application de la règle récursive à la base

La récursivité joue un rôle important en mathématique et en informatique. Elle permet non seulement de définir rigoureusement des ensembles infinis, mais aussi nous donne un mécanisme pour définir des opérations sur des ensembles infinie. En outre, on l'utilise comme stratégie de d'inférence, ce que l'on appel "preuve par induction".