Is there a sequence of two-set partitions of $[0,1]$ such that the partition generated by any subsequence is a partition into finite sets

descriptive-set-theoryreal-analysisset-partition

More specifically, I'm wondering if there is a sequence of partitions $\{\mathcal{P_n}\}_{n\in \mathbb{N}}$ of the unit interval $[0, 1]$, where each $\mathcal{P}_n$ consists of precisely two sets, such that for any infinite $A\subset\mathbb{N}$, the partition $\vee_{n\in A}\mathcal{P}_n$ is a partition where each member is finite. If the $\mathcal{P_n}$'s are measurable that would be nice, but I'm allowing non-measurable examples. For clarity, $\vee_{n\in A}\mathcal{P}_n$ is the partition obtained by taking all possible non-empty intersections of members in $\mathcal{P}_n$, $n\in A$, or, if you prefer, the least upper bound of all partitions $\mathcal{P}_n$, $n\in A$, where for partitions $\mathcal{P}$ and $\mathcal{Q}$ we declare $\mathcal{P}\leq \mathcal{Q}$ if each member of $\mathcal{Q}$ is contained in a member of $\mathcal{P}$.

As an example, consider the "Rademacher" partitions (of strictly speaking the interval $[0, 1)$) where $\mathcal{P}_n$ consists of the sets $\bigcup\limits_{0\leq k<2^n, \text{ }k \text{ even}}[k\ 2^{-n}, (k+1)2^{-n})$ and $\bigcup\limits_{0\leq k<2^n, \text{ }k \text{ odd}}[k\ 2^{-n}, (k+1)2^{-n})$. Then $\vee_{n\in \mathbb{N}} \mathcal{P}_n$ is the partition into points, but if for example $A$ is the set of all odd natural numbers, then members of $\vee_{n\in A}\mathcal{P}_n$ are uncountable "Cantor sets".

I don't know if the question changes much if one replaces $[0,1]$ by any uncountable set $X$.

This problem arose when I tried to solve the question Extracting a subsequence common to infinitely many sets from an uncountable collection with uniform positive upper density. I think it's equivalent to that question, but in my mind thinking of partitions is more transparent.

Best Answer

The answer is no (although I don't see how this answers the question you linked to); the negative answer to your question is a restatement of a classical result of Erdős and Rado on "polarized partition relations". In a stronger and more general form, it's Theorem 48 on p. 481 of P. Erdős and R. Rado, A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956), 427–489 (pdf), which I paraphrase:

Theorem. (Erdős and Rado) Let $\kappa$ be an infinite cardinal of uncountable cofinality (i.e., it's not the sum of countably many smaller cardinals). If $A\times B=K_0\cup K_1$, where $|A|=\aleph_0$ and $|B|=\kappa$, then there are sets $X\subseteq A$ and $Y\subseteq B$ such that either
(i) $|X|=\aleph_0$, $|Y|=\kappa$, and $X\times Y\subseteq K_0$, or else
(ii) $|X|=|Y|=\aleph_0$ and $X\times Y\subseteq K_1$.

[Scroll down for my summary of the proof.]

The following corollary (which Erdős and Rado don't bother to state) follows by induction on $n$.

Corollary. Let $n$ be a positive integer. If $|A|=\aleph_0$ and $|B|=\aleph_1$, and if $A\times B=K_1\cup\cdots\cup K_n$, then there are infinite sets $X\subseteq A$ and $Y\subseteq B$ such that $X\times Y\subseteq K_i$ for some $i$.

Now let $B$ be an uncountable set. An infinite sequence of partitions of $B$ into two parts can be viewed as a partition $\mathbb N\times B=K_1\cup K_2$, and a subsequence corresponds to an infinite set $X\subseteq\mathbb N$. By the corollary (with $n=2$) there are infinite sets $X\subseteq\mathbb N$ and $Y\subseteq B$ such that $X\times Y\subseteq K_i$ for some $i\in\{1,2\}$. That is, the infinite set $Y$ is not split by any of the partitions in the subsequence indexed by $X$.

Proof of the Theorem. Assuming that (i) fails, we show that (ii) must hold. We assume that $A\cap B=\varnothing$ and consider the bipartite graph $G$ with vertex set $V(G)=A\cup B$ and edge set $E(G)=\{\{x,y\}:(x,y)\in K_1\}$. We aim to show that $G$ contains a complete bipartite graph $K_{\aleph_0,\aleph_0}$. As usual $N(v)$ is the set of neighbors of the vertex $v$.

Claim 1. Whenever $X\times Y\subseteq A\times B$, $|X|=\aleph_0$ and $|Y|=\kappa$, there is a vertex $x\in X$ with $|N(x)\cap Y|=\kappa$.

Claim 2. Whenever $X\times Y\subseteq A\times B$, $|X|=\aleph_0$ and $|Y|=\kappa$, there is a vertex $y\in Y$ with $|N(y)\cap X|=\aleph_0$.

Note that, because of the countablility of $X$ and the uncountable cofinality of $Y$, a counterexample to either claim would lead to a witness to the truth of (i).

Now a complete bipartite subgraph $K_{\aleph_0,\aleph_0}$ can be constructed by an obvious back-and-forth procedure using Claims 1 and 2.

Related Question