Suppose $\mathcal{F} \subseteq \mathcal{P} (\omega) $ is an almost disjoint family and $\aleph_0 < \vert \mathcal{F} \vert = \kappa < 2^{\aleph_0} $. Is it consistent that for some such cardinal $\kappa$, we can uniformize every two-valued function on the family; that is, if $\mathcal{F} = \langle A_i \mid i < \kappa \rangle $ and for each $i < \kappa$ the function $f_i : A_i \to 2$ is either constant 1 or constant 0, we can find a total function $f: \omega \to 2$ that agrees with each function almost everywhere?

Shelah's Proper and Improper Forcing contains a positive result under the assumption that $\mathcal{F}$ is a $\textit{tree}$. I would like to know if there is something more general, at least for some special $\kappa$.


1 Answer 1


No, this is not consistent: there is (provably in ZFC) an almost disjoint family of size $\aleph_1$ and a two-valued function on that family such that the function cannot be uniformized in the way you've described.

To get such a family and function, we'll use a Hausdorff gap, or (more accurately) just an $(\omega_1,\omega_1)$-gap. An $(\omega_1,\omega_1)$-gap is a double sequence $\langle A_\alpha :\, \alpha < \omega_1 \rangle$, $\langle B_\alpha :\, \alpha < \omega_1 \rangle$ of subsets of $\omega$ such that

(1) the $A_\alpha$'s are almost increasing, in the sense that if $\alpha < \beta$ then $A_\alpha \subseteq^* A_\beta$ (where $\subseteq^*$ means that $A_\alpha \setminus A_\beta$ is finite).

(2) the $B_\alpha$'s are almost decreasing, in the sense that if $\alpha < \beta$ then $B_\alpha \supseteq^* B_\beta$.

(3) $A_\alpha \subseteq^* B_\beta$ for all $\alpha,\beta < \omega_1$.

(4) there is no $C \subseteq \omega$ such that $A_\alpha \subseteq^* C \subseteq^* B_\beta$ for all $\alpha,\beta < \omega_1$.

(Actually, there are two different kinds of sequences that are called "Hausdorff gaps" or $(\omega_1,\omega_1)$-gaps in various places. Some places use subsets of $\omega$ with the $\subseteq^*$ relation, as above, and some use functions $\omega \rightarrow \omega$ with the $\leq^*$ relation instead. The Wikipedia article I linked to takes the latter approach, but the former is more natural for this problem. But let me point out that given a gap in $(\omega^\omega,\leq^*)$, we can get one in $(\mathcal P(\omega),\subseteq^*)$ by just identifying a function with the set of points in $\omega \times \omega$ underneath its graph.)

Given a gap like this, let $\mathcal A$ be the family of all sets of the form $A_{\alpha+1} \setminus A_\alpha$ or $B_\alpha \setminus B_{\alpha+1}$. Let $f$ denote the function $\mathcal A \rightarrow 2$ that maps every set of the form $A_{\alpha+1} \setminus A_\alpha$ to $0$ and every set of the form $B_\alpha \setminus B_{\alpha+1}$ to $1$. Basically, $(3)$ implies that this is an AD family, and $(4)$ implies that there is no function $\omega \rightarrow \omega$ that uniformizes $f$. (If we had such a function, the preimages of $0$ and $1$ would "split the gap" and that can't happen.)

  • $\begingroup$ I was assuming that the sets in an almost disjoint family are infinite. Can you show that $A_{\alpha +1} \setminus A_\alpha $ is infinite? $\endgroup$ May 28 at 7:22
  • 1
    $\begingroup$ @MatteoCasarosa: Yes, Hausdorff's construction gives you that these sets are always infinite. I guess that the definition I wrote down doesn't prescribe this, but you could alter the definition, if you like, by replacing $\subseteq^*$ with $\subset^*$. $\endgroup$
    – Will Brian
    May 28 at 8:56
  • $\begingroup$ Great! One more question: you have shown how to go from a $\subseteq^\ast $ gap to a $\leq^\ast$ gap. What would the reverse process be? $\endgroup$ May 28 at 9:23
  • $\begingroup$ @MatteoCasarosa: I'm not sure there is a reverse process. It's not clear to me, anyway, how to produce a $\leq^*$ gap from a $\subseteq^*$ gap. $\endgroup$
    – Will Brian
    May 29 at 8:54
  • $\begingroup$ Ok but then wouldn't one notion be stronger than the other? $\endgroup$ May 29 at 20:25

Your Answer

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

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