Ultimately I'm trying to understand the result that for a set X the number of ultrafilters on X is equal to $2^{2^{|X|}}$. The proofs I've found use the notion of an independent family of subsets of X. My question has some parts: (1) What is the origin of this idea of independent family of subsets and what was it's motivation, i.e. what is it capturing? (2) Is there a basic treatment somewhere? I've been trying to figure out more about it, but the definitions vary a bit. In general it looks something like:

Definition Let X be a set. Let $\mathscr{A}$ be a collection of subsets of X. $\mathscr{A}$ is an independent family of subsets of X if, whenever $\mathscr{F}\subset\mathscr{A}$ and $\mathscr{G}\subset\mathscr{A}$ are finite and disjoint,

$$(\bigcap\limits_{A\in\mathscr{F}}A)\cap (\bigcap\limits_{A\in\mathscr{G}}A^{c})\neq\emptyset$$

Sometimes it's stated that the intersection is not only nonempty but has a particular cardinality, but I don't think that matters for the ultrafilter argument.

For a independent family of subsets it would seem as though it's a stronger property than the finite intersection property. We need at least that otherwise there would be ways of choosing $\mathscr{F}$ such that $\cap_{A\in\mathscr{F}}A=\emptyset$ and then the rest of the big ole intersection would fail.

Also it would seem that for any subsets A and B of X, if $A\cup B=X$, then you cannot have both A and B in the set since their intersection of their complements would be empty. Likewise we can't have the empty set or X in the family $\mathscr{A}$ because of complements.

I have been looking for treatments of this topic but I've missed something very obvious I'm willing to take some well meaning abuse :)

  • $\begingroup$ Considered hiw many untrafilters there is on a finite set. $\endgroup$ – William Elliot Nov 19 '18 at 0:29
  • $\begingroup$ I'm not sure how that helps, it's clearly |X|=n because every ultrafilter on a finite set is principal. Can you elaborate how that might lead me to think about independent families of subsets? $\endgroup$ – kevin roberge Nov 19 '18 at 14:01

Let $\mathcal F$ be a family of subsets of some set $X$, and suppose we play the following game. I pick some $A\in\mathcal F$ and tell you which $A$ it is; I tell you that I'm thinking of some $x\in X$ but I don't tell you which $x$ it is; you're supposed to guess whether $x\in A$. Before you make your guess, you're allowed to ask me questions "Is $x\in B$?" for any $B\in\mathcal F$ except that $B$ can't be $A$ (i.e., you can't ask me the question you're supposed to guess the answer to). You can ask lots of these questions, but at some point (after finitely many of your questions have been answered) you have to give your answer, either $x\in A$ or $x\notin A$. At that point, if I can find an $x\in X$ for which all my answers to your questions are correct but your decision about $x\in A$ is incorrect, then I win; otherwise, you win.

To say that $\mathcal F$ is an independent family is equivalent to saying that I can answer your questions completely arbitrarily (flipping a coin or just saying whatever comes to mind) as long as, if you ask the same question twice then I give the same answer both times, and then, whatever answer you decide about $x\in A$, I can still find an $x$ to win the game.

In other words, no matter how much information you collect from me about $x\in B$ for various (finitely many) $B\in\scr F$, it doesn't help you determine whether $x\in A$; I can always find an $x$ consistent with my answers yet violating yours.

I think this makes the terminology "independent" quite reasonable: Information about some members of $\mathcal F$ tells you nothing about other members.

  • $\begingroup$ Oh interesting. Let me see if I understand. $\endgroup$ – kevin roberge Nov 19 '18 at 14:13
  • $\begingroup$ Sorry (hit enter too quickly, ran out of edit time) Ok. So to refer back to the definition I stated in my question $\mathscr{F}$ is the set of subsets I asked about that you replied "yes" and $\mathscr{G}$ is the set of subsets I asked about that you replied "no." If the collection $\mathscr{A}$ is an independent family of subsets then the elements that are in the subsets in $\mathscr{F}$ and not in the subsets of $\mathscr{G}$ form a nonempty subset of X. The fact that the intersection is non empty gives you the wiggle room to find an $x$ consistent with your answers yet violating mine? $\endgroup$ – kevin roberge Nov 19 '18 at 14:29
  • $\begingroup$ To make my description match the definition of "independent", begin with F and G as in your comment but then also put A into F if you guessed "no" and put A into G if you guessed "yes". So the intersection in the definition is the set of x's for which all my answers are right but your answer is wrong, i.e., it's the set of x's that I can use to win the game. $\endgroup$ – Andreas Blass Nov 19 '18 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.