Independent families of subsets of $\mathbb N$ of size continuum

Question

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.)

Answer 1

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$.)

Answer 2

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.

Answer 3

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.

Answer 4

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.)

Answer 5

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}$.

Answer 6

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$.

Answer 7

Here's a way of rephrasing the HMP proof which doesn't invoke the HMP theorem. Let $B$ be the set of all continuous functions from $2^\omega$ to $2$. It's easy to see that $B$ is countable. Now $\{A_r: r \in 2^\omega \}$ (where $A_r=\{f \in B: f(r)=1 \}$) is an independent famiy of size continuum on $B$.

Answer 8

I just found the following construction in J. Novák, On the Cartesian product of two compact spaces, Fund. Math. 40 (1953), 106-112.

Let $A \subseteq \ell^2$ be the set of all sequences of rational numbers which are eventually zero (note that $A$ is a countable set). For each real number $t \in (0,1)$ let $A_t=\{x \in A : \sum_{i=0}^\infty t^ix_i\geq 0 \}$. Any $n$ of the hyperplanes associated with the $A_t$´s are linearly independent when restricted to $\mathbb{R}^n$ (first $n$ coordinates), since the coefficients form a Vandermonde matrix. It follows that $\{A_t : t \in (0,1) \}$ is an independent family on $A$.