independent family of sets



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.


Let XX be a set. A family FPXF \subseteq P X (or F2 XF \subseteq 2^X) is independent if, for any finite subfamily of pairwise distinct elements of FF, say S 1,,S m,T 1,,T nS_1, \ldots, S_m, T_1, \ldots, T_n, the intersection

S 1S m¬T 1¬T nS_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)Bool(F) denote the free Boolean algebra generated by the set FF. An inclusion i:FPXi: F \hookrightarrow P X names an independent family if the induced Boolean algebra map i^:Bool(F)PX\widehat{i}: Bool(F) \to P X is itself injective. (To see how the alternative condition follows, consider elements of Bool(F)Bool(F) as written in disjoint normal form, i.e., as disjoint unions of finite intersections of literals S,¬TS, \neg T; use this to deduce ker(i^)=0\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 XX be an infinite set, of cardinality κ\kappa.


The number of ultrafilters on XX is 2 2 κ2^{2^\kappa}.


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

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

For each S2 XS \in 2^X let A S={ϕBool(X):ϕ,S=1}A_S = \{\phi \in Bool(X): \langle \phi, S \rangle = 1\}. We claim that the A SA_S form an independent family, i.e., for pairwise distinct S 1,,S m,T 1,,T n2 XS_1, \ldots, S_m, T_1, \ldots, T_n \in 2^X, the finite intersection

A S 1A S m¬A T 1¬A T nA_{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,,S m,T 1,,T n2 XS_1, \ldots, S_m, T_1, \ldots, T_n \in 2^X there exists ϕBool(X)\phi \in Bool(X) such that ϕ,S i=1\langle \phi, S_i \rangle = 1 and ϕ,T j=0\langle \phi, T_j \rangle = 0. To prove this, note that ϕϕ,\phi \mapsto \langle \phi, - \rangle is an isomorphism Bool(X)CH(2 X,2)Bool(X) \to CH(2^X, 2) by Stone duality, where CH(2 X,2)CH(2^X, 2) is isomorphic to the Boolean algebra of clopens, and there exists a clopen separating the set of points {S 1,,S m}\{S_1,\ldots, S_m\} from the set of points {T 1,,T n}\{T_1, \ldots, T_n\} (a proof may be based on the lemma here, taking VV to be the complement of {T 1,,T n}\{T_1, \ldots, T_n\}).

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

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

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

Last revised on March 18, 2016 at 13:10:16. See the history of this page for a list of all contributions to it.