My question arises from a construction I gave in my recent answer to a question of Alexander Pruss concerning large families of independent non-measurable sets of reals. In that argument, using the continuum hypothesis and the existence of a thick Kurepa tree $T$, I produced a family of $2^{\frak c}$ many Vitali sets $\{\ A_s\mid s\in[T]\ \}$, which was almost disjoint in the sense that $A_s\cap A_t$ was countable whenever $s\neq t$. The only aspect of the Vitali relation that was used in the construction was that the Vitali equivalence classes (equivalence under rational translation) are countably infinite. Thus, the construction proves:

Theorem. If the CH holds and there is a thick Kurepa tree, then for every partition of $\mathbb{R}$ into countably infinite sets, there is an almost-disjoint family of selectors of size $2^{\frak c}$.

By almost-disjoint here, I mean that any two distinct elements of the family have countable intersection; by selector, I mean that each set in the family has exactly one element from each equivalence class; and by a partition into countably infinite sets, I mean that we have an equivalence relation on $\mathbb{R}$ with every equivalence class countably infinite. To prove the theorem, simply label the nodes on the $\alpha^{th}$ level of $T$ with distinct members of the $\alpha^{th}$ equivalence class in the partition. Being thick, the tree has $2^{\frak c}$ many branches, each of which provides a selector, and any two such selectors can agree only up to some countable height in the tree, where those branches separate.

My question is whether I really needed those set-theoretic assumptions in order to make the conclusion.

Question. How much can one weaken the hypotheses of the theorem and still prove the conclusion?

For example, can we drop the thick Kurepa tree assumption? Can we omit CH? Can we prove it in ZFC? Can one show the consistency with ZFC of a counterexample?

  • 1
    $\begingroup$ Under GCH this is Problem 19/A in the old "Unsolved problems in set theory" paper of P. Erdős and A. Hajnal. $\endgroup$
    – bof
    Mar 21, 2015 at 5:54

2 Answers 2


If CC (Chang's Conjecture) holds, then there are no $\aleph_2$ pairwise almost different $\omega_1\to\omega$ functions. For this, assume that $\{f_\alpha:\alpha<\omega_2\}$ are as described. By CC there is an elementary submodel $N$ such that $|N|=\aleph_1$ and $\delta=N\cap\omega_1<\omega_1$. (Technically, we have to consider the function $F(\alpha,\xi)=f_\alpha(\xi)$ for $\alpha<\omega_2$, $\xi<\omega_1$ to make the model of countable length. Then, apply CC to $M=(\omega_2;F,\omega_1,\in,\dots)$.) If $\alpha\neq \beta$ are in $N$, then they differ from some $\gamma<\omega_1$ on, by elementarity, there is such a $\gamma<\delta$, i.e., any two functions in $\{f_\alpha:\alpha\in N\}$ differ from some $\gamma<\delta$. Specifically, $\{f_\alpha(\delta):\alpha\in N\}$ are distinct, a contradiction.


The existence of such a family of almost-disjoint selectors which is merely uncountable is equivalent to CH. Indeed, suppose we have such a family; we can shrink it to a family of size $\aleph_1$. Then for each equivalence class, there must be a pair of selectors that makes the same choice in that class, but each pair of selectors can only make the same choice countably many times. Since there are only $\aleph_1$ pairs of selectors, there can only be $\aleph_1$ equivalence classes, and so $|\mathbb{R}|=\aleph_1$. Conversely, assuming CH, it easy easy to construct such an uncountable family: identify the collection of equivalence classes with $\omega_1$, and order the $\alpha$th equivalence class with order type $\alpha$. For each $\beta<\omega_1$, let the $\beta$th selector choose the $\beta$th element of each equivalence class (and an arbitrary element of the $\alpha$th equivalence class for $\alpha\leq\beta$).

  • 2
    $\begingroup$ Good, this is progress, showing that we cannot omit CH. But when CH holds, so far you've got only a disjoint family of size $\omega_1$. By my construction, one can push this to $\omega_2$, if there is a Kurepa tree, and to $2^{\omega_1}$, if there is a thick Kurepa tree. But do we really need these Kurepa trees? $\endgroup$ Mar 20, 2015 at 17:37
  • $\begingroup$ In my previous comment, I meant: almost-disjoint $\endgroup$ Mar 20, 2015 at 17:51
  • 1
    $\begingroup$ CH wouldn't be sufficient to get $\omega_2$ many almost disjoint selectors. For example, if there is an $\omega_2$-saturated sigma ideal over $\omega_1$. $\endgroup$
    – Ashutosh
    Mar 21, 2015 at 1:56
  • 1
    $\begingroup$ @Ashutosh Would it be possible for you to expand on your comment and post an answer? $\endgroup$ Mar 21, 2015 at 11:42

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.