2
$\begingroup$

How can we show that any splitting family is uncountable?

A family ${\cal F} \subset 2^\omega$ is called a splitting family if for every infinite $X \subset \omega$ there exists $A \in F$ such that both $X \cap A$ and $X \setminus A$ are infinite.

I think some sort of diagonalization argument can be used.

$\endgroup$
0

1 Answer 1

6
$\begingroup$

Suppose that $\mathcal F = \{ A_n : n \in \omega \}$ is a countable collection of infinite subsets of $\omega$.

To show that $\mathcal F$ is not splitting we will construct an infinite $X \subseteq \omega$ such that for each $n$ either $X \cap A_n$ is finite, or $X \setminus A_n$ is finite. We begin by inductively constructing a descending sequence $( B_n )_{n \in \omega}$ of infinite subsets of $\omega$ and a sequence $( b_n )_{n \in \omega}$ of elements of $\omega$ so that

  • either $B_n \subseteq A_n$ or $B_n \cap A_n = \emptyset$,
  • $b_n \in B_n$, and
  • the $b_n$ are distinct.

Now to proceed with the construction.

  • Set $B_0 = A_0$, and pick $b_0 \in B_0 = A_0$.
  • Suppose that $B_0 \supseteq \cdots \supseteq B_n$ and $b_0 , \ldots , b_n$ have been appropriately chosen. If $B_n \cap A_{n+1}$ is infinite, then set $B_{n+1} = B_n \cap A_{n+1}$. Otherwise it must be that $B_n \setminus A_{n+1}$ is infinite, so set $B_{n+1} = B_n \setminus A_{n+1}$. In either case, choose $b_{n+1} \in B_{n+1}$ different from $b_0 , \ldots , b_n$.

Consider the set $X = \{ b_n : n \in \omega \}$. Clearly $X$ is infinite. By our construction for each $n \in \omega$ it follows that $\{ b_n , b_{n+1} , \ldots \} \subseteq B_n$, and since $B_n$ is either a subset of $A_n$ or disjoint from $A_n$ it follows that either $X \setminus A_n$ is finite or $X \cap A_n$ is finite.

Therefore $\mathcal F$ is not a splitting family.

$\endgroup$

You must log in to answer this question.

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