Лекции - Математическая логика
Подождите немного. Документ загружается.
241
¬F. Ñëåäîâàòåëüíî, â ñèëó ïîëíîòû Ò îòíîñèòåëüíî M, ôîðìóëà
¬F äîêàçóåìà â T.
ÑËÅÄÑÒÂÈÅ. Òåîðèÿ T ïîëíà îòíîñèòåëüíî íåêîòîðîé ñâîåé
ìîäåëè òîãäà è òîëüêî òîãäà, êîãäà T ïîëíà îòíîñèòåëüíî âñÿêîé
ñâîåé ìîäåëè.
Çàìå÷àíèå 2. Òåîðåìà ðàâíîñèëüíà ñëåäóþùåìó óòâåðæäåíèþ,
çàïèñàííîìó â ñèìâîëè÷åñêîé ôîðìå:
(Ò) (
M
T
) (T ïîëíà îòíîñèòåëüíî M
T
↔ Ò ïîëíà).
§ 5.5. Òåîðèè ïåðâîãî ïîðÿäêৠ5.5. Òåîðèè ïåðâîãî ïîðÿäêà
§ 5.5. Òåîðèè ïåðâîãî ïîðÿäêৠ5.5. Òåîðèè ïåðâîãî ïîðÿäêà
§ 5.5. Òåîðèè ïåðâîãî ïîðÿäêà
ñ ðàâåíñòâîìñ ðàâåíñòâîì
ñ ðàâåíñòâîìñ ðàâåíñòâîì
ñ ðàâåíñòâîì
Ïðàêòè÷åñêè âî âñåõ äîñòàòî÷íî ãëóáîêèõ íå-
ôîðìàëüíûõ òåîðèÿõ ïðèñóòñòâóåò ïðåäèêàò ðàâåíñòâà, îáîçíà÷àå-
ìûé ñèìâîëîì =. Ïðåäëîæåíèå õ = ó ÿâëÿåòñÿ èñòèííûì òîãäà è
òîëüêî òîãäà, êîãäà îáúåêòû õ è ó ñîâïàäàþò. Ìîæíî âûäåëèòü
ñëåäóþùèå îñíîâíûå ñâîéñòâà ðàâåíñòâà. Âî-ïåðâûõ, âñÿêèé ïðåä-
ìåò ðàâåí ñàìîìó ñåáå (ðåôëåêñèâíîñòü), ÷òî ìîæíî âûðàçèòü ôîð-
ìóëîé >õ (õ = õ). Âî-âòîðûõ, ðàâíûå (ñîâïàäàþùèå) îáúåêòû íåëüçÿ
ðàçëè÷èòü â òîì ñìûñëå, ÷òî åñëè ÷òî-òî ïðèñóùå îäíîìó èç ðàâ-
íûõ îáúåêòîâ, òî îíî ïðèñóùå è äðóãîìó. Èíûìè ñëîâàìè, åñëè
íåêîòîðûì ñâîéñòâîì îáëàäàåò îäèí èç ðàâíûõ îáúåêòîâ, òî èì
îáëàäàåò è äðóãîé. Ñèìâîëè÷åñêè ýòî ìîæíî çàïèñàòü ñëåäóþùèì
îáðàçîì:
(
P) (õ) (ó) (õ = ó → (P(õ) → P(ó))).
Êàê ýòî çàïèñàòü íà ÿçûêå ïåðâîãî ïîðÿäêà? Ñâîéñòâà îáúåêòîâ
(ïðåäìåòîâ) ìîæíî âûðàæàòü ñ ïîìîùüþ ôîðìóë ýòîãî ÿçûêà, îä-
íàêî íå âñÿêîå ñâîéñòâî
P âûðàçèìî òàêèì îáðàçîì. Ìû âûíóæäå-
íû îãðàíè÷èòüñÿ ëèøü òåìè ñâîéñòâàìè, êîòîðûå âûðàçèìû ôîð-
ìóëàìè ßËÏ. Çàïèñàííàÿ íèæå ñõåìà ôîðìóë (ins) ïðè óêàçàííûõ
îãðàíè÷åíèÿõ âûðàæàåò, ÷òî ðàâíîå âñåãäà ìîæíî çàìåíèòü ðàâíûì.
Òåîðèåé ïåðâîãî ïîðÿäêà ñ ðàâåíñòâîì íàçûâàþò âñÿêóþ òåîðèþ
ïåðâîãî ïîðÿäêà Ò, ñðåäè ïðåäèêàòíûõ ñèìâîëîâ êîòîðîé èìå-
åòñÿ äâóìåñòíûé ïðåäèêàòíûé ñèìâîë (äëÿ îïðåäåëåííîñòè
áóäåì ñ÷èòàòü, ÷òî ýòî
2
1
P
, íî âìåñòî
2
1
P
(t
1
, t
2
) áóäåì ïèñàòü
t
1
= t
2
), è â êîòîðîé ÿâëÿþòñÿ äîêàçóåìûìè ñëåäóþùèå ôîðìóëû:
(rå) õ = õ (ðåôëåêñèâíîñòü ðàâåíñòâà);
242
(ins) õ = ó ⊃ (À(õ, õ) ⊃ À(õ, ó)) (ïîäñòàíîâî÷íîñòü ðàâåíñòâà),
ãäå õ è ó – ïðîèçâîëüíûå ïðåäìåòíûå ïåðåìåííûå; À(õ, õ) –
ïðîèçâîëüíàÿ ôîðìóëà ÿçûêà ß
T
; À(õ, ó) – ðåçóëüòàò çàìåíû â
À(õ, õ) êàêèõ-ëèáî (íå îáÿçàòåëüíî âñåõ) ñâîáîäíûõ âõîæäåíèé
õ âõîæäåíèÿìè ó, ïðè óñëîâèè, ÷òî çàìåíÿåìûå âõîæäåíèÿ õ íå
ëåæàò â îáëàñòè äåéñòâèÿ íèêàêîãî êâàíòîðà ïî ó.
Çàìå÷àíèå 1.  êà÷åñòâå ôîðìóëû, âûðàæàþùåé ðåôëåêñèâíîñòü
ðàâåíñòâà, äîñòàòî÷íî âìåñòî ñõåìû õ = õ ñ ïðîèçâîëüíîé ïåðå-
ìåííîé õ, èñïîëüçîâàòü ôîðìóëó õ
1
= õ
1
ñ ôèêñèðîâàííîé ïåðå-
ìåííîé õ
1
. Îäíàêî äëÿ óïðîùåíèÿ òåõíèêè ìû ýòîãî äåëàòü íå
áóäåì.
Îñòàíîâèìñÿ íà íåêîòîðûõ îáùèõ ñâîéñòâàõ òå-
îðèé ïåðâîãî ïîðÿäêà ñ ðàâåíñòâîì. Ñíà÷àëà
äîêàæåì, ÷òî â òàêèõ òåîðèÿõ äîêàçóåìû ôîðìó-
ëû, âûðàæàþùèå ðåôëåêñèâíîñòü (re), ñèììåò-
ðè÷íîñòü (si) è òðàíçèòèâíîñòü (tr) ðàâåíñòâà.
! ÒÅÎÐÅÌÀ 1. Âî âñÿêîé òåîðèè ïåðâîãî ïîðÿäêà ñ ðàâåíñòâîì
Ò äëÿ ëþáûõ ïðåäìåòíûõ ïåðåìåííûõ õ, ó, z ÿâëÿþòñÿ Ò-òåîðåìà-
ìè ôîðìóëû (re), (si) è (tr):
1)
T
õ = õ;
2)
T
õ = ó ⊃ ó = õ;
3)
T
õ = ó & ó = z ⊃ õ = z.
Äîêàçàòåëüñòâî. Ñïðàâåäëèâîñòü óòâåðæäåíèÿ ï. 1 ãà-
ðàíòèðîâàíà îïðåäåëåíèåì òåîðèè ñ ðàâåíñòâîì.
Äëÿ äîêàçàòåëüñòâà óòâåðæäåíèÿ ï. 2 ðàññìîòðèì ñëåäóþùåå
äåðåâî Ò-âûâîäà:
у
в
у
у
в
(ins)
1
(re)
(1)
()
[]
()
xy xz yz
xy
xz yz
zx z y z
xx yx
xx
yx
xy yx
⊃
∀
∀
⊃
⊃
=⊃ =⊃=
=
=⊃=
∀=⊃=
=⊃=
=
=
=⊃=
.
 ýòîì äåðåâå âûâîäà ôîðìóëà õ = ó ⊃ (õ = z ⊃ ó = z) ïîëó÷åíà
ïî ñõåìå (ins), â êîòîðîé â êà÷åñòâå ôîðìóëû À(õ, õ) âçÿòà ôîðìóëà
õ = z, à â êà÷åñòâå À(õ, ó) – ôîðìóëà ó = z.
Свойства теорий
первого порядка
с равенством
243
Äëÿ äîêàçàòåëüñòâà óòâåðæäåíèÿ ï. 3 ðàññìîòðèì ñëåäóþùåå
äåðåâî Ò-âûâîäà:
1
(si) (ins)
1
â(1)
[&]
[&]
()
&
xy yz
xy
yx
xy yz
yx yz xz
yz yz xz
xz
xy yz xz
⊃
==
=
=
==
=⊃ =⊃=
==⊃=
=
==⊃=
 ýòîì äåðåâå âûâîäà ôîðìóëà ó = õ ⊃ (ó = z ⊃ õ = z) ïîëó÷åíà ïî
ñõåìå (ins), â êîòîðîé â êà÷åñòâå ôîðìóëû À(ó, ó) âçÿòà ôîðìóëà
ó = z, à â êà÷åñòâå À(õ, ó) – ôîðìóëà õ = z (çäåñü õ è ó ïîìåíÿëèñü
ìåñòàìè).
ÑËÅÄÑÒÂÈÅ. Âî âñÿêîé òåîðèè ïåðâîãî ïîðÿäêà ñ ðàâåíñòâîì Ò
äëÿ ëþáûõ ïðåäìåòíûõ ïåðåìåííûõ õ, ó, z ÿâëÿþòñÿ Ò-òåîðåìàìè
ôîðìóëû (reR), (siR) è (trR), ÿâëÿþùèåñÿ çàìûêàíèÿìè ôîðìóë (re),
(si) è (tr) ñîîòâåòñòâåííî:
1)
T
>õ (õ = õ);
2)
T
>õ >ó (õ = ó ⊃ ó = õ);
3)
T
>õ >ó >z (õ = ó & ó = z ⊃ õ = z).
ÒÅÎÐÅÌÀ 2. Âî âñÿêîé òåîðèè ñ ðàâåíñòâîì äëÿ ëþáûõ òåð-
ìîâ t, r, s ÿçûêà ýòîé òåîðèè âûïîëíÿåòñÿ:
(rå
t
)
T
t = t;
(si
t
)
T
t = r ⊃ r = t;
(tr
t
)
T
t = r & r = s ⊃ t = s.
Äîêàçàòåëüñòâî. Äîêàæåì óòâåðæäåíèå (rå
t
) ïîñòðîåíèåì
ñîîòâåòñòâóþùåãî Ò-âûâîäà:
(re)
â
y
()
õõ
xx x
tt
∀
∀
=
∀=
=
Íà ïåðâûé âçãëÿä êàæåòñÿ, ÷òî äëÿ äîêàçàòåëüñòâà óòâåðæäå-
íèÿ (si
t
) äîñòàòî÷íî, îïèðàÿñü íà óòâåðæäåíèå ï. 2 òåîðåìû 1, äâàæäû
âîñïîëüçîâàòüñÿ ïðàâèëîì >ó, ñíà÷àëà ïîäñòàâèâ òåðì t âìåñòî õ, à
çàòåì òåðì r âìåñòî ó. Îäíàêî ðåçóëüòàò òàêîé ïîñëåäîâàòåëüíîé
ïîäñòàíîâêè ìîæåò îòëè÷àòüñÿ îò ðåçóëüòàòà îäíîâðåìåííîé ïîä-
244
ñòàíîâêè (êîòîðûé íàì è íóæåí). Íàïðèìåð, åñëè â òåðì t âõîäèò
ïåðåìåííàÿ ó, òî ïðè ïîäñòàíîâêå òåðìà r âìåñòî ó ïðè ïîâòîðíîì
ïðèìåíåíèè ïðàâèëà >ó ïðèäåòñÿ ïîäñòàâëÿòü r íå òîëüêî âìåñòî
èçíà÷àëüíûõ âõîæäåíèé ó, íî è âìåñòî âîçìîæíûõ íîâûõ âõîæäå-
íèé ó, ÷òî ñîâñåì íåæåëàòåëüíî. Èçáåæàòü ýòîé ñèòóàöèè ìîæíî
ñëåäóþùèì îáðàçîì. Ôèêñèðóåì ïðîèçâîëüíûå òåðìû t è r. Ïî-
ñêîëüêó âûâîäèìîñòü óòâåðæäåíèÿ ï. 2 â òåîðåìå 1 ñïðàâåäëèâà
äëÿ ëþáûõ ïåðåìåííûõ, ìû ìîæåì âûáðàòü òàêèå ïåðåìåííûå,
êîòîðûå íå âõîäÿò â òåðìû t è r. Áåç ïîòåðè îáùíîñòè ìîæíî ñ÷è-
òàòü, ÷òî òàêèìè ïåðåìåííûìè ÿâëÿþòñÿ õ è ó. Òåïåðü, ïðè ñîáëþ-
äåíèè óêàçàííûõ îãðàíè÷åíèé, ìîæíî ïîñòðîèòü ñîîòâåòñòâóþùåå
äåðåâî Ò-âûâîäà:
y
y
()
()
xyx y y x
yt y y t
tr rt
∀
∀
∀∀ = ⊃ =
∀=⊃=
=⊃=
Ïîñêîëüêó ïåðåìåííûå õ è ó íå âõîäÿò â òåðìû t è r, îáà ïðè-
ìåíåíèÿ ïðàâèëà >ó çàêîííû (íåò íàðóøåíèé èçâåñòíûõ îãðàíè-
÷åíèé).
Àíàëîãè÷íûì îáðàçîì, èñïîëüçóÿ óòâåðæäåíèå ï. 3 è ïðèìå-
íÿÿ òðè ðàçà ïðàâèëî >ó, ìîæíî äîêàçàòü (tr
t
).
Òîëüêî ÷òî äîêàçàííóþ òåîðåìó ìîæíî ïîëó÷èòü â êà÷åñòâå
ñëåäñòâèÿ ñëåäóþùåãî áîëåå îáùåãî óòâåðæäåíèÿ.
ÓÒÂÅÐÆÄÅÍÈÅ (î ïîäñòàíîâêàõ â äîêàçóåìûå ôîðìóëû).
1. Êàêîâû áû íè áûëè Ò-äîêàçóåìàÿ áåñêâàíòîðíàÿ ôîðìóëà
À(õ
1
) ñ åäèíñòâåííîé ïåðåìåííîé õ
1
è òåðì t ÿçûêà òåîðèè Ò, ôîð-
ìóëà À(t) òàêæå Ò-äîêàçóåìà:
T
À(õ
1
) → (t)(
T
À(t)).
2. Êàêîâû áû íè áûëè Ò-äîêàçóåìàÿ áåñêâàíòîðíàÿ ôîðìóëà
À(õ
1
, õ
2
) ñ äâóìÿ ïåðåìåííûìè õ
1
, õ
2
è òåðìû t, r ÿçûêà òåîðèè Ò,
ôîðìóëà À(t, r) òàêæå Ò-äîêàçóåìà (ãäå À(t, r) – ðåçóëüòàò îäíîâðå-
ìåííîé çàìåíû â ôîðìóëå À êàæäîãî âõîæäåíèÿ õ
1
è õ
2
íà âõîæäå-
íèÿ òåðìîâ t, r ñîîòâåòñòâåííî):
T
À(õ
1
, õ
2
) → (t) (r)(
T
À(t, r)).
Äîêàçàòåëüñòâî ýòîãî óòâåðæäåíèÿ (ïîñòðîåíèåì äåðåâà Ò-âû-
âîäà) îñòàâëÿåì ÷èòàòåëþ. Îòìåòèì ëèøü ñëåäóþùåå. Ïðè äîêàçà-
òåëüñòâå óòâåðæäåíèÿ ï. 2 ñëåäóåò ó÷åñòü, ÷òî ðåçóëüòàò îäíîâðå-
ìåííîé ïîäñòàíîâêè äâóõ òåðìîâ â ôîðìóëó À ñ äâóìÿ èëè áîëåå
ñâîáîäíûìè ïåðåìåííûìè
12
()
xx
tr
A
ìîæåò íå ñîâïàäàòü ñ ðåçóëüòà-
òîì ïîñëåäîâàòåëüíîé ïîäñòàíîâêè ýòèõ æå òåðìîâ â ôîðìóëó À,
245
ò. å. âîîáùå ãîâîðÿ,
12
()
xx
tr
A
≠
12
()
()
xx
tr
A
. Äëÿ èçáåæàíèÿ òàê íàçû-
âàåìîé êîëëèçèè ïåðåìåííûõ íóæíî ñíà÷àëà ïåðåèìåíîâàòü ïåðå-
ìåííûå õ
1
è õ
2
, ïåðåéäÿ ê ïåðåìåííûì, íå âõîäÿùèì â òåðìû t è r,
à çàòåì äåëàòü íóæíóþ ïîäñòàíîâêó.
Çàìå÷àíèå 2. Àíàëîãè÷íîå óòâåðæäåíèå ìîæíî äîêàçàòü äëÿ
áåñêâàíòîðíîé ôîðìóëû ñ òðåìÿ èëè áîëåå ïåðåìåííûìè.
S Â ñèëó òåîðåìû 1 âî âñÿêîé ìîäåëè M òåîðèè ñ ðàâåíñòâîì Ò
äâóìåñòíûé ïðåäèêàò, ñîîòâåòñòâóþùèé ïðåäèêàòíîìó ñèìâîëó =,
îïðåäåëÿåò íà íîñèòåëå M îòíîøåíèå ýêâèâàëåíòíîñòè.
!
Ìîäåëü òåîðèè ñ ðàâåíñòâîì Ò íàçûâàþò íîðìàëüíîé ìîäåëüþ,
åñëè ïðåäèêàòíûé ñèìâîë = èíòåðïðåòèðóåòñÿ êàê îòíîøåíèå
ñîâïàäåíèÿ, ò. å. ñèìâîëó = îòâå÷àåò ïðåäèêàò ðàâåíñòâà.
! ÒÅÎÐÅÌÀ (øäåëÿ î ñóùåñòâîâàíèè ìîäåëè (î ïîëíîòå) äëÿ òåî-
ðèé ñ ðàâåíñòâîì). Âñÿêàÿ íåïðîòèâîðå÷èâàÿ òåîðèÿ ïåðâîãî ïî-
ðÿäêà ñ ðàâåíñòâîì èìååò íîðìàëüíóþ ìîäåëü.
Ïðè ïîñòðîåíèè òåîðèé ïåðâîãî ïîðÿäêà ñõåìó (ins) îáû÷íî íå
èñïîëüçóþò â êà÷åñòâå ñõåìû àêñèîì, ïîñêîëüêó êëàññ ôîðìóë,
ïîñòðîåííûõ ïî ýòîé ñõåìå, âåñüìà ñëîæåí è ïëîõî îáîçðèì. Ñëå-
äóþùàÿ òåîðåìà ïðåäîñòàâëÿåò ïðîñòîå è óäîáíîå äîñòàòî÷íîå óñ-
ëîâèå òîãî, ÷òî òåîðèÿ ÿâëÿåòñÿ òåîðèåé ñ ðàâåíñòâîì. Îêàçûâàåò-
ñÿ, äîñòàòî÷íî ïðîâåðèòü, ÷òî óñëîâèå ïîäñòàíîâî÷íîñòè ðàâåí-
ñòâà âûïîëíÿåòñÿ äëÿ ýëåìåíòàðíûõ ôîðìóë è òåðìîâ.
ÒÅÎÐÅÌÀ 3 (î äîñòàòî÷íîì óñëîâèè òåîðèè ñ ðàâåíñòâîì)
1)
.
Ïóñòü äëÿ òåîðèè Ò âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ:
1) êàêîâà áû íè áûëà ïåðåìåííàÿ õ,
(rå)
T
õ = õ;
2) êàêîâû áû íè áûëè ïðåäèêàòíûé ñèìâîë
n
m
P
, ôóíêöèîíàëü-
íûé ñèìâîë
n
m
f
, íàáîð ïåðåìåííûõ (íå îáÿçàòåëüíî ðàçëè÷íûõ)
(ó
1
, …, ó
i
, …, ó
n
), ïåðåìåííàÿ z
i
, äëÿ êàæäîãî i (i = 1, …, n):
(i
ð
)
T
ó
i
= z
i
⊃ (
n
m
P
(ó
1
, …, ó
i
, …, ó
n
) ⊃
n
m
P
(ó
1
, …, z
i
, …, ó
n
));
(i
f
)
T
ó
i
= z
i
⊃ (
n
m
f
(ó
1
, …, ó
i
, …, ó
n
) =
n
m
f
(ó
1
, …, z
i
, …, ó
n
)).
Òîãäà òåîðèÿ Ò ÿâëÿåòñÿ òåîðèåé ñ ðàâåíñòâîì.
1)
Äîêàçàòåëüñòâî ýòîé òåîðåìû ÷èòàòåëü ïðè æåëàíèè ìîæåò íàéòè, íà-
ïðèìåð, â [3], [10].
246
Çàìå÷àíèå 3. Ýòîé òåîðåìîé óäîáíî ïîëüçîâàòüñÿ, êîãäà ñèãíà-
òóðà ß
Ò
ñîäåðæèò êîíå÷íîå ÷èñëî ïðåäèêàòíûõ è ôóíêöèîíàëüíûõ
ñèìâîëîâ.  ýòîì ñëó÷àå äîñòàòî÷íî âçÿòü â êà÷åñòâå àêñèîì êî-
íå÷íîå ÷èñëî ôîðìóë âèäà, îïèñàííîãî â ï. 2. Ñðåäè íèõ äîëæíû
ïðèñóòñòâîâàòü è ñëåäóþùèå ôîðìóëû, âûðàæàþùèå ëåâóþ è ïðà-
âóþ ïîäñòàíîâî÷íîñòü ðàâåíñòâà:
õ = ó ⊃ (õ = z ⊃ ó = z) è õ = ó ⊃ (z = õ ⊃ z = ó),
ãäå õ, y, z – ïðîèçâîëüíûå ïåðåìåííûå.
Îäíàêî âìåñòî ýòîé ïàðû ôîðìóë â êà÷åñòâå àêñèîì îáû÷íî
èñïîëüçóþò ïàðó ôîðìóë (si) è (tr), âûðàæàþùèõ ñèììåòðè÷íîñòü
è òðàíçèòèâíîñòü ðàâåíñòâà.
Ïðèìåðû.
1. Òåîðèÿìè ïåðâîãî ïîðÿäêà ñ ðàâåíñòâîì ÿâëÿþòñÿ òåîðèè
ÒÅ, ÒG, TF, Îrd.
2. Íîðìàëüíûìè ìîäåëÿìè ÒG ÿâëÿþòñÿ ãðóïïû, è òîëüêî îíè;
íîðìàëüíûìè ìîäåëÿìè ÒF ÿâëÿþòñÿ ïîëÿ, è òîëüêî îíè; è ò. ï.
§ 5.6. Ôîðìàëüíàÿ àðèôìåòèêৠ5.6. Ôîðìàëüíàÿ àðèôìåòèêà
§ 5.6. Ôîðìàëüíàÿ àðèôìåòèêৠ5.6. Ôîðìàëüíàÿ àðèôìåòèêà
§ 5.6. Ôîðìàëüíàÿ àðèôìåòèêà
Àðèôìåòèêà íàòóðàëüíûõ ÷èñåë (ýëåìåíòàðíàÿ
òåîðèÿ ÷èñåë) ÿâëÿåòñÿ îäíîé èç ôóíäàìåíòàëüíûõ îáëàñòåé ìàòå-
ìàòèêè. Àêñèîìàòè÷åñêîå íåôîðìàëüíîå ïîñòðîåíèå àðèôìåòèêè
áûëî ðàçðàáîòàíî íåçàâèñèìî äðóã îò äðóãà â êîíöå ÕIÕ âåêà
Ð. Äåäåêèíäîì è Äæ. Ïåàíî
1)
.
S Ðàññìîòðèì ñèñòåìó àêñèîì, èçâåñòíóþ ïîä íàçâàíèåì ñèñòå-
ìû àêñèîì Ïåàíî. Åå èñõîäíûå ïîíÿòèÿ – íàòóðàëüíîå ÷èñëî,
0 (íîëü) è ÷èñëî õ R, (íåïîñðåäñòâåííî) ñëåäóþùåå çà õ (ïîäðàçóìåâà-
åòñÿ, ÷òî R åñòü îäíîìåñòíàÿ îïåðàöèÿ, ò. å. èç õ = ó ñëåäóåò õ R = yR).
Ð1. 0 åñòü íàòóðàëüíîå ÷èñëî.
Ð2. Åñëè õ – íàòóðàëüíîå ÷èñëî, òî è ñëåäóþùåå çà íèì õ R –
íàòóðàëüíîå ÷èñëî.
Ð3. 0 íå ñëåäóåò íè çà êàêèì íàòóðàëüíûì ÷èñëîì.
Ð4. Åñëè õ è ó – íàòóðàëüíûå ÷èñëà è õR = yR, òî õ = ó.
Ð5. Êàêîâî áû íè áûëî ñâîéñòâî íàòóðàëüíûõ ÷èñåë
P, åñëè 0
îáëàäàåò ýòèì ñâîéñòâîì è äëÿ âñÿêîãî íàòóðàëüíîãî ÷èñëà õ, îá-
ëàäàþùåãî ñâîéñòâîì
P, ÷èñëî õR òàêæå îáëàäàåò ñâîéñòâîì P, òî
ñâîéñòâîì
P îáëàäàþò âñå íàòóðàëüíûå ÷èñëà (àêñèîìà èíäóêöèè).
1)
Ðèõàðä Äåäåêèíä (1831–1916) – íåìåöêèé ìàòåìàòèê.
Äæóçåïïå Ïåàíî (1858–1932) – èòàëüÿíñêèé ìàòåìàòèê.
247
S Èñïîëüçóÿ ñèìâîëû ìåòàÿçûêà, ýòè àêñèîìû ìîæíî çàïèñàòü
ñóùåñòâåííî êîðî÷å ñëåäóþùèì îáðàçîì (N, 0, R – îáîçíà÷åíèÿ
èñõîäíûõ ïîíÿòèé; õ – ïåðåìåííàÿ ïî ìíîæåñòâó N;
P – ïåðåìåí-
íàÿ ïî ìíîæåñòâó ñâîéñòâ íàòóðàëüíûõ ÷èñåë):
P1. 0 ∈ N.
Ð2. (õ) (õR ∈ N).
Ð3. (õ) (õR
≠
0).
Ð4. (õ) (ó) (õR = yR → õ = ó).
Ð5. (
P) (P(0) & (õ) (P(õ) → P(õ R)) → (õ) P(õ)).
 äîêàçàòåëüñòâàõ òåîðåì âèäà (õ)
P (õ), îñíîâàííûõ íà àêñèîìå
èíäóêöèè (ïðèíöèïå èíäóêöèè), ïðèíÿòî äîêàçàòåëüñòâî ïðåäëî-
æåíèÿ
P(0) íàçûâàòü áàçèñîì èíäóêöèè, à äîêàçàòåëüñòâî ïðåäëî-
æåíèÿ (õ) (
P(õ) → P(õR)) – øàãîì èíäóêöèè.
Âñå òåîðåìû ýëåìåíòàðíîé òåîðèè ÷èñåë ìîæíî äîêàçàòü, èñ-
ïîëüçóÿ ýòó àêñèîìàòèêó. Òî÷íåå, ïðè èñïîëüçîâàíèè íåêîòîðîãî
ôðàãìåíòà òåîðèè ìíîæåñòâ, ýòîé ñèñòåìû àêñèîì äîñòàòî÷íî äëÿ
ñèñòåìàòè÷åñêîãî ïîñòðîåíèÿ ýëåìåíòàðíîé òåîðèè ÷èñåë.
S Îïèøåì òåîðèþ ïåðâîãî ïîðÿäêà, êîòîðàÿ ôîðìàëèçóåò àêñèî-
ìàòè÷åñêóþ ñèñòåìó Ïåàíî (íåôîðìàëüíóþ àðèôìåòèêó). Ýòó òåî-
ðèþ ïåðâîãî ïîðÿäêà íàçûâàþò ôîðìàëüíîé àðèôìåòèêîé. Îáîçíà-
÷èì åå ñèìâîëîì Ar.
Ïîñòðîèì ýòó òåîðèþ, çàäàâ ïàðó < σ, Àõ
Ar
>. ßçûê òåîðèè Ar
èìååò ñèãíàòóðó σ = {
2
1
Р
,
2
1
f
,
2
2
f
,
1
1
f
, c
1
}.
Ââåäåì ïðèâû÷íûå îáîçíà÷åíèÿ. Ïóñòü t
1
è t
2
– ïðîèçâîëüíûå
òåðìû ß
Ar
. Òîãäà:
0
c
1
; t
1
+ t
2
2
1
f
(t
1
, t
2
); t
1
⋅
t
2
2
2
f
(t
1
, t
2
); t
1
'
1
1
f
(t
1
);
t
1
= t
2
2
1
Ð
(t
1
, t
2
); t
1
≠
t
2
¬
2
1
Ð
(t
1
, t
2
).
Èíîãäà äëÿ íàãëÿäíîñòè áóäåì èñïîëüçîâàòü ñêîáêè: (t
1
+ t
2
),
(t
1
⋅
t
2
), (t
1
)R è (t
1
= t
2
).
Ñëåäóþùèå ôîðìóëû ÿâëÿþòñÿ àêñèîìàìè Ar:
(Ar
1
) õ
1
= õ
2
⊃ (õ
1
= õ
3
⊃ õ
2
= õ
3
);
(Ar
2
) õ
1
= õ
2
⊃ õ
1
R = õ
2
R;
(Ar
3
) ¬(0 = õ
1
R);
(Ar
4
) õ
1
R = õ
2
R ⊃ õ
1
= õ
2
;
(Ar
5
) õ
1
+ 0 = õ
1
;
(Ar
6
) õ
1
+ õ
2
R = (õ
1
+ õ
2
)R;
(Ar
7
) õ
1
⋅
0 = 0;
248
(Ar
8
) õ
1
⋅
õ
2
R = (õ
1
⋅
õ
2
) + õ
1
;
(Ar
9
) À(0) & >õ (A(õ) ⊃ A(õR)) ⊃ >õ A(õ),
ãäå õ – ïðîèçâîëüíàÿ ïðåäìåòíàÿ ïåðåìåííàÿ, À(õ) – ïðîèçâîëü-
íàÿ ôîðìóëà ß
Ar
; À(0) è A(õR) – ôîðìóëû, ïîëó÷åííûå ïîäñòàíîâ-
êîé òåðìîâ 0 è õR âìåñòî ïåðåìåííîé õ â ôîðìóëó À(x).
Ar
9
ïðåäñòàâëÿåò ñîáîé ñõåìó ôîðìóë, íàçûâàåìóþ ñõåìîé èí-
äóêöèè, ïî êîòîðîé ìîæíî ïîñòðîèòü áåñêîíå÷íî ìíîãî àêñèîì.
Ýòà ñõåìà ôîðìàëèçóåò ñîäåðæàòåëüíûé ïðèíöèï ìàòåìàòè÷åñêîé
èíäóêöèè.
Íåòðóäíî äîêàçàòü ïîñòðîåíèåì äåðåâà Ar-âûâîäà, ÷òî â Ar
ÿâëÿåòñÿ ïðîèçâîäíûì ñëåäóþùåå ïðàâèëî:
(R
ind
)
(0) ( ( ) ( '))
()
À õ Àõ Àõ
õÀõ
∀⊃
∀
,
ãäå À – ïðîèçâîëüíàÿ ôîðìóëà ß
Ar
; õ – ïðîèçâîëüíàÿ ïåðåìåííàÿ.
Ñõåìà Ar
9
íå âïîëíå ñîîòâåòñòâóåò ïåàíîâñêîé àêñèîìå èíäóê-
öèè Ð5. Ýòà ñõåìà ïîçâîëÿåò èìåòü äåëî ëèøü ñî ñâîéñòâàìè íàòó-
ðàëüíûõ ÷èñåë, âûðàæàåìûìè ôîðìóëàìè ß
Ar
, à òàêîâûõ ñ÷åòíîå
ìíîæåñòâî. Â òî æå âðåìÿ â àêñèîìå Ð5 êâàíòîð îáùíîñòè ïðåäïî-
ëàãàåòñÿ ïî âñåì ñâîéñòâàì íàòóðàëüíûõ ÷èñåë, à ýòèõ ñâîéñòâ êîí-
òèíóóì. Òàêîå íåñîîòâåòñòâèå âåäåò ê òîìó, ÷òî ó Ar ñóùåñòâóþò
íåèçîìîðôíûå ìîäåëè, â òî âðåìÿ êàê âñå ìîäåëè íåôîðìàëüíîé
ïåàíîâñêîé àðèôìåòèêè èçîìîðôíû.
Ïîÿñíèì ñîäåðæàòåëüíûé ñìûñë îñòàëüíûõ àêñèîì Ar. Ôîðìó-
ëà Ar
3
âûðàæàåò àêñèîìó Ïåàíî Ð3, ôîðìóëà Ar
4
âûðàæàåò àêñèîìó
Ð4. Ôîðìóëû Ar
5
–Ar
8
âûðàæàþò èíäóêòèâíîå îïðåäåëåíèå ñëîæå-
íèÿ è óìíîæåíèÿ. Â ñèñòåìå àêñèîì Ïåàíî ñîîòâåòñòâóþùèõ àêñè-
îì íåò, ïîñêîëüêó èñïîëüçîâàíèå èíòóèòèâíîé òåîðèè ìíîæåñòâ
ïîçâîëÿåò âûâåñòè ñóùåñòâîâàíèå îïåðàöèé + è
⋅
ñ íóæíûìè ñâîé-
ñòâàìè. Àêñèîìû Ïåàíî Ð1 è Ð2 íå íóæäàþòñÿ â ñïåöèàëüíîì âûðà-
æåíèè íà ôîðìàëüíîì óðîâíå, ïîñêîëüêó íàëè÷èå â ß
Ar
ñèìâîëà
êîíñòàíòû 0 è ôóíêöèîíàëüíîãî ñèìâîëà R îáåñïå÷èâàåò èñòèííîñòü
ýòèõ àêñèîì â ëþáîé èíòåðïðåòàöèè ß
Ar
. Ïåðâûå äâå àêñèîìû Ar
1
è Ar
2
âûðàæàþò ñâîéñòâà ïðåäèêàòíîãî ñèìâîëà = (ïîäñòàíîâî÷íîñòü ðà-
âåíñòâà), îíè îáåñïå÷èâàþò âûïîëíåíèå â ìîäåëÿõ Ar îñíîâíûõ ñâîéñòâ
ðàâåíñòâà. Ñõåìà Ar
9
, êàê óæå áûëî îòìå÷åíî, ôîðìàëèçóåò ñîäåðæà-
òåëüíûé ïðèíöèï ìàòåìàòè÷åñêîé èíäóêöèè, ò. å. àêñèîìó Ð5.
Çàìå÷àíèå 1. Òåõíè÷åñêè áîëåå óäîáíî ðàññìàòðèâàòü â êà÷å-
ñòâå àêñèîì íå ïðèâåäåííûå âûøå ôîðìóëû Ar
1
–Ar
8
, à ïðîñòåé-
øèå ñõåìû, ïîñòðîåííûå èç õ, ó, z – îáîçíà÷åíèé ïðîèçâîëüíûõ
ïåðåìåííûõ (ñì. [3]).
249
Òåðìû 0, 0', 0'' è ò. ä. åñòåñòâåííî ðàññìàòðèâàòü êàê èçîáðàæå-
íèÿ ñîîòâåòñòâåííî íàòóðàëüíûõ ÷èñåë 0, 1, 2, è ò. ä.  ñîîòâåò-
ñòâèè ñ ýòèì îáîçíà÷èì òåðì
"'
0
nðàç
⋅⋅⋅
÷åðåç
n
(n = 1, 2, ...). Èíîãäà
äëÿ åäèíîîáðàçèÿ óäîáíî èñïîëüçîâàòü ñèìâîë
0
âìåñòî 0.
Ñòàíäàðòíîé èíòåðïðåòàöèåé ÿçûêà ôîðìàëüíîé
àðèôìåòèêè Ar áóäåì íàçûâàòü èíòåðïðåòàöèþ
N = < N, = , + ,
⋅
, ', 0 > , ãäå N – ìíîæåñòâî
íàòóðàëüíûõ ÷èñåë
1)
c îáû÷íûìè îïåðàöèÿìè ñëî-
æåíèÿ, óìíîæåíèÿ, ïåðåõîäà ê ñëåäóþùåìó íàòó-
ðàëüíîìó ÷èñëó è êîíñòàíòîé íîëü; ïðåäèêàòíûé
ñèìâîë
2
1
Р
èíòåðïðåòèðóåòñÿ êàê îòíîøåíèå ðà-
âåíñòâà (ñîâïàäåíèÿ).
S Ñòàíäàðòíóþ èíòåðïðåòàöèþ ïðèíÿòî ñ÷èòàòü ìîäåëüþ Ar è
íàçûâàòü åå ñòàíäàðòíîé ìîäåëüþ ôîðìàëüíîé àðèôìåòèêè. Îä-
íàêî ïðîâåðèòü èñòèííîñòü âñåõ àêñèîì Ar â ñòàíäàðòíîé èíòåð-
ïðåòàöèè
N ìû íå ìîæåì (òî÷íåå, íå ìîæåì ïðîâåðèòü èñòèí-
íîñòü ñõåìû èíäóêöèè, íåñìîòðÿ íà åå èíòóèòèâíóþ ÿñíîñòü).
 ñâÿçè ñ ýòèì ìîæíî ïðèçíàâàòü
N ìîäåëüþ Ar â òîé ñòåïåíè, â
êîòîðîé ìû âåðèì, ÷òî â
N èñòèííà ñõåìà èíäóêöèè Ar
9
.
Ïðèâåäåì åùå äâà ïðèìåðà èíòåðïðåòàöèé ß
Ar
:
1)
N
1
= < {0, –1, –2, …}, = , + , •, *, 0 > , ãäå + åñòü îáû÷íîå
ñëîæåíèå, õ • ó = –õ•ó, õ* = õ – 1 äëÿ ëþáûõ öåëûõ íåïîëîæè-
òåëüíûõ ÷èñåë õ è ó;
2)
N
2
= < {1, 2, 3, …}, = , ⊕, •, *, 1 > , ãäå õ ⊕ ó = õ + ó – 1,
õ • ó = (õ – 1)
⋅
(ó – 1), õ* = õ + 1 äëÿ ëþáûõ ïîëîæèòåëüíûõ
öåëûõ ÷èñåë õ è ó, 1 – èíòåðïðåòàöèÿ ñèìâîëà 0.
Íåñëîæíî äîêàçàòü, ÷òî îáå ýòè èíòåðïðåòàöèè èçîìîðôíû ñòàí-
äàðòíîé.
S Íåñòàíäàðòíîé ìîäåëüþ Ar íàçûâàþò âñÿêóþ íîðìàëüíóþ ìî-
äåëü ýòîé òåîðèè, íåèçîìîðôíóþ ñòàíäàðòíîé.
Ìîæíî äîêàçàòü, ÷òî ñóùåñòâóþò áåñêîíå÷íûå íåñòàíäàðòíûå
ìîäåëè Ar ëþáîé ìîùíîñòè, â òîì ÷èñëå ñ÷åòíûå (ñì. [7], [10] è [1]).
1)
Ïîä íàòóðàëüíûìè ÷èñëàìè ìîæíî ïîíèìàòü, íàïðèìåð, ñëîâà â àëôà-
âèòå |. Ñëîâà |, ||, |||, … îáîçíà÷àþò ïðè òàêîì ïîäõîäå ñîîòâåòñòâåííî 0, 1, 2, 3, …
Îïåðàöèè îïðåäåëÿþòñÿ èíäóêòèâíî (ñì. [9]).
Интерпретации
языка Ar.
Модели Ar
250
Ðàññìîòðèì íåêîòîðûå ïðèìåðû, èëëþñòðèðó-
þùèå âûðàçèòåëüíûå âîçìîæíîñòè ÿçûêà òåî-
ðèè Ar.
Áóäåì ãîâîðèòü, ÷òî ôîðìóëà F ÿçûêà ß
Ar
ñ n ñâîáîäíûìè ïå-
ðåìåííûìè âûðàæàåò â ñòàíäàðòíîé èíòåðïðåòàöèè
N àðèôìå-
òè÷åñêèé n-ìåñòíûé ïðåäèêàò
P (ò. å. ïðåäèêàò íà ìíîæåñòâå N),
åñëè ýòà ôîðìóëà â
N çàäàåò ïðåäèêàò
F
, ñîâïàäàþùèé ñ ïðåäè-
êàòîì
P.
Çàïèøåì íà ÿçûêå Ar ôîðìóëû, âûðàæàþùèå íà ß
Ar
èçâåñòíûå
àðèôìåòè÷åñêèå ïðåäèêàòû:
1) ôîðìóëà ∃z (y = õ
⋅
z) âûðàæàåò â N ïðåäèêàò äåëèìîñòè: äëÿ
ëþáûõ íàòóðàëüíûõ n è m
D
(n, m) = È òîãäà è òîëüêî òîãäà, êîãäà
n | m;
2) ôîðìóëà Pr(x)
>ó (∃z (õ = ó
⋅
z) ⊃ ó =
1
∨ ó = õ) & ¬(õ =
1
)
âûðàæàåò â
N ïðåäèêàò «n – ïðîñòîå ÷èñëî» – äëÿ ëþáîãî íàòóðàëü-
íîãî n
P
r
(n) = È òîãäà è òîëüêî òîãäà, êîãäà n ÿâëÿåòñÿ ïðîñòûì;
3) ôîðìóëà ∃z (y = õ + z) âûðàæàåò â
N ïðåäèêàò ;
4) ôîðìóëà ∃z (y = õ + z & z
≠
0) âûðàæàåò â
N ïðåäèêàò < .
Ìîæíî äîêàçàòü, ÷òî ÿâëÿåòñÿ Ar-òåîðåìîé ôîðìóëà ß
Ar
, âûðà-
æàþùàÿ òåîðåìó î äåëåíèè ñ îñòàòêîì (î ñóùåñòâîâàíèè è åäèí-
ñòâåííîñòè ÷àñòíîãî è îñòàòêà ïðè äåëåíèè):
>õ >ó (ó
≠
0 ⊃ ∃
1
u ∃
1
v (õ = y
⋅
u + v & v < y)),
ãäå ∃
1
õ À(õ) ∃õ À(x) & >õ >ó (À(x) & À(ó) ⊃ õ = ó).
Íà ÿçûêå Ar ìîæíî âûðàçèòü ñëåäóþùèå áîëåå ñèëüíûå ôîð-
ìû ïðèíöèïà èíäóêöèè.
1. Ïðèíöèï âîçâðàòíîé èíäóêöèè: åñëè äëÿ ëþáîãî íàòóðàëü-
íîãî õ èç òîãî, ÷òî ñâîéñòâîì
P îáëàäàþò âñå íàòóðàëüíûå ÷èñëà,
ìåíüøèå õ, âûòåêàåò, ÷òî èì îáëàäàåò è ñàìî ÷èñëî õ, òî ñâîé-
ñòâîì
P îáëàäàþò âñå íàòóðàëüíûå ÷èñëà.
Çàïèøåì ýòî óòâåðæäåíèå â âèäå ôîðìóëû ß
Ar
:
>õ (>ó (ó < õ ⊃ À(ó)) ⊃ À(x)) ⊃ >õ À(x).
2. Ïðèíöèï íàèìåíüøåãî ÷èñëà: âñÿêîå íåïóñòîå ïîäìíîæå-
ñòâî íàòóðàëüíûõ ÷èñåë èìååò íàèìåíüøèé ýëåìåíò. Äðóãèìè ñëî-
âàìè: åñëè ñâîéñòâîì
P îáëàäàåò õîòÿ áû îäíî íàòóðàëüíîå ÷èñëî,
òî ñóùåñòâóåò íàèìåíüøåå ÷èñëî ñðåäè âñåõ íàòóðàëüíûõ ÷èñåë,
Выразительные
возможности
языка арифметики