Исчисления высказываний классической логики. Гуров С.И. - 112 стр.

112                    Ãëàâà 3. Ãåíöåíîâñêèå èñ÷èñëåíèÿ âûñêàçûâàíèé


çàêëþ÷åíèÿ ëþáîãî èç óêàçàííûõ ïðàâèë íåâîçìîæíî îïðåäåëèòü, èç
êàêèõ ïîñûëîê îíî ñëåäóåò.
   Äàííàÿ îñîáåííîñòü íàòóðàëüíûõ èñ÷èñëåíèé ïðåâðàùàåò ïîèñê
âûâîäà â íèõ â, âîîáùå ãîâîðÿ, íåîïðåäåëåííóþ ïðîöåäóðó, è, ñëåäîâà-
òåëüíî, íàòóðàëüíûå èñ÷èñëåíèÿ ÿâëÿþòñÿ ïðàêòè÷åñêè áåñïîëåçíûìè
ïðè íàõîæäåíèè âûâîäîâ òåîðåì. Òåì íå ìåíåå, èññëåäîâàíèå íàòóðàëü-
íûõ èñ÷èñëåíèé ïîçâîëÿåò ñôîðìóëèðîâàòü îäíî èç âàæíåéøèõ òðåáî-
âàíèé ê ëîãè÷åñêèì èñ÷èñëåíèÿì âîîáùå. Îíî ñîñòîèò â ñëåäóþùåì:
äëÿ ñóùåñòâîâàíèå àëãîðèòìà ïîèñêà âûâîäà ïðîèçâîëüíîé ôîðìóëû
èñïîëüçóåìûå ïðàâèëà âûâîäà äîëæíû ñîäåðæàòü òîëüêî ïîäôîðìóëû
äàííîé ôîðìóëû.
   Ñåêâåíöèàëüíûå èñ÷èñëåíèÿ, îäíî èç êîòîðûõ ðàññìàòðèâàåòñÿ íè-
æå, óäîâëåòâîðÿþò ýòîìó òðåáîâàíèþ.


2 Èñ÷èñëåíèå S ñåêâåíöèàëüíîãî òèïà
   Èñ÷èñëåíèÿ ñåêâåíöèàëüíîãî òèïà îêàçûâàþòñÿ íàèáîëåå óäîáíûìè
äëÿ îáíàðóæåíèÿ âûâîäèìîñòè è àíàëèçà ñèíòàêñè÷åñêîé ñòðóêòóðû
âûâîäîâ. Èñõîäíîé ïîñûëêîé äëÿ ðàññìîòðåíèÿ òàêèõ èñ÷èñëåíèé áûëî
ñòðåìëåíèå äîêàçàòü íåïðîòèâîðå÷èâîñòü ôîðìàëüíîé àðèôìåòèêè3 .
   Íèæå îïèñûâàåòñÿ èñ÷èñëåíèå ñåêâåíöèàëüíîãî òèïà (íåñêîëüêî îò-
ëè÷àþùååñÿ îò ââåä¼ííîãî Ãåíöåíûì), êîòîðîå ìû áóäåì îáîçíà÷àòü S .
Åãî ìîæíî ðàññìàòðèâàòü êàê ìåòàèñ÷èñëåíèå, ò.å. ôîðìàëèçîâàííóþ
ìåòàòåîðèþ äëÿ ÈÑ N .

2.1 Îïðåäåëåíèå ÈÑ S . Ñâîéñòâî ïîäôîðìóëüíîñòè ïðàâèë
    âûâîäà

Ñèíòàêñèñ. Àëôàâèò Al(S) ÈÑ S âêëþ÷àåò â ñåáÿ òå æå ñèìâîëû,
÷òî è àëôàâèò ÈÑ N çà îäíèì èñêëþ÷åíèåì: êà÷åñòâå ñèìâîëà âûâî-
äèìîñòè (ñëåäîâàíèÿ) âìåñòî ` ìû, ÷òîáû îòëè÷àòü ýòè èñ÷èñëåíèÿ,
áóäåì óïîòðåáëÿòü çíàê →.
   3 Ñîãëàñíî âòîðîé òåîðåìå üäåëÿ î íåïîëíîòå (ñì. ñ. 47) ýòîãî ñäåëàòü íåëüçÿ
áåç ïðèâëå÷åíèÿ äîïîëíèòåëüíûõ ïðåäïîëîæåíèé. Íåïðîòèâîðå÷èâîñòü àðèôìåòè-
êè óäàëîñü äîêàçàòü, ïðèíÿâ ñõåìó àêñèîì äëÿ ò.í. òðàíñôèíèòíîé èíäóêöèè (ñì.,
íàïðèìåð, [19]) è èñïîëüçóÿ ïðàâèëà âûâîäà ñ áåñêîíå÷íûì ÷èñëîì ïîñûëîê, ò.å.
íå ôèíèòàðíûå ìåòîäû. Ïåðåâîäû ðàáîò Ãåíöåíà ¾Èññëåäîâàíèÿ ëîãè÷åñêèõ âûâî-
äîâ¿ è ¾Íåïðîòèâîðå÷èâîñòü ÷èñòîé òåîðèè ÷èñåë¿, â êîòîðûõ ââîäèòñÿ èñ÷èñëåíèå
ñåêâåíöèé è ïðèâåäåíî óïîìÿíóòîå äîêàçàòåëüñòâî, îïóáëèêîâàíû â ñáîðíèêå [13].
  Çàìåòèì, ÷òî â 1924-5 ãã. Àêêåðìàí ïîëàãàë, ÷òî åìó óäàëîñü äîêàçàòü íåïðîòè-
âîðå÷èâîñòü ôîðìàëüíîé àðèôìåòèêè. Îäíàêî âñêîðå ôîí Íåéìàí óêàçàë íà óïó-
ùåíèå â åãî äîêàçàòåëüñòâå, ñâÿçàííîå ñ íåêîððåêòíûì èñïîëüçîâàíèåì îáû÷íîé
ìàòåìàòè÷åñêîé èíäóêöèè.