Indexed Families of Sets

In topology, a topology on a space $X$ is, by definition, a family of subsets of $X$ closed under arbitrary unions indexed by any index set $I$ and finite intersections — the indexed-union axiom is precisely what distinguishes topology from mere finite Boolean combinatorics, and it is stated using exactly the $\bigcup_{i \in I}$ notation of this article. In measure theory and probability, $\sigma$-algebras are required to be closed under countably indexed unions $\bigcup_{n \in \mathbb N} A_n$, and the distinction between finite, countable, and arbitrary index sets (as flagged throughout this article) is the crux of why $\sigma$-algebras are more restrictive than topologies. In algebra, direct sums and direct products of a family of groups, rings, or modules $\{M_i\}_{i \in I}$ are defined directly via the indexed family, with the direct sum consisting of elements that are "almost all zero" — a condition that only makes sense once the family is indexed. In computer science, indexed families appear as dependent types / dependent products (a family of types indexed by a type, as in Martin-Löf type theory), and as the mathematical model behind indexed data structures such as arrays and hash tables keyed by an arbitrary index type. In cryptography, families of keyed functions or distributions indexed by a security parameter or key space are studied via exactly this apparatus, and indistinguishability arguments quantify over the index set of possible keys. In statistics, a parametric family of distributions $\{P_\theta\}_{\theta \in \Theta}$ is an indexed family in precisely this sense, with $\Theta$ the index (parameter) set, and questions about identifiability are questions about whether $\theta \mapsto P_\theta$ is injective.

:::quiz[In Example 2, why does $\bigcap_{n\in\mathbb N}\left(-\tfrac1n, 3+\tfrac1n\right) = [0,3]$ even though no single term of the family equals $[0,3]$?]

• Because the family is finite, so intersections always simplify
• Because every $A_n$ individually already equals $[0,3]$
• Because the intersection of infinitely many strictly larger open sets can equal a closed set not among them, by the Archimedean property ✓
• Because intersections of open intervals are always empty

Ask the tutor: How does the notion of an indexed family extend to define the Cartesian product $\prod_{i \in I} A_i$, and why does that construction require the Axiom of Choice to guarantee nonemptiness?

The key mental shift is: stop thinking of an indexed family as "a set of sets" and start thinking of it as a labeling scheme. A bare collection $\mathcal{F} = \{S : S \text{ is a set with property } P\}$ has no order and no repetition — it is a set, so $S \in \mathcal{F}$ either holds or does not, once and for all. An indexed family $\{A_i\}_{i \in I}$ is different: it is a function, and functions can send different inputs to the same output. So $\{A_i\}_{i\in I}$ remembers which index produced a set, even when two indices happen to produce the same set. This is exactly analogous to the difference between a sequence $(a_n)_{n \in \mathbb N}$ (which can repeat values, e.g. the constant sequence $a_n = 7$) and the set of values $\{a_n : n \in \mathbb N\}$ (which collapses repeats). Once you see a family as a function $A: I \to \mathcal U$, the definitions of $\bigcup_{i \in I} A_i$ and $\bigcap_{i\in I} A_i$ stop being new notation and become old friends in a bigger font: they are just $\exists$ and $\forall$ quantified over the domain of that function, exactly as $A \cup B$ and $A \cap B$ are the $I = \{1,2\}$ special case. This is the payoff of the definition — it is designed so that the two-set case, the finite $n$-set case, the countably infinite case, and the wildly uncountable case are all literally the same formula, differing only in what $I$ is. The picture below shows a finite family $\{A_1, A_2, A_3\}$ indexed by $I = \{1,2,3\}$, drawn as three overlapping disks, alongside a family indexed by an interval of the real line, $I = [0,3]$, where $A_t$ is an interval on a second number line whose endpoints move continuously as $t$ varies — illustrating that the index set need not be discrete or finite at all.

:::svg[Left: a finite family indexed by {1,2,3}; right: a continuously varying family indexed by the interval [0,3]]

Example 1 — an index set that is not a set of numbers at all. Let the index set be $I = \{\text{red}, \text{blue}, \text{green}\}$, a three-element set with no arithmetic structure, and define an indexed family of subsets of $\mathbb Z$ by

This is a legitimate indexed family exactly because the definition only demands a function $A : I \to \mathcal U$; there is no requirement that $I$ carry an order or that the family be given by a "formula in $i$." We compute the union and intersection directly from the definitions. Union. $x \in \bigcup_{i \in I} A_i$ iff $x \in A_{\text{red}}$ or $x \in A_{\text{blue}}$ or $x \in A_{\text{green}}$. Checking small integers: $0 \in A_{\text{red}}$ (multiple of 4) and also $\in A_{\text{green}}$; $1 \in A_{\text{blue}}$ ($1 \equiv 1 \bmod 3$) and $\in A_{\text{green}}$; $2 \in A_{\text{green}}$ but is it in $A_{\text{blue}}$? $2 \equiv 2 \bmod 3$, no, and $2$ is not a multiple of $4$, so $2$'s membership in the union comes solely from $A_{\text{green}}$. Meanwhile $6 \equiv 0 \bmod 3 \notin A_{\text{blue}}$, not a multiple of 4, not in $[-2,2]$, so $6 \notin \bigcup_i A_i$. In general

which cannot be simplified to a single congruence class because the three pieces genuinely overlap in a complicated pattern (e.g. $4 \mid n$ and $n\equiv 1 \pmod 3$ simultaneously exactly when $n \equiv 4 \pmod{12}$, by the Chinese Remainder Theorem, since $\gcd(4,3)=1$). Intersection. $x \in \bigcap_{i \in I} A_i$ requires $x$ to be a multiple of 4, and $x \equiv 1 \pmod 3$, and $-2 \le x \le 2$. The third condition restricts to $x \in \{-2,-1,0,1,2\}$; among these, multiples of 4 are only $x=0$; but $0 \equiv 0 \pmod 3 \ne 1$. So no integer satisfies all three simultaneously, giving

This example shows the machinery works verbatim when $I$ has no numerical or ordering structure whatsoever — the quantifiers $\exists i \in I$, $\forall i \in I$ range over an arbitrary three-element set of color-labels, and the proof of the Distributive and De Morgan Laws for Indexed Families theorem applies to this family exactly as stated.

Example 2 — a countably infinite family with a "collapsing" intersection, contrasted with a shifted version. For $n \in \mathbb N = \{1, 2, 3, \dots\}$ define, inside the universe $\mathcal U = \mathbb R$,

Note the family is not symmetric: the left endpoint tends to $0$ from below and the right endpoint tends to $3$ from above, at different rates relative to a fixed interval, and the interval is not centered at a nice point. Claim: $\bigcap_{n \in \mathbb N} A_n = [0,3]$. Proof. First, if $x \in [0,3]$, then for every $n \in \mathbb N$ we have $-\frac1n < 0 \le x \le 3 < 3 + \frac1n$, so $x \in A_n$; since this holds for all $n$, $x \in \bigcap_n A_n$. This shows $[0,3] \subseteq \bigcap_n A_n$. Conversely, suppose $x \in \bigcap_n A_n$, so $-\frac1n < x < 3+\frac1n$ for every $n \in \mathbb N$. If $x < 0$, then $-x > 0$, and by the Archimedean property of $\mathbb R$ there is $n \in \mathbb N$ with $\frac1n < -x$, i.e. $-\frac1n > x$, contradicting $-\frac1n < x$ for that particular $n$. So $x \ge 0$. Symmetrically, if $x > 3$, then $x - 3 > 0$, so there is $n$ with $\frac1n < x - 3$, giving $3 + \frac1n < x$, contradicting $x < 3+\frac1n$. So $x \le 3$. Hence $x \in [0,3]$, proving $\bigcap_n A_n \subseteq [0,3]$. Combining both inclusions, $\bigcap_{n\in\mathbb N} A_n = [0,3]$, even though no single term $A_n$ of the family equals $[0,3]$ — every $A_n$ is a strictly larger open interval. This is the sense in which indexed intersections over an infinite family can produce a set not equal to (and not equal to any) individual term of the family, a phenomenon impossible for a finite union or intersection of distinct named sets read off literally from the list. Union. By contrast, $\bigcup_{n \in \mathbb N} A_n = \left(-1,\, 4\right)$. Indeed $A_1 = (-1, 4)$ already, and $A_1 \subseteq A_n$ fails for larger $n$ in general — wait, check directly: since $\frac1n$ decreases as $n$ increases, $A_n = (-\frac1n, 3+\frac1n)$ shrinks as $n \to \infty$ (each $A_{n+1} \subsetneq A_n$, because $-\frac{1}{n+1} > -\frac1n$ and $3 + \frac{1}{n+1} < 3+\frac1n$). So the family is nested decreasing, $A_1 \supseteq A_2 \supseteq A_3 \supseteq \cdots$, which means the largest term is $A_1 = (-1,4)$ and the union of a decreasing chain equals its first (largest) term:

This second example foreshadows the general theory of nested families to be developed under Arbitrary Unions and Intersections, where monotone families of sets play a role directly analogous to monotone sequences of real numbers.