13
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Jason
    Dec 12, 2010 at 8:02
  • $\begingroup$ @Jason: Actually, adding a single Cohen real already adds $2^\omega$ many Cohen reals which give rise to an independent family of size continuum. $\endgroup$ Dec 12, 2010 at 18:34
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 6, 2011 at 2:11
  • $\begingroup$ @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? $\endgroup$ Oct 6, 2011 at 7:19
  • 1
    $\begingroup$ 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$. $\endgroup$ Oct 7, 2011 at 14:15

8 Answers 8

17
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Dec 10, 2010 at 17:30
13
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – gowers
    Dec 14, 2010 at 14:58
  • 1
    $\begingroup$ KP, this is my favorite proof among several very nice arguments so far. Thanks for the answer. $\endgroup$ Dec 14, 2010 at 22:36
  • $\begingroup$ 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, ... }. $\endgroup$
    – mathahada
    Dec 19, 2010 at 15:33
11
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This is a nice construction! $\endgroup$ Dec 11, 2010 at 19:00
  • 4
    $\begingroup$ It can be done explicitly, as asked in this question: (unfortunately I don't know how put links in comments). [1]: mathoverflow.net/questions/23202/… $\endgroup$ Dec 11, 2010 at 19:31
  • 5
    $\begingroup$ Amusingly, it seems that I gave an answer to that question. That's senility for you. $\endgroup$
    – gowers
    Dec 11, 2010 at 20:52
10
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ That's very nice and short. Thank you. $\endgroup$ Oct 16, 2011 at 9:51
  • $\begingroup$ 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 <mathoverflow.net/questions/48914/…> - 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. $\endgroup$
    – matvei64
    Apr 10, 2015 at 16:56
  • $\begingroup$ @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. $\endgroup$ Apr 10, 2015 at 21:43
6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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