Кіріспе
Есептеу теориясында өнімді жиынтықтар және шығармашылық жиынтықтар – математикалық логикада маңызды қолданысқа ие табиғи сандар жиынтықтарының түрлері. Олар математикалық логика оқулықтарындағы стандартты тақырыптардың бірі болып табылады.
Математикалық логиканың қолданылуы
Нақты аксиоматикалық жүйедегі барлық дәлелденетін сөйлемдердің жиынтығы әрқашан рекурсивті түрде саналатын жиын болып табылады. Егер жүйе бірінші реттік арифметика сияқты жеткілікті күрделі болса, онда жүйедегі шын сөйлемдердің Гёдель нөмірлерінің жиынтығы T өнімді жиын болады, яғни егер W шын сөйлемдердің рекурсивті саналатын жиыны болса, онда W жиынтығына кірмейтін кем дегенде бір шын сөйлем болады. Бұл Гёделдің бірінші толық еместік теоремасын қатаң түрде дәлелдеуге қолданылуы мүмкін, себебі ешбір рекурсивті саналатын жиын өнімді емес. T жиынтығының толықтыруы рекурсивті саналамайды, демек T – толықтыруы шығармашыл емес өнімді жиынға мысал.
Тарих
Оның шығармашылық жиын деп аталатын ұғымды анықтады. Жоғарыда аталған және барлық санамаланған 1 орынды есептелетін бөлшек функциялардың диагоналін алып, оларға 1-ді қосатын функцияның домені ретінде анықталған жиын шығармашылық жиынға мысал болып табылады. Пост өзінің шығармашылық жиындарын пайдаланып Гёдельдің толық емес теоремасының нұсқасын ұсынды, ал Гёдель бастапқыда «Мен осы аксиоматикалық теорияда дәлелденбеймін» деп аударуға болатын сөйлемді құрған болатын. Дегенмен, Гёдельдің дәлелі шын сөйлемдер ұғымына емес, керісінше, екінші толық емес теоремаға әкелген дәйекті теория ұғымына негізделді. Пост толық емес теореманың өзінің нұсқасын аяқтағаннан кейін былай деп қосты: «Бұл қорытындыдан қашуға болмайды, тіпті осындай нақты және жақсы анықталған математикалық ұйғарымдар жинағы үшін математикалық ойлау, мәні бойынша, шығармашылық болып табылады және осылай болуы керек». Әдеттегі шығармашылық жиын, диагональдық функцияны пайдаланып анықталған, өзінің тарихи дамуына ие. Алан Тьюринг 1936 жылғы Тьюринг машинасы туралы мақаласында функцияны есептейтін әмбебап компьютердің бар екенін көрсетті. Функция (енгізілген деректерге кодталған нұсқаулардың қолданылуының нәтижесі) ретінде анықталады және кез келген есептелетін бөлшек функцияның барлық жерде берілуі мағынасында универсалды болып табылады, мұнда кодталған нұсқаулар қолданылады. Жоғарыдағы белгілеулерді пайдаланып, диагональдық функция табиғи түрде туындайды. Ақырында, бұл идеялар Чирчтің математикалық есептеуге қабілетті бөлшек функциялар туралы ұғымының дұрыс формалдануы екенін айтатын тезисімен байланысты. Чирч лямбда-есептеуін, Тьюринг – идеалды компьютерді, ал кейін Эмиль Пост өзінің тәсілінде қолданды, олардың барлығы эквивалентті. Компьютерлік күрделілік теориясында полиномдық шығармашылық деп аталатын ұқсас ұғымды тұжырымдады және оны NP-толық жиындардың изоморфизмі туралы Берман-Хартманис болжамына қарсы мысалдар келтіру үшін пайдаланды.
"The conclusion is unescapable that even for such a fixed, well defined body of mathematical propositions, mathematical thinking is, and must remain, essentially creative." The usual creative set defined using the diagonal function has its own historical development. Alan Turing in a 1936 article on the Turing machine showed the existence of a universal computer that computes the function. The function is defined such that
(the result of applying the instructions coded by to the input ), and is universal in the sense that any calculable partial function is given by for all where codes the instructions for Using the above notation , and the diagonal function arises quite naturally as Ultimately, these ideas are connected to Church's thesis that says the mathematical notion of computable partial functions is the correct formalization of an effectively calculable partial function, which can neither be proved or disproved. Church used lambda calculus, Turing an idealized computer, and later Emil Post in his approach, all of which are equivalent. formulated an analogous concept, polynomial creativity, in computational complexity theory, and used it to provide potential counterexamples to the Berman–Hartmanis conjecture on isomorphism of NP complete sets.