Лекции 12-23. Математическая логика (после колка) (1161871), страница 23
Текст из файла (страница 23)
s( 0) . . . ))| {z }n ðàçÍàïðèìåð, 4̄ ýòî òåðì s(s(s(s(0)))) .Îòíîøåíèå P (k) íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë íàçûâàåòñÿàðèôìåòèçóåìûì , åñëè ñóùåñòâóåò òàêàÿ ôîðìóëàϕ(x1 , x2 , . . . , xk ) , ÷òî äëÿ âñÿêîãî íàáîðà íàòóðàëüíûõ ÷èñåë(n1 , n2 , . . . , nk ) âåðíû ñîîòíîøåíèÿIP (k) (n1 , n2 , .
. . , nk ) = true ⇐⇒ PA ` ϕ(n̄1 , n̄2 , . . . , n̄k ) ,IP (k) (n1 , n2 , . . . , nk ) = false ⇐⇒ PA ` ¬ϕ(n̄1 , n̄2 , . . . , n̄k ) .Ôîðìàëüíàÿ àðèôìåòèêàÍóìåðàëû è àðèôìåòèçóåìûå îòíîøåíèÿÒåîðåìà ÃåäåëÿÒüþðèíãà.Îòíîøåíèå P (k) íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåëàðèôìåòèçóåìî â òîì è òîëüêî òîì ñëó÷àå, åñëè ñóùåñòâóåòòàêàÿ ìàøèíà Òüþðèíãà M , êîòîðàÿ äëÿ ëþáîãî íàáîðàíàòóðàëüíûõ ÷èñåë (n1 , n2 , . . . , nk ) èìååò çàâåðøàþùååñÿâû÷èñëåíèå, ïðåîáðàçóþùåå íà÷àëüíóþ êîíôèãóðàöèþ. .
. 1} 0 . . . 0 11. . . 1}q1 11. . . 1} 0 11| {z| {z| {zn1 +1 ðàç n2 +1 ðàçnk +1 ðàçIâ çàêëþ÷èòåëüíóþ êîíôèãóðàöèþ q0 1 , åñëèP (k) (n1 , n2 , . . . , nk ) = true ,Iâ çàêëþ÷èòåëüíóþ êîíôèãóðàöèþ q0 0 , åñëèP (k) (n1 , n2 , . . . , nk ) = false .Ôîðìàëüíàÿ àðèôìåòèêàÍóìåðàöèÿ ÃåäåëÿÇàêîäèðóåì íàòóðàëüíûìè ÷èñëàìè (çàíóìåðóåì) ñèìâîëûàëôàâèòà ôîðìàëüíîé àðèôìåòèêè, ôîðìóëû è êîíå÷íûåïîñëåäîâàòåëüíîñòè ôîðìóë.gn(0) = 3, gn(s) = 5, gn(+) = 7, gn(×) = 9, gn(=) = 11,gn(¬) = 13, gn(&) = 15, gn(∨) = 17, gn(→) = 19,gn(∀) = 21, gn(∃) = 23,gn( ) = 25, gn( ) = 27,gn(x1) = 29, gn(x2) = 31, . . . , gn(xi) = 27 + 2i, .
. . .Ãåäåëåâ íîìåð ñëîâà:gn(a )gn(a1 a2 a3 . . . an) = 2gn(a1) 3gn(a2) 5gn(a3) . . . pn n .Ãåäåëåâ íîìåð ïîñëåäîâàòåëüíîñòè ñëîâ:gn(α )gn(α1 α2 α3 . . . αm) = 2gn(α1) 3gn(α2) 5gn(α3 . . . pm m .Ôîðìàëüíàÿ àðèôìåòèêàÏðèìåðû àðèôìåòèçóåìûõ îòíîøåíèéÐàññìîòðèì äâà îòíîøåíèÿ1.2.Form(1): Form(n) = true ⇐⇒ n ãåäåëåâ íîìåðôîðìóëû àðèôìåòèêè Ïåàíî.Proof(2): Proof(n, m) = true ⇐⇒ n ãåäåëåâ íîìåðíåêîòîðîé ôîðìóëû ϕ àðèôìåòèêè Ïåàíî, à m ãåäåëåâíîìåð êîíå÷íîé ïîñëåäîâàòåëüíîñòè ôîðìóë,ñîñòàâëÿþùåé äîêàçàòåëüñòâî ôîðìóëû ϕ .ËåììàÎòíîøåíèÿFormèProof àðèôìåòèçèðóåìû.Îáîçíà÷èì Proof àðèôìåòè÷åñêóþ ôîðìóëó, ðåàëèçóþùóþïðåäèêàò Proof .Ôîðìàëüíàÿ àðèôìåòèêàÑòðàííûå ïðåäèêàòûÍó, åñëè âû ïîâåðèëè, ÷òî ïðåäèêàò Proof(2) àðèôìåòèçóåì, òîñîâåðøåííî î÷åâèäíî, ÷òî àðèôìåòèçóåìûì ÿâëÿåòñÿ è òàêîéñòðàííûé ïðåäèêàò MetaProof(2) :MetaProof(n, m) = truemn ãåäåëåâ íîìåð íåêîòîðîé ôîðìóëû àðèôìåòèêè Ïåàíî,ϕ(x) , çàâèñÿùåé îò îäíîé ïåðåìåííîé,à m ãåäåëåâ íîìåð êîíå÷íîé ïîñëåäîâàòåëüíîñòè ôîðìóë,ñîñòàâëÿþùåé äîêàçàòåëüñòâî ôîðìóëû ϕ(n̄) .Íî åñëè ïðåäèêàò MetaProof(2) àðèôìåòèçóåì, òî ñóùåñòâóåòàðèôìåòè÷åñêàÿ ôîðìóëà W(x, y ) , âûðàæàþùàÿ îòíîøåíèåMetaProof .Ôîðìàëüíàÿ àðèôìåòèêàÑòðàííûå ïðåäèêàòûÐàññìîòðèì ôîðìóëó ϕ(x) = ¬∃y W(x, y ) è åå ãåäåëåâ íîìåðn0 = gn(ϕ(x)) .Èíòåðåñíî, à ÷òî çà âûñêàçûâàíèå âûðàæàåò çàìêíóòàÿôîðìóëà ϕ(n̄0 ) ?Ýòî âûñêàçûâàíèå òàêîâî: Íåëüçÿ äîêàçàòü ôîðìóëó ϕ(n̄0 ) ,ò.
å. ôîðìóëà ϕ(n̄0 ) óòâåðæäàåò, ÷òî îíà íåäîêàçóåìà.Òàêèì îáðàçîì, ìû èìååì äåëî ñî ñòðîãî ñôîðìóëèðîâàííûìàíàëîãîì ¾ïàðàäîêñà ëæåöà¿.È åñëè ýòà ôîðìóëà äåéñòâèòåëüíî íå èìååò äîêàçàòåëüñòâà âàðèôìåòèêå Ïåàíî, òî îíà âûðàæàåò èñòèííîå ñóæäåíèå.Òåîðåìà Ãåäåëÿ î íåïîëíîòå PA(îáëåã÷åííûé âàðèàíò)Åñëè ìíîæåñòâî íàòóðàëüíûõ ÷èñåë ñ îïåðàöèÿìè ñëîæåíèÿ èóìíîæåíèÿ (N0 , +, ×) ÿâëÿåòñÿ ìîäåëüþ äëÿ àêñèîì PA, òî PAíåïîëíà.Äîêàçàòåëüñòâî.1.
Ïîêàæåì, ÷òî PA 6` ϕ(n̄0 ) .Äîïóñòèì ïðîòèâíîå PA ` ϕ(n̄0 ) . Òîãäà ôîðìóëà ϕ(n̄0 ) èìååòäîêàçàòåëüñòâî â PA: ψ1 , ψ2 , . . . , ψN = ϕ(n̄0 ).Ïóñòü m = gn(ψ1 , ψ2 , . . . , ψN ) . Òîãäà MetaProof (n0 , m) = true .Ïîýòîìó, ó÷èòûâàÿ àðèôìåòèçóåìîñòü ïðåäèêàòà MetaProof ,ïîëó÷àåì PA ` W(n̄0 , m̄) . Íî ýòî îçíà÷àåò, ÷òîPA ` ∃y W(n̄0 , y ) è, ñëåäîâàòåëüíî, PA ` ¬ϕ(n̄0 ) .Íî ýòî îçíà÷àåò, ÷òî PA ïðîòèâîðå÷èâàÿ òåîðèÿ, âîïðåêèóñëîâèþ òåîðåìû (PA èìååò ìîäåëü).Òåîðåìà Ãåäåëÿ î íåïîëíîòå PA(îáëåã÷åííûé âàðèàíò)Åñëè ìíîæåñòâî íàòóðàëüíûõ ÷èñåë ñ îïåðàöèÿìè ñëîæåíèÿ èóìíîæåíèÿ (N0 , +, ×) ÿâëÿåòñÿ ìîäåëüþ äëÿ àêñèîì PA, òî PAíåïîëíà.Äîêàçàòåëüñòâî.2.
Ïîêàæåì, ÷òî PA 6` ¬ϕ(n̄0 ) .Äîïóñòèì ïðîòèâíîå PA ` ¬ϕ(n̄0 ) , ò. å. PA ` ∃y W(n̄0 , y ) .Òîãäà (ïî÷åìó?) ñóùåñòâóåò òàêîå íàòóðàëüíîå ÷èñëî m, äëÿêîòîðîãî âåðíî PA ` W(n̄0 , m̄) . Ó÷èòûâàÿ, ÷òî ôîðìóëà Wâûðàæàåò îòíîøåíèå MetaProof , ïðèõîäèì ê âûâîäó: m ýòîãåäåëåâ íîìåð äîêàçàòåëüñòâà ôîðìóëû ϕ(n̄0 ) â PA. Çíà÷èò,PA ` ϕ(n̄0 ) .Íî ýòî îçíà÷àåò, ÷òî PA ïðîòèâîðå÷èâàÿ òåîðèÿ, âîïðåêèóñëîâèþ òåîðåìû (PA èìååò ìîäåëü).Òåîðåìà Ãåäåëÿ î íåïîëíîòå PA(îáëåã÷åííûé âàðèàíò)Åñëè ìíîæåñòâî íàòóðàëüíûõ ÷èñåë ñ îïåðàöèÿìè ñëîæåíèÿ èóìíîæåíèÿ (N0 , +, ×) ÿâëÿåòñÿ ìîäåëüþ äëÿ àêñèîì PA, òî PAíåïîëíà.Äîêàçàòåëüñòâî.3.
Èòàê,PA 6` ϕ(n̄0 )PA 6` ¬ϕ(n̄0 ) .Çíà÷èò, ϕ(n̄0 ) = ¬∃y W(n̄0 , y ) ýòî èñòèííîå àðèôìåòè÷åñêîåóòâåðæäåíèå, êîòîðîå íåëüçÿ íè äîêàçàòü, íè îïðîâåðãíóòü âàðèôìåòèêå Ïåàíî.Çíà÷èò, àðèôìåòèêà Ïåàíî íåïîëíà.Òåîðåìà Ãåäåëÿ î íåïîëíîòå PA(Îñíîâíîé âàðèàíò)Ïóñòü çàïèñü Consist îáîçíà÷àåò àðèôìåòè÷åñêóþ ôîðìóëó¬∃X Proof (gn(0 = s(0)), X )Åñëè ôîðìàëüíàÿ àðèôìåòèêà PA íåïðîòèâîðå÷èâà, òîPA `6ConsistPA `6¬Consist.Ýòî îçíà÷àåò, ÷òî àêñèîìàòè÷åñêèå òåîðèè (ñêîëü áûâûðàçèòåëüíû îíè íè áûëè) íå ïîçâîëÿþò ïîñòðîèòüäîêàçàòåëüñòâî èõ ñîáñòâåííîé íåïðîòèâîðå÷èâîñòè.Ïîñëåäîâàòåëüíîñòè ÃóäøòåéíàÎäèí èç íàèáîëåå ÿðêèõ ïðèìåðîâ, ïîêàçûâàþùèõ íåïîëíîòóàêñèîìàòè÷åñêîé àðèôìåòèêè, áûë ïðåäëîæåí àíãëèéñêèììàòåìàòèêîì Ðóáåíîì Ãóäøòåéíîì.Êàæäîå íàòóðàëüíîå ÷èñëî m ìîæåò áûòü ïðåäñòàâëåíîåäèíñòâåííûì îáðàçîì â n-÷íîé ñèñòåìå ñ÷èñëåíèÿm = ak nk + ak−1 nk−1 + · · · + a1 n1 + a0 n0 ,ãäå ak , ak−1 , .
. . , a1 , a0 ÷èñëà èç äèàïàçîíà 0, . . . , n − 1. Íîñòåïåíè k, k − 1, . . . , 1, 0 òàêæå ìîæíî ïðåäñòàâèòü â n-÷íîéñèñòåìå ñ÷èñëåíèÿ. È â ïðåäñòàâëåíèè ýòèõ ñòåïåíåé òàêæåìîæíî ñîîòâåòñòâóþùèå ñòåïåíè ïðåäñòàâëÿòü â n-÷íîéñèñòåìå ñ÷èñëåíèÿ.È îêîí÷àòåëüíîå ïðåäñòàâëåíèå ÷èñëà m, â êîòîðîì âñå ÷èñëà è êîýôôèöèåíòû è ñòåïåíè ïðåäñòàâëåíû â n-÷íîéñèñòåìå ñ÷èñëåíèÿ, íàçûâàåòñÿ íàñëåäñòâåííî n-÷íîé ñèñòåìîéñ÷èñëåíèÿ . Òàêîå ïðåäñòàâëåíèå áóäåì îáîçíà÷àòü H(m, n).Ïîñëåäîâàòåëüíîñòè ÃóäøòåéíàÍàïðèìåð,555 = 1 · 29 + 1 · 25 + 1 · 23 + 1 · 21 + 1 · 20302010= 1 · 21·2 +1·2 + 1 · 21·2 +1·2 + 1 · 21·2 +1·2 + 1 · 21 + 1 · 201·21 +1 +1·20= 1 · 21·22 +1·20+ 1 · 21·21 +1·20+ 1 · 21·2+ 1 · 21 + 1 · 20 .Òàêèì îáðàçîì,1·21 +1 +1H(555, 2) = 1 · 21·2+ 1 · 21·22 +11 +1+ 1 · 21·2+ 1 · 21 + 1.Ïîñëåäîâàòåëüíîñòè ÃóäøòåéíàÏîñëåäîâàòåëüíîñòü Ãóäøòåéíà G (N) îïðåäåëÿåòñÿ òàê:1.
Âîçüìèòå ïðîèçâîëüíîå íàòóðàëüíîå ÷èñëî N . Ýòî ÷èñëî ïåðâûé ÷ëåí ïîñëåäîâàòåëüíîñòè a1 .2. ×òîáû ïîëó÷èòü âòîðîé ÷ëåí a2 , ïîñòðîéòå H(a1 , 2),çàìåíèòå â ýòîì ïðåäñòàâëåíèè 2 íà 3 è âû÷òèòå èçïîëó÷èâøåãîñÿ ÷èñëà 1.n. ×òîáû ïîëó÷èòü n-é ÷ëåí an , ïîñòðîéòå H(an−1 , n),çàìåíèòå â ýòîì ïðåäñòàâëåíèè n íà n + 1 è âû÷òèòå èçïîëó÷èâøåãîñÿ ÷èñëà 1.Òåîðåìà Ãóäøòåéíà î ñõîäèìîñòèG (N).Ëþáàÿ ïîñëåäîâàòåëüíîñòü Ãóäøòåéíà ñõîäèòñÿ ê 0, ò.å.äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà N ñóùåñòâóåò òàêîåíàòóðàëüíîå ÷èñëî n, äëÿ êîòîðîãî an = 0.Ïîñëåäîâàòåëüíîñòè ÃóäøòåéíàÍàïðèìåð, ïîñëåäîâàòåëüíîñòü G (3) ñõîäèòñÿ ê 0 ÷åðåç 6øàãîâ:3, 3, 3, 2, 1, 0Ïîñëåäîâàòåëüíîñòü G (4) ñõîäèòñÿ ñïóñòÿ 3 · 2402653211 − 1øàãîâ.Òåîðåìà Êèðáè-ÏàðèÓòâåðæäåíèå î ñõîäèìîñòè ëþáîé ïîñëåäîâàòåëüíîñòè G (N)íåäîêàçóåìî â àðèôìåòèêå Ïåàíî.ÊÎÍÅÖ ËÅÊÖÈÈ 23.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
