Автореферат (1104033), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Ïðè âñåõ n ≥ 2 íåðàçðåøèìû ýëåìåíòàðíûå òåîðèè ïîëóðåøåòîê (Wn/∼; ∧).Òåîðåìà3.Îòìåòèì, ÷òî ïðè äîêàçàòåëüñòâå ýòîé òåîðåìû ìû óñòàíàâëèâàåì,÷òî â ( /∼; ∧) ôîðìóëàìè ïåðâîãî ïîðÿäêà âûðàçèìû âñå áèíàðíûå îòíîøåíèÿ <k è âñå ôóíêöèè h i. Áîëåå òîãî, ìû äîêàçûâàåì, ÷òî äëÿ âñåõíàòóðàëüíûõ â ( n /∼; ∧) ôîðìóëàìè ïåðâîãî ïîðÿäêà âûðàçèìû âñåáèíàðíûå îòíîøåíèÿ <k è âñå ôóíêöèè h i ïðè ≤ .WnÒåîðåìà 4.ðåøèìà.kWkk nÝëåìåíòàðíàÿ òåîðèÿ íèæíåé ïîëóðåøåòêè (W1/∼; ∧) ðàç- ãëàâå 3 ìû èçó÷àåì âîïðîñ îá ðàçðåøèìîñòè ýëåìåíòàðíûõ òåîðèéìîäåëåé ñ íîñèòåëÿìè /∼ èëè n /∼ è ñ ñèãíàòóðàìè ìîãóùèìè âêëþ÷àòü ëèøü ïðåäèêàò <0 , êîíñòàíòó > è ôóíêöèè âèäà h i. Îòìåòèì, ÷òîìîäåëè ( /∼; <0 , >, h0i, h1i, .

. . , h i, . . .) è ( n /∼; <0 , h0i, h1i, . . . , h i) ÿâëÿþòñÿ åñòåñòâåííûìè êîíñòðóêòèâíûìè ïðåäñòàâëåíèÿìè îðäèíàëîâ ε0è ωn+1 , ñîîòâåòñòâåííî.WWWkWknÏóñòü p, q è n íàòóðàëüíûå ÷èñëà òàêèå, ÷òî 0 < p èp + 1 < q ≤ n. Òîãäà ýëåìåíòàðíûå òåîðèè ìîäåëåé (W/∼; <0, hpi, hqi) è(Wn /∼; <0 , hpi, hqi) íåðàçðåøèìû.Ìîäåëü (W/∼; <0 , >, h0i, h1i, . . . , hki, .

. .), â ñèëó òåîðåìû 5, èìååòíåðàçðåøèìóþ ýëåìåíòàðíóþ òåîðèþ. Òàêæå, èç ýòîé òåîðåìû ñëåäóåò, ÷òî ïðè âñåõ n ≥ 3 íåðàçðåøèìà ýëåìåíòàðíàÿ òåîðèÿ ìîäåëè(Wn /∼; <0 , >, h0i, h1i, . . . , hni).Òåîðåìà 5.Êðîìå òîãî ìû óñòàíàâëèâàåì ñëåäóùèå òåîðåìû.Ïðè âñåõ n ≥ 2 ó ìîäåëè (Wn/∼; <0, >, h0i, h1i, h2i) ðàçðåøèìà ýëåìåíòàðíàÿ òåîðèÿ.Ýëåìåíòàðíàÿ òåîðèÿ ìîäåëè (W/∼; <0, >, h0i, h1i, h2i) ðàçðåøèìà. Ïðè âñåõ n ≥ 2 ðàçðåøèìà ýëåìåíòàðíàÿ òåîðèÿ ìîäåëè(Wn /∼; <0 , >, h0i, h1i, h2i).Òåîðåìà 6.Òåîðåìà 7.9Äëÿ äîêàçàòåëüñòâà òåîðåìû 7 ìû ïîêàçûâàåì, ÷òî âñå ñòðóêòóðû( n /∼; <0 , >, h0i, h1i, h2i), ãäå ≥ 3, è ñòðóêòóðà ( /∼; <0 , >, h0i, h1i, h2i)ïîïàðíî ýëåìåíòàðíî ýêâèâèâàëåíòû, à äàëåå ïðèìåíÿåì òåîðåìó 6.WnWß âûðàæàþ ãëóáîêóþ áëàãîäàðíîñòü ñâîåìó íàó÷íîìó ðóêîâîäèòåëþ÷ëåíó-êîððåñïîíäåíòó ÐÀÍ Ë.Ä. Áåêëåìèøåâó çà ïîñòàíîâêó çàäà÷ è ïîääåðæêó â ðàáîòå.

ß áëàãîäàðþ ó÷àñòíèêîâ ñåìèíàðîâ ¾Ëîãè÷åñêèå ïðîáëåìû èíôîðìàòèêè¿ è ¾Àëãîðèòìè÷åñêèå ïðîáëåìû àëãåáðû è ëîãèêè¿çà êîíñòðóêòèâíîå îáñóæäåíèå. Êðîìå òîãî, ÿ áëàãîäàðþ çà ïîëåçíûå çàìå÷àíèÿ àíîíèìíûõ ðåöåíçåíòîâ ñâîèõ ñòàòåé ïî òåìå äèññåðòàöèè.Ðàáîòû àâòîðà ïî òåìå äèññåðòàöèè[1] Ô.Í. Ïàõîìîâ. Íåðàçðåøèìîñòü ýëåìåíòàðíîé òåîðèè ïîëóðåøåòêèGLP-ñëîâ., 203(8):141160, 2012.[2] Ô.Í.

Ïàõîìîâ. Îá ýëåìåíòàðíûõ òåîðèÿõ ñèñòåì îðäèíàëüíûõ îáîçíà÷åíèé íà îñíîâå ñõåì ðåôëåêñèè., 289:206226, 2015.[3] F.N. Pakhomov. On the complexity of the closed fragment of Japaridze'sprovability logic., 53(7-8):949967, 2014.Ìàòåìàòè÷åñêèé ñáîðíèêÒðóäû Ìàòåìàòè÷åñêîãî èí-ñòèòóòà èì. Â.À. ÑòåêëîâàArchive for Mathematical Logic10Íàó÷íîå èçäàíèåÏàõîìîâ Ôåäîð Íèêîëàåâè÷ÀÂÒÎÐÅÔÅÐÀÒäèññåðòàöèè íà ñîèñêàíèå ó÷åíîé ñòåïåíèêàíäèäàòà ôèçèêî-ìàòåìàòè÷åñêèõ íàóê íà òåìó:Íåêîòîðûå àëãîðèòìè÷åñêèå âîïðîñûäëÿ ïîëèìîäàëüíûõ ëîãèê äîêàçóåìîñòèÏîäïèñàíî â ïå÷àòü 18.06.2015Òèðàæ 100 ýêç.Îòïå÷àòàíî â Ìàòåìàòè÷åñêîì èíñòèòóòå èì.

Â.À. Ñòåêëîâà ÐÀÍÌîñêâà, 119991, óë. Ãóáêèíà, 8.

Характеристики

Список файлов диссертации