2.5. Familles, opérateurs booléens sur les ensembles

Familles

La notion de famille est formellement synonyme de celle de fonction, mais visant à jouer des rôles intuitivement similaires à ceux des uplets: alors que les domaines des uplets sont finis et faits de symboles ou de nombres, ceux des familles peuvent être plus généraux mais toujours vus comme des ensembles intuitivement "simples", fixes dans chaque contexte d'utilisation, et extérieurs au "système principal étudié" contenant l'ensemble d'arrivée. Une «famille de... » est une famille dont l'image est «un ensemble de... » (inclus dans la dite notion).

Les familles utilisent le formalisme des fonctions déguisé dans le style des symboles des uplets (eux-mêmes inapplicables par leur finitude pour des domaines infinis). L'évaluateur pour une famille u en i, au lieu de u(i), est noté πi(u), ou ui (tel un symbole méta-variable de variable). Le définisseur de famille sur un terme t, se note (t(i))iI ou parfois avec des points de suspension comme (t(0),…,t(n−1)) abrégeant le définisseur de n-uplet, au lieu de Iit(i). L'argument i est appelé indice, et la famille est dite indexée par son domaine I. On peut écrire u = (ui)iI comme raccourci pour Fnc u ∧ Dom u = I.

En formalisant la théorie des modèles en théorie des ensembles, les "listes" de composants formant le contenu des théories sont essentiellement des familles. Plus précisément:

Structures et symboles liants

Voyant les uplets comme fonctions (familles) particulières, les structures (structures unaires sur les classes d'uplets) apparaissent comme cas particuliers de symboles liant sur des termes (structures unaires sur des classes de fonctions définies par ces termes: 1.8).
De même, les connecteurs logiques sont des quantificateurs particuliers. Ainsi ∀ et ∃ généralisent respectivement les chaînes de ∧ et de ∨:

(B0∧…∧Bn−1) ⇔ (∀iVn, Bi)
(B0∨…∨Bn−1) ⇔ (∃iVn, Bi)

La distributivité des connecteurs (1.6) s'étend aux quantificateurs comme suit. Pour tout prédicat unaire R admissible sur E, et tout Booléen C,

(C ∧ ∃xE, R(x))  ⇔  (∃xE, CR(x))
(C ∨ ∀xE, R(x))  ⇔  (∀xE, CR(x))
(C ⇒ ∀xE, R(x))  ⇔  (∀xE, CR(x))
((∃xE, R(x)) ⇒ C)  ⇔  (∀xE, R(x) ⇒ C)
(∃xE, C) ⇔ (CE≠∅) ⇒ C ⇒ (CE=∅) ⇔ (∀xE, C)

Ecriture d'ensembles en extension

Les opérateurs d'ensemble vide ∅, singleton {a} et paire {a,b} 2.2) sont les premiers cas (ceux d'arité 0,1,2), d'opérateurs d'écriture en extension d'ensembles (qui énumèrent leurs éléments) revenant à appliquer le foncteur Im aux uplets :

{a,b,…} = Im(a,b,…).

La définition de Vn de 2.3 peut s'écrire {0,…,n−1}. Les images d'uplets sont des ensembles finis.
Des notations semblables s'utilisent pour le symbole liant aussi donné par Im:

{T(x)|xE} = {T(x)}xE = Im(ExT(x))

Cette notation ressemblant à celle du symbole de compréhension, on peut les combiner en une troisième notation :

{T(x)| xER(x)} = {T(x)| x∈{yE|R(y)}}

Une fonction f est dite constante lorsque !: Im f. La constance d'un uplet est la chaîne d'égalités:

x=y=z ⇔ !:{x,y,z} ⇔ ((x=y)∧(y=z)) ⇒ x=z

Union d'une famille d'ensembles

Le symbole liant d'union d'une famille d'ensembles (F = (Fi)iI ∧ ∀iI, Set Fi), se définit à l'aide du précédent foncteur d'union d'un ensemble d'ensembles (2.2):
F =
iI
Fi = {Fi}iI = Im F
x, x
iI
Fi ⇔ (∃X∈ Im F, xX) ⇔ ∃iI, xFi

XY = {X, Y}
x, xXY ⇔ (xXxY)
XYZ = {X, Y, Z} = (XY) ∪ Z
fnc f, Im f =
x∈ Dom f
{f(x)}
(x
iI
Fi, A(x)) ⇔ ∀iI, ∀xFi, A(x)
(x
iI
Fi, A(x)) ⇔ ∃iI, ∃xFi, A(x)
Set E,
iI
FiE ⇔ ∀iI, FiE

Autre operateurs booléens sur les ensembles

Un prédicat binaire de domaines un ensemble I et une classe C, peut être vu de chaque manière curryfiée, comme une méta-famille (Ai)iI de prédicats unaires admissibles dans C, ou comme une famille de variables booléennes (Ai(x))iI dépendant d'un paramètre commun x parcourant C. Ainsi, tout quantificateur Q de domaine I (donc, pour I fini, tout connecteur) définit un méta-liant (resp. une méta-opération) sur cette méta-famille (resp. ce méta-uplet) de prédicats unaires (sous-classes de C), de résultat un prédicat unaire R, défini par

C x, R(x) ⇔ Qi, Ai(x).

Lorsque C est un ensemble E, cela définit un véritable symbole liant (resp. une opération) opérant dans la classe des parties de E. Cependant, le résultat dépend a priori non seulement de la famille d'ensembles donnée mais aussi de l'ensemble E choisi. Ce paramètre peut être maintenu implicite comme fixé dans certains contextes, mais dans d'autres il doit être explicitement ajouté comme argument.

Le foncteur ainsi défini par le connecteur de négation (¬) est le complementaireE (de paramètre l'ensemble E) : ∁E F est appelé le complémentaire de F dans E. Il est synonyme de l'opérateur binaire \ de différence entre deux ensembles, sauf que ∁E F n'est considéré admissible que si FE :

Set E,F, E\F = {xE | xF}
Set E,F, FE ⇒ ∁E F = E\FE ∴ (∀xE, x ∈ ∁E F ⇔ ¬xF)

Analysons la question de la dépendance à E dans le cas général. Toute famille d'ensembles (Fi)iI est une famille de parties de leur union U=⋃iI Fi et de tout ensemble plus grand EU.

Dans chacun d'eux, le quantificateur existentiel (Q = ∃) définit le symbole liant d'union :

(∀iI, FiE) ⇒
iI
Fi = {xE| ∃iI, xFi}
Le symbole liant défini par tout Q donne un ensemble X = {xE| R(x)} où R(x) abrège (Qi, xFi). Pour que cela définisse un symbole liant (resp. une opération) sur la classe de tous les ensembles, ce X doit être indépendent de EU, et peut alors s'écrire

X = {xU| R(x)}.

Notant que

x, xU ∨ (R(x) ⇔ Qi, 0)

la condition d'indépendance voulue s'avère être ¬Qi, 0 ce qui implique également que X coïncide avec la classe R.
L'opérateur de différence peut ainsi se définir par le connecteur (A∧¬B) qui satisfait cette condition ¬(0∧¬0):

Set E,F, ∀x, x∈ E\F ⇔ (xExF).

Intersection

Le quantificateur ∀ définit l'intersection de toute famille de parties Fi d'un ensemble fixe E:


iI
Fi = {xE | ∀iI, xFi} = ∁E
iI
E Fi

La condition d'indépendance vis-à-vis de E est que I ≠ ∅. Comme défini ci-dessus, l'intersection de la famille vide donne E. L'intersection de toute famille non vide d'ensembles (I ≠ ∅) peut s'écrire

 ∀jI,
iI
Fi = {xFj | ∀iI, xFi}
x, x
iI
Fi ⇔ ∀iI, xFi
Set G, G
iI
Fi ⇔ ∀iI, GFi
Set E,F, EF = {xE | xF} = FE
x, xEF ⇔ (xExF)
EFEEF
E = EFFEF = EF

Deux ensembles E et F sont dits disjoints quand EF = ∅, ce qui équivaut à ∀xE, xF.
L'union et l'intersection ont les mêmes propriétés d'associativité et de distributivité que ∧ et ∨ :

EFG = (EF)⋂G = E⋂(FG) =(E,F,G)

E
iI
Fi =

iI
EFi E
iI
Fi =
iI
EFi
E⋂(FG) =  (EF)∪(EG) E∪(FG) =  (EF)⋂(EG)

Enfin le connecteur ⇎ donne la différence symétrique: EF = (EF) \ (EF).

Théorie des ensembles et fondements des mathématiques
1. Premiers fondements des mathématiques
2. Théorie des ensembles
2.1. Premiers axiomes de théorie des ensembles
2.2. Principe de génération des ensembles
2.3. Curryfication et uplets
2.4. Quantificateurs d'unicité
2.5. Familles, opérateurs booléens sur les ensembles
2.6. Graphes
2.7. Produits et ensembles des parties
2.8. Injections, bijections
2.9. Propriétés des relations binaires
2.10. Axiome du choix
Temps en théorie des ensembles
Interprétation des classes
Concepts de vérité en mathématiques
3. Algebra - 4. Arithmetic - 5. Second-order foundations
Other languages:
EN : 2.5. Families, Boolean operators on sets