Familles, opérateurs booléens sur les ensembles, union et intersection

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 u_i (tel un symbole méta-variable de variable). Le définisseur de famille sur un terme t, se note (t(i))_i∈I ou parfois avec des points de suspension comme (t(0),…,t(n−1)) abrégeant le définisseur de n-uplet, au lieu de I ∋ i ↦ t(i). L'argument i est appelé indice, et la famille est dite indexée par son domaine I. On peut écrire u = (u_i)_i∈I 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:

La liste des types abstraits est un ensemble d'urelements, servant d'ensemble indexant (domaine) pour la famille des types interprétés
Les deux listes de symboles de prédicat et de symboles d'opérateur sont des familles d'uplets de types abstraits
De la liste des axiomes, seule son image compte, qui est une partie de l'ensemble des énoncés.

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 ∨:

(B₀∧…∧B_n−1) ⇔ (∀i∈V_n, B_i)
(B₀∨…∨B_n−1) ⇔ (∃i∈V_n, B_i)

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 ∧ ∃x∈E, R(x)) ⇔ (∃x∈E, C ∧ R(x))
(C ∨ ∀x∈E, R(x)) ⇔ (∀x∈E, C ∨ R(x))
(C ⇒ ∀x∈E, R(x)) ⇔ (∀x∈E, C ⇒ R(x))
((∃x∈E, R(x)) ⇒ C) ⇔ (∀x∈E, R(x) ⇒ C)
(∃x∈E, C) ⇔ (C ∧ E≠∅) ⇒ C ⇒ (C ∨ E=∅) ⇔ (∀x∈E, 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 V_n 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)|x∈E} = {T(x)}_x∈E = Im(E∋x ↦ T(x))

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

{T(x)| x∈E ∧ R(x)} = {T(x)| x∈{y∈E|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 = (F_i)_i∈I ∧ ∀i∈I, Set F_i), se définit à l'aide du précédent foncteur d'union d'un ensemble d'ensembles (2.2):

⋃ F = ⋃
i∈I F_i = ⋃{F_i}_i∈I = ⋃ Im F
∀x, x ∈ ⋃
i∈I F_i ⇔ (∃X∈ Im F, x∈X) ⇔ ∃i∈I, x∈F_i

X ∪ Y = ⋃{X, Y}
∀x, x ∈ X∪Y ⇔ (x∈X ∨ x∈Y)
X ∪ Y ∪ Z = ⋃{X, Y, Z} = (X ∪ Y) ∪ Z

∀_fncf, Im f = ⋃
x∈ Dom f {f(x)}
(∀x∈⋃
i∈I F_i, A(x)) ⇔ ∀i∈I, ∀x∈F_i, A(x)
(∃x∈⋃
i∈I F_i, A(x)) ⇔ ∃i∈I, ∃x∈F_i, A(x)
∀_SetE, ⋃
i∈I F_i ⊂ E ⇔ ∀i∈I, F_i ⊂ E

Inversement, l'union d'un ensemble d'ensembles est exprimable par celle d'une famille : ⋃ E = ⋃ Id_E car Im Id_E = E.

Autres 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 (A_i)_i∈I de prédicats unaires admissibles dans C, ou comme une famille de variables booléennes (A_i(x))_i∈I 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

∀_Cx, R(x) ⇔ Qi, A_i(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 complementaire ∁_E (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 F⊂E :

∀_SetE,F, E\F = {x∈E | x ∉ F}
∀_SetE,F, F⊂E ⇒ ∁_E F = E\F ⊂ E ∴ (∀x∈E, x ∈ ∁_E F ⇔ ¬x∈F)

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

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

(∀i∈I, F_i ⊂ E) ⇒ ⋃
i∈I F_i = {x∈E| ∃i∈I, x∈F_i}

Le symbole liant défini par tout Q donne un ensemble X = {x∈E| R(x)} où R(x) abrège (Qi, x ∈ F_i). 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 E ⊃ U, et peut alors s'écrire

X = {x∈U| R(x)}.

Notant que

∀x, x ∈ U ∨ (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):

∀_SetE,F, ∀x, x∈ E\F ⇔ (x∈E ∧ x∉F).

Intersection

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

⋂
i∈I F_i = {x∈E | ∀i∈I, x ∈ F_i} = ∁_E ⋃
i∈I ∁_E F_i

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

∀j∈I, ⋂
i∈I F_i = {x∈F_j | ∀i∈I, x∈F_i}
∀x, x ∈ ⋂
i∈I F_i ⇔ ∀i∈I, x ∈ F_i
∀_SetG, G ⊂ ⋂
i∈I F_i ⇔ ∀i∈I, G ⊂ F_i
∀_SetE,F, E∩F = {x∈E | x∈F} = F∩E
∀x, x ∈ E∩F ⇔ (x∈E ∧ x∈F)
E∩F ⊂ E ⊂ E∪F
E = E∪F ⇔ F ⊂ E ⇔ F = E∩F

L'union et l'intersection ont les mêmes propriétés d'associativité et de distributivité que ∧ et ∨ :

E∩F∩G = (E∩F)∩G = E∩(F∩G) = ⋂(E,F,G)

E ∩	⋃ i∈I	F_i =	⋃ i∈I	E ∩ F_i	E ∪	⋂ i∈I	F_i =	⋂ i∈I	E ∪ F_i
E∩(F∪G) =			(E∩F)∪(E∩G)		E∪(F∩G) =			(E∪F)∩(E∪G)

Enfin le connecteur ⇎ donne la différence symétrique: E ∆ F = (E∪F) \ (E∩F).

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