Here we are considering subsets $\mathcal{F}$ of $2^\omega$, which are in correspondence with families of subsets of $\omega$ (sets of "reals"). Such a family is Borel if it is a Borel subset of $2^\omega$ under the usual topology.

Such a family is almost disjoint if, for every pair $X\not=Y$ from $\mathcal{F}$, $X\cap Y$ is finite.

Note: the question originally only required that the symmetric difference between $X$ and $Y$ be infinite, which is substantially weaker.

Countable almost disjoint families can be constructed fairly trivially. Uncountable almost disjoint families exist, and are a standard object of study in some branches of set theory. However, the constructions I've seen do not result in a Borel set. Can this be done? Can $\mathcal{F}\subset 2^\omega$ be an uncountable Borel set which is an almost disjoint family?

  • 7
    $\begingroup$ If you look at the tree $2^{<\omega}$, the set of branches is almost disjoint. $\endgroup$
    – Asaf Karagila
    Jan 14 '16 at 15:23
  • 6
    $\begingroup$ Your definition of "almost disjoint" is much weaker than the usual one, which would be "for every pair $X\neq Y$ from $\mathcal{F}$, $X\cap Y$ is finite". In any case, Asaf's example satisfies both definitions. $\endgroup$ Jan 14 '16 at 15:38
  • 4
    $\begingroup$ I think it's a typo: the proposed "weak" definition of almost disjointness leads to families that are not at all disjoint in any typical sense. For example, $\{(-\infty,x)\cap\mathbb{Q}: x \in \mathbb{R}\}$. $\endgroup$ Jan 14 '16 at 15:50
  • 2
    $\begingroup$ @GeraldEdgar That's easy, though. Being a complete theory (coded appropriately as a subset of $\omega$) is a $\Pi^0_1$ property - in fact, the set of codes for complete theories is closed! $\endgroup$ Jan 14 '16 at 16:03
  • 1
    $\begingroup$ Asaf's example is Noah's example when the language is a propositional language with countably many propositional atoms. $\endgroup$ Jan 14 '16 at 18:29

Firstly, as commented by Asaf Karagila, it is routine to build a Borel uncountable family of almost disjoint subsets of $\omega$: fix a one-to-one map $f$ from the set $2^{<\omega}$ of finite binary sequences to $\omega$. It is clear that if $B$ and $B'$ are any two distinct branches of $2^{<\omega}$, then $f(B)$ and $f(C)$ are almost disjoint. This makes it evident that the collection of all subsets of $\omega$ of the form $f(B)$, where $B$ is a branch of $2^{<\omega}$, is an uncountable almost disjoint family. I will leave the verification that it is also Borel as an exercise.

On the other hand, there is no Borel mad family, where mad stands for maximal almost disjoint. This follows from a theorem of Mathias, who showed that no mad family can even be analytic (analytic = $\Sigma^1_1$ = continuous image of a Borel set).

However, by a joint result of Miller and Kunen, it is consistent with $ZFC$ that there is a co-analytic (i.e., $\Pi^1_1$) mad family, they showed this by building a co-analytic mad family assuming $ZF + V =L$. See Arnie Miller's wonderful paper for this and other gems exploring definability issues in infinite combinatorics (mad families are treated in sec.8).


The answers to this question: Uncountable family of infinite subsets with pairwise finite intersections describe several Borel constructions of uncountable Borel families. (Usually: perfect families)


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.