Креативное множество

творческое множество, - рекурсивно перечислимое множество Анатуральных чисел, дополнение к-рого Адо натурального ряда является продуктивным множеством;иными словами, множество Акреативно, если оно рекурсивно перечислимо и существует такая частично рекурсивная функция j(x), что для всякого содержащегося в [img: http://localhost:8080/file/031209-61.jpg] рекурсивно перечислимого множества Wx с гёделевым номером х [img: http://localhost:8080/file/031209-62.jpg] К. м. часто встречаются в различных алгоритмически неразрешимых проблемах, в силу чего образуют важнейший класс рекурсивно перечислимых множеств, неявляющихся рекурсивными. Креативными оказываются множества номеров доказуемых и опровержимых формул многих формальных теорий (при естественной нумерации всех формул теории); в частности, так обстоит дело в арифметике Пеано и вообще во всех рекурсивно-неотделимых теориях (т. е. в теориях, множества доказуемых и опровержимых формул к-рых эффективно неотделимы). Все К. м. рекурсивно изоморфны между собой (т. е. для каждой пары К. м. существует рекурсивное взаимно однозначное преобразование натурального ряда, отображающее одно из них на другое) и принадлежат одной тьюринговой степени, наибольшей среди степеней рекурсивно перечисленных множеств. Понятие креативности обобщается на последовательности множеств и другие объекты.