Boolean operators on sets

2.5. Families and Boolean operators on sets

Families

The notion of family is formally synonymous with that of function, but meant to play roles intuitively similar to those of tuples : while the domains of tuples are finite and made of symbols or numbers, those of families can be more general but still seen as intuitively "simple" sets, fixed in each context of use, and outside the "main studied system" containing the target set. A «family of...» is a family whose image is a «set of... » (included in the said notion).

Families use the formalism of functions disguised in the style of the symbols for tuples (themselves inapplicable due to their finiteness for infinite domains). The evaluator for a family u at i, instead of u(i), is written π_i(u) or u_i (looking like a meta-variable symbol of variable). The family definer on a term t is written (t(i))_i∈I or sometimes with ellipsis as (t(0),…,t(n−1)) abbreviating the n-tuple definer, instead of I ∋ i ↦ t(i). The argument i is called index, and the family is said indexed by its domain I. We may write u = (u_i)_i∈I as a shorthand for Fnc u ∧ Dom u = I.

When formalizing model theory in set theory, the "lists" of components forming the contents of theories are basically families. More precisely:

The list of abstract types is a set of urelements, serving as indexing set (i.e. domain) for the family of interpreted types
Both lists of predicate symbols and operator symbols, are families of tuples of abstract types
Of the list of axioms, only its image matters, which is a subset of the set of all statements.

Structures and binders

Seeing tuples as particular functions, explains that structures (unary structures on classes of tuples) are particular binders over terms (unary structures on classes of functions defined by these terms: 1.8).
Similarly, logical connectives are particular quantifiers. In particular, ∀ and ∃ respectively generalize the chains of conjunctions and of disjunctions:

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

The distributivity of connectives (1.6) also works for quantifiers as follows. For any unary predicate R definite on E and any Boolean 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)

Extensional definitions of sets

The operators of empty set ∅, singleton {a} and pairing {a,b} (2.2) are the first cases (those of arities 0,1,2) of operator symbols of exensional definition of sets (listing their elements) which amount to applying the Im functor to tuples :

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

The definition of V_n from 2.3 can be written {0,…,n−1}. Images of tuples are finite sets.
Similar notations are used for the binder also given by Im:

{T(x)| x∈E} = {T(x)}_x∈E = Im(E ∋ x ↦ T(x))

As this notation looks similar to the set builder, both may be combined into a third notation :

{T(x)| x∈E ∧ R(x)} = {T(x)| x∈{y∈E|R(y)}}

A function f is said constant when !: Im f. The constancy of a tuple is the chain of equalities:

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

Union of a family of sets

The binder of union of any family of sets (F = (F_i)_i∈I ∧ ∀i∈I, Set F_i), is defined from the previous functor of union of a set of sets (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

In return, the union of a set of sets is expressible from that of a family : ⋃ E = ⋃ Id_E because Im Id_E = E.

Other Boolean operators on sets

A binary predicate with domains a set I and a class C, can be seen in either curried way, as a meta-family (A_i)_i∈I of unary predicates definite in C, or as a family of Boolean variables (A_i(x))_i∈I depending on a common parameter x with range C. This way, any quantifier Q with range I (thus, for finite I, any connective) defines a meta-binder (resp. a meta-operation) on this meta-family (resp. this meta-tuple) of unary predicates (sub-classes of C), with result a unary predicate R, defined as

∀_Cx, R(x) ⇔ Qi, A_i(x).

When C is a set E, this defines a genuine binder (resp. operation) acting in the class of subsets of E. However, the result depends a priori not only on the given family of sets but also on the chosen set E. This parameter may be kept implicit as fixed in some contexts, but in others it needs to be explicitly added as argument.

The functor so defined by the negation connective (¬) is the complement ∁_E (with set parameter E) : ∁_E F is called the complement of F in E. It is synonymous with the following binary operator \ of difference between any two sets, except that ∁_E F is considered only definite if 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)

Let us analyze the issue of the dependence on E in the general case. Any family of sets F = (F_i)_i∈I is a family of subsets of its union U = ⋃_i∈I F_i and of any larger set E ⊃ U.

In any of these, the existential quantifier (Q = ∃) defines the union binder:

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

The binder defined by any Q gives a set X = {x∈E| R(x)} where R(x) abbreviates (Qi, x ∈ F_i). For this to define a binder (resp. operation) on the class of all sets, this X must be independent of the chosen E ⊃ U, and then it can be written

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

Noting that

∀x, x ∈ U ∨ (R(x) ⇔ Qi, 0)

the needed independence condition appears to be ¬Qi, 0 which also implies that X coincides with the class R.
The difference operator can be so defined by the connective (A∧¬B) which satisfies this condition ¬(0∧¬0):

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

Intersection

The quantifier ∀ defines the intersection of any family of subsets F_i of a fixed set E:

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

The condition of independence from E is that I ≠ ∅. As above defined, the intersection of the empty family gives E. The intersection of any non-empty family of sets (I ≠ ∅) can be written

∀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

Union and intersection have the same associativity and distributivity properties as ∧ and ∨ :

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)

Finally the connective ⇎ gives the symmetric difference: E ∆ F = (E∪F) \ (E∩F).

Set theory and Foundations of Mathematics
1. First foundations of mathematics
2. Set theory
2.1. Formalization of set theory 2.2. Set generation principle 2.3. Tuples 2.4. Uniqueness quantifiers ⇦ 2.5. Families, Boolean operators on sets ⇨ 2.6. Graphs 2.7. Products and powerset	2.8. Injections, bijections 2.9. Properties of binary relations 2.10. Axiom of choice
	Time in set theory Interpretation of classes Concepts of truth in mathematics
3. Algebra - 4. Arithmetic - 5. Second-order foundations

Other languages:
FR : 2.5. Familles, opérateurs booléens sur les ensembles