Лекции - Математическая логика
Подождите немного. Документ загружается.
251
îáëàäàþùèõ ýòèì ñâîéñòâîì. Ýòî óòâåðæäåíèå ìîæíî çàïèñàòü â
âèäå ôîðìóëû ñëåäóþùèì îáðàçîì:
∃õ À(x) ⊃ ∃ó (À(ó) & >z (z < ó ⊃ ¬À(z))),
ãäå z < ó
∃õ (y = õ + z & õ
≠
0).
Ìîæíî äîêàçàòü, ÷òî ýòè ôîðìóëû ÿâëÿþòñÿ Ar-òåîðåìàìè. Îêà-
çûâàåòñÿ, äëÿ âñåõ èçâåñòíûõ òåîðåì ýëåìåíòàðíîé òåîðèè ÷èñåë,
çàïèñàííûõ â âèäå ôîðìóë ÿçûêà ß
Ar
, ìîæíî ïîñòðîèòü äåðåâüÿ
Ar-âûâîäà, äîêàçàâ òåì ñàìûì, ÷òî îíè ÿâëÿþòñÿ Ar-òåîðåìàìè.
Èñêëþ÷åíèÿìè ñëóæàò òå òåîðåìû òåîðèè ÷èñåë, â ôîðìóëèðîâêàõ
êîòîðûõ èñïîëüçóþòñÿ íåýëåìåíòàðíûå ïîíÿòèÿ, èëè äîêàçàòåëü-
ñòâà êîòîðûõ èñïîëüçóþò, ñêàæåì, ñðåäñòâà òåîðèè ôóíêöèé êîì-
ïëåêñíîãî ïåðåìåííîãî (íàïðèìåð, òåîðåìà Äèðèõëå).
Ìîæíî äîêàçàòü, ÷òî Ar ÿâëÿåòñÿ òåîðèåé ñ ðà-
âåíñòâîì.
ÒÅÎÐÅÌÀ. Â Ar äîêàçóåìû ôîðìóëû (re), (si)
è (tr):
1)
Ar
õ
1
= õ
1
;
2)
Ar
õ
1
= õ
2
⊃ õ
2
= õ
1
;
3)
Ar
õ
1
= õ
2
& õ
2
= õ
3
⊃ õ
1
= õ
3
.
Äîêàçàòåëüñòâî. Â ñèëó óòâåðæäåíèÿ î ïîäñòàíîâêàõ â
äîêàçóåìûå áåñêâàíòîðíûå ôîðìóëû (§ 5.5), âñÿêàÿ îäíîâðåìåí-
íàÿ ïîäñòàíîâêà òåðìîâ â àêñèîìû Ar äîêàçóåìà â Ar.
Äëÿ ïðîñòîòû çàïèñè âìåñòî õ
1
, õ
2
, õ
3
áóäåì èñïîëüçîâàòü áóêâû
õ, y, z.
1. Äîêàæåì, ÷òî
Ar
õ = õ ïîñòðîåíèåì äåðåâà Ar-âûâîäà:
у
у
51
5
Ar Ar
Ar
0
0(0 )
00
xx
xxxxxx
xx xxxx
xx
⊃
⊃
+=
+= ⊃ += ⊃ =
+= += ⊃ =
=
2. Äîêàæåì, ÷òî
Ar
õ = ó ⊃ ó = õ, ïîñòðîèâ ñîîòâåòñòâóþùåå
äåðåâî Ar-âûâîäà:
у
у
в
1
Ar
1
(re)
(1)
()
[]
xyxy xx yx
xx yx
xx
yx
xy yx
⊃
⊃
⊃
=⊃ =⊃=
=
=⊃=
=
=
=⊃=
Формальная
арифметика –
теория
с равенством
252
Çàìå÷àíèå 2. Ôîðìóëà õ = ó ⊃ (õ = õ ⊃ ó = õ) ÿâëÿåòñÿ ïîäñòà-
íîâêîé â àêñèîìó Ar
1
è, ñîãëàñíî óòâåðæäåíèþ î ïîäñòàíîâêàõ â
äîêàçóåìûå ôîðìóëû, ÿâëÿåòñÿ Ar-äîêàçóåìîé. Èìåííî ýòî è îò-
ðàæàåò äâîéíàÿ ÷åðòà íàä ðàññìàòðèâàåìîé ôîðìóëîé.
3. Äëÿ äîêàçàòåëüñòâà óòâåðæäåíèÿ
Ar
õ = ó & ó = z ⊃ õ = z,
ðàññìîòðèì ñëåäóþùåå äåðåâî Ar-âûâîäà:
1
1
&
Ar
(si)
1
&
(1)
y
y y
y
â
[&]
[&]
()
&
xy yz
xy
xy yz
yx
yx yz xz
yz yz xz
xz
xy yz xz
⊃
⊃
⊃
==
=
==
=
=⊃ =⊃=
==⊃=
=
==⊃=
Çäåñü ìû èñïîëüçîâàëè îáîçíà÷åíèå
xy
yx
=
=
äëÿ Ar-äåðåâà, ñîîò-
âåòñòâóþùåãî âûâîäèìîñòè õ = ó
Ar
ó = õ (ñì. ï. 2).
ÑËÅÄÑÒÂÈÅ. Äëÿ ëþáûõ òåðìîâ t, r è s ÿçûêà Ar ñëåäóþùèå
ôîðìóëû âûâîäèìû â Ar:
1) t = t;
2) t = r ⊃ r = t;
3) t = r & r = s ⊃ t = s.
Äëÿ äîêàçàòåëüñòâà äîñòàòî÷íî ñîñëàòüñÿ íà òîëüêî ÷òî äîêà-
çàííóþ òåîðåìó è óòâåðæäåíèå î ïîäñòàíîâêàõ â äîêàçóåìûå áåñ-
êâàíòîðíûå ôîðìóëû èç § 5.5.
Äëÿ äîêàçàòåëüñòâà òîãî, ÷òî Ar – òåîðèÿ ñ ðàâåíñòâîì, ñîãëàñ-
íî êðèòåðèþ òåîðèè ñ ðàâåíñòâîì îñòàëîñü ïîêàçàòü, ÷òî
Ar
õ = ó ⊃ õ + z = ó + z;
Ar
õ = ó ⊃ z + õ = z + ó;
Ar
õ = ó ⊃ õ•z = ó•z;
Ar
õ = ó ⊃ z•õ = z•ó.
Äîêàçàòåëüñòâî ýòèõ óòâåðæäåíèé îñòàâëÿåì ÷èòàòåëþ
1)
.
Ìîæíî äîêàçàòü, ÷òî äëÿ ëþáûõ òåðìîâ t, r è s ÿçûêà Ar ñëåäó-
þùèå ôîðìóëû âûâîäèìû â Ar:
1) t = r ⊃ t + s = r + s;
2) t = 0 + t;
1)
Äîêàçàòåëüñòâî ýòèõ óòâåðæäåíèé, êàê è ïîñëåäóþùèõ óòâåðæäåíèé î
âûâîäèìîñòè ôîðìóë, âûðàæàþùèõ îñíîâíûå ñâîéñòâà îïåðàöèé äëÿ ôîðìàëü-
íîé àðèôìåòèêè íà áàçå ãèëüáåðòîâñêîãî èñ÷èñëåíèÿ ïðåäèêàòîâ ìîæíî íàé-
òè, íàïðèìåð, â [10].
253
3) t R + r = (t + r)R;
4) t + r = r + t;
5) t = r ⊃ s + t = s + r;
6) (t + r) + s = t + (r + s);
7) 0•t = 0;
8) t R•r = t•r + r ;
9) t•r = r•t ;
10) t = r ⊃ s•t = s•r;
11)
1
⋅
t = t.
Ôîðìóëû, âûðàæàþùèå äðóãèå èçâåñòíûå ñâîéñòâà àðèô-
ìåòè÷åñêèõ îïåðàöèé, à òàêæå ñâîéñòâà íåðàâåíñòâ è îòíîøå-
íèÿ äåëèìîñòè (ñì., íàïðèìåð, [9]), òàêæå ìîãóò áûòü äîêàçà-
íû â Ar.
Òåïåðü ìû ïîäîøëè âïëîòíóþ ê òîìó, ÷òîáû âû-
ÿñíèòü, íàñêîëüêî àäåêâàòíà òåîðèÿ Ar íåôîð-
ìàëüíîé àðèôìåòèêå. Òî÷íåå, âûÿñíèì, êàêîâû
îòâåòû íà ñëåäóþùèå âîïðîñû:
1. Âñÿêàÿ ëè ôîðìóëà, èñòèííàÿ â ñòàíäàðòíîé èíòåðïðåòàöèè
N, ÿâëÿåòñÿ Ar-òåîðåìîé?
2. Ïîëíà ëè òåîðèÿ Ar, ò. å. äëÿ âñÿêîé ëè çàìêíóòîé ôîðìóëû
F ÿçûêà ß
Ar
â Ar äîêàçóåìà îíà ñàìà èëè åå îòðèöàíèå?
3. Ðàçðåøèìà ëè òåîðèÿ Ar? Íåïðîòèâîðå÷èâà ëè òåîðèÿ Ar?
Ãèëüáåðò íàäåÿëñÿ ïîëó÷èòü ïîëîæèòåëüíûå îòâåòû íà ýòè âîï-
ðîñû, îäíàêî åãî íàäåæäû íå îïðàâäàëèñü. Â 1931 ãîäó ìîëîäîé
àâñòðèéñêèé ìàòåìàòèê Êóðò øäåëü (1906–1978) ïîëó÷èë óäèâè-
òåëüíûå ðåçóëüòàòû.
S Ñóòü ýòèõ ðåçóëüòàòîâ çàêëþ÷àåòñÿ â ñëåäóþùåì:
1) ñóùåñòâóþò ôîðìóëû, èñòèííûå â ñòàíäàðòíîé èíòåðïðåòà-
öèè, íî íåäîêàçóåìûå â Ar;
2) åñëè òåîðèÿ Ar íåïðîòèâîðå÷èâà, òî ñóùåñòâóþò çàìêíóòûå
ôîðìóëû, êîòîðûå íåäîêàçóåìû è íåîïðîâåðæèìû â Ar;
3) íåïîëíîòà Ar âûçâàíà íå òåì, ÷òî Ar íåñîâåðøåííà, à òåì,
÷òî ïîñòðîåíèå ïîëíîé òåîðèè, óäîâëåòâîðÿþùåé íåêîòîðûì åñ-
òåñòâåííûì óñëîâèÿì, â ïðèíöèïå íåâîçìîæíî.
Èçëîæåíèå ðåçóëüòàòîâ øäåëÿ ñ ïîëíûì äîêàçàòåëüñòâîì â
ðàìêàõ íàøåãî êóðñà íåâîçìîæíî. Îäíàêî, îïóñêàÿ äîêàçàòåëüñòâà
íåêîòîðûõ óòâåðæäåíèé, òðåáóþùèõ èñïîëüçîâàíèÿ òåõíè÷åñêîãî
àïïàðàòà òåîðèè àëãîðèòìîâ, ìîæíî èçëîæèòü èäåéíóþ ÷àñòü äî-
êàçàòåëüñòâà òåîðåì øäåëÿ.
Неполнота
формальной
арифметики
254
øäåëü â 1930 ãîäó äëÿ ðåøåíèÿ ïîñòàâëåííûõ
çàäà÷ ïðåäëîæèë ïðîíóìåðîâàòü âñå ñèìâîëû,
òåðìû, ôîðìóëû ß
Ar
è âûâîäû â Ar òàêèì îáðà-
çîì, ÷òîáû ìîæíî áûëî çàìåíèòü óòâåðæäåíèÿ î
òåîðèè Ar ýêâèâàëåíòíûìè óòâåðæäåíèÿìè î íàòóðàëüíûõ ÷èñëàõ,
êîòîðûå çàòåì âûðàçèòü â Ar. Ýòà èäåÿ ñûãðàëà êëþ÷åâóþ ðîëü â
äîêàçàòåëüñòâå øäåëåì òåîðåì î íåïîëíîòå Ar, à òàêæå ïðè ðåøå-
íèè ðÿäà âàæíûõ ïðîáëåì ìàòåìàòè÷åñêîé ëîãèêè.
Ïóñòü à
1
… à
m
åñòü àëôàâèò ôîðìàëüíîãî ÿçûêà ß.
Àðèôìåòèçàöèåé ôîðìàëüíîãî ÿçûêà ß íàçûâàþò âñÿêîå èíú-
åêòèâíîå îòîáðàæåíèå g ìíîæåñòâà Å âñåõ áóêâ àëôàâèòà ÿçû-
êà ß, âñåõ ñëîâ è âñåõ êîíå÷íûõ ïîñëåäîâàòåëüíîñòåé ñëîâ â
ýòîì àëôàâèòå âî ìíîæåñòâî N, óäîâëåòâîðÿþùåå ñëåäóþùèì
óñëîâèÿì:
1) g – ýôôåêòèâíî âû÷èñëèìàÿ ôóíêöèÿ, ò. å. ñóùåñòâóåò àëãî-
ðèòì, êîòîðûé êàæäîå α èç Å ïåðåðàáàòûâàåò â g(α);
2) ñóùåñòâóåò àëãîðèòì, êîòîðûé ïî êàæäîìó íàòóðàëüíîìó n
ïîçâîëÿåò óñòàíîâèòü, ÿâëÿåòñÿ ëè n çíà÷åíèåì g ïðè íåêîòî-
ðîì α èç Å, è â ñëó÷àå, êîãäà ÿâëÿåòñÿ, ïîñòðîèòü òîò îáúåêò α,
äëÿ êîòîðîãî n = g(α).
Áóäåì èñïîëüçîâàòü áóêâó α äëÿ îáîçíà÷åíèÿ ïðîèçâîëüíîãî
ýëåìåíòà èç Å.
Íàòóðàëüíîå ÷èñëî g(α) íàçûâàþò ã¸äåëåâûì íîìåðîì α.
Ðàññìîòðèì îäèí èç ñïîñîáîâ ïîñòðîåíèÿ òàêîé ôóíêöèè g:
1. Åñëè α åñòü áóêâà à
i
(i = 1, …, m), òî
g(à
i
) = 2i + 1, i = 1, …, m.
2. Åñëè α åñòü ñëîâî â àëôàâèòå ÿçûêà ß (äëÿ ïðîñòîòû çàïèñè
áóäåì ñ÷èòàòü, ÷òî α
à
1
… à
n
), òî
g(α) =
12
()() ()
23...
n
gaga ga
n
p
⋅⋅⋅
,
ãäå p
n
– n-å ïðîñòîå ÷èñëî ïðè ïåðåñ÷åòå âñåõ ïðîñòûõ ÷èñåë â
ïîðÿäêå âîçðàñòàíèÿ (p
1
= 2, p
2
= 3, …).
3. Åñëè α åñòü Õ
1
, …,
Õ
k
– êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ñëîâ â
àëôàâèòå ß, òî
g(α) =
⋅⋅⋅
12
()() ( )
23...
k
gXgX gX
k
p
.
Âñÿêîå äåðåâî ôîðìóë ÿçûêà ß ìîæíî çàêîäèðîâàòü íåêîòî-
ðûì ñëîâîì â àëôàâèòå ýòîãî ÿçûêà
1)
. Åñëè íåêîòîðûé ñïîñîá òà-
1)
Îäèí èç ñïîñîáîâ êîäèðîâàíèÿ äåðåâüåâ ôîðìóë ñëîâàìè ðàññìîòðåí â [3].
Арифметизация
формальных
языков
255
êîãî êîäèðîâàíèÿ ôèêñèðîâàí, òî íàçîâåì ã¸äåëåâûì íîìåðîì äåðå-
âà ôîðìóë íîìåð ñëîâà, êîäèðóþùåãî ýòî äåðåâî.
Áóäåì íàçûâàòü n-ìåñòíûì àðèôìåòè÷åñêèì ïðå-
äèêàòîì âñÿêîå îòîáðàæåíèå âèäà N
n
→ {È, Ë}.
Àðèôìåòè÷åñêèé ïðåäèêàò ìåñòíîñòè n íàçûâà-
þò ðàçðåøèìûì ïðåäèêàòîì, åñëè ñóùåñòâóåò àë-
ãîðèòì, ïîçâîëÿþùèé ïî ïðîèçâîëüíîìó íàáî-
ðó íàòóðàëüíûõ ÷èñåë (k
1
, …, k
n
) âûÿñíèòü, êà-
êîå çíà÷åíèå ïðèíèìàåò ïðåäèêàò íà ýòîì íà-
áîðå: È èëè Ë.
Àðèôìåòè÷åñêèé n-ìåñòíûé ïðåäèêàò
P íàçûâàþò ïðåäñòàâè-
ìûì â Ar, åñëè ñóùåñòâóåò ôîðìóëà F(õ
1
, …, õ
n
) ÿçûêà Ar ñ n
ñâîáîäíûìè ïåðåìåííûìè òàêàÿ, ÷òî äëÿ ëþáîãî íàáîðà íàòó-
ðàëüíûõ ÷èñåë (k
1
, … ,k
n
) âûïîëíÿþòñÿ óñëîâèÿ:
1) åñëè
P(k
1
, …, k
n
) = È, òî
Ar
F(
1
,...,
n
kk
);
2) åñëè
P(k
1
, …, k
n
) = Ë, òî
Ar
¬F(
1
,...,
n
kk
).
Çàìå÷àíèå 3. Óñëîâèå
Ar
¬F(
1
,...,
n
kk
), èñïîëüçóåìîå â îïðå-
äåëåíèè ïðåäñòàâèìîãî â Ar ïðåäèêàòà, íåðàâíîñèëüíî óñëîâèþ
Ar
F(
1
,...,
n
kk
).
Ïðèìåðû. Ìîæíî äîêàçàòü, ÷òî:
1) ôîðìóëà õ
1
= õ
2
ïðåäñòàâëÿåò â Ar ïðåäèêàò ðàâåíñòâà = ;
2) ôîðìóëà ∃õ
3
(õ
1
+ õ
3
= õ
2
& õ
3
≠ 0) ïðåäñòàâëÿåò â Ar ïðåäèêàò <;
3) ôîðìóëà ∃õ
3
(õ
1
+ õ
3
= õ
2
) ïðåäñòàâëÿåò â Ar ïðåäèêàò ≤;
4) ôîðìóëà ∃õ
3
(õ
2
= õ
1
⋅
õ
3
) ïðåäñòàâëÿåò â Ar ïðåäèêàò äåëè-
ìîñòè.
Íåñëîæíî äîêàçàòü, ÷òî êîíúþíêöèÿ, äèçúþíêöèÿ, èìïëèêà-
öèÿ è îòðèöàíèå ïðåäñòàâèìûõ â Ar ïðåäèêàòîâ òàêæå ïðåäñòàâè-
ìû â Ar.
Ìîæíî äîêàçàòü, ÷òî äëÿ ëþáîãî ïðåäñòàâèìîãî â Ar ïðåäè-
êàòà
P è ëþáîé ïðåäñòàâëÿþùåé åãî â Ar ôîðìóëû F ýòîò ïðåäèêàò
ñîâïàäàåò ñ ïðåäèêàòîì
F
, ïîðîæäàåìûì ôîðìóëîé F â ñòàíäàð-
òíîé èíòåðïðåòàöèè
N.
ÒÅÎÐÅÌÀ. Âñÿêèé ðàçðåøèìûé ïðåäèêàò ïðåäñòàâèì â Ar
1)
.
1)
Ýòó òåîðåìó íåñëîæíî äîêàçàòü íà íåôîðìàëüíîì óðîâíå.
Представимость
арифметических
предикатов
в теории Ar
256
ÒÅÎÐÅÌÀ. Åñëè Ar íåïðîòèâîðå÷èâà, òî âñÿêèé ïðåäñòàâè-
ìûé â Ar àðèôìåòè÷åñêèé ïðåäèêàò ðàçðåøèì
1)
.
Ìîæíî äîêàçàòü, ÷òî ñëåäóþùèå ïðåäèêàòû ðàçðåøèìû
2)
, à çíà-
÷èò, ïðåäñòàâèìû â Ar:
1)
Fr(n) – «n åñòü ã¸äåëåâ íîìåð ôîðìóëû»;
2)
Ax(n) – «n åñòü ã¸äåëåâ íîìåð àêñèîìû Ar»;
3)
D
1
(n) – «n åñòü ã¸äåëåâ íîìåð äåðåâà âûâîäà â Ar»;
4)
D
2
(n, m) – «n åñòü ã¸äåëåâ íîìåð äåðåâà âûâîäà â Ar ôîðìó-
ëû ñ ã¸äåëåâûì íîìåðîì m».
Ê. øäåëþ â 1931 ãîäó óäàëîñü ïîñòðîèòü çàìê-
íóòóþ ôîðìóëó, òàêóþ ÷òî íè îíà ñàìà, íè åå
îòðèöàíèå íåäîêàçóåìû â Ar, äîêàçàâ òåì ñàìûì
íåïîëíîòó Ar. Íàïîìíèì, ÷òî âñÿêóþ çàìêíóòóþ ôîðìóëó, íåäî-
êàçóåìóþ â òåîðèè âìåñòå ñî ñâîèì îòðèöàíèåì, íàçûâàþò íåðàç-
ðåøèìûì ïðåäëîæåíèåì ýòîé òåîðèè.
Ïåðåéäåì ê ïîñòðîåíèþ ýòîé ôîðìóëû. Ââåäåì ñíà÷àëà äâóìå-
ñòíûé àðèôìåòè÷åñêèé ïðåäèêàò
W, êîòîðûé èãðàåò îñîáóþ ðîëü
â äîêàçàòåëüñòâå òåîðåìû øäåëÿ (áóäåì íàçûâàòü åãî ã¸äåëåâûì
ïðåäèêàòîì). Ïðåäèêàò
W çàäàäèì ñëåäóþùèì ïðåäëîæåíèåì ñ
äâóìÿ ïåðåìåííûìè:
«n åñòü ã¸äåëåâ íîìåð íåêîòîðîé ôîðìóëû À ñ åäèíñòâåííîé
ñâîáîäíîé ïåðåìåííîé õ
1
, à m åñòü ã¸äåëåâ íîìåð äåðåâà âûâîäà â
Ar ôîðìóëû À(
n
)».
øäåëåâ ïðåäèêàò W îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè
3)
:
1) ïðåäèêàò
W ðàçðåøèì;
2) ïðåäèêàò
W ïðåäñòàâèì â Ar.
Ïóñòü W(õ
1
, õ
2
) – ôîðìóëà ñ äâóìÿ ïåðåìåííûìè õ
1
è õ
2
, ïðåä-
ñòàâëÿþùàÿ â Ar ïðåäèêàò
W, ò. å. äëÿ ëþáûõ íàòóðàëüíûõ ÷èñåë
k
1
, k
2
:
1) åñëè
W(k
1
, k
2
) = È, òî
Ar
W(
12
,
kk
);
2) åñëè
W(k
1
, k
2
) = Ë, òî
Ar
¬W(
12
,
kk
).
1)
Áîëåå òî÷íóþ ôîðìóëèðîâêó ýòîé òåîðåìû ïîëó÷àþò èç äàííîé ôîðìó-
ëèðîâêè çàìåíîé ñëîâ «ïðåäèêàò ðàçðåøèì» íà ñëîâà «ïðåäèêàò ðåêóðñèâåí».
 äîêàçàòåëüñòâå ýòîé òåîðåìû èñïîëüçóþò ñðåäñòâà òåîðèè àëãîðèòìîâ, ÷òî
âûõîäèò çà ðàìêè íàøåãî êóðñà. Ýòî äîêàçàòåëüñòâî ìîæíî íàéòè, íàïðèìåð,
â [10].
2)
Äîêàçàòåëüñòâî òîãî, ÷òî ýòè ïðåäèêàòû ðàçðåøèìû (òî÷íåå ãîâîðÿ, ðå-
êóðñèâíû), ìîæíî íàéòè, íàïðèìåð, â [10].
3)
Äîêàçàòåëüñòâî ìîæíî íàéòè, íàïðèìåð, â [10].
Теорема Гёделя
о неполноте
Ar
257
Ïîñòðîèì ôîðìóëó ñ åäèíñòâåííîé ñâîáîäíîé ïåðåìåííîé õ
1
:
G
1
(õ
1
) >õ
2
¬W(õ
1
, õ
2
).
Îáîçíà÷èì ÷åðåç m – ã¸äåëåâ íîìåð ôîðìóëû G
1
(õ
1
). Ïîäñòà-
âèâ òåðì
m
â ôîðìóëó G
1
(õ
1
), ïîëó÷èì íîâóþ ôîðìóëó G
1
(
m
).
Îáîçíà÷èì åå ÷åðåç G, ò. å.
G
>õ
2
¬W(
m
, õ
2
).
Ïóñòü T – òåîðèÿ, â ÿçûêå êîòîðîé åñòü òåðìû, èçîáðàæàþùèå
íàòóðàëüíûå ÷èñëà:
0
,
1
, …,
n
, …
øäåëü ââåë ñëåäóþùóþ õàðàêòåðèñòèêó òåîðèé ïåðâîãî ïîðÿäêà.
Òåîðèþ T íàçûâàþò
ωω
ωω
ω-ïðîòèâîðå÷èâîé, åñëè ñóùåñòâóåò ôîð-
ìóëà À(x) ÿçûêà T ñ îäíîé ñâîáîäíîé ïåðåìåííîé õ òàêàÿ, ÷òî:
1)
T
À(
0
),
T
À(
1
), …,
T
À(
n
), … (ò. å.
T
À(
n
) äëÿ ëþáîãî
íàòóðàëüíîãî n);
2)
T
∃õ ¬À(x).
Òåîðèþ T íàçûâàþò ω-íåïðîòèâîðå÷èâîé, åñëè ôîðìóëû, óäîâ-
ëåòâîðÿþùåé óñëîâèÿì 1 è 2, íå ñóùåñòâóåò.
ÓÒÂÅÐÆÄÅÍÈÅ. Åñëè òåîðèÿ Ò ω-íåïðîòèâîðå÷èâà, òî îíà
íåïðîòèâîðå÷èâà.
Äîêàçàòåëüñòâî. Äîïóñòèì, ÷òî Ò ω-íåïðîòèâîðå÷èâà,
íî ïðîòèâîðå÷èâà. Ïóñòü
n
k
P
– êàêîé-íèáóäü ïðåäèêàòíûé ñèìâîë
ß
Ò
. Îáîçíà÷èì ÷åðåç À(x) ôîðìóëó
n
k
P
(õ, …, õ). Òîãäà, òàê êàê â Ò
âûâîäèìû âñå ôîðìóëû, äëÿ ëþáîãî íàòóðàëüíîãî n
T
À(
n
) è
T
∃õ ¬À(x). Ñëåäîâàòåëüíî, Ò ω-ïðîòèâîðå÷èâà, ÷òî ïðîòèâîðå÷èò
äîïóùåíèþ.
Çàìåòèì, ÷òî îáðàòíîå íåâåðíî. Â ïðåäïîëîæåíèè, ÷òî Ar íå-
ïðîòèâîðå÷èâà, ìîæíî ïðèâåñòè ïðèìåð íåïðîòèâîðå÷èâîãî, íî
ω-ïðîòèâîðå÷èâîãî ðàñøèðåíèÿ Ar. Ýòîò ïðèìåð áóäåò ïðèâåäåí
ïîçæå.
! ÒÅÎÐÅÌÀ (øäåëÿ î íåïîëíîòå Ar, 1931).
1. Åñëè Ar íåïðîòèâîðå÷èâà, òî
Ar
G.
2. Åñëè Ar ω-íåïðîòèâîðå÷èâà, òî
Ar
¬G.
258
Äîêàçàòåëüñòâî.
1. Ïðåäïîëîæèì, ÷òî Ar íåïðîòèâîðå÷èâà. Äîïóñòèì, ÷òî
Ar
G.
Ïóñòü
DD
DD
D åñòü íåêîòîðûé Ar-∅-G-âûâîä, à p åãî ã¸äåëåâ íîìåð.
Ïîñêîëüêó G = G
1
(
m
), òî ð åñòü ã¸äåëåâ íîìåð íåêîòîðîãî
Ar-äîêàçàòåëüñòâà
DD
DD
D ôîðìóëû G
1
(
m
), ãäå m åñòü ã¸äåëåâ íîìåð
ôîðìóëû G
1
(õ
1
). Ñîãëàñíî îïðåäåëåíèþ ã¸äåëåâà ïðåäèêàòà W, ïî-
ëó÷àåì, ÷òî
W(m, p) = È. Ïîñêîëüêó ôîðìóëà W(õ
1
, õ
2
) ïðåäñòàâëÿ-
åò ïðåäèêàò
W â Ar, òî
Ar
W(
m
,
p
). Ñ äðóãîé ñòîðîíû, ñîãëàñíî
äîïóùåíèþ,
Ar
G, ò. å.
Ar
>õ
2
¬W(
m
, õ
2
), îòêóäà ïî ïðàâèëó >ó
ïîëó÷àåì, ÷òî
Ar
¬W(
m
,
p
). Èòàê, ïîëó÷èëè, ÷òî
Ar
W(
m
,
p
) è
Ar
¬W(
m
,
p
), à ýòî ïðîòèâîðå÷èò ïðåäïîëîæåíèþ î íåïðîòèâî-
ðå÷èâîñòè Ar.
2. Ïðåäïîëîæèì, ÷òî Ar ω-íåïðîòèâîðå÷èâà. Äîïóñòèì, ÷òî
Ar
¬G, ò. å.
Ar
¬>õ
2
¬W(
m
, õ
2
). Òîãäà, èñïîëüçóÿ ïðîèçâîäíîå
PN-ïðàâèëî äå Ìîðãàíà, ïîëó÷àåì, ÷òî
Ar
∃õ
2
¬¬W(
m
, õ
2
).
Âìåñòå ñ òåì èç äîïóùåíèÿ îá ω-íåïðîòèâîðå÷èâîñòè Ar ñëå-
äóåò, ÷òî Ar íåïðîòèâîðå÷èâà. Îòñþäà, ó÷èòûâàÿ, ÷òî
Ar
¬G, ïî-
ëó÷àåì:
Ar
G. Ñëåäîâàòåëüíî, íèêàêîå íàòóðàëüíîå ÷èñëî íå ÿâëÿ-
åòñÿ ã¸äåëåâûì íîìåðîì Ar-∅-G-âûâîäà. Ýòî îçíà÷àåò, ÷òî
W(m, n) = Ë äëÿ ëþáîãî n. Îòñþäà, ñîãëàñíî îïðåäåëåíèþ ïðåä-
ñòàâèìîãî â Ar ïðåäèêàòà, äëÿ ëþáîãî íàòóðàëüíîãî n âåðíî
Ar
¬W(
m
,
n
).  ñèëó ïðåäïîëîæåíèÿ îá ω-íåïðîòèâîðå÷èâîñòè
Ar, ïîëó÷àåì, ÷òî
Ar
∃õ
2
¬¬W(
m
, õ
2
). Òàêèì îáðàçîì, ïðèøëè ê
ïðîòèâîðå÷èþ:
Ar
∃õ
2
¬¬W(
m
, õ
2
) è
Ar
∃õ
2
¬¬W(
m
, õ
2
), ÷òî è çà-
âåðøàåò äîêàçàòåëüñòâî.
Çàìå÷àíèå 4. Åñëè Ar íåïðîòèâîðå÷èâà, òî, ñîãëàñíî òåîðåìå
øäåëÿ,
Ar
G. Ñëåäîâàòåëüíî, ïî âòîðîé òåîðåìå ðåäóêöèè, òåîðèÿ
Ar + ¬G íåïðîòèâîðå÷èâà.  òî æå âðåìÿ, åñëè Ar ω-íåïðîòèâîðå-
÷èâà, òî
Ar
¬G, à çíà÷èò, Ar + G íåïðîòèâîðå÷èâà.
Çàìå÷àíèå 5. Ìîæíî äîêàçàòü, ÷òî òåîðèÿ Ar + ¬G íåïðîòèâî-
ðå÷èâà, íî ω-ïðîòèâîðå÷èâà.
259
S Âûÿñíèì, ÷òî ïðåäñòàâëÿåò ñîáîé âûñêàçûâàíèå
G
, ñîîòâåò-
ñòâóþùåå ã¸äåëåâñêîé íåðàçðåøèìîé ôîðìóëå G â ñòàíäàðòíîé
èíòåðïðåòàöèè N. Çàìêíóòàÿ ôîðìóëà G, ïîñòðîåííàÿ øäåëåì,
åñëè åå ïðî÷èòàòü â óïðîùåííîì âèäå â ñòàíäàðòíîé èíòåðïðåòà-
öèè, ïðåäñòàâëÿåò ñîáîé ïðåäëîæåíèå «íå ñóùåñòâóåò äîêàçàòåëü-
ñòâà ôîðìóëû G â òåîðèè Ar». Òàêèì îáðàçîì, G «ãîâîðèò» î ñâîåé
ñîáñòâåííîé íåäîêàçóåìîñòè â Ar (ñîäåðæàòåëüíî âûðàæàåò ñâîþ
ñîáñòâåííóþ íåäîêàçóåìîñòü â Ar).
S Çäåñü ïðîñìàòðèâàåòñÿ àíàëîãèÿ ñ èçâåñòíûì ïàðàäîêñîì ëæå-
öà. Ñóòü åãî â ñëåäóþùåì. Íåêòî ãîâîðèò: «ß ëãó» (òî÷íåå, «Òî, ÷òî
ÿ ñåé÷àñ ãîâîðþ, åñòü ëîæü»). Òàêèì îáðàçîì, èìååì ïðåäëîæåíèå,
ãîâîðÿùåå î ñâîåé ñîáñòâåííîé ëîæíîñòè. Íåñëîæíûå ðàññóæäå-
íèÿ ïîêàçûâàþò, ÷òî ýòî ïðåäëîæåíèå íå ìîæåò áûòü íè èñòèí-
íûì, íè ëîæíûì. Åñëè íåôîðìàëüíûå ðàññóæäåíèÿ, êîòîðûå ïðè-
âîäÿò ê ïàðàäîêñó ëæåöà, ôîðìàëèçîâàòü, ò. å. ïåðåâåñòè íà ÿçûê
Ar, çàìåíèâ ïðè ýòîì èñòèííîñòü íà äîêàçóåìîñòü â Ar, òî íèêàêî-
ãî ïðîòèâîðå÷èÿ íå âîçíèêàåò, íî îêàçûâàåòñÿ âîçìîæíûì ïîñò-
ðîèòü çàìêíóòóþ ôîðìóëó, íåäîêàçóåìóþ è íåîïðîâåðæèìóþ â Ar
(â ïðåäïîëîæåíèè, ÷òî Ar ω-íåïðîòèâîðå÷èâà).
Ïîçæå, â 1936 ãîäó, Ðîññåð äîêàçàë, ÷òî äîñòàòî÷íî îãðàíè-
÷èòüñÿ ïðåäïîëîæåíèåì î ïðîñòîé íåïðîòèâîðå÷èâîñòè Ar. Ïðàâ-
äà, äîêàçàòåëüñòâî íåïîëíîòû Ar ïðè ýòîì íåñêîëüêî óñëîæíè-
ëîñü. Ïîñòðîåííàÿ Ðîññåðîì çàìêíóòàÿ ôîðìóëà G
R
, íåäîêàçóåìàÿ
è íåîïðîâåðæèìàÿ â Ar, ñëîæíåå, ÷åì ã¸äåëåâà ôîðìóëà G.
! ÒÅÎÐÅÌÀ (øäåëÿ â ôîðìå Ðîññåðà). Åñëè Ar íåïðîòèâîðå÷èâà,
òî ñóùåñòâóåò òàêàÿ çàìêíóòàÿ ôîðìóëà, ÷òî íè îíà, íè åå îòðèöà-
íèå íåäîêàçóåìû â Ar.
Èòàê, ã¸äåëåâñêàÿ çàìêíóòàÿ ôîðìóëà G èñòèí-
íà â ñòàíäàðòíîé èíòåðïðåòàöèè, íî íåäîêàçóå-
ìà â Ar (â ïðåäïîëîæåíèè, ÷òî Ar íåïðîòèâîðå-
÷èâà).
Ïåðâîå, ÷òî ïðèõîäèò â ãîëîâó – äëÿ «èñïðàâëåíèÿ» ñèòóàöèè
äîáàâèòü ê àêñèîìàì Ar ôîðìóëó G â êà÷åñòâå íîâîé àêñèîìû.
Îêàçûâàåòñÿ, ÷òî äëÿ òåîðèè Ar + G òàêæå ìîæíî ïîñòðîèòü
íåðàçðåøèìîå ïðåäëîæåíèå àíàëîãè÷íî òîìó, êàê ýòî áûëî ñäåëà-
íî äëÿ ñàìîé Ar. Áîëåå òîãî, èìååò ìåñòî ñëåäóþùàÿ òåîðåìà.
! ÒÅÎÐÅÌÀ (îáîáùåíèå òåîðåìû øäåëÿ î íåïîëíîòå). Âñÿêîå íå-
ïðîòèâîðå÷èâîå ýôôåêòèâíî àêñèîìàòèçèðîâàííîå ðàñøèðåíèå Ar
íåðàçðåøèìî è íåïîëíî.
Существенная
неполнота Ar
260
Çàìå÷àíèå 6. Èñïîëüçóÿ îáîáùåíèå òåîðåìû øäåëÿ î íåïîëíî-
òå Ar, ìîæíî â êà÷åñòâå óïðàæíåíèÿ äîêàçàòü, ÷òî:
1) ìíîæåñòâî ôîðìóë, èñòèííûõ â ñòàíäàðòíîé èíòåðïðåòàöèè
ÿçûêà Ar, íåðàçðåøèìî;
2) íå ñóùåñòâóåò ýôôåêòèâíî àêñèîìàòèçèðîâàííîé ýëåìåí-
òàðíîé òåîðèè, êëàññ âñåõ òåîðåì êîòîðîé ñîâïàäàåò ñ êëàññîì ôîð-
ìóë, èñòèííûõ â ñòàíäàðòíîé èíòåðïðåòàöèè
N.
Ìîæíî ïîñòðîèòü çàìêíóòóþ ôîðìóëó Con
Ar
ÿçû-
êà Ar, êîòîðîé â ñòàíäàðòíîé èíòåðïðåòàöèè
ñîîòâåòñòâóåò óòâåðæäåíèå î íåïðîòèâîðå÷èâî-
ñòè Ar, ò. å. î íåñóùåñòâîâàíèè ôîðìóëû, âûâîäèìîé â Ar âìåñòå
ñî ñâîèì îòðèöàíèåì
1)
. Äðóãèìè ñëîâàìè, ôîðìóëà Con
Ar
ñîäåðæà-
òåëüíî âûðàæàåò óòâåðæäåíèå î íåïðîòèâîðå÷èâîñòè Ar (ñì., íà-
ïðèìåð, [10]): |
Ar
Con
| = È òîãäà è òîëüêî òîãäà, êîãäà Ar íåïðîòè-
âîðå÷èâà. Òàêîãî òèïà ôîðìóëó ìîæíî ïîñòðîèòü íååäèíñòâåííûì
îáðàçîì.
★ Ðàññìîòðèì ïðèìåð ïîñòðîåíèÿ ôîðìóëû òèïà Con
Ar
. Ýëåìåí-
òàðíàÿ òåîðèÿ Ar íåïðîòèâîðå÷èâà òîãäà è òîëüêî òîãäà, êîãäà
Ar
01=
. Â ñàìîì äåëå, â Ar äîêàçóåìà ôîðìóëà ¬(
01=
), à çíà-
÷èò, Ar ïðîòèâîðå÷èâà òîãäà è òîëüêî òîãäà, êîãäà
Ar
01=
.
Òàêèì îáðàçîì, ñëåäóþùèå òðè âûñêàçûâàíèÿ ýêâèâàëåíòíû:
1) Ar íåïðîòèâîðå÷èâà;
2)
Ar
01=
(ôîðìóëà
01=
íåäîêàçóåìà â Ar);
3) íèêàêîå íàòóðàëüíîå ÷èñëî íå ÿâëÿåòñÿ ã¸äåëåâûì íîìåðîì
âûâîäà ôîðìóëû
01=
.
Âûðàçèì íà ÿçûêå Ar ïîñëåäíåå èç ýòèõ óòâåðæäåíèé.
Ìû îáîçíà÷èëè ÷åðåç
D
2
ïðåäèêàò, çàäàâàåìûé ïðåäëîæåíèåì
«n åñòü ã¸äåëåâ íîìåð äåðåâà âûâîäà â Ar ôîðìóëû ñ ã¸äåëåâûì
íîìåðîì m». Îáîçíà÷èì ÷åðåç q
0
– ã¸äåëåâ íîìåð ôîðìóëû
01=
.
Ôîðìóëà
01=
íåäîêàçóåìà â Ar òîãäà è òîëüêî òîãäà, êîãäà äëÿ
âñÿêîãî íàòóðàëüíîãî m
D
2
(m, q
0
) = Ë: (m) (¬D
2
(m, q
0
)).
1)
Îáîçíà÷åíèå Con ïðîèñõîäèò îò àíãë. consistency – «íåïðîòèâîðå÷èâîñòü,
ñîâìåñòíîñòü».
Вторая теорема
Гёделя о неполноте