5
$\begingroup$

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?

Improve this question
$\endgroup$
15
  • 7
    $\begingroup$ If you look at the tree $2^{<\omega}$, the set of branches is almost disjoint. $\endgroup$
    – Asaf Karagila ♦
    Commented Jan 14, 2016 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$
    – Paul McKenney
    Commented Jan 14, 2016 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$
    – François G. Dorais
    Commented Jan 14, 2016 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$
    – Noah Schweber
    Commented Jan 14, 2016 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$
    – Andreas Blass
    Commented Jan 14, 2016 at 18:29

2 Answers 2

Reset to default
16
$\begingroup$

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).

Improve this answer
$\endgroup$
1
3
$\begingroup$

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)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .