Sets, families and intersections

This unit gives you the language for one move that appears all over mathematics for AI: defining the smallest set with some property that contains a given set $S$, as the intersection of all such sets. Linear algebra uses it for the span, optimisation for the convex hull, probability for the events generated by a random variable. Learn it once here.

Needs: nothing. Used by: LA1 Vector spaces, LA2 Span.

Full explanationWhy set theory, in a course about AI?

Most introductions define the span of vectors $v_1, \dots, v_n$ as “all vectors of the form $a_1 v_1 + \dots + a_n v_n$”. That works while you have finitely many vectors. Now take infinitely many, say the functions $1, x, x^2, x^3, \dots$. What is “all combinations” of those? Is $1 + x + x^2/2 + x^3/6 + \cdots$ one of them? A vector space only tells you how to add two vectors, so an infinite sum has no meaning there, and the finite-list definition has nothing to say.

There is a cleaner definition that never mentions sums at all: the span of $S$ is the intersection of every subspace that contains $S$. To read it you need to know what “the intersection of a family of sets” means, including the edge cases (what if the family is empty?). That is what this unit covers, and nothing more. We use naive set theory in the sense of Halmos: sets are collections, and we stay away from the corners where that intuition breaks.

Sets and membership

Definition F1.1Set, element#

A set is a collection of objects, its elements. We write $x \in A$ for ”$x$ is an element of $A$” and $x \notin A$ otherwise. Two sets are equal exactly when they have the same elements.

So $\{1, 2, 2\} = \{2, 1\}$: order and repetition do not matter, only membership. Sets can contain sets: $\{\varnothing\}$ is a set with one element, which happens to be the empty set.

Definition F1.2Subset#

$A$ is a subset of $B$, written $A \subseteq B$, if every element of $A$ is an element of $B$.

Theorem F1.3Equality by double inclusion#

$A = B$ if and only if $A \subseteq B$ and $B \subseteq A$.

This is how almost every “these two sets are the same” proof goes, including the main theorem of LA2: show each set sits inside the other.

Definition F1.4Empty set, set-builder notation#

The empty set $\varnothing$ is the set with no elements. For a set $A$ and a property $P$, the set $\{x \in A : P(x)\}$ contains exactly the elements of $A$ that have property $P$.

Theorem F1.5The empty set is a subset of everything#

For every set $A$, $\varnothing \subseteq A$.

Proofof F1.5

We must show: every element of $\varnothing$ is an element of $A$. There are no elements of $\varnothing$, so there is nothing to check, and the statement is true. A claim of the form “every element of an empty collection has property $P$” is called vacuously true.

Full explanationVacuous truth, and why set-builder notation always says “x ∈ A”

Vacuous truth feels like a trick, but it is forced on us. “Every element of $\varnothing$ is in $A$” can only be false if some element of $\varnothing$ is not in $A$, and there is no element to be the counterexample. Hold on to this: in the next section, the same reasoning makes the intersection of an empty family behave strangely.

Notice also that set-builder notation selects elements from an existing set $A$. The unrestricted version $\{x : P(x)\}$ is not allowed, because some properties define something that cannot be a set. Russell’s example is $\{x : x \notin x\}$, the collection of all sets that are not members of themselves. Ask whether it is a member of itself: if it is, it isn’t; if it isn’t, it is. Selecting from a set you already have avoids that. It matters to us for one reason only: “the set of everything” is not a set. If some set $U$ contained everything, then $\{x \in U : x \notin x\}$ would be a legal selection from $U$, and it would be Russell’s paradoxical collection. So no such $U$ exists.

Convention F1.6Number sets used on this site#

$\mathbb{N} = \{0, 1, 2, \dots\}$, $\mathbb{Z}$ the integers, $\mathbb{Q}$ the rationals, $\mathbb{R}$ the reals, $\mathbb{C}$ the complex numbers. "$:=$" means “is defined as”.

Check Is ∅ an element of {∅}? Is ∅ a subset of {∅}? Is {∅} equal to ∅?

Yes, $\varnothing \in \{\varnothing\}$: it is the one element listed. Yes, $\varnothing \subseteq \{\varnothing\}$, as it is a subset of every set (F1.5). No, $\{\varnothing\} \neq \varnothing$: the left side has one element, the right side none.

Combining two sets

Definition F1.7Union, intersection, difference#

$A \cup B := \{x : x \in A \text{ or } x \in B\}$, $\quad A \cap B := \{x \in A : x \in B\}$, $\quad A \setminus B := \{x \in A : x \notin B\}$.

Intersections and differences are selections from $A$, as F1.4 requires. Unions are not carved out of an existing set: that $A \cup B$ exists is a separate basic principle of set theory (the axiom of union), which we take for granted.

Definition F1.8Cartesian product#

$A \times B$ is the set of ordered pairs $(a, b)$ with $a \in A$ and $b \in B$, where $(a, b) = (a', b')$ exactly when $a = a'$ and $b = b'$. More generally $A^n = A \times \cdots \times A$ is the set of ordered $n$-tuples.

Unlike sets, pairs care about order: $(1, 2) \neq (2, 1)$. You need products for two reasons. $\mathbb{R}^n$ is literally the set of $n$-tuples of reals. And the operations of a vector space are functions of two inputs: addition takes a pair of vectors, $V \times V \to V$ (LA1.3).

Functions and support

Definition F1.9Function#

A function $f : A \to B$ assigns to every $a \in A$ exactly one element $f(a) \in B$. $A$ is the domain, $B$ the codomain. The set of all functions from $A$ to $B$ is written $B^A$.

Full explanationA vector is a function

The notation $B^A$ is not a coincidence. A vector $x = (x_1, \dots, x_n) \in \mathbb{R}^n$ is exactly a function from the index set $\{1, \dots, n\}$ to $\mathbb{R}$: index $i$ goes to $x_i$. So $\mathbb{R}^n$ and $\mathbb{R}^{\{1, \dots, n\}}$ are the same thing written two ways.

Push the idea and many objects line up:

Object	Index set $X$	As a function $X \to \mathbb{R}$
vector in $\mathbb{R}^n$	$\{1, \dots, n\}$	$i \mapsto x_i$
$m \times n$ matrix	$\{1, \dots, m\} \times \{1, \dots, n\}$	$(i, j) \mapsto a_{ij}$
greyscale image, $H \times W$ pixels	pixel grid	pixel $\mapsto$ intensity
infinite sequence	$\mathbb{N}$	$k \mapsto x_k$
real function	$\mathbb{R}$	$t \mapsto f(t)$

In LA1 this turns into one theorem: all of these are vector spaces for the same reason.

Definition F1.10Support, finitely supported#

For a function $c : A \to \mathbb{R}$ (or into any number system with a zero), its support is $\operatorname{supp} c := \{a \in A : c(a) \neq 0\}$. The function is finitely supported if its support is a finite set.

A finitely supported function can live on an enormous, even uncountable, domain, yet be non-zero in only finitely many places. That is exactly the bookkeeping needed for linear combinations of infinitely many vectors (LA2.2).

Where this shows up in AI

Sparse vectors are finitely supported functions in practice: a bag-of-words document over a 50,000-word vocabulary has non-zero counts for a few hundred words, and sparse storage keeps only the support. Tensors are functions on product index sets, which is why a batch of RGB images has a shape like $B \times H \times W \times 3$: the index set is a Cartesian product.

Families of sets

Definition F1.11Family of sets#

A family of sets is a set whose elements are themselves sets. We write families with script letters, $\mathcal{A}$. An indexed family $(A_i)_{i \in I}$ assigns a set $A_i$ to each index $i$ in an index set $I$.

Definition F1.12Union and intersection of a family#

For a family $\mathcal{A}$,

$$\bigcup \mathcal{A} := \{x : x \in A \text{ for some } A \in \mathcal{A}\}, \qquad \bigcap \mathcal{A} := \{x : x \in A \text{ for every } A \in \mathcal{A}\}.$$

The intersection is only defined when $\mathcal{A}$ is non-empty. For an indexed family, $\bigcup_{i \in I} A_i$ and $\bigcap_{i \in I} A_i$ mean the same with $A$ ranging over the $A_i$; the intersection requires $I \neq \varnothing$.

Full explanationWhy the intersection needs a non-empty family

Try $\mathcal{A} = \varnothing$. Which $x$ satisfy ”$x \in A$ for every $A \in \mathcal{A}$”? There is no $A$ to check, so the condition is vacuously true for every object whatsoever. The empty intersection would be “the set of everything”, which we saw is not a set. Halmos puts it bluntly: an empty intersection does not make sense.

The non-empty case is safe. Pick any $A_0 \in \mathcal{A}$; every element of the intersection is in particular in $A_0$, so

$$\bigcap \mathcal{A} = \{x \in A_0 : x \in A \text{ for every } A \in \mathcal{A}\},$$

an honest set-builder selection from the existing set $A_0$. The answer does not depend on which $A_0$ you pick.

When all sets in a family are subsets of one fixed ambient set $X$, some books define the empty intersection to be $X$ itself. That is a convention, and you will rarely need it here: every intersection we take, like “all subspaces of $V$ that contain $S$”, has at least one member ($V$ itself), so it is never empty.

Example F1.13Infinite intersections can be surprising#

For $n = 1, 2, 3, \dots$ let $A_n = [-\tfrac{1}{n}, \tfrac{1}{n}]$ and $B_n = (0, \tfrac{1}{n})$. Then

$$\bigcap_{n \ge 1} A_n = \{0\}, \qquad \bigcap_{n \ge 1} B_n = \varnothing, \qquad \bigcup_{n \ge 1} A_n = [-1, 1].$$

Every $B_n$ is non-empty, and each contains the next, yet nothing lies in all of them. If $x \le 0$, then $x \notin B_1$. If $x > 0$, some $\tfrac{1}{n}$ is smaller than $x$ (the Archimedean property of the reals), so $x \notin B_n$.

Theorem F1.14The intersection is the largest common subset#

Let $\mathcal{A}$ be a non-empty family.

1. $\bigcap \mathcal{A} \subseteq A$ for every $A \in \mathcal{A}$.
2. If a set $C$ satisfies $C \subseteq A$ for every $A \in \mathcal{A}$, then $C \subseteq \bigcap \mathcal{A}$.

Proofof F1.14

(1) Take $x \in \bigcap \mathcal{A}$. By definition $x$ is in every member of $\mathcal{A}$, in particular in $A$.

(2) Take $x \in C$. For each $A \in \mathcal{A}$ we have $C \subseteq A$, so $x \in A$. Hence $x$ is in every member of $\mathcal{A}$, which means $x \in \bigcap \mathcal{A}$.

The smallest set containing S

This is the payoff of the unit. Suppose you have a kind of “nice” subset (subspaces, convex sets, closed sets) and a set $S$ that is not nice. Is there a smallest nice set containing $S$?

Theorem F1.15Closure under intersection gives a smallest member#

Let $X$ be a set and $\mathcal{C}$ a family of subsets of $X$ such that

• $X \in \mathcal{C}$, and
• the intersection of every non-empty subfamily of $\mathcal{C}$ belongs to $\mathcal{C}$.

For $S \subseteq X$ define $\langle S \rangle := \bigcap \{C \in \mathcal{C} : S \subseteq C\}$. Then $\langle S \rangle \in \mathcal{C}$, $S \subseteq \langle S \rangle$, and $\langle S \rangle \subseteq C$ for every $C \in \mathcal{C}$ with $S \subseteq C$. In words: $\langle S \rangle$ is the smallest member of $\mathcal{C}$ containing $S$.

Proofof F1.15

Let $\mathcal{F} = \{C \in \mathcal{C} : S \subseteq C\}$. It is non-empty, because $X \in \mathcal{C}$ and $S \subseteq X$, so the intersection is defined.

• $\mathcal{F}$ is a non-empty subfamily of $\mathcal{C}$, so by assumption $\langle S \rangle = \bigcap \mathcal{F} \in \mathcal{C}$.
• Every member of $\mathcal{F}$ contains $S$, so F1.14(2), applied to the set $S$, gives $S \subseteq \langle S \rangle$.
• If $C \in \mathcal{C}$ and $S \subseteq C$, then $C \in \mathcal{F}$, and F1.14(1) gives $\langle S \rangle \subseteq C$.

Full explanationWhat “smallest” means, and why the two conditions matter

“Smallest” means smallest for $\subseteq$: contained in every competitor. That is stronger than “has the fewest elements” and it need not exist. Take $X = \{1, 2, 3\}$ and let $\mathcal{C}$ be the subsets with exactly two elements. For $S = \{1\}$, both $\{1, 2\}$ and $\{1, 3\}$ contain $S$, but neither is inside the other, and their intersection $\{1\}$ is not in $\mathcal{C}$. No smallest member exists, because $\mathcal{C}$ is not closed under intersection.

The condition $X \in \mathcal{C}$ is what keeps the family $\mathcal{F}$ non-empty. Without it, there may be no member containing $S$ at all.

The same theorem, with different families $\mathcal{C}$, produces many objects you will meet:

Family $\mathcal{C}$	$\langle S \rangle$ is called	Used in
subspaces of a vector space	the span of $S$	linear algebra, everywhere
convex subsets of $\mathbb{R}^n$	the convex hull	optimisation, attention outputs
closed subsets of $\mathbb{R}^n$	the closure	limits, approximation
σ-algebras on a set	the generated σ-algebra	probability: the events you can observe

Each one needs its own check of both conditions: $\mathcal{C}$ is closed under non-empty intersections and contains $X$. For subspaces, that check is LA1.14.

Check Let C be the family of all finite subsets of ℕ. It is closed under intersections of non-empty subfamilies. Does every S ⊆ ℕ have a smallest finite superset?

No. The second condition holds (an intersection is inside one of its finite members, so it is finite), but the first fails: $\mathbb{N}$ itself is not finite, so $\mathbb{N} \notin \mathcal{C}$. For infinite $S$, such as the even numbers, no finite set contains $S$ at all, so the family $\mathcal{F}$ in F1.15 is empty and there is nothing to intersect.

Check Why is “the intersection of all subspaces of V that contain S” never an empty intersection?

Because $V$ is itself a subspace of $V$ and contains $S$, so the family always has at least one member.

Check Is the union of two subsets in C always in C? Think of two lines through the origin in ℝ², with C the subspaces.

No. The $x$-axis and the $y$-axis are subspaces, but their union is not: $(1, 0) + (0, 1) = (1, 1)$ is in neither line. Intersections preserve “niceness”; unions usually don’t. That is why the span is defined by intersecting.

Sources

• Paul R. Halmos, Naive Set Theory (1960): sets, families, unions and intersections; the remark that an empty intersection does not make sense.
• ProofWiki, Intersection of Empty Set: how different authors handle the empty intersection.