nLab independent family of sets

Idea

To say a family of subsets of a set is independent means that there are no trivial Boolean combinations that can be formed from them except tautologically trivial ones.

Definition

Let $X$ be a set. A family $F \subseteq P X$ (or $F \subseteq 2^X$) is independent if, for any finite subfamily of pairwise distinct elements of $F$, say $S_1, \ldots, S_m, T_1, \ldots, T_n$, the intersection

$$S_1 \cap \ldots \cap S_m \cap \neg T_1 \cap \ldots \cap \neg T_n$$

is inhabited.

Another way of saying it: let $Bool(F)$ denote the free Boolean algebra generated by the set $F$. An inclusion $i: F \hookrightarrow P X$ names an independent family if the induced Boolean algebra map $\widehat{i}: Bool(F) \to P X$ is itself injective. (To see how the alternative condition follows, consider elements of $Bool(F)$ as written in disjoint normal form, i.e., as disjoint unions of finite intersections of literals $S, \neg T$; use this to deduce $\ker(\widehat{i}) = 0$) This is likely the origin of the term “independent family”; cf. the abstract definition of linearly independent set.

Application: counting ultrafilters

Let $X$ be an infinite set, of cardinality $\kappa$.

Theorem

The number of ultrafilters on $X$ is $2^{2^\kappa}$.

Proof

Begin by noting that the set of ultrafilters $Bool(P X, 2)$ is a subset of $Set(P X, 2)$, a set of cardinality $2^{2^\kappa}$. So it suffices to prove $Bool(P X, 2)$ has at least $2^{2^\kappa}$ elements.

The free Boolean algebra $Bool(X)$ generated by $X$ also has cardinality $\kappa$. (Consider it as the directed union of $Bool(F)$ ranging over finite subsets $F$ of $X$, and use the fact that $Bool(F)$ is finite.) The Stone space of $Bool(X)$, i.e., the spectrum? of $Bool(X)$ consisting of Boolean ring homomorphisms $S: Bool(X) \to 2$, is the compactum $2^X$. Let $\langle -, - \rangle: Bool(X) \times 2^X \to 2$ be the associated canonical pairing.

For each $S \in 2^X$ let $A_S = \{\phi \in Bool(X): \langle \phi, S \rangle = 1\}$. We claim that the $A_S$ form an independent family, i.e., for pairwise distinct $S_1, \ldots, S_m, T_1, \ldots, T_n \in 2^X$, the finite intersection

$$A_{S_1} \cap \ldots \cap A_{S_m} \cap \neg A_{T_1} \cap \ldots \cap \neg A_{T_n}$$

is inhabited; this is equivalent to the claim that for pairwise distinct $S_1, \ldots, S_m, T_1, \ldots, T_n \in 2^X$ there exists $\phi \in Bool(X)$ such that $\langle \phi, S_i \rangle = 1$ and $\langle \phi, T_j \rangle = 0$. To prove this, note that $\phi \mapsto \langle \phi, - \rangle$ is an isomorphism $Bool(X) \to CH(2^X, 2)$ by Stone duality, where $CH(2^X, 2)$ is isomorphic to the Boolean algebra of clopens, and there exists a clopen separating the set of points $\{S_1,\ldots, S_m\}$ from the set of points $\{T_1, \ldots, T_n\}$ (a proof may be based on the lemma here, taking $V$ to be the complement of $\{T_1, \ldots, T_n\}$).

By transport along a bijection $X \cong |Bool(X)|$, this result implies there is an independent family $\{A_S\}_{S \in 2^\kappa}$ of subsets of $X$ that has size $2^\kappa$, or in other words there is an injective Boolean algebra map $Bool(2^\kappa) \to P X$ sending $S \in 2^\kappa$ to $A_S$. We finish by observing that given a Boolean algebra injection $i: A \to B$, any Boolean algebra map $f: A \to 2$ extends to a Boolean algebra map $g: B \to 2$; this follows from the ultrafilter principle as the ultrafilter $f^{-1}(1) \subset A$ in $A$ generates a proper filter in $B$ by injectivity of $i$, which may then be extended to an ultrafilter in $B$. (See also here: $2$ is an injective object.) From this observation, the induced map

$$Bool(P X, 2) \to Bool(Bool(2^\kappa), 2) \cong 2^{2^\kappa}$$

is surjective, and thus the set $Bool(P X, 2)$ of ultrafilters on $X$ has cardinality at least $2^{2^\kappa}$.