" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

ПРОСТОЕ МНОЖЕСТВО

Значение ПРОСТОЕ МНОЖЕСТВО в математической энциклопедии:

- рекурсивно перечислимое множество натуральных чисел, дополнение к-рого есть иммунное множество. П. м. являются промежуточными в смысле так наз. m-сводимости (см. Рекурсивная теория множеств).между разрешимыми множествами и творческими (креативными) множествами - последние являются наибольшими среди перечислимых множеств в смысле m-сводимости. Пусть Р - произвольное П. м., а К- произвольное креативное множество натуральных чисел (напр., множество гёделевых номеров теорем формальной арифметики). Тогда не существует общерекурсивной функции f(x), сводящей Кк Р, т, е. такой, что

Сводимость Р к К имеет место всегда, а к Р не сводится ни одно разрешимое множество.

Лит.:[1] Успенский В. А., Лекции о вычислимых функциях, М., 1960; [2] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [3] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972. С. Н. Артемов.