Таран Т.А. Основы дискретной математики

Подождите немного. Документ загружается.

240 241

åì ñâîè çíàíèÿ î ïðîáëåìå. Â êà÷åñòâå ïåðâîé ïîñûëêè âîçüìåì

óòâåðæäåíèå î òîì, ÷òî êîìïåòåíòíûé ñëóæàùèé ïðîäâèãàåòñÿ ïî

ñëóæåáíîé ëåñòíèöå: ∀x(C(x)&K(x)→ P(x)).

Âòîðîé ïîñûëêîé ìîæåò ñëóæèòü óòâåðæäåíèå î òîì, ÷òî íà÷àëü-

íèê ïåðåñòàåò ïðîäâèãàòüñÿ ïî ñëóæåáíîé ëåñòíèöå:

∀x(N(x) → ¬P(x)).

Ó÷òåì òàêæå òîò ôàêò, ÷òî íà÷àëüíèê  òîæå ñëóæàùèé:

∀x(N(x) → C(x)).

Òîãäà âûâîä, êîòîðûé íóæíî ïðîâåðèòü, ìîæíî ñôîðìóëèðîâàòü

òàê: «Âñå íà÷àëüíèêè íåêîìïåòåíòíû»: ∀x(N(x) → ¬K(x)).

Ïðèâåäåì ïîñûëêè è îòðèöàíèå çàêëþ÷åíèÿ ê ÑÑÔ è ïîñòðîèì

ðåçîëþòèâíûé âûâîä:

1. N(a)

2. K(a)

3. ¬C(x) ∨ ¬K(x) ∨ P(x)

4. ¬N(x) ∨ ¬P(x)

5. ¬N(x) ∨ C(x)

6. ¬C(a) ∨ P(a){a/x} â 3, ðåçîëüâåíòà 2, 3

7. ¬N(a) ∨ P(a){a/x} â 5, ðåçîëüâåíòà 5, 6

8. ¬N(a){a/x} â 4, ðåçîëüâåíòà 4,7

ðåçîëüâåíòà 1,8

Èòàê, ìû ïîëó÷èëè, ÷òî êîìïåòåíòíûõ íà÷àëüíèêîâ íå ñóùåñòâóåò.

Ïðèìåð 13.6. Ðàññìîòðèì çàäà÷ó î áðàäîáðåå: Â îäíîì ñåëå

áðàäîáðåé áðååò òåõ è òîëüêî òåõ æèòåëåé ñåëà, êîòîðûå íå

áðåþòñÿ ñàìè. Äîëæåí ëè áðàäîáðåé áðèòü ñàìîãî ñåáÿ?

Âîçüìåì ïðåäèêàòû: P(x): x áðàäîáðåé, Q(x, y): x áðååò y.

Ôîðìàëèçóåì ïîñûëêó è ïðèâåäåì åå ê ÑÑÔ:

∃x(P(x)&∀y(Q(y, y) → ¬Q(x, y))&(¬Q(y, y) → Q(x, y))).

ÑÑÔ: (P(a)&∀y(¬Q(y, y) ∨ ¬Q(a, y))&(Q(y, y) ∨ Q(a, y))).

Ïðîâåðèì, áðååò ëè áðàäîáðåé ñàìîãî ñåáÿ: Q(a, a). Ïîñòðîèì âûâîä:

1. P(a)

2. ¬Q(y, y) ∨ ¬Q(a, y)

3. Q(y, y) ∨ Q(a, y)

4. ¬Q(a, a)

5. Q( a, a) ïîäñòàíîâêà {a/y} â 3, ñêëåéêà 3

ðåçîëüâåíòà 4, 5

Ëîãè÷åñêîå ñëåäîâàíèå âûïîëíåíî, ò.å. áðàäîáðåé äîëæåí áðèòü

ñàìîãî ñåáÿ.

Ïîñòàâèì ïðîòèâîïîëîæíûé âîïðîñ: áðàäîáðåé íå äîëæåí áðèòü

ñàìîãî ñåáÿ: ¬Q(a, a), è ïîñòðîèì ðåçîëþòèâíûé âûâîä:

1. P(a)

2. ¬Q(y, y) ∨ ¬Q(a, y)

3. Q(y, y) ∨ Q(a, y)

4. Q(a, a)

5. ¬Q( a, a) ïîäñòàíîâêà {a/y} â 2, ñêëåéêà 2

ðåçîëüâåíòà 4, 5

Ëîãè÷åñêîå ñëåäîâàíèå òàêæå âûïîëíåíî, ò.å. áðàäîáðåé íå

äîëæåí áðèòü ñàìîãî ñåáÿ.

Â ýòîé çàäà÷å íà äâà ïðîòèâîïîëîæíûõ âîïðîñà ìû ïîëó÷àåì

îäèíàêîâûé îòâåò, ïîñêîëüêó èñõîäíîå óòâåðæäåíèå ïðîòèâîðå÷èâî

ñàìî ïî ñåáå.

Ìåòîä ðåçîëþöèé  ýòî î÷åíü ñèëüíûé ìåòîä ïîèñêà äîêàçà-

òåëüñòâà îáùåçíà÷èìîñòè ôîðìóë (â äðóãîé ôîðìóëèðîâêå ëîãè-

÷åñêèõ ñëåäîâàíèé). Èìåííî ïîýòîìó îí ïîðîäèë íîâóþ ïàðàäèãìó

ïðîãðàììèðîâàíèÿ  ëîãè÷åñêîå ïðîãðàììèðîâàíèå. Íàèáîëåå

ðàñïðîñòðàíåííûì ÿçûêîì ëîãè÷åñêîãî ïðîãðàììèðîâàíèÿ ÿâëÿ-

åòñÿ ÏÐÎËÎÃ. Â ëîãè÷åñêîì ïðîãðàììèðîâàíèè ëþáàÿ çàäà÷à ñòà-

âèòñÿ êàê çàäà÷à äîêàçàòåëüñòâà ëîãè÷åñêîãî ñëåäîâàíèÿ íåêîòîðîãî

ïðåäëîæåíèÿ èç çàäàííûõ ïîñûëîê. Âûïîëíåíèå ïðîãðàììû çàêëþ-

÷àåòñÿ â ïîèñêå äîêàçàòåëüñòâà ìåòîäîì ðåçîëþöèé.

Ãëàâà 13 Àâòîìàòè÷åñêîå äîêàçàòåëüñòâî òåîðåì

243

Ãëàâà 14. ÑÂÎÉÑÒÂÀ ÒÅÎÐÈÉ

ÏÅÐÂÎÃÎ ÏÎÐßÄÊÀ

Óñïåõè ðàçâèòèÿ äåäóêòèâíîãî ìåòîäà ïîðîäèëè áîëüøîå êîëè÷åñòâî

ðàáîò ïî ôîðìàëèçàöèè îñíîâíûõ ðàçäåëîâ ìàòåìàòèêè. Èäåÿ ñîçäàíèÿ

óíèâåðñàëüíîãî ÿçûêà äëÿ âñåé ìàòåìàòèêè è ôîðìàëèçàöèè

ìàòåìàòè÷åñêèõ äîêàçàòåëüñòâ ñðåäñòâàìè ýòîãî ÿçûêà âûäâèãàëàñü

åùå Ëåéáíèöåì. Â ñåðåäèíå 19-ãî âåêà ðàáîòû Áóëÿ è äå Ìîðãàíà ïî

ôîðìàëèçàöèè àðèñòîòåëåâîé ëîãèêè ñîçäàëè ïðåäïîñûëêè äëÿ

ïîñòðîåíèÿ òàêîãî ÿçûêà. Ïîñëå òîãî, êàê Ã.Ôðåãå (1879) è ×. Ïèðñ

(1885) ââåëè â ÿçûê ëîãèêè ïðåäèêàòû, ïðåäìåòíûå ïåðåìåííûå è

êâàíòîðû, âîçíèêëà ðåàëüíàÿ âîçìîæíîñòü ïðèìåíèòü ýòîò ÿçûê ê

ôîðìàëèçàöèè îñíîâàíèé ìàòåìàòèêè. Â ðàáîòàõ Âåéåðøòðàññà,

Äåäåêèíäà è Êàíòîðà áûëà ïîêàçàíà âîçìîæíîñòü «àðèôìåòèçàöèè»

àíàëèçà è òåîðèè ôóíêöèé, â ðåçóëüòàòå ÷åãî àðèôìåòèêà

íàòóðàëüíûõ ÷èñåë ñòàëà ðàññìàòðèâàòüñÿ êàê ôóíäàìåíò âñåé

êëàññè÷åñêîé ìàòåìàòèêè. Ïîýòîìó âïîëíå åñòåñòâåííî áûëî íà÷àòü

ôîðìàëèçàöèþ îñíîâàíèé ìàòåìàòèêè ñ àêñèîìàòèçàöèè àðèôìåòèêè.

Íàèáîëåå óäîáíàÿ ñèñòåìà àêñèîì àðèôìåòèêè áûëà ïðåäëîæåíà Ïåàíî

(1891). Â íà÷àëå 20-ãî âåêà âîçíèêëî íàïðàâëåíèå â ìàòåìàòèêå, öåëüþ

êîòîðîãî áûëî ïðåäñòàâèòü âñþ ÷èñòóþ ìàòåìàòèêó êàê ÷àñòü

ôîðìàëüíîé ëîãèêè. Óàéòõåä è Ðàññåë â 1910  1913 ã.ã. îïóáëèêîâàëè

ñâîé ôóíäàìåíòàëüíûé òðóä «Principia Mathematica», ïîñâÿùåííûé

ìàòåìàòè÷åñêîé ëîãèêå è îñíîâàíèÿì ìàòåìàòèêè. Â ýòîé ðàáîòå

áûëà óñîâåðøåíñòâîâàíà àêñèîìàòèêà àðèôìåòèêè è íà åå îñíîâå

ôîðìàëèçîâàíû íåêîòîðûå äðóãèå ðàçäåëû ìàòåìàòèêè. Îäíàêî, íå

âñå îáñòîÿëî ãëàäêî íà ýòîì ïóòè. Òàê, íàïðèìåð, îêàçàëîñü

íåâîçìîæíûì âûâåñòè èç ÷èñòî ëîãè÷åñêèõ àêñèîì ñóùåñòâîâàíèå

áåñêîíå÷íûõ ìíîæåñòâ. Îòêðûòèå ïàðàäîêñîâ, ñâÿçàííûõ ñ îñíîâíûìè

ïîíÿòèÿìè òåîðèè ìíîæåñòâ, åùå áîëüøå ïîêîëåáàëî óâåðåííîñòü

ìàòåìàòèêîâ â äîñòèæåíèè ïîñòàâëåííîé öåëè. Îñíîâíàÿ ïðîáëåìà

çàêëþ÷àëàñü â äîêàçàòåëüñòâå íåïðîòèâîðå÷èâîñòè âûáðàííîé ñèñòåìû

àêñèîì. Ä. Ãèëüáåðò ïîñòàâèë ïåðåä ñîáîé çàäà÷ó ðàçâèòèÿ òåîðèè

äîêàçàòåëüñòâ. Çàñëóãà Ãèëüáåðòà ñîñòîèò â òîì, ÷òî îí óêàçàë ïóòü

äëÿ èññëåäîâàíèÿ íåïðîòèâîðå÷èâîñòè àêñèîìàòè÷åñêèõ ñèñòåì.

Íåïðîòèâîðå÷èâîñòü òåîðèè îçíà÷àåò, ÷òî â íåé íåëüçÿ âûâåñòè

ïðîòèâîðå÷èå. Òîãäà äëÿ äîêàçàòåëüñòâà íåïðîòèâîðå÷èâîñòè ôîðìàëü-

íîé òåîðèè íóæíî äîêàçàòü íåâûâîäèìîñòü â íåé êàêèõ-ëèáî óòâåðæäå-

íèé. Òàêèì îáðàçîì ìàòåìàòè÷åñêàÿ òåîðèÿ, íåïðîòèâîðå÷èâîñòü

êîòîðîé íóæíî äîêàçàòü, ñòàíîâèòñÿ îáúåêòîì èçó÷åíèÿ äðóãîé

ìàòåìàòè÷åñêîé íàóêè, êîòîðóþ Ãèëüáåðò íàçâàë ìåòàìàòåìàòèêîé

èëè òåîðèåé äîêàçàòåëüñòâ. Äâóõòîìíàÿ ìîíîãðàôèÿ Ä. Ãèëüáåðòà è

Ï. Áåðíàéñà «Îñíîâàíèÿ ìàòåìàòèêè. Ëîãè÷åñêèå èñ÷èñëåíèÿ è ôîðìà-

ëèçàöèÿ àðèôìåòèêè», âûøåäøàÿ â 30-õ ã.ã., ïîäâåëà èòîã ïðîöåññó

ñòàíîâëåíèÿ ìàòåìàòè÷åñêîé ëîãèêè êàê ñàìîñòîÿòåëüíîé ìàòåìàòè-

÷åñêîé äèñöèïëèíû.

Â 1930 ã. àâñòðèéñêèé ìàòåìàòèê Êóðò Ã¸äåëü äîêàçàë òåîðåìó î

ïîëíîòå èñ÷èñëåíèÿ ïðåäèêàòîâ, ñîãëàñíî êîòîðîé ìíîæåñòâî ëîãè÷åñêè

îáùåçíà÷èìûõ ôîðìóë ëîãèêè ïðåäèêàòîâ ñîâïàäàåò ñ ìíîæåñòâîì

òåîðåì èñ÷èñëåíèÿ ïðåäèêàòîâ. Îäíàêî óæå â 1931 ã. ïîÿâèëàñü äðóãàÿ

ðàáîòà Ã¸äåëÿ: «Î ôîðìàëüíî íåðàçðåøèìûõ ïðåäëîæåíèÿõ Principia

Mathematica è ðîäñòâåííûõ ñèñòåì». Äîêàçàííàÿ â íåé òåîðåìà î

íåïîëíîòå ôîðìàëüíîé àðèôìåòèêè ïðèçíàíà îäíèì èç âåëè÷àéøèõ

äîñòèæåíèé ñîâðåìåííîé ìàòåìàòèêè. Ã¸äåëþ â ýòî âðåìÿ áûëî 25ëåò.

Ñîãëàñíî ýòîé òåîðåìå, åñëè ôîðìàëüíàÿ ñèñòåìà, ñîäåðæàùàÿ àðèô-

ìåòèêó, íåïðîòèâîðå÷èâà, òî â íåé ñóùåñòâóþò èñòèííûå, íî íå

âûâîäèìûå èç àêñèîì ýòîé òåîðèè ïðåäëîæåíèÿ. Îòñþäà ñëåäóåò, ÷òî

ôîðìàëüíàÿ òåîðèÿ, ñðåäñòâàìè êîòîðîé ìîæíî ïîñòðîèòü

àðèôìåòèêó, ñóùåñòâåííî íåïîëíà, ò.å. íèêàêîå ðàñøèðåíèå åå ñèñòåìû

àêñèîì íå ñäåëàåò åå ïîëíîé, òàê êàê â íîâîé ñèñòåìå âñå ðàâíî íàé-

äóòñÿ èñòèííûå, íî íå âûâîäèìûå åå ñðåäñòâàìè ïðåäëîæåíèÿ. Äðóãîé

ðåçóëüòàò Ã¸äåëÿ çàêëþ÷àåòñÿ â òîì, ÷òî íåëüçÿ äîêàçàòü íåïðîòèâî-

ðå÷èâîñòü ôîðìàëüíîé òåîðèè ïåðâîãî ïîðÿäêà, âêëþ÷àþùåé ôîðìàëü-

íóþ àðèôìåòèêó, ñðåäñòâàìè, âûðàçèìûìè â ýòîé òåîðèè. Äëÿ

äîêàçàòåëüñòâà íåïðîòèâîðå÷èâîñòè íåîáõîäèìî ïðèâëå÷åíèå ñðåäñòâ,

âûõîäÿùèõ çà ðàìêè ôîðìàëüíîé àðèôìåòèêè. Òàêèå äîêàçàòåëüñòâà

íåïðîòèâîðå÷èâîñòè àðèôìåòèêè áûëè ïîëó÷åíû ïîçæå Ã. Ãåíöåíîì è

Ï.Ñ.Íîâèêîâûì. Ðåçóëüòàòû, ïîëó÷åííûå Ã¸äåëåì, ïîêàçàëè, ÷òî âîç-

ìîæíîñòè àêñèîìàòè÷åñêîãî ìåòîäà îïðåäåëåííûì îáðàçîì

îãðàíè÷åíû, ïðè÷åì îãðàíè÷åíèÿ òàêîâû, ÷òî äàæå àðèôìåòèêà íàòó-

ðàëüíûõ ÷èñåë íå ìîæåò áûòü ïîëíîñòüþ àêñèîìàòèçèðîâàíà. Îòêðû-

òèÿ Ã¸äåëÿ ðàçðóøèëè íàäåæäû ëîãèêîâ î ïîëíîé ôîðìàëèçàöèè ìàòå-

ìàòèêè. Îäíàêî ðàáîòû Ã¸äåëÿ îáîãàòèëè ìàòåìàòè÷åñêóþ íàóêó

ñîâåðøåííî íîâûìè ìåòîäàìè ðàññóæäåíèé è èìåëè îãðîìíîå çíà÷åíèå

äëÿ ðàçâèòèÿ ôèëîñîôèè íàóêè. Ðåçóëüòàòû Ã¸äåëÿ ïîêàçûâàþò, ÷òî

âîçìîæíîñòè íàøåãî ìûøëåíèÿ íå ñâîäÿòñÿ ê ïîëíîñòüþ ôîðìàëè-

çóåìûì ïðîöåäóðàì äåäóêòèâíûõ ðàññóæäåíèé. ×åëîâå÷åñêîå ìûøëåíèå

è ñïîñîáû ÷åëîâå÷åñêèõ ðàññóæäåíèé ãîðàçäî áîãà÷å, è äëÿ èõ ôîðìàëè-

çàöèè (äàæå ÷àñòè÷íîé), íåîáõîäèìî ïðèâëå÷åíèå ñðåäñòâ, âûõîäÿùèõ

çà ðàìêè äåäóêòèâíûõ ðàññóæäåíèé.

14.1. Ñâîéñòâà èñ÷èñëåíèÿ

ïðåäèêàòîâ ïåðâîãî ïîðÿäêà

Ðàññìîòðèì ñâîéñòâà èñ÷èñëåíèÿ ïðåäèêàòîâ: íåïðîòèâîðå÷è-

âîñòü è ïîëíîòó. Íàïîìíèì, ÷òî èñ÷èñëåíèå ïðåäèêàòîâ ïåðâîãî

ïîðÿäêà ñîäåðæèò òîëüêî ëîãè÷åñêèå àêñèîìû è íå ñîäåðæèò ñîá-

ñòâåííûõ àêñèîì.

Ñâîéñòâà òåîðèé ïåðâîãî ïîðÿäêà

244 245Ñâîéñòâà òåîðèé ïåðâîãî ïîðÿäêàÃëàâà 14

Òåîðåìà 14.1. Âñÿêîå èñ÷èñëåíèå ïðåäèêàòîâ ïåðâîãî ïîðÿäêà

íåïðîòèâîðå÷èâî.

Äîêàçàòåëüñòâî. Äëÿ ëþáîé ïðîèçâîëüíîé ôîðìóëû A ââåäåì

ïðåîáðàçîâàíèå h(A): â A îïóñêàþòñÿ âñå êâàíòîðû è òåðìû âìåñòå

ñ ñîîòâåòñòâóþùèìè ñêîáêàìè è çàïÿòûìè. Ðåçóëüòàò ïðåîáðàçîâà-

íèÿ h âñåãäà åñòü ïðîïîçèöèîíàëüíàÿ ôîðìà, â êîòîðîé ðîëü

ïðîïîçèöèîíàëüíûõ áóêâ èãðàþò ïðåäèêàòíûå ñèìâîëû. Íàïðèìåð,

h(¬∀x(P(x,y)→∃yQ(y)) = ¬P→Q. Î÷åâèäíî, ÷òî h(¬A) = ¬h(A)

è h(A→B) = h(A) → h(B). Ïðè ïðèìåíåíèè ïðåîáðàçîâàíèÿ h(A)

ê ñõåìàì àêñèîì À1  À3? òåîðèè Ê îíè íå èçìåíÿòñÿ. Ñõåìà àêñè-

îìû À4: ∀õÀ(õ) → À(y) ïðåîáðàçóåòñÿ â òàâòîëîãèþ À → À, à

ñõåìà À5: ∀õ(À → Â(õ)) → (À → ∀õÂ(õ))  â òàâòîëîãèþ

(À→Â)→(À →Â). Åñëè h(A) è h(A→B)  òàâòîëîãèè, òî è

h(B) òîæå òàâòîëîãèÿ, à åñëè h(A) òàâòîëîãèÿ, òî è h(∀õÀ(õ))

òàâòîëîãèÿ, òàê êàê ðåçóëüòàòû ïðèìåíåíèÿ ïðåîáðàçîâàíèÿ h ê A

è ∀õÀ(õ) ñîâïàäàþò. Ñëåäîâàòåëüíî, åñëè À åñòü òåîðåìà òåîðèè Ê,

òî h(A) åñòü òàâòîëîãèÿ. Åñëè áû ñóùåñòâîâàëà ôîðìóëà Â â K òàêàÿ,

÷òî |

Â è |

¬Â, òî îáà âûðàæåíèÿ h(B) è h(¬B) áûëè áû òàâòî-

ëîãèÿìè, ÷òî íåâîçìîæíî. Òàêèì îáðàçîì, Ê íåïðîòèâîðå÷èâî.

Òåîðåìà 14.2. Âî âñÿêîì èñ÷èñëåíèè ïðåäèêàòîâ ïåðâîãî ïîðÿä-

êà âñÿêàÿ òåîðåìà ÿâëÿåòñÿ ëîãè÷åñêè îáùåçíà÷èìîé.

Äîêàçàòåëüñòâî. Àêñèîìû, çàäàâàåìûå ñõåìàìè À1  À3, ÿâëÿ-

åòñÿ ëîãè÷åñêè îáùåçíà÷èìûìè ôîðìóëàìè, òàê êàê êàæäàÿ èç íèõ

ÿâëÿåòñÿ òàâòîëîãèåé ëîãèêè âûñêàçûâàíèé. Ñõåìû àêñèîì À4, À5

ÿâëÿþòñÿ ëîãè÷åñêè îáùåçíà÷èìûìè â ëîãèêå ïðåäèêàòîâ,

ñëåäîâàòåëüíî, ëþáàÿ àêñèîìà, ïîðîæäåííàÿ ýòèìè ñõåìàìè, îáùå-

çíà÷èìà. Ïðàâèëà âûâîäà ÌÐ è Gen ñîõðàíÿþò ñâîéñòâî îáùåçíà÷è-

ìîñòè, ñëåäîâàòåëüíî, âñÿêàÿ òåîðåìà èñ÷èñëåíèÿ ïðåäèêàòîâ ëîãè-

÷åñêè îáùåçíà÷èìà.

Òåîðåìà 14.2 ïðåäñòàâëÿåò ñîáîé ëèøü ïîëîâèíó òåîðåìû î ïîë-

íîòå èñ÷èñëåíèÿ ïðåäèêàòîâ: íåîáõîäèìî åùå äîêàçàòü îáðàòíóþ

òåîðåìó î òîì, ÷òî âñÿêàÿ ëîãè÷åñêè îáùåçíà÷èìàÿ ôîðìóëà òåîðèè

ïðåäèêàòîâ ÿâëÿåòñÿ òåîðåìîé èñ÷èñëåíèÿ ïðåäèêàòîâ. Ýòà òåîðåìà

áûëà äîêàçàíà Ã¸äåëåì â 1930 ã. è èçâåñòíà êàê òåîðåìà î ïîëíîòå.

Çäåñü ìû ïðèâåäåì åå áåç äîêàçàòåëüñòâà.

Òåîðåìà 14.3. (Òåîðåìà Ã¸äåëÿ î ïîëíîòå). Âî âñÿêîì èñ÷èñëå-

íèè ïðåäèêàòîâ ïåðâîãî ïîðÿäêà òåîðåìàìè ÿâëÿåòñÿ òå è òîëüêî

òå ôîðìóëû, êîòîðûå ëîãè÷åñêè îáùåçíà÷èìû.

Äëÿ èñ÷èñëåíèÿ âûñêàçûâàíèé òåîðåìà î ïîëíîòå òåîðèè L ïðè-

âîäèò ê ðåøåíèþ ïðîáëåìû ðàçðåøèìîñòè: ñ ïîìîùüþ ïîñòðîåíèÿ

òàáëèöû èñòèííîñòè äëÿ ëþáîé ôîðìóëû èñ÷èñëåíèÿ âûñêàçûâà-

íèé ìîæíî ïðîâåðèòü, ÿâëÿåòñÿ îíà òåîðåìîé èëè íåò. Îäíàêî äëÿ

òåîðèé ïåðâîãî ïîðÿäêà íåëüçÿ ïîëó÷èòü ðàçðåøàþùóþ ïðîöåäóðó

äëÿ äîêàçàòåëüñòâà îáùåçíà÷èìîñòè, èëè, ÷òî òî æå ñàìîå, äëÿ âûâî-

äèìîñòè ôîðìóëû èç ìíîæåñòâà ãèïîòåç. Ýòîò ðåçóëüòàò, à òàêæå

íåêîòîðûå äðóãèå ðåçóëüòàòû, áóäóò ðàññìîòðåíû â ãëàâå 15.

14.2. Ôîðìàëüíàÿ àðèôìåòèêà

14.2.1. Ñèñòåìà àêñèîì Ïåàíî

Èìåííî ñ àðèôìåòèêè íàòóðàëüíûõ ÷èñåë áûëè íà÷àòû ïîïûòêè

ôîðìàëèçàöèè ìàòåìàòèêè. Ïåðâîå, ïîëóàêñèîìàòè÷åñêîå ïîñòðîå-

íèå ýòîé äèñöèïëèíû áûëî ïðåäëîæåíî Ïåàíî è óñîâåðøåíñòâîâàíî

Äåäåêèíäîì â 1901 ã. Ýòó ñèñòåìó ìîæíî ñôîðìóëèðîâàòü ñëåäó-

þùèì îáðàçîì.

(Ð1) 0 åñòü íàòóðàëüíîå ÷èñëî.

(Ð2) Äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà x ñóùåñòâóåò äðóãîå íàòó-

ðàëüíîå ÷èñëî, êîòîðîå îáîçíà÷àåòñÿ x′ è íàçûâàåòñÿ (íåïîñðåä-

ñòâåííî) ñëåäóþùåå çà x.

(Ð3) 0 ≠ x′ äëÿ ëþáîãî íàòóðàëüíîãî ÷èñëà x.

(Ð4) Åñëè x′=y′, òî x=y.

(Ð5) Åñëè Q åñòü ñâîéñòâî, êîòîðûì îáëàäàþò îäíè è, ìîæåò

áûòü, íå îáëàäàþò äðóãèå íàòóðàëüíûå ÷èñëà, è åñëè

(I) íàòóðàëüíîå ÷èñëî 0 îáëàäàåò ñâîéñòâîì Q è

(II) äëÿ âñÿêîãî íàòóðàëüíîãî ÷èñëà x èç òîãî, ÷òî x îáëàäàåò ñâîé-

ñòâîì Q, ñëåäóåò, ÷òî è íàòóðàëüíîå ÷èñëî x′ îáëàäàåò ñâîéñòâîì Q, òî

ñâîéñòâîì Q îáëàäàþò âñå íàòóðàëüíûå ÷èñëà (ïðèíöèï èíäóêöèè).

Ýòèõ àêñèîì, âìåñòå ñ íåêîòîðûì ôðàãìåíòîì òåîðèè ìíîæåñòâ,

äîñòàòî÷íî äëÿ ïîñòðîåíèÿ íå òîëüêî àðèôìåòèêè, íî è òåîðèè

ðàöèîíàëüíûõ, âåùåñòâåííûõ è êîìïëåêñíûõ ÷èñåë. Ïîýòîìó

ìîæíî ïîñòðîèòü òåîðèþ ïåðâîãî ïîðÿäêà S, îñíîâàííóþ íà ñèñòåìå

àêñèîì Ïåàíî, êîòîðàÿ äîñòàòî÷íà äëÿ âûâîäà âñåõ îñíîâíûõ

ðåçóëüòàòîâ ýëåìåíòàðíîé àðèôìåòèêè.

14.2.2. Ôîðìàëüíàÿ òåîðèÿ S

Îïðåäåëåíèå 14.1. Òåîðèÿ ïåðâîãî ïîðÿäêà S èìååò åäèí-

ñòâåííóþ ïðåäèêàòíóþ áóêâó A

: t=s, åäèíñòâåííóþ ïðåäìåò-

íóþ êîíñòàíòó a

= 0 è òðè ôóíêöèîíàëüíûå áóêâû f

(t): t′,

(t,s): t+s, f

(t,s): t⋅s, ãäå t è s - òåðìû. Ñîáñòâåííûå àêñèîìû

òåîðèè S:

S1. x

=x

→ (x

=x

→ x

=x

);

S2. x

=x

→ x

'=x

S3. 0 ≠ x

′;

S4. x

'=x

' → x

=x

;

S5. x

+ 0=x

;

246 247Ñâîéñòâà òåîðèé ïåðâîãî ïîðÿäêàÃëàâà 14

S6. x

+ x

'=(x

+ x

)′;

S7. x

⋅0=0;

S8. (x

⋅x

')=(x

⋅x

) + x

;

S9. A(0) → (∀x(A(x) → A(x′)) → ∀xA(x)), ãäå A(x)  ïðîèçâîëü-

íàÿ ôîðìóëà òåîðèè S.

Àêñèîìû S1  S8 ÿâëÿþòñÿ êîíêðåòíûìè ôîðìóëàìè, â òî

âðåìÿ, êàê S9 ïðåäñòàâëÿåò ñîáîé ñõåìó àêñèîì, ïîðîæäàþùóþ

áåñêîíå÷íîå ìíîæåñòâî àêñèîì. Ïðè ýòîì ñõåìà àêñèîì S9, êîòîðàÿ

íàçûâàåòñÿ ïðèíöèïîì ìàòåìàòè÷åñêîé èíäóêöèè, íå ñîîòâåòñòâóåò

ïîëíîñòüþ àêñèîìå (Ð5) ñèñòåìû àêñèîì Ïåàíî, ïîñêîëüêó â (Ð5)

ñâîéñòâà íàòóðàëüíûõ ÷èñåë íå îïðåäåëÿþòñÿ êîíñòðóêòèâíî, à â

S îíè îïðåäåëÿþòñÿ ôîðìóëàìè òåîðèè.

Ñ ïîìîùüþ MP èç ñõåìû àêñèîì S9 ìîæíî ïîëó÷èòü ñëåäóþùåå

ïðàâèëî èíäóêöèè:

A(0), ∀x(A(x)→A(x′) | ∀xA(x).

Èíòåðïðåòàöèÿ òåîðèè S, â êîòîðîé:

(a) ìíîæåñòâî âñåõ íåîòðèöàòåëüíûõ öåëûõ ÷èñåë ñëóæèò

îáëàñòüþ îïðåäåëåíèÿ,

(b) öåëîå ÷èñëî 0 èíòåðïðåòèðóåò ñèìâîë 0,

èíòåðïðåòèðóåò ôóíêöèþ ′ (ò.å. ôóíêöèîíàëüíóþ áóêâó f

(t)),

(d) îáû÷íûå ñëîæåíèå è óìíîæåíèå èíòåðïðåòèðóþò ôóíêöèè

+ è ⋅,

(e) ïðåäèêàòíàÿ áóêâà A

èíòåðïðåòèðóåòñÿ îòíîøåíèåì òîæ-

äåñòâà =, íàçûâàåòñÿ ñòàíäàðòíîé ìîäåëüþ òåîðèè S.

14.3. Ïðèìèòèâíî ðåêóðñèâíûå

è ðåêóðñèâíûå ôóíêöèè

14.3.1. Ïðèìèòèâíî ðåêóðñèâíûå ôóíêöèè

Îïðåäåëåíèå 14.2. Àðèôìåòè÷åñêèìè ôóíêöèÿìè íàçûâàþòñÿ

ôóíêöèè, ó êîòîðûõ îáëàñòü îïðåäåëåíèÿ è ìíîæåñòâî çíà÷åíèé

ñîñòîÿò èç íàòóðàëüíûõ ÷èñåë, à àðèôìåòè÷åñêèì îòíîøåíèåì

íàçûâàþòñÿ îòíîøåíèÿ, çàäàííûå íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë.

Òàê, íàïðèìåð, óìíîæåíèå åñòü àðèôìåòè÷åñêàÿ ôóíêöèÿ ñ äâó-

ìÿ àðãóìåíòàìè, à âûðàæåíèå x+y<z îïðåäåëÿåò àðèôìåòè÷åñêîå

îòíîøåíèå ñ òðåìÿ àðãóìåíòàìè.

Îïðåäåëåíèå 14.3.

(1). Ñëåäóþùèå ôóíêöèè íàçûâàþòñÿ èñõîäíûìè ôóíêöèÿìè.

(I) Íóëü-ôóíêöèÿ: Z(x)=0 äëÿ êàæäîãî x.

(II) Ïðèáàâëåíèå åäèíèöû (ñëåäóþùèé çà): N(x)=x + 1 äëÿ

êàæäîãî x.

(III) Ïðîåêòèðóþùèå ôóíêöèè: U

, ..., x

)=x

ïðè âñåõ x

,...,x

(i=1,..., n; n=1, 2,...).

(2). Ñëåäóþùèå äâà ïðàâèëà: ïîäñòàíîâêà è ïðèìèòèâíàÿ ðåêóð-

ñèÿ,  ñëóæàò äëÿ ïîëó÷åíèÿ íîâûõ ôóíêöèé, èñõîäÿ èç óæå

èìåþùèõñÿ.

(IV) Ïîäñòàíîâêà. Ãîâîðÿò, ÷òî ôóíêöèÿ f ïîëó÷åíà ñ ïîìîùüþ

ïîäñòàíîâêè èç ôóíêöèé g(y

,...,y

), h

,...,x

), , h

,...,x

åñëè f(x

,..., x

)=g(h

,..., x

),..., h

,..., x

)).

(V) Ñõåìà ïðèìèòèâíîé ðåêóðñèè. Ôóíêöèÿ f ïîëó÷åíà èç

ôóíêöèé g è h ñ ïîìîùüþ ðåêóðñèè, åñëè

f(x

,..., x

, 0)=g(x

,..., x

f(x

,..., x

, y + 1)=h(x

,..., x

, y, f(x

,..., x

, y)).

Ïðè ýòîì èñêëþ÷àåòñÿ ñëó÷àé n=0, äëÿ êîòîðîãî îòäåëüíî:

f(0)=k (ãäå k  ôèêñèðîâàííîå öåëîå íåîòðèöàòåëüíîå ÷èñëî),

f(y + 1)=h(y, f(y)).

Çàìåòèì, ÷òî ôóíêöèÿ f âïîëíå îïðåäåëåíà: çíà÷åíèå f(x

,...,x

,0)

îïðåäåëÿåòñÿ èç ïåðâîãî ðàâåíñòâà, à åñëè ìû óæå çíàåì çíà÷åíèå

f(x

,..., x

, y), òî èç âòîðîãî ðàâåíñòâà ìû ìîæåì íàéòè çíà÷åíèå

f(x

,..., x

, y + 1).

(3). Ôóíêöèÿ f íàçûâàåòñÿ ïðèìèòèâíî ðåêóðñèâíîé, åñëè îíà

ìîæåò áûòü ïîëó÷åíà èç èñõîäíûõ ôóíêöèé ñ ïîìîùüþ êîíå÷-

íîãî ÷èñëà ïîäñòàíîâîê (IV) è ðåêóðñèé (V), ò.å. åñëè ñóùåñòâóåò

òàêàÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ôóíêöèé f

,...,f

, ÷òî f

=f

è äëÿ êàæäîãî i, 0≤i≤n, ôóíêöèÿ f

ëèáî èñõîäíàÿ, ëèáî ìîæåò

áûòü ïîëó÷åíà èç íåêîòîðûõ ïðåäøåñòâóþùèõ åé â ýòîé ïîñëåäî-

âàòåëüíîñòè ôóíêöèé ñ ïîìîùüþ ïðèìåíåíèÿ ïðàâèëà (IV)

(ïîäñòàíîâêè) èëè ïðàâèëà (V) (ðåêóðñèè).

Òåîðåìà 14.4. Ñëåäóþùèå ôóíêöèè ÿâëÿþòñÿ ïðèìèòèâíî

ðåêóðñèâíûìè.

(a) x + y (ñëîæåíèå).

Äîêàçàòåëüñòâî.

Ïî ïðàâèëó ðåêóðñèè (V):

x + 0=x, ò.å. f(x, 0)=U

(x)=x.

x+(y+1)=N(x+y), ò.å. f(x,y+1)=N(f(x,y)).

(b) x ⋅ y (óìíîæåíèå).

Äîêàçàòåëüñòâî.

x ⋅ 0=0, ò.å. g(x,0)=Z(x).

x ⋅ (y+1)=(x ⋅ y)+x, ò.å. g(x,y+1)=f(x, g(x,y)), ãäå f åñòü

ôóíêöèÿ ñëîæåíèÿ.

248 249Ñâîéñòâà òåîðèé ïåðâîãî ïîðÿäêàÃëàâà 14

(âîçâåäåíèå â ñòåïåíü).

Äîêàçàòåëüñòâî.

=1, x

y+1

=(x

) ⋅ x.

(d) δ(x)=x1, åñëè x > 0, è δ(x)=0, åñëè õ=0 (âû÷èòàíèå

åäèíèöû).

Äîêàçàòåëüñòâî.

δ(0)=0, δ(y + 1)=y.

(e) x ÷ y=xy, åñëè x ≥ y, è x ÷ y=0, åñëè x<y (îãðàíè÷åííàÿ

ðàçíîñòü).

Äîêàçàòåëüñòâî.

x ÷ 0=x, x ÷ (y + 1)=δ(x ÷ y).

(f) |xy|=xy, åñëè x ≥ y, |xy|=yx, åñëè x < y (ìîäóëü

ðàçíîñòè).

Äîêàçàòåëüñòâî.

|xy|=(x ÷ y) + (y ÷ x) (ïîäñòàíîâêà).

(g) sg(x)=0, åñëè x=0, sg(x)=1, åñëè x ≠ 0 (ñèãíóì x).

Äîêàçàòåëüñòâî.

sg(0)=0, sg(y + 1)=1.

(h) unsg(x)=1, åñëè x=0, unsg(x)=0, åñëè x ≠ 0;

Äîêàçàòåëüñòâî.

unsg(x)=1 ÷ sg(x).

(i) x! (ôàêòîðèàë x).

Äîêàçàòåëüñòâî.

0!=1, (y + 1)!=(y!) ⋅ (y + 1).

(j) min(x, y)=íàèìåíüøåìó èç ÷èñåë x è y;

Äîêàçàòåëüñòâî.

min(x, y)=x ÷ (x ÷ y).

(k) min(x

,..., x

Äîêàçàòåëüñòâî.

Ïðåäïîëîæèì, ÷òî ôóíêöèÿ min(x

,..., x

)  ïðèìèòèâíî ðåêóðñèâíàÿ.

Äëÿ min(x

,...,x

n+1

) èìååì min(x

,...,x

n+1

)=min(min(x

,...,x

),x

n+1

(l) max(x, y)=íàèáîëüøåìó èç ÷èñåë x è y.

Äîêàçàòåëüñòâî.

max(x,y)=y+(x÷y).

(m) max(x

,..., x

);

Äîêàçàòåëüñòâî.

max(x

,..., x

n+1

)=max(max(x

,..., x

), x

n+1

(n) rm(x, y)=îñòàòêó îò äåëåíèÿ y íà x, åñëè x ≠ 0, è y,

åñëè x=0.

Äîêàçàòåëüñòâî.

rm(x, 0)=0, rm(x, y + 1)=N(rm(x, y)) ⋅ sg(|x  N(rm(x, y))|).

(o) qt(x, y)=÷àñòíîìó îò äåëåíèÿ y íà x.

Äîêàçàòåëüñòâî.

qt(x, 0)=0, qt(x, y + 1)=qt(x, y) + unsg(|x  N(rm(x, y))|).

Îïðåäåëåíèÿ (îãðàíè÷åííûõ ñóìì è ïðîèçâåäåíèé).

14.4. ∑

y<z

f(x

, , x

, y)= 0, åñëè z=0,

∑

y<z

f(x

,, x

, y)= f(x

, , x

, 0) +  + f(x

,, x

, z  1),

åñëè z > 0.

14.5. ∑



≤



z

f(x

,, x

, y)=∑

y<z+1

f(x

,, x

, y).

14.6. ∏

y<z

f(x

,, x

, y)=1, åñëè z=0,

∏

y<z

f(x

,, x

, y)=f(x

,, x

, 0) ⋅  ⋅ f(x

,, x

, z  1),

åñëè z > 0.

14.7. ∏



≤



f(x

,, x

, y)=∏

y<z+1

f(x

,, x

, y).

Ýòè îãðàíè÷åííûå ñóììû è ïðîèçâåäåíèÿ ÿâëÿþòñÿ ôóíêöèÿìè

àðãóìåíòîâ x

,..., x

, z. Ñóììû è ïðîèçâåäåíèÿ, îãðàíè÷åííûå ñ äâóõ

ñòîðîí, ìîæíî òåïåðü îïðåäåëèòü ÷åðåç ââåäåííûå òîëüêî ÷òî îãðà-

íè÷åííûå ñóììû è ïðîèçâåäåíèÿ, íàïðèìåð:

∑

u<y<v

f(x

,, x

, y)=f(x

,, x

, u + 1) +  + f(x

,, x

, v  1)=

=∑

y<(y÷u)÷1

f(x

,, x

, y + u + 1).

14.3.2. Ðåêóðñèâíûå ôóíêöèè

Ââåäåì åùå îäíî ïðàâèëî ïîëó÷åíèÿ íîâûõ ôóíêöèé.

(VI)

µµ

µ-îïåðàòîð (îïåðàòîð ìèíèìèçàöèè). Ïóñòü ôóíêöèÿ

g(x

,..., x

, y) òàêîâà, ÷òî äëÿ ëþáûõ x

,..., x

ñóùåñòâóåò ïî êðàéíåé

ìåðå îäíî çíà÷åíèå y, ïðè êîòîðîì g(x

,..., x

, y)=0. Îáîçíà÷èì

÷åðåç µy(g(x

,..., x

, y)=0) íàèìåíüøåå çíà÷åíèå y, ïðè êîòîðîì

g(x

,..., x

, y)=0. Òîãäà ôóíêöèÿ f ïîëó÷åíà èç ôóíêöèè g ñ ïî-

ìîùüþ µ-îïåðàòîðà, åñëè f(x

,...,x

)=µy(g(x

,...,x

,y)=0).

Ïðè ïðèìåíåíèè µ-îïåðàòîðà ìîæíî èñïîëüçîâàòü íå òîëüêî

îòíîøåíèå ðàâåíñòâà, íî è äðóãèå îòíîøåíèÿ: <, ≤, >, ≥. Âîîáùå,

äëÿ âñÿêîãî îòíîøåíèÿ R(x

, ..., x

, y) áóäåì îáîçíà÷àòü ÷åðåç

µyR(x

,...,x

,y) òî íàèìåíüøåå çíà÷åíèå y, ïðè êîòîðîì R(x

,...,x

,y)

èñòèííî, åñëè âîîáùå òàêèå çíà÷åíèÿ ñóùåñòâóþò.

(4). Ôóíêöèÿ f íàçûâàåòñÿ ðåêóðñèâíîé, åñëè îíà ìîæåò áûòü

ïîëó÷åíà èç èñõîäíûõ ôóíêöèé ñ ïîìîùüþ êîíå÷íîãî ÷èñëà

ïðèìåíåíèé ïîäñòàíîâêè (IV), ðåêóðñèè (V) è µ-îïåðàòîðà (VI).

Ýòî ïîñëåäíåå îïðåäåëåíèå îòëè÷àåòñÿ îò îïðåäåëåíèÿ ïðèìè-

òèâíî ðåêóðñèâíîé ôóíêöèè ëèøü äîïîëíèòåëüíûì ðàçðåøåíèåì

ïðèìåíÿòü µ-îïåðàòîð. Ïîýòîìó âñÿêàÿ ïðèìèòèâíî ðåêóðñèâíàÿ

250 251Ñâîéñòâà òåîðèé ïåðâîãî ïîðÿäêàÃëàâà 14

ôóíêöèÿ ÿâëÿåòñÿ òàêæå è ðåêóðñèâíîé ôóíêöèåé. Îáðàòíîå, âïðî-

÷åì, íå âñåãäà âåðíî. (Â ëèòåðàòóðå âìåñòî òåðìèíà «ðåêóðñèâíûé»

èíîãäà óïîòðåáëÿåòñÿ òåðìèí «÷àñòè÷íî ðåêóðñèâíûé».)

Îïðåäåëåíèå 14.8. Îãðàíè÷åííûé µ-îïåðàòîð îïðåäåëèì òàê:

µy

y<z

R(x

,..., x

, y) ðàâíî íàèìåíüøåìó y òàêîìó, ÷òî y < z è

R(x

,..., x

, y) èñòèííî, åñëè òàêîå y ñóùåñòâóåò, è z â ïðîòèâíîì

ñëó÷àå.

Íåîãðàíè÷åííûé µ-îïåðàòîð (îïðåäåëåííûé â (VI) ) çàäàåò

ñëåäóþùóþ ñõåìó âû÷èñëåíèé n-ìåñòíîé ôóíêöèè ¦(x

,,x

). Äëÿ

ôèêñèðîâàííûõ çíà÷åíèé àðãóìåíòîâ x

,,x

íàõîäèòñÿ ðåøåíèå

óðàâíåíèÿ g(x

,,x

,y)=x

n+1

äëÿ y=0, 1, 2,  Íàèìåíüøåå çíà÷åíèå

y=b, äëÿ êîòîðîãî g(x

,,x

,b)=x

n+1

è åñòü çíà÷åíèå ôóíêöèè

f(x

,...,x

)=µy(g(x

,...,x

,y)=x

n+1

), ïîëó÷åííîé èç ôóíêöèè g ñ

ïîìîùüþ µ-îïåðàòîðà. Ýòîò ïðîöåññ íàõîæäåíèÿ çíà÷åíèÿ ôóíêöèè

ƒ áóäåò ïðîäîëæàòüñÿ áåñêîíå÷íî, åñëè: (1) çíà÷åíèå g(x

,...,x

,0)íå

îïðåäåëåíî; (2) çíà÷åíèÿ g(x

,...,x

,y) îïðåäåëåíû äëÿ y= 0, 1,,

b1, íî îòëè÷íû îò x

n+1

, à g(x

,...,x

,b)íå îïðåäåëåíî; (3) çíà÷åíèÿ

g(x

,...,x

,y) îïðåäåëåíû äëÿ âñåõ y, íî îòëè÷íû îò x

n+1

. Âî âñåõ

ýòèõ ñëó÷àÿõ âû÷èñëåíèÿ ïðîäîëæàþòñÿ áåñêîíå÷íî è çíà÷åíèå

ôóíêöèè ƒ(x

,,x

)

ñ÷èòàåòñÿ íåîïðåäåëåííûì. Òàêèì îáðàçîì,

ïðèìåíåíèå µ-îïåðàòîðà ïîçâîëÿåò ïîëó÷èòü ÷àñòè÷íî îïðåäåëåí-

íûå ôóíêöèè, ÷òî è îáúÿñíÿåò òåðìèí «÷àñòè÷íî ðåêóðñèâíûå»

ôóíêöèè. Ïðèìåíåíèå îãðàíè÷åííîãî µ-îïåðàòîðà ïîçâîëÿåò

îñòàíîâèòü ïðîöåññ âû÷èñëåíèé, ââåäÿ âåðõíþþ ãðàíèöó ïåðåáîðà

y<z, è äîîïðåäåëèòü ôóíêöèþ ƒ(x

,,x

), ïðèñâîèâ åé íåêîòîðîå

ïðîèçâîëüíîå çíà÷åíèå, íàïðèìåð, z.

µ-îïåðàòîð ÿâëÿåòñÿ óäîáíûì ñðåäñòâîì äëÿ ïîñòðîåíèÿ

îáðàòíûõ ôóíêöèé. Åñëè çàäàííàÿ ôóíêöèÿ g îäíîìåñòíà, òî ƒ(x)=

= g

1

(x)= µy(g(y)=x). Äëÿ ìíîãîìåñòíûõ ôóíêöèé çàïèñü g

1

íå

óïîòðåáëÿåòñÿ.

Ïðèìåðû.

1.Äëÿ ôóíêöèè sg(x) îáðàòíóþ ôóíêöèþ ìîæíî îïðåäåëèòü êàê

1

(x)=µx(sg(x)=1). Òîãäà sg

1

(x)=x, åñëè x=0, 1, è sg

1

(x)íå

îïðåäåëåíî, åñëè x>1.

2.Îïðåäåëèì ôóíêöèþ y=[z/x] (÷àñòíîå îò äåëåíèÿ z íà x) êàê ôóíê-

öèþ, îáðàòíóþ óìíîæåíèþ: z=y⋅x. Òîãäà y=µy



≤z

(|y⋅xz|=0),

ò.å. ýòî áóäåò íàèìåíüøåå çíà÷åíèå y, ïðè êîòîðîì ñóùåñòâóåò

ðåøåíèå óðàâíåíèÿ |y⋅xz|=0. Ôóíêöèÿ íå ïîëíîñòüþ îïðåäå-

ëåíà, òàê êàê íå êàæäûå äâà ÷èñëà äåëÿòñÿ äðóã íà äðóãà áåç îñòàòêà.

3.Ôóíêöèÿ y=[√x] (öåëàÿ ÷àñòü √x) ìîæåò áûòü îïðåäåëåíà ñ

ïîìîùüþ îãðàíè÷åííîãî µ-îïåðàòîðà êàê y=µy



≤



x

=x). Ýòà

ôóíêöèÿ òàêæå ÿâëÿåòñÿ ÷àñòè÷íî îïðåäåëåííîé.

Òåîðåìà 14.5. Åñëè f  ïðèìèòèâíî ðåêóðñèâíàÿ (èëè ðåêóðñèâ-

íàÿ) ôóíêöèÿ, òî îãðàíè÷åííûå ñóììû è ïðîèçâåäåíèÿ ýòîé

ôóíêöèè ÿâëÿþòñÿ òàêæå ïðèìèòèâíî ðåêóðñèâíûìè (èëè

ðåêóðñèâíûìè) ôóíêöèÿìè.

Äîêàçàòåëüñòâî.

Ïóñòü g(x

, , x

, z)= ∑

y<z

f(x

, , x

, y).

Òîãäà ìîæíî çàïèñàòü ðåêóðñèâíîå îïðåäåëåíèå:

g(x

,, x

, 0)= 0,

g(x

,, x

, z + 1)= g(x

,, x

, z)+ f(x

,, x

, z).

Åñëè h(x

,, x

, z)= ∑

y ≤ z

f(x

,, x

, y), òî èìååì â ðåçóëüòàòå

ïîäñòàíîâêè: h(x

,, x

, z)= g(x

,, x

, z+1).

Àíàëîãè÷íî ìîæíî ïîëó÷èòü ñîîòâåòñòâóþùèå âûðàæåíèÿ äëÿ

ñóìì è ïðîèçâåäåíèé, îãðàíè÷åííûõ ñ äâóõ ñòîðîí.

14.3.3. Ðåêóðñèâíûå îòíîøåíèÿ

Îïðåäåëåíèå 14.9. Õàðàêòåðèñòè÷åñêîé ôóíêöèåé îòíîøåíèÿ

R(x

,...,x

) íàçûâàåòñÿ ôóíêöèÿ C

,...,x

), çàäàâàåìàÿ

óñëîâèÿìè:







0, åñëè

(

,...,

)

(

,...,

)

1, åñëè

(

,...,

)

Rx x T

Cx x

Rx x F

Îïðåäåëåíèå 14.10. Îòíîøåíèå R(x

,..., x

) íàçûâàåòñÿ ïðèìè-

òèâíî ðåêóðñèâíûì (ðåêóðñèâíûì) îòíîøåíèåì, åñëè ïðèìèòèâ-

íî ðåêóðñèâíîé (ñîîòâåòñòâåííî ðåêóðñèâíîé) ÿâëÿåòñÿ åãî

õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ C

,...,x

Ïîñêîëüêó êàæäîìó îòíîøåíèþ ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå

ïðåäèêàò, ýòî îïðåäåëåíèå ÿâëÿåòñÿ òàêæå îïðåäåëåíèåì ïðèìèòèâ-

íî ðåêóðñèâíîãî (ðåêóðñèâíîãî) ïðåäèêàòà.

Ïðèìåðû.

1.Îòíîøåíèå x

=x

ïðèìèòèâíî ðåêóðñèâíî, òàê êàê åãî õàðàê-

òåðèñòè÷åñêàÿ ôóíêöèÿ ñîâïàäàåò ñ ôóíêöèåé sg(|x

x

|), êîòîðàÿ

ïðèìèòèâíî ðåêóðñèâíà, â ñèëó ïðåäëîæåíèé (f), (g) òåîðåìû 14.4.

2.Ïðèìèòèâíî ðåêóðñèâíàÿ ôóíêöèÿ unsg(x

÷ x

) ñëóæèò õàðàêòå-

ðèñòè÷åñêîé ôóíêöèåé îòíîøåíèÿ x

<x

, êîòîðîå, òàêèì îáðàçîì,

ïðèìèòèâíî ðåêóðñèâíî.

3.Îòíîøåíèå x

äåëèòñÿ íà x

áåç îñòàòêà) ïðèìèòèâíî ðåêóð-

ñèâíî, òàê êàê åãî õàðàêòåðèñòè÷åñêîé ôóíêöèåé ÿâëÿåòñÿ ïðèìè-

òèâíî ðåêóðñèâíàÿ ôóíêöèÿ sg(rm(x

, x

)).

4.Îòíîøåíèå Pr(x), ò.å. «x åñòü ïðîñòîå ÷èñëî», ïðèìèòèâíî ðåêóð-

ñèâíî, òàê êàê C

(x)=sg((D(x)÷2)+unsg(|x1|+unsg(|x0|)),

ãäå ôóíêöèÿ D(x) ðàâíà 1, åñëè x=0, è ÷èñëó äåëèòåëåé x, åñëè

252 253

x>0. Ôóíêöèÿ D(x) ïðèìèòèâíî ðåêóðñèâíà, òàê êàê D(x) =

=∑

y<x

unsg(rm(y, x)).

Òåîðåìà 14.6. Îòíîøåíèÿ, êîòîðûå ìîæíî ïîëó÷èòü èç ïðèìè-

òèâíî ðåêóðñèâíûõ (èëè ðåêóðñèâíûõ) ñ ïîìîùüþ ïðîïîçèöèî-

íàëüíûõ ñâÿçîê è îãðàíè÷åííûõ êâàíòîðîâ, òàêæå ïðèìèòèâíî

ðåêóðñèâíû (ñîîòâåòñòâåííî, ðåêóðñèâíû); ïðèìåíåíèå îãðàíè-

÷åííûõ µ-îïåðàòîðîâ µy

y<z

èëè µy

y≤z

ê ïðèìèòèâíî ðåêóðñèâíûì

(ðåêóðñèâíûì) îòíîøåíèÿì ïðèâîäèò ê ïðèìèòèâíî ðåêóð-

ñèâíûì (ðåêóðñèâíûì) ôóíêöèÿì.

Äîêàçàòåëüñòâî.

Ïóñòü îòíîøåíèÿ P(x

,, x

) è Q(x

,,x

) ïðèìèòèâíî ðåêóðñèâ-

íû (ðåêóðñèâíû). Ýòî îçíà÷àåò, ÷òî ïðèìèòèâíî ðåêóðñèâíûìè

(ðåêóðñèâíûìè) ÿâëÿþòñÿ èõ õàðàêòåðèñòè÷åñêèå ôóíêöèè C

. Òîãäà ïðèìèòèâíî ðåêóðñèâíûìè (ðåêóðñèâíûìè) ÿâëÿþòñÿ è

îòíîøåíèÿ: ¬P(x

,,x

) (åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ:

¬P

=1÷C

), P(x

,,x

)∨Q(x

,,x

) (õàðàêòåðèñòè÷åñêàÿ ôóíê-

öèÿ: C

P∨Q

=C

P

⋅C

), P(x

,,x

)&Q(x

,,x

) (õàðàêòåðèñòè÷åñêàÿ

ôóíêöèÿ: C

P&Q

=sg(C

P

+C

). Îòñþäà íåòðóäíî ïîëó÷èòü õàðàêòå-

ðèñòè÷åñêèå ôóíêöèè äëÿ ôîðìóë: R1=∀y

y<z

P(x

,,x

,y) è

R2=∃y

y<z

P(x

,,x

,y) ñ ïîìîùüþ îãðàíè÷åííîé ñóììû è

îãðàíè÷åííîãî ïðîèçâåäåíèÿ: C

R1

= sg(∑

y<z

,,x

,y)) è C

R2

=Π

y<z

,,x

,y).

Ïîêàæåì òåïåðü, ÷òî ïðèìåíåíèå îãðàíè÷åííîãî µ-îïåðàòîðà ê

ïðèìèòèâíî ðåêóðñèâíîìó (ðåêóðñèâíîìó) îòíîøåíèþ ïðèâîäèò

ê ïðèìèòèâíî ðåêóðñèâíîé (ðåêóðñèâíîé) ôóíêöèè.

Ôóíêöèÿ Π

u≤z

,,x

,u)=1 ïðè êàæäîì y, äëÿ êîòîðîãî

P(x

,,x

,u) ëîæíî ïðè âñåõ u≤y, è ïðèíèìàåò çíà÷åíèå 0 âñÿêèé

ðàç, êîãäà ñóùåñòâóåò òàêîå u≤y, ïðè êîòîðîì P(x

,,x

,u) èñòèííî

(ïî îïðåäåëåíèþ õàðàêòåðèñòè÷åñêîé ôóíêöèè). Ïîýòîìó, åñëè äëÿ

äàííîãî z ñóùåñòâóþò ÷èñëà y ìåíüøèå, ÷åì z, è òàêèå, ÷òî P(x

,,x

,y)

èñòèííî, òî çíà÷åíèå ôóíêöèè ∑

y<z

u≤y

,,x

,u)ðàâíî ÷èñëó

öåëûõ íåîòðèöàòåëüíûõ ÷èñåë, ìåíüøèõ, ÷åì íàèìåíüøåå èç òàêèõ

÷èñåë y. Â ïðîòèâíîì ñëó÷àå çíà÷åíèå ôóíêöèè ∑

y<z

u≤y

,,

,u)ðàâíî z. Íî ýòî çíà÷èò, ÷òî ∑

y<z

u≤y

,,x

,u)=

=µy

y<z

P(x

,,x

,y), ò.å. ôóíêöèÿ, ïîëó÷åííàÿ â ðåçóëüòàòå ïðèìåíå-

íèÿ îãðàíè÷åííîãî µ-îïåðàòîðà, ÿâëÿåòñÿ ïðèìèòèâíî ðåêóðñèâíîé

(ðåêóðñèâíîé).

14.3.4. Àðèôìåòè÷åñêèå ôóíêöèè è îòíîøåíèÿ â òåîðèè S

Ðàññìîòðèì âûðàçèòåëüíûå âîçìîæíîñòè òåîðèè S. Òåðìû 0, 0',

0'', 0''',  â äàëüíåéøåì áóäåì íàçûâàòü öèôðàìè è îáîçíà÷àòü æèð-

íûìè ñèìâîëàìè 0, 1, 2, 3,, è äëÿ ëþáîãî öåëîãî íåîòðèöàòåëüíîãî

÷èñëà n ñîîòâåòñòâóþùóþ öèôðó áóäåì îáîçíà÷àòü ÷åðåç n.

Îïðåäåëåíèå 14.11. Àðèôìåòè÷åñêîå îòíîøåíèå R(x

,...,x

)

íàçûâàåòñÿ âûðàçèìûì â òåîðèè S, åñëè ñóùåñòâóåò ôîðìóëà

A(x

,..., x

) òåîðèè S ñ n ñâîáîäíûìè ïåðåìåííûìè òàêàÿ, ÷òî

äëÿ ëþáûõ íàòóðàëüíûõ ÷èñåë k

,..., k

(1) åñëè R(k

,..., k

) èñòèííî, òî |

A(k

,..., k

(2) åñëè R(k

,..., k

) ëîæíî, òî |

¬A(k

,..., k

Òàê, íàïðèìåð, îòíîøåíèå ðàâåíñòâà ìåæäó íàòóðàëüíûìè

÷èñëàìè âûðàçèìî â S ôîðìóëîé x

=x

. Â ñàìîì äåëå, åñëè k

=k

òî òåðìû k

è k

ñîâïàäàþò, è òîãäà |

S

=k

. Àíàëîãè÷íî, åñëè

≠k

, òî |

S

≠k

. Â ñâîþ î÷åðåäü, ôîðìóëîé x

<x

âûðàçèìî â

S îòíîøåíèå «ìåíüøå». Åñëè k

<k

, òî ñóùåñòâóåò îòëè÷íîå îò

íóëÿ ÷èñëî n, òàêîå ÷òî k

=k

1

+n, è òîãäà |

S

=k

+n, à â ñèëó

(S3) è n≠0, |

S

n≠0. Ñëåäîâàòåëüíî, â S ìîæíî âûâåñòè ôîðìóëó

∃ω(k

=k

+ω&ω≠0), ò.å. k

<k

. Åñëè æå ¬(k

<k

), òî k

=k

èëè k

<k

, ïðè÷åì â ýòîì ïîñëåäíåì ñëó÷àå, òàê æå, êàê è äëÿ

ñëó÷àÿ k

<k

, äîêàçûâàåòñÿ |

S

<k

. Íàêîíåö, åñëè k

=k

, òî

|

S

=k

. Èòàê, â îáîèõ ñëó÷àÿõ |

≤k

è òîãäà, |

¬(k

<k

Áóäåì îáîçíà÷àòü ∃

xA(x) âûñêàçûâàíèå: «ñóùåñòâóåò

åäèíñòâåííîå x, òàêîå, ÷òî A(x) èñòèííî».

Îïðåäåëåíèå 14.12. Àðèôìåòè÷åñêàÿ ôóíêöèÿ f(x

,...,x

)

íàçûâàåòñÿ ïðåäñòàâèìîé â S, åñëè ñóùåñòâóåò ôîðìóëà

A(x

,...,x

n+1

) òåîðèè S ñî ñâîáîäíûìè ïåðåìåííûìè x

,...,x

n+1

òàêàÿ, ÷òî äëÿ ëþáûõ íàòóðàëüíûõ ÷èñåë k

,...,k

n+1

(1) åñëè f(k

,...,k

)=k

n+1

, òî |

S

A(k

,...,k

,k

n+1

(2) |

∃

n+1

A(k

,...,k

,x

n+1

Åñëè â ýòîì îïðåäåëåíèè óñëîâèå (2) çàìåíèòü óñëîâèåì

(2′) |

∃

n+1

A(x

,...,x

,x

n+1

òî ìû ïîëó÷èì îïðåäåëåíèå ñèëüíî ïðåäñòàâèìîé â S ôóíêöèè.

Çàìåòèì, ÷òî, â ñèëó ïðàâèë Gen è A4 èç (2′), ñëåäóåò (2). Ñëåäî-

âàòåëüíî, âñÿêàÿ ñèëüíî ïðåäñòàâèìàÿ ôóíêöèÿ ÿâëÿåòñÿ òàêæå

ïðåäñòàâèìîé ôóíêöèåé.

Ïðèìåðû.

1. Íóëü-ôóíêöèÿ Z(x)=0 ñèëüíî ïðåäñòàâèìà â S ñ ïîìîùüþ

ôîðìóëû x

=x

&x

=0. Â ñàìîì äåëå, åñëè Z(k

)=k

, òî k

=0 è

|k

=k

&0=0 ò. å. âûïîëíåí ïóíêò (1) îïðåäåëåíèÿ ñèëüíî ïðåä-

ñòàâèìîé ôóíêöèè. Êðîìå òîãî, î÷åâèäíî |∃

=x

&x

=0),

ò. å. âûïîëíåí è ïóíêò (2′) ýòîãî îïðåäåëåíèÿ.

2. Ôóíêöèÿ N(x)=x+1 ñèëüíî ïðåäñòàâèìà â S ôîðìóëîé x

=x

′.

Äåéñòâèòåëüíî, ïðè ëþáîì k

èç N(k

)=k

, ò.å. èç k

=k

+1, ñëåäó-

åò, ÷òî òåðìû k

è (k

)′ ñîâïàäàþò è ïîòîìó |k

=(k

)′. Êðîìå

òîãî, |∃

=x

′).

Ñâîéñòâà òåîðèé ïåðâîãî ïîðÿäêàÃëàâà 14

254 255

3. Ïðîåêòèðóþùàÿ ôóíêöèÿ U

,...,x

)=x

ñèëüíî ïðåäñòàâèìà

â S ñ ïîìîùüþ ôîðìóëû x

=x

&...&x

=x

&x

n+1

=x

. Åñëè

,...,k

)=k

n+1

, òî k

n+1

=k

è k

n+1

=k

. Ñëåäîâàòåëüíî,

|k

=k

&&k

=k

&k

n+1

=k

, è óñëîâèå (1) âûïîëíåíî. Êðîìå

òîãî, |∃

n+1

=x

&...&x

=x

&x

n+1

=x

), ò.å. âûïîëíåíî è

óñëîâèå (2′) îïðåäåëåíèÿ ñèëüíî ïðåäñòàâèìîé â S ôóíêöèè.

4. Ïðåäïîëîæèì, ÷òî ôóíêöèè g(x

,...,x

), h(x

,...,x

),..., h

,...,x

)

(ñèëüíî) ïðåäñòàâèìû â S ñîîòâåòñòâåííî ôîðìóëàìè B(x

,...,

,x

m+1

), A

,...,x

n+1

),..., A

,...,x

n+1

). Çàäàäèì íîâóþ ôóíêöèþ f

ðàâåíñòâîì f(x

,...,x

)=g(h

,...,x

),..., h

,...,x

)), ò.å. ôóíêöèÿ

f ïîëó÷åíà èç g, h

,...,h

ñ ïîìîùüþ ïîäñòàíîâêè. Ôóíêöèÿ f òàêæå

(ñèëüíî) ïðåäñòàâèìà â S, íàïðèìåð, ñ ïîìîùüþ ôîðìóëû

∃y

... ∃y

,..., x

, y

) & ... & A

,..., x

, y

) & B(y

,..., y

,x

n+1

)).

Òåîðåìà 14.7. Åñëè îòíîøåíèå R(x

,...,x

) âûðàçèìî â S, òî

õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ C

,...,x

) ýòîãî îòíîøåíèÿ

ñèëüíî ïðåäñòàâèìà â S, à åñëè ôóíêöèÿ C

,...,x

) ïðåäñòà-

âèìà â S, òî â S âûðàçèìî è îòíîøåíèå R(x

,...,x

Äîêàçàòåëüñòâî. Íå ñîñòàâëÿåò òðóäà ïðîâåðèòü, ÷òî:

1) åñëè îòíîøåíèå R(x

,...,x

) âûðàçèìî â S ñ ïîìîùüþ ôîðìóëû

A(x

,...,x

), òî ôóíêöèÿ C

,...,x

) ñèëüíî ïðåäñòàâèìà â S ñ

ïîìîùüþ ôîðìóëû

(A(x

,...,x

)&x

n+1

=0)∨(¬A(x

,...,x

)&x

n+1

=1), è

2) åñëè ôóíêöèÿ C

,...,x

) ïðåäñòàâèìà â S ñ ïîìîùüþ ôîðìóëû

B(x

,...,x

,x

n+1

), òî îòíîøåíèå R(x

,...,x

) âûðàçèìî â S ñ ïîìîùüþ

ôîðìóëû B(x

,...,x

,0).

Òåîðåìà 14.8. Âñÿêàÿ ðåêóðñèâíàÿ ôóíêöèÿ ïðåäñòàâèìà â S.

Äîêàçàòåëüñòâî.

Èñõîäíûå ôóíêöèè Z, N, U

ïðåäñòàâèìû â S, ñîãëàñíî ïðèìåðàì

13. Â ñèëó ïðèìåðà 4, ïðàâèëî ïîäñòàíîâêè (IV) íå âûâîäèò çà

ïðåäåëû êëàññà ïðåäñòàâèìûõ ôóíêöèé. Äîêàçàòåëüñòâî äëÿ

ïðàâèëà ðåêóðñèè è µ-îïåðàòîðà ñì. [Ìåíäåëüñîí Ý., ñòð. 147150].

Ñëåäñòâèå. Âñÿêîå ðåêóðñèâíîå îòíîøåíèå âûðàçèìî â S.

Äîêàçàòåëüñòâî.

Ïóñòü R(x

,,x

)  ðåêóðñèâíûé ïðåäèêàò. Õàðàêòåðèñòè÷åñêàÿ

ôóíêöèÿ C

ýòîãî ïðåäèêàòà ðåêóðñèâíà. Â ñèëó òåîðåìû 14.8,

ôóíêöèÿ C

ïðåäñòàâèìà â S è, ñëåäîâàòåëüíî, â ñèëó òåîðåìû 14.7,

ïðåäèêàò R âûðàçèì â S.

Òåîðåìà 14.9. Âñÿêàÿ ôóíêöèÿ f(x

,..., x

, z), ïðåäñòàâèìàÿ â S,

ðåêóðñèâíà.

Òåîðåìà 14.9 âìåñòå ñ òåîðåìîé 14.8 ïîêàçûâàåò, ÷òî êëàññ ðåêóð-

ñèâíûõ ôóíêöèé ñîâïàäàåò ñ êëàññîì ôóíêöèé, ïðåäñòàâèìûõ â S.

Ñëåäñòâèå. Âñÿêèé çàäàííûé íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë

ïðåäèêàò R(x

,..., x

) ðåêóðñèâåí òîãäà è òîëüêî òîãäà, êîãäà îí

âûðàçèì â òåîðèè S.

Äîêàçàòåëüñòâî.

Ñîãëàñíî îïðåäåëåíèþ, ïðåäèêàò R(x

,..., x

) ðåêóðñèâåí òîãäà

è òîëüêî òîãäà, êîãäà ðåêóðñèâíà ôóíêöèÿ C

. Ñ äðóãîé ñòîðîíû,

ïðåäèêàò R âûðàçèì â S òîãäà è òîëüêî òîãäà, êîãäà ôóíêöèÿ C

ïðåäñòàâèìà â S (òåîðåìà 14.7).

14.4. Ã¸äåëåâà íóìåðàöèÿ

Ã¸äåëü ïðåäëîæèë ñïîñîá êîäèðîâàíèÿ ñèìâîëîâ è âûðàæåíèé

ëþáîé ôîðìàëüíîé òåîðèè òàê, ÷òî êàæäîìó ñèìâîëó, âûðàæåíèþ

è ïîñëåäîâàòåëüíîñòè âûðàæåíèé îäíîçíà÷íî ñîîòâåòñòâóåò íåêî-

òîðîå íàòóðàëüíîå ÷èñëî. Ýòî ñïîñîá êîäèðîâàíèÿ ïîëó÷èë íàçâà-

íèå «ã¸äåëåâîé íóìåðàöèè». Ðàññìîòðèì åãî.

Êàæäîìó ñèìâîëó u ïðîèçâîëüíîé òåîðèè ïåðâîãî ïîðÿäêà K

ñëåäóþùèì îáðàçîì ïîñòàâèì â ñîîòâåòñòâèå ïîëîæèòåëüíîå ÷èñëî

g(u), íàçûâàåìîå ã¸äåëåâûì íîìåðîì ñèìâîëà u:

g(( )=3;

g( ))=5;

g(,)=7;

g(¬)=9;

g(→)=11;

g(x

)=5 + 8k äëÿ k=1, 2, ...;

g(a

)=7 + 8k äëÿ k=1, 2, ...;

g(f

)=9 + 8(2

) äëÿ k, n ≥ 1;

g(A

)=11 + 8(2

) äëÿ k, n ≥ 1;

ïðè ýòîì ïîëîæèì g(∀x

)=g((x

)).

Òàêèì îáðàçîì, ðàçëè÷íûì ñèìâîëàì ïîñòàâëåíû â ñîîòâåòñòâèå

ðàçëè÷íûå ã¸äåëåâû íîìåðà, ÿâëÿþùèåñÿ ïîëîæèòåëüíûìè

÷èñëàìè. Íàïðèìåð, g(x

)=21, g(a

)=39, g(f

)=105, g(A

)=155.

Ïóñòü äàíî âûðàæåíèå u

...u

, ïðåäñòàâëÿþùåå, íàïðèìåð,

ôîðìóëó òåîðèè ïåðâîãî ïîðÿäêà. Ã¸äåëåâ íîìåð g(u

...u

)

ýòîãî âûðàæåíèÿ îïðåäåëèì êàê 2

g(u

)

g(u

)

...p

g(u

)

, ãäå p

åñòü i-å

ïðîñòîå ÷èñëî è p

=2. Íàïðèìåð, g(A

→(A

→A

)) =

=2

g(A1)

g(→)

g(()

g(A2)

g(→)

g(A1)

g())

. Çàìåòèì, ÷òî, â ñèëó

åäèíñòâåííîñòè ðàçëîæåíèÿ íàòóðàëüíûõ ÷èñåë â ïðîèçâåäåíèÿ

ñòåïåíåé ïðîñòûõ ÷èñåë, ðàçëè÷íûå âûðàæåíèÿ ïîëó÷àþò ïðè ýòîì

ðàçíûå ã¸äåëåâû íîìåðà. Êðîìå òîãî, ã¸äåëåâû íîìåðà âûðàæåíèé

Ñâîéñòâà òåîðèé ïåðâîãî ïîðÿäêàÃëàâà 14

256 257Ñâîéñòâà òåîðèé ïåðâîãî ïîðÿäêàÃëàâà 14

÷åòíû è ïîòîìó îòëè÷íû îò ã¸äåëåâûõ íîìåðîâ ñèìâîëîâ. (Âñÿêèé

ñèìâîë ìîæíî ðàññìàòðèâàòü êàê âûðàæåíèå, è òîãäà îí ñíàáæàåòñÿ

ã¸äåëåâûì íîìåðîì, îòëè÷íûì îò òîãî, êîòîðûé ñòàâèòñÿ åìó â

ñîîòâåòñòâèå êàê ñèìâîëó. Ýòî íå äîëæíî, îäíàêî, ïðèâîäèòü ê

íåäîðàçóìåíèþ.)

Íàêîíåö, ã¸äåëåâ íîìåð ïðîèçâîëüíîé ïîñëåäîâàòåëüíîñòè

,,e

âûðàæåíèé (íàïðèìåð, âûâîäà ôîðìóëû e

â òåîðèè Ê)

îïðåäåëèì ñëåäóþùèì îáðàçîì: g(e

,,e

)=2

g(e0)

3

g(e1)

p

g(er)

. Êàê

è ïðåæäå, ðàçëè÷íûå ïîñëåäîâàòåëüíîñòè âûðàæåíèé èìåþò

ðàçëè÷íûå ã¸äåëåâû íîìåðà, à òàê êàê ýòè ïîñëåäíèå ÷åòíû è, êðîìå

òîãî, èìåþò ÷åòíûé ïîêàçàòåëü ñòåïåíè ïðè 2, òî îíè îòëè÷íû è îò

ã¸äåëåâûõ íîìåðîâ ñèìâîëîâ, è îò ã¸äåëåâûõ íîìåðîâ âûðàæåíèé.

Òàêèì îáðàçîì, ôóíêöèÿ g âçàèìíî îäíîçíà÷íî îòîáðàæàåò ìíî-

æåñòâî âñåõ ñèìâîëîâ, âûðàæåíèé è êîíå÷íûõ ïîñëåäîâàòåëüíîñòåé

âûðàæåíèé â ìíîæåñòâî öåëûõ ïîëîæèòåëüíûõ ÷èñåë. Ìíîæåñòâî

çíà÷åíèé ôóíêöèè g íå ñîâïàäàåò, îäíàêî, ñ ìíîæåñòâîì âñåõ öåëûõ

ïîëîæèòåëüíûõ ÷èñåë, òàê êàê íå âñå ÷èñëà ÿâëÿþòñÿ ãåäåëåâûìè

íîìåðàìè, íàïðèìåð, ÷èñëî 12 íå ÿâëÿåòñÿ ã¸äåëåâûì íîìåðîì.

Òàêàÿ íóìåðàöèÿ ñèìâîëîâ, âûðàæåíèé è ïîñëåäîâàòåëüíîñòåé

âûðàæåíèé áûëà ïðåäëîæåíà Ã¸äåëåì â 1931 ã. ñ öåëüþ àðèôìåòèçà-

öèè ìàòåìàòèêè, ò.å. ñ öåëüþ çàìåíû óòâåðæäåíèé î ôîðìàëüíîé

ñèñòåìå ýêâèâàëåíòíûìè âûñêàçûâàíèÿìè î íàòóðàëüíûõ ÷èñëàõ

ñ ïîñëåäóþùèì âûðàæåíèåì ýòèõ âûñêàçûâàíèé â ôîðìàëüíîé

ñèñòåìå. Ïîñêîëüêó êàæäîìó âûðàæåíèþ èñ÷èñëåíèÿ ïðèïèñàí

ã¸äåëåâ íîìåð, òî êàæäîå ìåòàìàòåìàòè÷åñêîå âûñêàçûâàíèå î âûðà-

æåíèÿõ èñ÷èñëåíèÿ è îòíîøåíèÿõ ìåæäó íèìè ìîæíî âûðàçèòü

êàê âûñêàçûâàíèå î ñîîòâåòñòâóþùèõ ãåäåëåâûõ íîìåðàõ è îòíî-

øåíèÿõ ìåæäó íèìè. Òàêèì îáðàçîì ìåòàìàòåìàòèêà îêàçûâàåòñÿ

ïîëíîñòüþ «àðèôìåòèçèðîâàííîé», è ÿçûê àðèôìåòèêè ñòàíîâèòñÿ

ÿçûêîì ìåòàìàòåìàòèêè. Èçó÷åíèå ìåòàìàòåìàòè÷åñêèõ âîïðîñîâ

ñâîäèòñÿ ê èçó÷åíèþ ñîîòíîøåíèé è ñâîéñòâ íåêîòîðûõ ÷èñåë.

14.5. Òåîðåìà Ã¸äåëÿ î íåïîëíîòå

Äåòàëè äîêàçàòåëüñòâà çíàìåíèòîé òåîðåìû Ã¸äåëÿ äîâîëüíî

ñëîæíû, ïîýòîìó ìû îïóñòèì äîêàçàòåëüñòâà íåêîòîðûõ ïðåäâàðè-

òåëüíûõ óòâåðæäåíèé. (Ñ ïîëíûì äîêàçàòåëüñòâîì ìîæíî îçíàêî-

ìèòüñÿ â [Ìåíäåëüñîí, 1976]).

Ïóñòü äëÿ äàííîé òåîðèè ïåðâîãî ïîðÿäêà K ñëåäóþùèå îòíîøå-

íèÿ ïðèìèòèâíî ðåêóðñèâíû (ðåêóðñèâíû):

(à) IC(x), ÷òî îçíà÷àåò «x åñòü ã¸äåëåâ íîìåð ïðåäìåòíîé êîí-

ñòàíòû òåîðèè K»,

(b) FL(x), ÷òî îçíà÷àåò «x åñòü ã¸äåëåâ íîìåð ôóíêöèîíàëüíîé

áóêâû òåîðèè K»,

òåîðèè K».

Òîãäà, íà îñíîâå ýòèõ îòíîøåíèé ìîæíî îïðåäåëèòü íîâûå îòíî-

øåíèÿ è ôóíêöèè, òàê ÷òî ýòè îòíîøåíèÿ áóäóò îïðåäåëÿòü âûñêà-

çûâàíèÿ îòíîñèòåëüíî âûðàæåíèé è îïåðàöèé ôîðìàëüíîé òåîðèè

S, ïðè÷åì ýòè îòíîøåíèÿ è ôóíêöèè òàêæå áóäóò ïðèìèòèâíî

ðåêóðñèâíû (ðåêóðñèâíû). Çäåñü ìû ðàññìîòðèì (áåç äîêàçàòåëü-

ñòâà) òîëüêî îäíî îòíîøåíèå, êîòîðîå, êàê ìîæíî ïîêàçàòü, ÿâëÿåòñÿ

ïðèìèòèâíî ðåêóðñèâíûì: W(u,y): «u åñòü ã¸äåëåâ íîìåð ôîðìóëû

A(x

), ñîäåðæàùåé ñâîáîäíóþ ïåðåìåííóþ x

, è ó åñòü ã¸äåëåâ íîìåð

âûâîäà â S ôîðìóëû A(u)».

Ââåäåì åùå äîïîëíèòåëüíîå ïîíÿòèå íåïðîòèâîðå÷èâîñòè

ôîðìàëüíîé òåîðèè.

Îïðåäåëåíèå 14.13. Ïóñòü K  òåîðèÿ ïåðâîãî ïîðÿäêà ñ òåìè

æå ñàìûìè ñèìâîëàìè, ÷òî è S. Òåîðèÿ K íàçûâàåòñÿ ω-íåïðî-

òèâîðå÷èâîé, åñëè äëÿ âñÿêîé ôîðìóëû A(x) ýòîé òåîðèè èç

òîãî, ÷òî ïðè ëþáîì n |

K

A(n), ñëåäóåò íåâîçìîæíîñòü |

K

∃x¬A(x).

Î÷åâèäíî, ÷òî åñëè ïðèíÿòü ñòàíäàðòíóþ èíòåðïðåòàöèþ òåîðèè

S â êà÷åñòâå ìîäåëè ýòîé òåîðèè, òî òîãäà òåîðèþ S ñëåäóåò ïðèçíàòü

ω-íåïðîòèâîðå÷èâîé.

Òåîðåìà 14.10. Åñëè òåîðèÿ K ω-íåïðîòèâîðå÷èâà, òî îíà íåïðî-

òèâîðå÷èâà.

Äîêàçàòåëüñòâî.

Ïóñòü òåîðèÿ K ω-íåïðîòèâîðå÷èâà. Ðàññìîòðèì êàêóþ-íèáóäü

âûâîäèìóþ â K ôîðìóëó A(x) ñî ñâîáîäíîé ïåðåìåííîé, íàïðèìåð

x=x→x=x. Ïðè ëþáîì n èìååì |

n=n→n=n. Ïîýòîìó

ôîðìóëà ∃x¬(x=x→x=x) íåâûâîäèìà â K. Ñëåäîâàòåëüíî, òåî-

ðèÿ K íåïðîòèâîðå÷èâà (èáî, â ñèëó òàâòîëîãèè ¬A→(A→B), èç

ïðîòèâîðå÷èâîñòè K ñëåäîâàëà áû âûâîäèìîñòü â K ëþáîé

ôîðìóëû).

Ïåðåéäåì ê ôîðìóëèðîâêå òåîðåìû Ã¸äåëÿ. Ðàññìîòðèì îòíî-

øåíèå W(u,y).

Îòíîøåíèå W(u,y) ïðèìèòèâíî ðåêóðñèâíî è ïîòîìó âûðàçèìî

â S íåêîòîðîé ôîðìóëîé W(x

,x

) ñ äâóìÿ ñâîáîäíûìè ïåðåìåííû-

ìè x

, x

. Ýòî çíà÷èò, ÷òî åñëè W(k

,k

) èñòèííî, òî |

W(k

,k

), è

åñëè W(k

,k

) ëîæíî, òî |

S

¬W(k

,k

). Ðàññìîòðèì òåïåðü ôîðìóëó

∀x

¬W(x

,x

). (*)

Ýòî ôîðìóëà ñ îäíîé ñâîáîäíîé ïåðåìåííîé x

. Ïóñòü m åñòü

ã¸äåëåâ íîìåð ôîðìóëû (*). Ïîäñòàâèâ â (*) m âìåñòî ñâîáîäíîé

ïåðåìåííîé x

, ìû ïîëó÷èì çàìêíóòóþ ôîðìóëó

∀x

¬W

(m,x

). (G)

258 259Ñâîéñòâà òåîðèé ïåðâîãî ïîðÿäêàÃëàâà 14

Âñïîìíèì, ÷òî óòâåðæäåíèå W(u,y) èñòèííî òîãäà è òîëüêî

òîãäà, êîãäà u åñòü ã¸äåëåâ íîìåð íåêîòîðîé ôîðìóëû A(x

ñîäåðæàùåé ñâîáîäíóþ ïåðåìåííóþ x

, à y åñòü ã¸äåëåâ íîìåð

âûâîäà â S ôîðìóëû A(u). Ñëåäîâàòåëüíî,

(I)W(m, x

) èñòèííî òîãäà è òîëüêî òîãäà, êîãäà x

åñòü ã¸äåëåâ

íîìåð âûâîäà â S ôîðìóëû G.

Òåîðåìà 14.11. (Òåîðåìà Ã¸äåëÿ äëÿ òåîðèè S).

(1) Åñëè òåîðèÿ S íåïðîòèâîðå÷èâà, òî ôîðìóëà G íåâûâîäèìà

â S.

(2) Åñëè òåîðèÿ S ω-íåïðîòèâîðå÷èâà, òî ôîðìóëà ¬G íåâûâî-

äèìà â S.

(Òàêèì îáðàçîì, â ñèëó òåîðåìû 14.10, åñëè òåîðèÿ S ω-íåïðîòè-

âîðå÷èâà, òî çàìêíóòàÿ ôîðìóëà G íåâûâîäèìà è íåîïðîâåðæèìà

â S. Çàìêíóòûå ôîðìóëû, îáëàäàþùèå òàêèì ñâîéñòâîì, íàçûâà-

þòñÿ íåðàçðåøèìûìè ïðåäëîæåíèÿìè òåîðèè S.)

Äîêàçàòåëüñòâî.

(1) Ïðåäïîëîæèì, ÷òî òåîðèÿ S íåïðîòèâîðå÷èâà è |

∀x

¬W(m,x

Ïóñòü òîãäà k  ã¸äåëåâ íîìåð êàêîãî-íèáóäü âûâîäà â S ýòîé

ïîñëåäíåé ôîðìóëû. Â ñèëó ïðåäëîæåíèÿ (I), ñïðàâåäëèâî W(m,k).

Òàê êàê W âûðàæàåò W â S, òî |

W(m,k). Èç ∀x

¬W(m,x

) ïî

ïðàâèëó A4 (óíèâåðñàëüíîé êîíêðåòèçàöèè) ìû ìîæåì âûâåñòè

¬W(m,k). Òàêèì îáðàçîì, â S îêàçûâàþòñÿ âûâîäèìûìè ôîðìóëû

W(m,k) è ¬W(m,k), ÷òî ïðîòèâîðå÷èò ïðåäïîëîæåíèþ î íåïðîòè-

âîðå÷èâîñòè S.

(2) Ïðåäïîëîæèì, ÷òî òåîðèÿ S ω-íåïðîòèâîðå÷èâà è

|

S

¬∀x

¬W(m,x

), ò.å. |

S

¬G. Íà îñíîâàíèè òåîðåìû 14.10,

çàêëþ÷àåì, ÷òî òåîðèÿ S íåïðîòèâîðå÷èâà è, ñëåäîâàòåëüíî, íå

|

S

G. Ïîýòîìó, êàêîâî áû íè áûëî íàòóðàëüíîå ÷èñëî n, n íå åñòü

ã¸äåëåâ íîìåð âûâîäà â S ôîðìóëû G, ò.å. W(m,n) ëîæíî äëÿ ëþáîãî

n. À ýòî çíà÷èò, ÷òî |

¬W(m,n) äëÿ ëþáîãî n. Âçÿâ â êà÷åñòâå

ôîðìóëû A(x

) ôîðìóëó ¬W(m,x

), ìû, íà îñíîâàíèè ïðåäïî-

ëîæåíèÿ îá ω-íåïðîòèâîðå÷èâîñòè òåîðèè S, çàêëþ÷àåì, ÷òî íå

|

S

∃x

¬¬W(m,x

) è, ñëåäîâàòåëüíî, íå |

S

∃x

W(m,x

). Ìû ïðèøëè,

òàêèì îáðàçîì, ê ïðîòèâîðå÷èþ ñ ïðåäïîëîæåíèåì, ÷òî

|

S

∃x

W(m,x

Ðàññìîòðèì ñòàíäàðòíóþ èíòåðïðåòàöèþ íåðàçðåøèìîãî

ïðåäëîæåíèÿ G: ∀x

¬W(m,x

). Òàê êàê W âûðàæàåò â S îòíîøåíèå

W, òî, â ñîîòâåòñòâèè ñî ñòàíäàðòíîé èíòåðïðåòàöèåé, G óòâåð-

æäàåò, ÷òî W(m,x

) ëîæíî äëÿ êàæäîãî íàòóðàëüíîãî ÷èñëà x

Ñîãëàñíî (I), ýòî îçíà÷àåò, ÷òî íå ñóùåñòâóåò âûâîäà ôîðìóëû G â

S. Äðóãèìè ñëîâàìè, ôîðìóëà G óòâåðæäàåò ñâîþ ñîáñòâåííóþ

íåâûâîäèìîñòü â S. Ïî òåîðåìå æå Ã¸äåëÿ, åñëè òîëüêî òåîðèÿ S

íåïðîòèâîðå÷èâà, ýòà ôîðìóëà è â ñàìîì äåëå íåâûâîäèìà â S è

ïîòîìó èñòèííà ïðè ñòàíäàðòíîé èíòåðïðåòàöèè.

Èòàê, äëÿ íàòóðàëüíûõ ÷èñåë, ñîîòâåòñòâóþùèõ îáû÷íîé

èíòåðïðåòàöèè, ôîðìóëà G âåðíà, íî â S íåâûâîäèìà. Ýòî îçíà÷àåò,

÷òî â ñîäåðæàòåëüíîé àðèôìåòèêå (â ñòàíäàðòíîé èíòåðïðåòàöèè

òåîðèè S) ñóùåñòâóåò èñòèííîå óòâåðæäåíèå, êîòîðîìó, îäíàêî, íå

ñîîòâåòñòâóåò íèêàêàÿ òåîðåìà òåîðèè S. Òàêèì îáðàçîì, òåîðèÿ S

íåïîëíà.

Ìîæåò ïîêàçàòüñÿ, ÷òî òåîðåìà Ã¸äåëÿ ïîòîìó ñïðàâåäëèâà äëÿ

òåîðèè S, ÷òî ïåðâîíà÷àëüíî âûáðàííàÿ äëÿ ýòîé òåîðèè ñèñòåìà

àêñèîì îêàçàëàñü ñëèøêîì ñëàáîé è ÷òî, åñëè áû ìû óñèëèëè

òåîðèþ S, äîáàâèâ ê íåé íîâûå àêñèîìû, òî íîâàÿ òåîðèÿ ìîãëà áû

îêàçàòüñÿ ïîëíîé. Òàê, íàïðèìåð, ÷òîáû ïîëó÷èòü íåêîòîðóþ áîëåå

ñèëüíóþ òåîðèþ S

, ìû ìîãëè áû äîáàâèòü ê S èñòèííóþ ôîðìóëó

G. Îäíàêî âñÿêàÿ ðåêóðñèâíàÿ ôóíêöèÿ, áóäó÷è ïðåäñòàâèìîé â

S, ïðåäñòàâèìà òàêæå è â òàêîé òåîðèè S

. Òî÷íî òàê æå è òåîðåìû

14.6, 14.7, 14.8 îñòàþòñÿ, î÷åâèäíî, â ñèëå, åñëè èõ ïåðåôîðìóëèðî-

âàòü äëÿ S

. Íî ýòî è åñòü âñå, ÷òî òðåáóåòñÿ äëÿ òîãî, ÷òîáû ïîëó-

÷èòü ðåçóëüòàò Ã¸äåëÿ; è ïîòîìó, åñëè òåîðèÿ S

ω-íåïðîòèâîðå÷èâà,

òî è îíà èìååò íåêîòîðîå íåðàçðåøèìîå ïðåäëîæåíèå B. (B èìååò

òó æå ôîðìó ∀x

¬(W)

(k,x

), íî, ðàçóìååòñÿ, áóäåò îòëè÷àòüñÿ îò

G, ïîñêîëüêó îòíîøåíèå W äëÿ S

îòëè÷íî îò îòíîøåíèÿ W äëÿ S,

è, ñëåäîâàòåëüíî, ôîðìóëà (W)

, è âõîäÿùàÿ â B öèôðà k îòëè÷íû

îò ôîðìóëû W è öèôðû m â G.) Òàêèì îáðàçîì, äîáàâëåíèå

ôîðìóëû G ê àêñèîìàì òåîðèè S íå ñäåëàåò ýòó òåîðèþ ïîëíîé,

ò.å. òåîðèÿ S ÿâëÿåòñÿ íå òîëüêî íåïîëíîé, íî è íåïîïîëíèìîé.

14.6. Âòîðàÿ òåîðåìà Ã¸äåëÿ

Îïðåäåëèì Neg(x) òàê, ÷òî åñëè x åñòü ã¸äåëåâ íîìåð ôîðìóëû

A, òî Neg(x) åñòü ã¸äåëåâ íîìåð ôîðìóëû ¬A. Ôóíêöèÿ Neg,

î÷åâèäíî, ðåêóðñèâíà è, ñëåäîâàòåëüíî, ïðåäñòàâèìà â S íåêîòîðîé

ôîðìóëîé Neg(x

,x

). Ââåäåì ïðåäèêàò Pf(y,x), èñòèííûé òîãäà è

òîëüêî òîãäà, êîãäà x åñòü ã¸äåëåâ íîìåð íåêîòîðîé ôîðìóëû A

òåîðèè S, à y åñòü ã¸äåëåâ íîìåð íåêîòîðîãî âûâîäà A â S. Ïðåäèêàò

Pf ïðèìèòèâíî ðåêóðñèâåí, è ïîòîìó âûðàçèì â S ñ ïîìîùüþ íåêî-

òîðîé ôîðìóëû Pf(x

,x

Îáîçíà÷èì ÷åðåç Con

ôîðìóëó:

∀x

¬(Pf(x

,x

)&Pf(x

,x

)&Neg(x

,x

)).

Ñîäåðæàòåëüíî, ò.å. â ñîîòâåòñòâèè ñî ñòàíäàðòíîé èíòåðïðå-

òàöèåé, Con

âûðàæàåò íåâîçìîæíîñòü âûâîäà â S êàêîé-ëèáî

ôîðìóëû âìåñòå ñ åå îòðèöàíèåì è ÿâëÿåòñÿ èñòèííîé â òîì è

òîëüêî òîì ñëó÷àå, êîãäà òåîðèÿ S íåïðîòèâîðå÷èâà. Èíûìè ñëîâà-

ìè, ôîðìóëó Con

ìîæíî èíòåðïðåòèðîâàòü êàê óòâåðæäåíèå î