# Is there an uncountable Borel almost disjoint family?

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?

• If you look at the tree $2^{<\omega}$, the set of branches is almost disjoint. Jan 14 '16 at 15:23
• 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. Jan 14 '16 at 15:38
• 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}\}$. Jan 14 '16 at 15:50
• @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! Jan 14 '16 at 16:03
• Asaf's example is Noah's example when the language is a propositional language with countably many propositional atoms. 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).