|
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$.
Received: 26.04.1976
Citation:
E. Z. Dyment, “Two theorems on finite unions of regressive immune sets”, Mat. Zametki, 21:2 (1977), 259–269; Math. Notes, 21:2 (1977), 141–146
Linking options:
https://www.mathnet.ru/eng/mzm7953 https://www.mathnet.ru/eng/mzm/v21/i2/p259
|
|