Математическая энциклопедия - креативное множество

творческое множество, рекурсивно перечислимое множество Анатуральных чисел, дополнение к-рого Адо натурального ряда является продуктивным множеством;иными словами, множество Акреативно, если оно рекурсивно перечислимо и существует такая частично рекурсивная функция j(x), что для всякого содержащегося в рекурсивно перечислимого множества Wx с гёделевым номером х

К. м. часто встречаются в различных алгоритмически неразрешимых проблемах, в силу чего образуют важнейший класс рекурсивно перечислимых множеств, неявляющихся рекурсивными. Креативными оказываются множества номеров доказуемых и опровержимых формул многих формальных теорий (при естественной нумерации всех формул теории); в частности, так обстоит дело в арифметике Пеано и вообще во всех рекурсивно-неотделимых теориях (т. е. в теориях, множества доказуемых и опровержимых формул к-рых эффективно неотделимы). Все К. м. рекурсивно изоморфны между собой (т. е. для каждой пары К. м. существует рекурсивное взаимно однозначное преобразование натурального ряда, отображающее одно из них на другое) и принадлежат одной тьюринговой степени, наибольшей среди степеней рекурсивно перечисленных множеств. Понятие креативности обобщается на последовательности множеств и другие объекты.

Лит.:[1] Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972; [2] Шенфилд Дж., Математическая логика, пер. с англ., М., 1975. В. А. Душский.

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

И. М. Виноградов

1977—1985