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