Введение

В теории вычислимости, продуктивные множества и творческие множества — это типы множеств натуральных чисел, имеющие важное применение в математической логике. Они являются стандартной темой в учебниках по математической логике, таких как и .

Применение в математической логике

Множество всех доказуемых предложений в эффективной аксиоматической системе всегда является рекурсивно перечислимым множеством. Если система достаточно сложна, например, арифметика первого порядка, то множество T, состоящее из чисел Гёделя истинных предложений в системе, будет продуктивным множеством, что означает, что для любого рекурсивно перечислимого множества W истинных предложений существует по крайней мере одно истинное предложение, не входящее в W. Это можно использовать для строгого доказательства первой теоремы о неполноте Гёделя, поскольку никакое рекурсивно перечислимое множество не является продуктивным. Дополнение множества T не будет рекурсивно перечислимым, и, следовательно, T является примером продуктивного множества, дополнение которого не является творческим.

История

В своей основополагающей работе он определил концепцию, которую назвал "Творческое множество". Повторяя, множество, упомянутое выше и определенное как область функции, которая принимает диагонали всех перечисленных 1-местных вычислимых частичных функций и добавляет к ним 1, является примером творческого множества. Пост представил версию теоремы о неполноте Гёделя, используя свои творческие множества, где изначально Гёдель в некотором смысле сконструировал предложение, которое можно было бы свободно перевести как "Я недоказуемо в этой аксиоматической теории". Однако доказательство Гёделя опиралось не на концепцию истинных предложений, а скорее на концепцию непротиворечивой теории, что привело ко второй теореме о неполноте. Завершив свою версию теоремы о неполноте, Пост добавил следующее:

"Вывод неизбежен, что даже для такого фиксированного, чётко определённого набора математических утверждений, математическое мышление является и должно оставаться по своей сути творческим". Обычное творческое множество, определённое с использованием диагональной функции, имеет свою собственную историю развития. Алан Тьюринг в статье 1936 года о машине Тьюринга показал существование универсального компьютера, вычисляющего функцию. Функция определяется таким образом, что (результат применения инструкций, закодированных , к входу ), и является универсальной в том смысле, что любая вычислимая частичная функция даётся для всех , где кодирует инструкции для. Используя вышеуказанную нотацию , диагональная функция возникает вполне естественно как. В конечном счёте, эти идеи связаны с тезисом Черча, утверждающим, что математическое понятие вычислимых частичных функций является корректной формализацией эффективно вычислимой частичной функции, которую нельзя ни доказать, ни опровергнуть. Черч использовал лямбда-исчисление, Тьюринг – идеализированный компьютер, а позже Эмиль Пост в своём подходе, все из которых эквивалентны. сформулировал аналогичную концепцию, полиномиальную креативность, в теории вычислительной сложности и использовал её для предоставления потенциальных контрпримеров к гипотезе Бермана — Хартманиса об изоморфизме NP-полных множеств.