Définitions

Formellement, en mathématiques on définit un ensemble de 2 manières différentes :

- en extension, c.a.d. en indiquant tous les éléments, séparés par des virgules, entre 2 accolades ; par exemple :

B = {Pierre, Jacques, Rémi, André} signifie "soit B l'ensemble des prénoms des garçons"

ℕ = {0, 1, 2, …, n, …} signifie "soit N l'ensemble des nombres entiers positifs ou nuls"

- en compréhension, c.a.d. en indiquant un élément générique (x, y, z …) et la caractéristique commune des éléments de l'ensemble. ; par exemple : ℕ = {x| x est un entier positif ou nul}

On peut définir un ensemble d'ensembles, i.e un ensemble dont les éléments sont des ensembles qui partagent une même caractéristique.

En mathématiques, on indique l'appartenance d'un élément x à un ensemble par le symbole ∈. Ainsi, 2 ∈ ℕ, se lit 2 appartient à l'ensemble ℕ, ou 2 est un élément de ℕ. Et -1 n'appartient pas à l'ensemble ℕ.

Le cardinal d'un ensemble A – noté Card.A ou |A| – est le nombre d'éléments de cet ensemble. L'ensemble vide -- noté ∅ – est un ensemble qui ne contient aucun élément. (Card.A = 0).

L'ensemble qui ne contient qu'un élément est dénommé « singleton ». Attention : {a} diffère de a, car une boîte qui contient l'élément a ne peut pas être l'élément a.

Equipotence de 2 ensembles

Deux ensembles A et B sont équipotents s'ils ont une même cardinalité (même nombre d'éléments quand ils sont finis) et s'il existe un moyen d'associer à chaque élément de A un et un seul élément de B et inversement. On écrit A == B si Card.A = Card. B et si A = {a, b} et B = {a, b}.

On peut ainsi démontrer que l'ensemble N des entiers naturels a la même cardinalité que l'ensemble Q des nombres rationnels, bien que N soit un sous-ensemble propre de Q . Ces deux ensembles sont dits infinis dénombrables. D'un autre côté, l'ensemble R des nombres réels n'a pas la même cardinalité que N ou Q, mais une cardinalité supérieure que l'on appelle la puissance du continu. Cantor a donné deux preuves que R n'est pas dénombrable.

Inclusion de 2 ensembles

Un ensemble E est inclus dans l'ensemble F si chaque élément de E appartient à F. Ce qui s'écrit : E ⊂ F. Exemple : si E = {a,b,f,g} et F = {a,b c,d,e,f,g,h,i,j,k,l,m,n,o} alors E ⊂ F.

Complément d'un ensemble

L'ensemble G complément de l'ensemble E dans F comprend tous les élément de F – dénommé alors référentiel – qui ne sont pas dans E. Exemple : si E = {a,b,f,g} et F = {a,b c,d,e,f,g,h,i,j,k,l,m,n,o} alors G = {c,d,e,,h,i,j,k,l,m,n,o}. On dit que E et G réalisent une partition de F. On écrit G = C_F E.

Intersection de 2 ensembles

Dans F={a,b c,d,e,f,g,h,i,j,k,l,m,n,o}, l'intersection d'un ensemble E={a,b,f,g} et d'un ensemble H={b,c,d} est l'ensemble I={b} qui comprend tous les éléments communs à E et H.On écrit I=E∩H.

Lorsque l'intersection de 2 ensembles disjoints est vide.

L''intersection est commutative, i.e indifférente à l'ordre des ensembles : E∩H = H∩E .

Réunion de 2 ensembles

Dans F={a,b c,d,e,f,g,h,i,j,k,l,m,n,o}, la réunion d'un ensemble E = {a,b,c } et d'un ensemble H={b,c,d} est l'ensemble J = {a,b,c,d} qui comprend tous les éléments de E et H.On écrit J = E∪H.

La réunion est commutative, i.e indifférente à l'ordre des ensembles : E∪H = H∪E.

La réunion est associative, i.e indifférente à l'ordre des ensembles : (E∪H)∪K = E∪(H∪K).

Les éléments communs à un ensemble E= {a,b,c } et à son intersection I = {b,c} avec l'ensemble H={b,c,d} appartiennent à la réunion J des 2 ensembles E et I : E∩H ⊂ E∪H..

La réunion est distributive par rapport à l'intersection, i.e. indifférente à l'ordre des opérations :

E∩(H∪K) = (E∩H) ∪(E∩K).

Lois de Morgan

C_E (F∪H) = C_E F∩C_E H

C_E (F∩H) = C_E F∪C_E H

Card (F∪H) = Card F + Card H - Card (F∩H)

Indiscernabilité de 2 ensembles

Soit un ensemble d'objets U = {… , x, y, … .}, dans lequel chaque objet est décrit par un ensemble fini d'attributs A {a,b,c,d}, dont la valeur est un nombre entier appartenant à l'ensemble fini C qui représentent le numéro d'ordre de la classe de valeur à laquelle appartient la valeur des attributs.

Soit X un sous-ensemble d'éléments de U (X ⊆ U). Lorsque deux objets x, y ∊ X sont décrits par un ensemble d’attributs de même valeur (ex :B= {a,b}), ces deux objets sont qualifiés d’indiscernables du point de vue B. La relation d’indiscernabilité entre x et y s’écrit IND(B) = (x,y)∊U2 |a(x) = a(y) | ∀a∊B.

Réduction d'un ensemble

L’attribut c ∊ B est qualifié d'indispensable dans B si IND( B - { c }) # IND(B). Sinon l'attribut c est qualifié de superflu dans B. Lorsque tous les attributs c ∊ B-B1 sont superflus et IND(B1) = IND(B), l’ensemble d’attributs B1 ∊ B constitue une réduction de l’ensemble B. L’ensemble des réductions possibles de B { RED(B) } est déterminé par la fonction de discernabilité de B.

Ensembles approximatifs

Les ensembles d'objets indiscernables peuvent constituer des « granules de connaissances élémentaires » sur les relations qui existent entre les valeurs de d et les valeurs des attributs a,b et c , à partir desquelles on peut construire des connaissances plus ou moins précises sur ces relations. L’union de tous les objets B-C ⊆ U que l’ensemble d’attributs B ∊ A permet d’affecter avec certitude à un ensemble C { B-C = ⋃ (E ∊ U | IND(B) | E ⊆ X } constitue la plus faible approximation de la valeur C de l'attribut d du point de vue B.

En revanche, l’union de tous les ensembles élémentaires qui ont une intersection non vide avec l'ensemble d’objets C -- i.e. les objets que certains attributs seulement de l’ensemble B permettent d’affecter à la classe C {B+C = ∪ (E ∊ U | IND(B) | E ∩ X # Ø } -- constitue la plus forte approximation de la valeur C de de l'attribut d du point de vue B. Ces ensembles d’objets sont qualifiés d’ensembles approximatifs en raison du caractère plus vague des connaissances qu’ils représentent.

Régions limites d'un ensemble

L’ensemble complémentaire de l’espace de plus faible approximation de la valeur C de l'attribut d dans l’espace de plus forte approximation de C { BNC = B+C - B-C } est appelé « région limite des connaissances sur la classe de valeur C de l'attribut d ». Il rassemble les objets qui ne peuvent être affectés avec certitude, ni dans la classe C, ni dans cette classe du point de vue B.

L’ensemble complémentaire de l’espace de plus forte approximation de la valeur C de l'attribut d dans l’ensemble des objets U est appelé « région hors de la valeur C de l'attribut d ». Il rassemble les objets qui peuvent être affectés avec certitude hors de la classe X, du point de vue B.

Exemple : Soient :

un ensemble de personnes OBJ = {Joe,Mary,Peter,Paul,Cathy},

un ensemble d'attributs AT = {HighSchool,Elementary,University,Doctorate},

un ensemble de valeurs VAL = {No,Yes},

et une fonction f: OBJ * AT -> VAL, qui définit la valeur de l'attribut « perspectives » de chaque personne

(cf. tableau ci-dessous).

OBJ (pers) |AT (Education) |VAL (Perspectives)
--------------------------------------------------------------
Joe | High School | No
Mary | High School | Yes
Peter | Elementary | No
Paul | University | Yes
Cathy | Doctorate | Yes

On peut définir 4 sous ensembles A de AT tels que o1 R(Ai) o2 <=> f(o1,a) = f(o2, a) quelque soit a dans Ai

A1={Joe, Mary},

A2={Peter},

A3={Paul},

A4={Cathy}

Notons que Joe et Mary sont indiscernables du point de vue de A={High School}.

On peut donc utiliser cette relation pour partager l'univers en 4 classes d'équivalence

R(A)* = {{Joe, Mary}, {Peter}, {Paul}, {Cathy}}

qui sont des sous ensembles de AT tel que o1 R(A) o2 <=> f(o1,a) = f(o2, a) quelque soit a dans Ai

La paire (OBJ, R) forme un espace d'approximation avec lequel on peut approximer arbitrairement les sous ensembles de OBJ référés comme suits :

L'ensemble de plus faible approximation de VAL – i.e. cas positifs – est :

LOWER(O) = POS(O) = Union_{e_i subset O} e_i = {Paul, Cathy}
L'ensemble de plus forte approximation est :
UPPER(O) = Union_{e_i \interset O \not= empty} e_i = POS(O) + BND(O) = {Paul, Cathy, Joe, Mary}
L'ensemble de cas négatifs est :

NEG(O) = OBJ – POS(O) = {Peter}
L'ensemble des cas limites est :
BND(O) = UPPER(O) - LOWER(O) = {Joe, Mary}

On peut donc écrire 3 règles de décision:
des(POS(O)) --> Yes
des(NEG(O)) --> No
des(BND(O)) ~~> Yes ou No
Soit:
(Education, University) or (Education, Doctorate) --> Bonnes perspectives
(Education, Elementary) --> Pas de bonnes perspectives
(Education, High School) ~~> Possibles bonnes perspectives

Un ensemble approximatif est un ensemble O, tel que BND(O) est non vide. Un ensemble approximatif est donc uniquement définit par son approximation la plus faible et la plus forte. Un ensemble donc la région limite est vide est exactement défini, il n'est pas approximatif.

Si un ensemble d'attributs A est suffisant pour créer une partition R(A)* qui définit l'ensemble O, alors A est une réduction de AT. L'intersection de toutes les réductions sont appelées le core.