Лекции В.А. Захарова, страница 39

. }, ñóùåñòâóåò ìíîæåñòâî Y ,ñîäåðæàùåå â òî÷íîñòè ïî îäíîìó ïðåäñòàâèòåëþ èç êàæäîãîìíîæåñòâà X1 , X2 , . . . ñåìåéñòâà U .Àêñèîìà âûáîðà èñïîëüçóåòñÿ ïðè äîêàçàòåëüñòâå î÷åíüáîëüøîãî ÷èñëà òåîðåì ìàòåìàòèêè. Ñ åå ïîìîùüþ ìîæíîäîêàçàòü âåñüìà íåîæèäàííûå óòâåðæäåíèÿ. Ê èõ ÷èñëóîòíîñèòñÿÒåîðåìà ÖåðìåëîËþáîå ìíîæåñòâî ìîæíî âïîëíå óïîðÿäî÷èòü, ò.

å. îïðåäåëèòüíà ýòîì ìíîæåñòâå òàêîå îòíîøåíèå ëèíåéíîãî ïîðÿäêà, ïðèêîòîðîì íå ñóùåñòâóåò áåñêîíå÷íî óáûâàþùèõïîñëåäîâàòåëüíîñòåé ýëåìåíòîâ.Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÀ íå ïðèâíåñåò ëè àêñèîìà âûáîðà êàêîå-íèáóäü ïðîòèâîðå÷èåâ òåîðèþ ZF? Ýòîò âîïðîñ îñòàåòñÿ îòêðûòûì è ïî ñåé äåíü.Åñòü â òåîðèè ìíîæåñòâ è äðóãèå çàäà÷è, äëÿ ðåøåíèÿ êîòîðûõíåäîñòàòî÷íî àêñèîì òåîðèè ìíîæåñòâ ZF.Êîíòèíóóì-ãèïîòåçà (CH)Ëþáîå ïîäìíîæåñòâî ìíîæåñòâà âåùåñòâåííûõ ÷èñåë ëèáîÿâëÿåòñÿ ñ÷åòíûì, ëèáî ðàâíîìîùíî ìíîæåñòâó âåùåñòâåííûõ÷èñåë (ÿâëÿåòñÿ êîíòèíóàëüíûì). 1939 ã.

Ê. Ãåäåëü äîêàçàë òåîðåìó:Åñëè òåîðèÿ ìíîæåñòâ ZF+CA íåïðîòèâîðå÷èâà, òî òåîðèÿZF+AC+CH òàêæå íåïðîòèâîðå÷èâà . 1963 ã. Ï. Êîýí äîêàçàë òåîðåìó:Åñëè òåîðèÿ ìíîæåñòâ ZF+CA íåïðîòèâîðå÷èâà, òî òåîðèÿZF+AC+¬CH òàêæå íåïðîòèâîðå÷èâà .Ôîðìàëüíàÿ àðèôìåòèêàÀ ìîæíî ëè ïîëíîñòüþ àêñèîìàòèçèðîâàòü àðèôìåòèêóíàòóðàëüíûõ ÷èñåë? 1889 ã. èòàëüÿíñêèé ìàòåìàòèê Ä. Ïåàíî ïðåäëîæèë ñïèñîêàêñèîì, ïðè ïîìîùè êîòîðûõ ìîæíî äîêàçûâàòü óòâåðæäåíèÿ îñâîéñòâàõ íàòóðàëüíûõ ÷èñåë.Àðèôìåòèêà Ïåàíî (PA) îáðàçóåòñÿ çà ñ÷åò äîáàâëåíèÿ êÊÈÏ= ñèãíàòóðû h0, s, +, ×i ñëåäóþùèõ àêñèîì.Çäåñü s(x) íóæíî ðàññìàòðèâàòü êàê îäíîìåñòíóþ îïåðàöèþ,ðåàëèçóþùóþ ôóíêöèþ âû÷èñëåíèÿ ñëåäóþùåãî íàòóðàëüíîãî÷èñëà x + 1 .Ôîðìàëüíàÿ àðèôìåòèêà1.

∀x, y (s(x) = s(y ) → x = y );2. ∀x (s(x) 6= 0);3. ∀x ∃y (x 6= 0 → x = s(y ));4. ∀x (x + 0 = x);5. ∀x, y (x + s(y ) = s(x + y ));6. ∀x (x × 0 = 0);7. ∀x, y (x × s(y ) = x × y + x);8. ϕ(0) & ∀x (ϕ(x) → ϕ(s(x))) → ∀x ϕ(x).Âîïðîñ î íåïðîòèâîðå÷èâîñòè è ïîëíîòå ýòîé àêñèîìàòè÷åñêîéòåîðèè äîëãîå âðåìÿ îñòàâàëñÿ öåíòðàëüíîé ïðîáëåìîéìàòåìàòèêè.  1931 ã. Ê.

Ãåäåëü äîêàçàë òåîðåìó, êîòîðàÿ äàëàñîâåðøåííî íåîæèäàííûé îòâåò íà ýòîò âîïðîñ.Ôîðìàëüíàÿ àðèôìåòèêàÍóìåðàëû è àðèôìåòèçóåìûå îòíîøåíèÿÍóìåðàëîì n̄ íàòóðàëüíîãî ÷èñëà n íàçûâàåòñÿ òåðìs(s(. . . 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.