MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A family $\mathcal F$ of subsets of $\mathbb N$ is independent if for any two finite, disjoint subsets $\mathcal A,\mathcal B\subseteq\mathcal F$ the set $$\bigcap_{A\in\mathcal A}A\cap\bigcap_{B\in\mathcal B}(\mathbb N\setminus B)$$ is infinite.

It is well-known that there is an independent family on $\mathbb N$ of size $2^{\aleph_0}$. This for example implies that there are $2^{2^{\aleph_0}}$ ultrafilters on $\mathbb N$.

My favourite proof of the existence of a large independent family uses the Hewitt-Marczewski-Pondiczery Theorem that says that the space $2^{\mathbb R}$ (with the product topology) is separable: Pick a countable dense subset $D\subseteq 2^{\mathbb R}$ and consider, for each $r\in\mathbb R$, the set $A_r$ of all functions $f\in D$ (from $\mathbb R$ to $2$) with $f(r)=1$. The $A_r$ form an independent family of the required size on $D$.

There is a purely combinatorial proof as an exercise in Kunen's set theory book, but that proof is rather by computation than by visualization. There is a large number of nice proofs of the fact that there is a large almost disjoint family on $\mathbb N$.

So here is my question: Does anyone know a nice proof of the existence of a large independent family (large=of size continuum) on $\mathbb N$? (Other than the two proofs mentioned above or a combinatorialized version of the H.M.P.-argument.)

share|cite|improve this question
Observation: If we force to add $2^{\omega}$ many Cohen Reals, then this collection will form an independent family of size $2^{\omega}$ in the extension. Just thought I'd point out this fact to anyone perusing the post. – Jason Dec 12 '10 at 8:02
@Jason: Actually, adding a single Cohen real already adds $2^\omega$ many Cohen reals which give rise to an independent family of size continuum. – Stefan Geschke Dec 12 '10 at 18:34
How do you prove the Hewitt-Marczewski-Pondiczery theorem without using the existence of large independent sets in the first place? Otherwise the argument is circular. – Emil Jeřábek Oct 6 '11 at 2:11
@Emil Jerabek: The set of functions from $\mathbb R$ to $2$ that are 1 on a finite union of disjoint open intervals with rational endpoints and otherwise zero is a countable dense subset of $2^{\mathbb R}$. How do you prove the HMP-theorem using independent families? – Stefan Geschke Oct 6 '11 at 7:19
To prove HMP using an independent family $F$ of size continuum, identify $2^{\mathbb R}$ with $2^F$ and let, for each $n\in\mathbb N$, $f_n$ be the element of $2^F$ defined by $f_n(X)=1$ iff $n\in X$. The set of these countably many $f_n$'s is dense, because when you untangle the definition of what it means for it to be dense, it boils down to the independence of $F$. – Andreas Blass Oct 7 '11 at 14:15

The original proof by Fichtenholz and Kantorovich is, in my opinion, a nice one. It suffices to find continuum many independent subsets of some countably infinite set $C$; let's take $C$ to be the collection of finite sets of rational numbers. Associate to each real number $r$, the subset $A_r$ of $C$ consisting of those finite sets $s\in C$ that have an odd number of members $<r$. It is easy to check that the intersection of any finitely many sets of the form $A_r$ and the complements of any finitely many others is infinite; that is $\{A_r:r\in\mathbb R\}$ is an independent family.

(I don't have a copy of Kunen's book handy, but I assume the proof there, the one you don't want here, is Hausdorff's proof, which generalizes to give $2^\kappa$ independent subsets of $\kappa$ for any infinite cardinal $\kappa$.)

share|cite|improve this answer
Yes, Andreas, the exercise in Kunen's book is to construct an independent family of size $2^\kappa$ of subsets of $\kappa$. I agree that the proof that you sketch is nice. – Stefan Geschke Dec 10 '10 at 17:30

I don't know whether this is the same as one of the proofs you already know, but the following seems to work. Take a set of irrationals of continuum size that is linearly independent over the rationals. (I don't know whether this can be done explicitly, but it's easy to show that it exists.) Now for each real r in this set, let $A_r$ be the set of all integers $n$ such that the integer part of $rn$ is even.

share|cite|improve this answer
This is a nice construction! – Andrés E. Caicedo Dec 11 '10 at 19:00
It can be done explicitly, as asked in this question: (unfortunately I don't know how put links in comments). [1]:… – HenrikRüping Dec 11 '10 at 19:31
Amusingly, it seems that I gave an answer to that question. That's senility for you. – gowers Dec 11 '10 at 20:52

A variant of Hewitt-Marczewski-Pondiczery: Let the base set $B$ be the set of all polynomials with integer (or rational) coefficients. For each real $r$, let $A_r$ be the set of $p(x)\in B$ with $p(r)>0$. This is an independent family of size continuum.

(I think I learned this from Menachem Kojman.)

share|cite|improve this answer

Let $2^{<\omega}$ be the binary tree and assign to each branch $x$ the family $F_x$ of finite sets that intersect it. If $x_1$, $x_2$, $\ldots$ $x_k$ is a finite set of (distinct) branches then there is a level, $n$ say, where they all differ. On each level above $n$ you can find finite sets that satisfy any Boolean combination of the $F_{x_i}$ you like.

share|cite|improve this answer
An obvious remark to make here is that all you need as your starting point is continuum-many subsets of a countable set with all intersections finite: thus, the binary tree is one of many constructions that will do the job. It's nice to see such a direct link between the two problems. – gowers Dec 14 '10 at 14:58
KP, this is my favorite proof among several very nice arguments so far. Thanks for the answer. – Stefan Geschke Dec 14 '10 at 22:36
An easy construction of an almost disjoint family of size continuum is given by taking, for each real number with, say, decimal expansions 0.123411... the set {1, 12, 123, 1234, ... }. – mathahada Dec 19 '10 at 15:33

First argue that for every $N$ there is a family of $N$ finite sets which are independent, i.e., all Boolean combinations are nonempty. Indeed, take the $2^N$ nodes of the $N$-dimensional cube as the underlying set and consider $N$ nonparallel hyperplanes. Apply this, for each $k=0,1,\dots$ to obtain some family of $2^k$ sets, on some finite set $S_k$, indexed by the length-$k$ 0-1 sequences: $\{X^k_{00\dots 0},\dots,X^k_{11\dots 1}\}$. We may assume that the sets $S_0,S_1,\dots$ are disjoint. Our system will contain the sets $Y_f$ for all infinite 0-1 sequences where $Y_f=X^0_{f|0}\cup X^1_{f|1}\cup X^2_{f|2}\cup\cdots$. If we take finitely many infinite 0-1 sequences $f_1,\dots,f_n,g_1,\dots,g_m$, then for $k$ large enough $f_1|k,\dots,f_n|k,g_1|k,\dots,g_m|k$ all differ and so $Y_{f_1}\cap\cdots\cap Y_{f_n}-(Y_{g_1}\cup\cdots\cup Y_{g_m})$ contains an element in $S_k$.

share|cite|improve this answer

I realize that the question is rather old, but here is another proof: Let $\mathcal{B}$ be a countable base for the topology of $\mathbb{R}$ closed under finite unions. For each $r \in \mathbb{R}$, let $ A_r = \{ B \in \mathcal{B} : r \in B \}$. The family $\{A_r : r \in \mathbb{R} \}$ is an independent family on $\mathcal{B}$.

share|cite|improve this answer
That's very nice and short. Thank you. – Stefan Geschke Oct 16 '11 at 9:51
I fully agree that Ramiro's family of sets is very nice. I just would like to point out that the indicator functions of these sets coincide with the ones in Stefan Geschke's comment <…; - functions from R to 2 that are 1 on a finite union of disjoint open intervals with rational endpoints and otherwise zero. So via the 1:1 relationship between subsets of R and indicator functions from R to 2 the two solutions are essentially the same. – matvei64 Apr 10 '15 at 16:56
@matvei64: Stefan's comment gives a countable dense subset of the Cantor cube $2^\mathbb{R}$, which coincides (assuming we are talking about the same base and identifying sets with indicator functions) with the set $\mathcal{B}$ in my answer. But note that no independent family is mentioned in Stefan's comment. – Ramiro de la Vega Apr 10 '15 at 21:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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