Two theorems on finite unions of regressive immune sets

E. Z. Dyment

Brest State Pedagogical Institute

Abstract: 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\&D_{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$.

UDC: 519.5

Received: 26.04.1976

 English version: Mathematical Notes, 1977, 21:2, 141–146

Bibliographic databases:

• 
•