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

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

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


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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Нужен реферат?

Смотреть что такое "ПРОСТОЕ МНОЖЕСТВО" в других словарях:

  • Множество Мандельброта — Множество Мандельброта  это множество таких точек c на комплексной плоскости, для которых итеративная последовательность z0=0, z …   Википедия

  • Множество мандельброта — В математике множество Мандельброта это фрактал, определённый как множество точек на комплексной плоскости, для которых итеративная последовательность …   Википедия

  • Простое число — Простое число  это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы… …   Википедия

  • ПРОСТОЕ ЧИСЛО — натуральное (целое положительное) число р>1, имеющее только два делителя 1 и p: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ... Числа, имеющие не менее трех различных делителей, наз. составными. Понятие П. ч. является основным ири изучении… …   Математическая энциклопедия

  • множество — КЛАСС (МНОЖЕСТВО)(В ЛОГИКЕ И МАТЕМАТИКЕ) конечная или бесконечная совокупность объектов, выделенная по общему для них признаку (свойству или отношению), мыслимая как нечто целое. Объекты, составляющие К., называются его элементами. Примером К. (м …   Словарь терминов логики

  • РАЗНОСТНОЕ МНОЖЕСТВО — совершенное разностное множество, множество D, состоящее из kвычетов но модулю некрого натурального числа , причем для каждого , , существует точно l упорядоченных пар (di, dj).элементов из Dтаких, что числа наз. п а р а м е т р а м и Р. м. Напр …   Математическая энциклопедия

  • Незаконное простое число — Незаконное простое число  это простое число, представляющее охраняемую законом информацию, которую запрещено хранить и распространять. Одно из первых незаконных простых чисел было обнародовано в 2001 году. При правильной интерпретации оно… …   Википедия

  • Случайное простое число — В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов , на алгоритм генерации которого накладываются определенные ограничения. Получение случайных простых чисел является… …   Википедия

  • Кольцо (множество) — Кольцо это множество, на котором заданы две операции, «сложение» и «умножение», со свойствами, напоминающими сложение и умножение целых чисел. Содержание 1 Определения 2 Связанные определения 3 Простейшие свойства …   Википедия

  • БЛИЗОСТИ ПРОСТРАНСТВО — множество Рс бинарным отношением на множестве всех его подмножеств, удовлетворяющее следующим аксиомам: 1) равносильно (симметричность); 2) равносильно или (аддитивность); 3) равносильно …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»