2.5. Families and Boolean operators on sets


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 ui (looking like a meta-variable symbol of variable). The family definer on a term t is written (t(i))iI or sometimes with ellipsis as (t(0),…,t(n−1)) abbreviating the n-tuple definer, instead of Iit(i). The argument i is called index, and the family is said indexed by its domain I. We may write u = (ui)iI 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:

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:

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

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 ∧ ∃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)

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 Vn 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)| xE} = {T(x)}xE = Im(ExT(x))

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

{T(x)| xER(x)} = {T(x)| x∈{yE|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 = (Fi)iI ∧ ∀iI, Set Fi), is defined from the previous functor of union of a set of sets (2.2) :

F =
Fi = ⋃{Fi}iI = ⋃ Im F
x, x
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)}
Fi, A(x)) ⇔ ∀iI, ∀xFi, A(x)
Fi, A(x)) ⇔ ∃iI, ∃xFi, A(x)
Set E,
FiE ⇔ ∀iI, FiE
In return, the union of a set of sets is expressible from that of a family : ⋃ E = ⋃ IdE because Im IdE = 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 (Ai)iI of unary predicates definite in C, or as a family of Boolean variables (Ai(x))iI 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

C x, R(x) ⇔ Qi, Ai(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 complementE (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 FE :

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

Let us analyze the issue of the dependence on E in the general case. Any family of sets F = (Fi)iI is a family of subsets of its union U = ⋃iI Fi and of any larger set EU.

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

(∀iI, FiE) ⇒
Fi = {xE| ∃iI, xFi}
The binder defined by any Q gives a set X = {xE| R(x)} where R(x) abbreviates (Qi, xFi). For this to define a binder (resp. operation) on the class of all sets, this X must be independent of the chosen EU, and then it can be written

X = {xU| R(x)}.

Noting that

x, xU ∨ (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):

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


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

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

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

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

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

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

Fi =

Fi =
E∩(FG) =  (EF)∪(EG) E∪(FG) =  (EF)∩(EG)

Finally the connective ⇎ gives the symmetric difference: EF = (EF) \ (EF).

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