Existence of infinite sets of a certain property

74 Views Asked by At

I've been thinking about this problem for a long time, but I can't come up with a solution. It must be proved that there exists an infinite family of infinite pairwise disjoint subsets of $\mathbb{N}$, $$ A_1, A_2, A_3, ... $$ such that any infinite recursively enumerable subset of $\mathbb{N}$ intersects each of the $ A_i $. Thank you in advance!

1

There are 1 best solutions below

0
On

If I understand the question, the set of all infinite enumerable subsets of $\mathbb{N}$ is countable since each can be described by a finite sentence. Say the infinite enumerable subsets of $\mathbb{N}$ are $B_1, B_2, \cdots$. Then let $f$ be a bijection between $\mathbb{N}$ and $\mathbb{N \times N}$. Enumerate the natural numbers into $A_1, A_2, \cdots$ by on the $n$th step, if $f(n) = (a,b)$, select the smallest number from $B_b$ that has not been selected on a previous step and put it into $A_a$.