Файзрахманов М. Х.
Вычислимые нумерации семейств низких множеств и тьюринговы скачки в иерархии Ершова
Получен следующий результат: если даны Δ02-вычислимые нумерации ν, μ семейств множеств натуральных чисел, то предикат P(x, y) , ν(x)´ ≠ μ(y) является Σ02-предикатом. Как следствия из этого результата можно получить достаточное условие существования Δ02-вычислимой нумерации подсемейства всех множеств данного семейства, тьюринговы скачки которых лежат в фиксированном уровне иерархии Ершова, и существование Σ-1ω-вычислимой нумерации семейства всех супернизких множеств.
|
Faizrahmanov M.Kh.
Computable numberings of families of low sets and Turing jumps in the Ershov hierarchy
If ν and μ are some Δ02-computable numberings of families of sets of the naturals then P(x, y) , ν(x)´ ≠ μ(y) is a Σ02-predicate. Deriving corollaries from this result, we obtain a sufficient condition for existence of a Δ02-computable numbering of the subfamily of all sets in a given family with the Turing jumps belonging to a fixed level of the Ershov hierarchy, and we deduce existence of a Σ-1ω-computable numbering of the family of all superlow sets.
|
