Two theorems on finite unions of regressive immune sets

E. Z. Dyment

Matematičeskie zametki, Tome 21 (1977) no. 2, pp. 259-269.

Résumé

It is proved that the set of all natural numbers cannot be represented as the union of a finite number of regressive immune sets. This answers a question of Appel and McLaughlin. Incidentally, we obtain the following two results: 1. If $A_1,\dots,A_n$ are regressive immune sets, then there exists a general recursive function $f$ such that $D_{f(0)},\dots,D_{f(n)},\dots$ is a sequence of pairwise disjoint sets and $$ \forall\,x\ (|D_{f(x)}|\le n+1\{f(x)}\cap\overline{A_1\cup\dots\cup A_n}\ne\varnothing). $$ 2. If $A_1,\dots,A_n$ are regressive and $B$ is an infinite subset of $\bigcup\limits_{i=1}^nA_i$, then there exists an $i$ that $A_i\le{}_eB$.