Анисов А.М. Современная логика

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

231

äåðæàùèìè îäèíàêîâîå êîëè÷åñòâî áóêâ, ðàçíèöà ëèøü â íå

áîëåå, ÷åì îäíîé áóêâå, òî è ìåæäó ñëîâàìè ó è õ òàêàÿ æå

ðàçíèöà, ïîýòîìó èç õ ñõîäåí ñ ó âûâîäèòñÿ ó ñõîäåí ñ õ. Çíà÷èò,

ââåä¸ííîå îòíîøåíèå íà óíèâåðñóìå ñëîâ äåéñòâèòåëüíî ÿâëÿ-

åòñÿ îòíîøåíèåì ñõîäñòâà. Íî ýòî îòíîøåíèå íå òðàíçèòèâíî.

Òàê, ñëîâà «ñëîí» è «ñòîí» ñõîäíû: ñëîí ≈ ñòîí. Äàëåå, ñòîí ≈

ñòàí. Íî óæå íå âåðíî, ÷òî ñëîâà ñëîí è ñòàí ïîõîæè: ¬(ñëîí ≈

ñòàí). Ñòàëî áûòü, èç (õ ≈ ó) è (ó ≈ z) íå âûâîäèòñÿ, ÷òî (õ ≈ z),

ò.å. îòíîøåíèå ≈ íå òðàíçèòèâíî.

Îïðåäåëèì áèíàðíîå îòíîøåíèå «õ ðîâåñíèê ó» ñëåäóþùèì

îáðàçîì: (õ ðîâåñíèê ó) òîãäà, è òîëüêî òîãäà, êîãäà ðàçíèöà â

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

ðàçíèöû ìåæäó âîçðàñòîì õ è

õ íåò íèêàêîé, ïîýòîìó (õ ðî-

âåñíèê õ) è ðåôëåêñèâíîñòü

îáåñïå÷åíà. Âûïîëíÿåòñÿ òàê-

æå àêñèîìà ñèììåòðè÷íîñòè:

åñëè (õ ðîâåñíèê ó), òî ðàç-

íèöà â âîçðàñòå ìåæäó õ è ó

íå ïðåâûøàåò îäíîãî ãîäà.

Çíà÷èò, ðàçíèöà â âîçðàñòå

ìåæäó ó è õ òàêæå íå ïðåâû-

øàåòîäíîãî ãîäà, îòêóäà èìå-

åì (ó ðîâåñíèê õ). Ïóñòü, îä-

íàêî, õ ìëàäøå ó íà 7 ìåñÿ-

öåâ, à ó ìëàäøå z íà 7

ìåñÿöåâ. Ïîñêîëüêó ðàçíèöà

â âîçðàñòå ìåæäó õ è ó, à òàê

æå ìåæäó ó è z íå ïðåâûøàåò ãîäà, ïîëó÷àåì (õ ðîâåñíèê ó) è (ó

ðîâåñíèê z). Íî ðàçíèöà ìåæäó õ è z óæå ïðåâûøàåò ãîä, ïîýòî-

ìó ¬(õ ðîâåñíèê z), òàê ÷òî îòíîøåíèå ñõîäñòâà (õ ðîâåñíèê ó)

âíîâü íå òðàíçèòèâíî. Â îáðàçíîé ôîðìå ïðèìåð îòíîøåíèÿ

ñõîäñòâà ïðåäñòàâëåí íà ãðàâþðå Ì.Ýøåðà «Íåáî è âîäà».

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

íî íå òðàíçèòèâíî, íî ýòî îøèáî÷íûé âûâîä. Åñëè áû ìû õîòå-

ëè çàïðåòèòü òðàíçèòèâíîñòü, òî íàäî áûëî áû ÿâíî ïðèíÿòü

ñîîòâåòñòâóþùóþ àêñèîìó. Íàïðèìåð, ñëåäóþùóþ àêñèîìó.

∃õ∃ó∃z(((x ≈ y) & (y ≈ z)) & ¬ (x ≈ z))

Íî áûëî áû íå ðàçóìíî ýòî äåëàòü. Ïî÷åìó, íàïðèìåð, ñ÷è-

òàòü îòíîøåíèåì ñõîäñòâà íå òðàíçèòèâíîå ïîíÿòèå «áûòü ðî-

âåñíèêîì», íî íå ñ÷èòàòü îòíîøåíèåì ñõîäñòâà ïîíÿòèå «áûòü

îäíîãîäêîì» (â ñìûñëå «õ ðîäèëñÿ â òîì æå ãîäó, ÷òî è ó»),

óäîâëåòâîðÿþùåå àêñèîìå òðàíçèòèâíîñòè?

232

Áîëåå ïðàâîìåðíî ðàññìàòðèâàòü îòíîøåíèå ñõîäñòâà êàê

áîëåå îáùåå ïî ñðàâíåíèþ ñ îòíîøåíèåì ýêâèâàëåíòíîñòè. Âñÿ-

êîå îòíîøåíèå ýêâèâàëåíòíîñòè åñòü, îäíîâðåìåííî, è îòíî-

øåíèå ñõîäñòâà (ïîñêîëüêó ëþáàÿ ýêâèâàëåíòíîñòü óäîâëåòâî-

ðÿåò àêñèîìàì ñõîäñòâà). Îáðàòíîå óòâåðæäåíèå íå âåðíî. Íå

âñÿêîå ñõîäñòâî ÿâëÿåòñÿ ýêâèâàëåíòíîñòüþ (âåäü ñóùåñòâóþò

íå òðàíçèòèâíûå îòíîøåíèÿ ñõîäñòâà).

Ïðèìåíèòåëüíî ê õàðàêòåðèñòèêàì ñîîòâåòñòâóþùèõ òåîðèé,

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

ëåíòíîñòè, à íå òåîðèÿ ñõîäñòâà. Âåäü êàæäîå óòâåðæäåíèå î

ñõîäñòâå À, âûâåäåííîå èç àêñèîì ñõîäñòâà À1 è À2, ïîñëå çàìå-

íû â âûâîäå çíàêà «≈» íà çíàê «~» îäíîâðåìåííî îêàæåòñÿ âû-

âåäåííûì â òåîðèè ýêâèâàëåíòíîñòè. Íî íå âñ¸, ÷òî ìîæíî âû-

âåñòè â òåîðèè ýêâèâàëåíòíîñòè ìîæíî áóäåò âûâåñòè (ïîñëå

îáðàòíîé çàìåíû «~» íà «≈») â òåîðèè ñõîäñòâà. Íàïðèìåð, àê-

ñèîìà òðàíçèòèâíîñòè À3 çà îäèí øàã âûâîäèìà â òåîðèè ýêâè-

âàëåíòíîñòè, íî íå âûâîäèìà çà ëþáîå êîëè÷åñòâî øàãîâ â òåî-

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

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

òðàíçèòèâíûõ îòíîøåíèé ñõîäñòâà. Åñëè áû òðàíçèòèâíîñòü

âûâîäèëàñü â òåîðèè ñõîäñòâà, òî âñÿêîå ñõîäñòâî áûëî áû òðàí-

çèòèâíûì, è ìû íå ñìîãëè áû ïîñòðîèòü ïðèìåð íå òðàíçèòèâ-

íîãî ñõîäñòâà.

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

èç àêñèîì À1 è À2 òåîðèè ñõîäñòâà. Òîãäà â ýòîé òåîðèè áó-

äåò òåîðåìîé ôîðìóëà òðàíçèòèâíîñòè: ⎟⎯ ∀õ∀y∀z(((x ≈ y) &

(y ≈ z))→ (x ≈ z)). Çíà÷èò, â ëþáîì óíèâåðñóìå, íà êîòîðîì

çàäàíî îòíîøåíèå ñõîäñòâà ≈, îíî äîëæíî áûòü òðàíçèòèâ-

íûì. Íî îòíîøåíèå «áûòü ðîâåñíèêîì», çàäàííîå íà óíè-

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

óäîâëåòâîðÿåò àêñèîìàì ñõîäñòâà). Îäíàêî äàííîå îòíîøå-

íèå íå òðàíçèòèâíî. Ñëåäîâàòåëüíî, òðàíçèòèâíîñòü íå ÿâ-

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

íîñòü àêñèîì À1 è À2 íå èñêëþ÷àåò ëîæíîñòè ôîðìóëû òðàí-

çèòèâíîñòè. Èíûìè ñëîâàìè, èç À1 è À2 òðàíçèòèâíîñòü íå

ñëåäóåò. À ðàç íå ñëåäóåò, òî è íå âûâîäèòñÿ. Â ïðîòèâíîì

ñëó÷àå èìåëè áû ñèòóàöèþ âèäà Ã ⎥≠ À, Ã ⎟⎯ À, ÷òî ïðîòèâî-

ðå÷èò ìåòàòåîðåìå Ã ⎟⎯ À ⇔ Ã ⎥= À.

233

§2. Àêñèîìû ðàâåíñòâà

Âñåì èçâåñòíî áèíàðíîå îòíîøåíèå ðàâåíñòâà. Ìû òîæå óæå

íå ðàç èñïîëüçîâàëè åãî â äàííîé êíèãå. Ìîæíî ëè íåÿâíî îï-

ðåäåëèòü ïîíÿòèå ðàâåíñòâà ïîñðåäñòâîì ïîäõîäÿùåé àêñèîìà-

òè÷åñêîé òåîðèè? Íà óì ïðèõîäèò ðàññìîòðåííàÿ â ïðåäûäóùåì

ïàðàãðàôå òåîðèÿ ýêâèâàëåíòíîñòè. Ñîâåðøåííî î÷åâèäíî, ÷òî

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

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

èñòèííû ñëåäóþùèå ôîðìóëû.

∀õ(õ = õ)

∀õ∀ó((õ = ó) → (ó = õ))

∀õ∀y∀z(((x = y) & (y = z))→ (x = z))

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

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

âåðøåííî ïðàâèëüíîé, òåì íå ìåíåå, ÿâíî íåäîñòàòî÷íà. Äåé-

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

ïðèçíàêó, íå îáÿçàíû áûòü ðàâíûìè. Ê ïðèìåðó, êîìïîçèòîðû

Ð.Âàãíåð è Äæ.Âåðäè îáà ðîäèëèñü â 1813 ã., òàê ÷òî âûñêàçûâà-

íèå «Âàãíåð îäíîãîäîê Âåðäè» èñòèííî. Ïîñêîëüêó îòíîøåíèå

«õ îäíîãîäîê ó» ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè, âîñ-

ïîëüçóåìñÿ ââåä¸ííûì îáîçíà÷åíèåì ýêâèâàëåíòíîñòè «~»: (Âàã-

íåð ~ Âåðäè). Íî îòñþäà íèêàê íå ñëåäóåò, ÷òî (Âàãíåð = Âåð-

äè), ò.å. ÷òî ðå÷ü èä¸ò îá îäíîì è òîì æå èíäèâèäå. Íà ñàìîì

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

ñÿ, ÷òî è âûñêàçûâàíèå (à ~ b), è âûñêàçûâàíèå (à = b) âìåñòå

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

ò.å. (Àðèñòîòåëü ~ Ñòàãèðèò), íî, ïîñêîëüêó Àðèñòîòåëü è Ñòàãè-

ðèò – ýòî äâà èìåíè îäíîãî è òîãî æå èíäèâèäà, ìîæåì îäíî-

âðåìåííî óòâåðæäàòü (Àðèñòîòåëü = Ñòàãèðèò). Âàæíî òî, ÷òî

òàê áûâàåò íå âñåãäà, ïîýòîìó èñòèííîñòü (à ~ b) íå ãàðàíòèðóåò

èñòèííîñòè (à = b), è ïîòîìó èç (à ~ b) íå ñëåäóåò (à = b).

Îáðàòíîå èìååò ìåñòî: ((a = b) → (a ~ b)). Ñëîâåñíî, ëþáûå

ðàâíûå èíäèâèäû áóäóò ýêâèâàëåíòíûìè. Íî â êàêîì ñìûñëå

ýêâèâàëåíòíûìè? Ìû âèäåëè, ÷òî çà îáîçíà÷åíèåì ýêâèâàëåíò-

íîñòè «~» ìîãóò ñêðûâàòüñÿ ðàçëè÷íûå êîíêðåòíûå ðåàëèçàöèè

(ñàìî ðàâåíñòâî «õ = ó», îòíîøåíèÿ «õ îäíîãîäîê ó», «õ èìååò

îäèíàêîâóþ óñïåâàåìîñòü ñ ó» è ò.ä.). Âîò ýòî, îêàçûâàåòñÿ, íå-

âàæíî! ×òî áû êîíêðåòíîå íè ïîäðàçóìåâàëîñü ïîä îòíîøåíèåì

~, â ñèëó ðàâåíñòâà (a = b) è ðåôëåêñèâíîñòè ~, îäèí è òîò æå

èíäèâèä, îáîçíà÷åííûé ðàçíûìè èìåíàìè a è b, â ëþáîì ñëó÷àå

âñòóïèò â îòíîøåíèå ýêâèâàëåíòíîñòè ñ ñàìèì ñîáîé: (a ~ b).

234

Ïîëó÷àåòñÿ, ÷òî îòíîøåíèå ðàâåíñòâà ñèëüíåå îòíîøåíèÿ

ýêâèâàëåíòíîñòè â ëîãè÷åñêîì ñìûñëå: èç (a = b) ñëåäóåò (a ~

b), íî èç (a ~ b) íå ñëåäóåò (a = b). Çíà÷èò, äëÿ âûðàæåíèÿ

ðàâåíñòâà íåîáõîäèìî ïîèñêàòü òàêèå àêñèîìû, êîòîðûå áû óñè-

ëèëè òåîðèþ.

Â ñâî¸ âðåìÿ íåìåöêèé ôèëîñîô Ãîòôðèä Ëåéáíèö ïðåäëî-

æèë ðåøåíèå ïðîáëåìû, êîòîðîå îí íàçâàë ïðèíöèïîì òîæäå-

ñòâà íåðàçëè÷èìûõ. Â âîëüíîì èçëîæåíèè ýòîò ïðèíöèï ìîæíî

ñôîðìóëèðîâàòü òàê: åñëè âñ¸, ÷òî ìîæíî ñêàçàòü îá îäíîì èíäè-

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

òîì æå èíäèâèäå, à íå î äâóõ èíäèâèäàõ. Íàäî òîëüêî óòî÷íèòü,

÷òî îçíà÷àþò ñëîâà «÷òî-òî ñêàçàòü îá èíäèâèäå». Â ëîãèêå ÷òî-òî

ñêàçàòü îá èíäèâèäå b – çíà÷èò ïðèïèñàòü b ñâîéñòâî èëè óêàçàòü

íà îòíîøåíèå, â êîòîðîå b âñòóïàåò ñ äðóãèìè èíäèâèäàìè.

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

òðåáóåò ñëåäóþùèõ äåéñòâèé. Èññëåäóÿ èíäèâèäû à è b, íåîáõî-

äèìî ïðîâåðèòü âñå ïðåäèêàòû âèäà À(õ), ãäå ïåðåìåííàÿ õ ñî-

äåðæèòñÿ ñâîáîäíî. Ïîä÷åðêí¸ì, ÷òî â À(õ) äðóãèå ïåðåìåííûå

ìîãóò âõîäèò êàê ñâîáîäíî, òàê è íå ñâîáîäíî. Íàïðèìåð, À(õ)

ìîæåò ñîâïàäàòü ñ ôîðìóëîé Â(õ, õ

, õ

, ..., õ

), â êîòîðóþ, íàðÿ-

äó ñ õ, âõîäÿò ñâîáîäíî ïåðåìåííûå õ

, õ

, ..., õ

(òàêàÿ ôîðìóëà

âûðàæàåò íåêîòîðîå n+1-ìåñòíîå îòíîøåíèå). Ïóñòü ôîðìóëû

À(à) è À(b) ïîëó÷àþòñÿ èç À(õ) çàìåíîé âñåõ âõîæäåíèé ïåðå-

ìåííîé õ íà èìåíà à è b ñîîòâåòñòâåííî.

Åñëè íàéä¸òñÿ ïðåäèêàò À(õ) òàêîé, ÷òî À(à), íî ¬À(b),

ñðàçó çàêëþ÷àåì: ñëåäîâàòåëüíî, à ≠ b. (Ïîïóòíî îòìåòèì, ÷òî

ñëó÷àé À(b) è ¬À(à) ðàçáèðàòü íå íàäî, ò.ê. èç À(à) è ¬À(b)

ñëåäóåò, ÷òî ñóùåñòâóåò ïðåäèêàò Â(õ), äëÿ êîòîðîãî Â(b), íî

¬Â(à); äîñòàòî÷íî â êà÷åñòâå Â(õ) âçÿòü ¬À(õ), ÷òî îáåñïå÷èò

¬À(b) è ¬¬À(à).)

Åñëè æå äëÿ ëþáîãî ïðåäèêàòà À(õ) èìååò ìåñòî À(à) ↔ À(b),

òî çàêëþ÷àåì: ñëåäîâàòåëüíî, à = b.

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

íàòàëêèâàåòñÿ íà îäíî ïðåïÿòñòâèå: âûøå ïðèâåä¸ííîå ðàññóæ-

äåíèå èñïîëüçîâàëî êâàíòèôèêàöèþ íå ïî èíäèâèäàì, à ïî ïðå-

äèêàòàì, ÷òî âûâîäèëî åãî çà ãðàíèöû ëîãèêè ïåðâîãî ïîðÿäêà.

Âûõîä áûë íàéäåí â òîì, ÷òîáû, îòêàçàâøèñü îò ïîïûòêè äàòü

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

ïîíÿòèå ðàâåíñòâà â êà÷åñòâå èñõîäíîãî, à çàòåì àêñèîìàòè÷åñêè

îïèñàòü åãî â íåÿâíîì âèäå, ïî âîçìîæíîñòè óäåðæàâ ñóùåñòâåí-

íûå õàðàêòåðèñòèêè ðàâåíñòâà, âûÿâëåííûå åù¸ Ëåéáíèöåì.

235

Ïóñòü À(õ

, õ

, ..., õ

) – ëþáàÿ ôîðìóëà, ñîäåðæàùàÿ ïåðå-

ìåííûå õ

, õ

, ..., õ

ñâîáîäíî, è íå ñîäåðæàùàÿ ïåðåìåííûõ ó

, ..., ó

. ×åðåç À(ó

, ó

, ..., ó

) îáîçíà÷èì ôîðìóëó, ïîëó÷åííóþ

èç À(õ

, õ

, ..., õ

) çàìåíîé êàæäîãî âõîæäåíèÿ ïåðåìåííîé õ

íà

ïåðåìåííóþ ó

(1 ≤ i ≤ n).

Àêñèîìàìè ðàâåíñòâà ÿâëÿþòñÿ ñëåäóþùèå ôîðìóëû.

À1 ∀õ(õ = õ)

À2 ∀õ

∀õ

...∀õ

∀ó

...∀ó

((õ

= ó

& x

= y

& … & x

= y

) →

(À(õ

, õ

, ..., õ

) → À(ó

, ó

, ..., ó

))

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

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

Âòîðàÿ àêñèîìà èäåéíî âîñõîäèò ê ïðèíöèïó òîæäåñòâà íåðàç-

ëè÷èìûõ. Îíà óòâåðæäàåò, ÷òî åñëè èíäèâèäû õ

, õ

, ..., õ

âñòó-

ïàþò â îòíîøåíèå À, òî ðàâíûå èì èíäèâèäû ó

, ó

, ..., ó

òàêæå

îêàæóòñÿ â îòíîøåíèè À. Êàêèå êîíêðåòíî îòíîøåíèÿ âçÿòü â

êà÷åñòâå À – çàâèñèò òîëüêî îò âûðàçèòåëüíûõ âîçìîæíîñòåé

ÿçûêà. Âåäü ñìûñë àêñèîìû À2 â òîì, ÷òî À – ëþáîå îòíîøå-

íèå, âûðàçèìîå â ÿçûêå, õîòÿ â ñàìîé àêñèîìå íåçàêîííûé îáî-

ðîò «ëþáîå îòíîøåíèå» íå èñïîëüçóåòñÿ. Â äåéñòâèòåëüíîñòè

À2 ÿâëÿåòñÿ ñõåìîé àêñèîì, ïîòåíöèàëüíî ñîäåðæàùåé áåñêî-

íå÷íîå êîëè÷åñòâî êîíêðåòíûõ âàðèàíòîâ ýòîé àêñèîìû.

×èòàòåëü, êîíå÷íî, óæå îáðàòèë âíèìàíèå, ÷òî â ñïèñêå àê-

ñèîì ðàâåíñòâà îòñóòñòâóþò àêñèîìû ñèììåòðè÷íîñòè è òðàí-

çèòèâíîñòè. Áåñïîêîèòüñÿ íå íàäî, ïîòîìó ÷òî òåïåðü ýòè àêñè-

îìû âûâîäÿòñÿ â êà÷åñòâå ñëåäñòâèé àêñèîì ðàâåíñòâà. Ïðîäå-

ìîíñòðèðóåì ýòî.

⎟⎯ ∀õ∀ó(õ = ó → ó = õ)

1. õ = ó – äîï.

2.∀õ(õ = õ) – À1

3. õ = õ – 2, ∀ó

4.∀õ∀ó((õ = ó & õ = õ) → (õ = õ → ó = õ)) – À2

5.∀ó((õ = ó & õ = õ) → (õ = õ → ó = õ)) – 4, ∀ó

6. ((õ = ó & õ = õ) → (õ = õ → ó = õ)) – 5, ∀ó

7. (õ = ó & õ = õ) – 1, 3, &â

8. (õ = õ → ó = õ) – 7, 6, →ó

9. ó = õ – 3, 8, →ó

10. õ = ó ⎟⎯ ó = õ – 1-9, ⎟⎯â

11. ⎟⎯ (õ = ó → ó = õ) – 10, →â

12. ⎟⎯ ∀ó(õ = ó → ó = õ) – 11, ∀â

236

13. ⎟⎯ ∀õ∀ó(õ = ó → ó = õ) – 12, ∀â

Â äàííîì äîêàçàòåëüñòâå êëþ÷åâîé øàã – ýòî øàã íîìåð 4.

Â âàðèàíòå àêñèîìû À2 ∀õ∀ó((õ = ó & õ = õ) → (õ = õ → ó = õ))

âìåñòî õ

ñòîèò õ, âìåñòî ó

– ó, âìåñòî õ

– ñíîâà õ, âìåñòî ó

–

îïÿòü õ. Ðîëü ôîðìóëû À(õ

, õ

) èãðàåò, ñòàëî áûòü, ôîðìóëà (õ =

õ), à ðîëü ôîðìóëû À(ó

, ó

) – ôîðìóëà (ó = õ). Ìû óæå ïîä÷¸ð-

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

â òîì ÷èñëå À ìîæåò áûòü è ôîðìóëîé ðàâåíñòâà. Äàëüíåéøåå

ðàññóæäåíèå – ÷èñòàÿ ëîãèêà.

⎟⎯ ∀õ∀y∀z((x = y & y = z)→ x = z)

1. (x = y & y = z) – äîï.

2. x = y – 1, &ó1

3. y = z – 1, &ó2

4. ⎟⎯ (õ = ó → ó = õ) – äîê.

5. (õ = ó → ó = õ) – 4, ⎟⎯ó

6. ó = õ – 2, 5, →ó

7. (ó = õ & y = z) – 6, 3, &â

8.∀ó∀õ∀z((ó = õ & y = z) → (ó = ó → õ = z)) – À2

9.∀õ∀z((ó = õ & y = z) → (ó = ó → õ = z)) – 8, ∀ó

10.∀z((ó = õ & y = z) → (ó = ó → õ = z)) – 9, ∀ó

11. ((ó = õ & y = z) → (ó = ó → õ = z)) – 10, ∀ó

12. (ó = ó → õ = z) – 7, 11, →ó

13.∀õ(õ = õ) – À1

14. ó =ó – 13, ∀ó

15. õ = z – 14, 12, →ó

16. (x = y & y = z) ⎟⎯ õ = z – 1-15, ⎟⎯â

17. ⎟⎯ ((x = y & y = z)→ x = z) – 16, →â

18. ⎟⎯ ∀z((x = y & y = z)→ x = z) – 17, ∀â

19. ⎟⎯ ∀y∀

z((x = y & y = z)→ x = z) – 18, ∀â

20. ⎟⎯ ∀õ∀y∀z((x = y & y = z)→ x = z) – 19, ∀â

Íà ýòîò ðàç êëþ÷åâûì øàãîì äîêàçàòåëüñòâà áûë øàã íîìåð

8. Â âàðèàíòå àêñèîìû À2 ∀ó∀õ∀z((ó = õ & y = z) → (ó = ó → õ

= z)) âìåñòî õ

ñòîèò ó, âìåñòî ó

– õ, âìåñòî õ

– ñíîâà ó, âìåñòî

– z. Ðîëü ôîðìóëû À(õ

, õ

) èãðàåò ôîðìóëà (ó = ó), à ðîëü

ôîðìóëû À(ó

, ó

) – ôîðìóëà (õ = z).

Ðàññìàòðèâàÿ ïîíÿòèå ýêâèâàëåíòíîñòè, ìû îòìåòèëè, ÷òî

êàæäîå çàäàííîå íà óíèâåðñóìå ðàññóæäåíèé îòíîøåíèå ýêâè-

âàëåíòíîñòè äåëèò óíèâåðñóì, ïîðîæäàåò åãî ðàçáèåíèå íà íå-

ïóñòûå íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà. Ðàç, êàê ìû òîëüêî

÷òî äîêàçàëè, ðàâåíñòâî â ñàìîì äåëå ÿâëÿåòñÿ îòíîøåíèåì ýêâè-

âàëåíòíîñòè, îíî òàêæå äîëæíî ïîðîæäàòü ðàçáèåíèå ñîîòâåò-

ñòâóþùåãî óíèâåðñóìà. ×òî æå ýòî çà ðàçáèåíèå? Â ïðåäûäóùèõ

ïðèìåðàõ ñ ýêâèâàëåíòíîñòÿìè ñëó÷àëîñü òàê, ÷òî (à ~ b), íî (à

≠ b). Ñåìàíòè÷åñêè ýòî îçíà÷àåò, ÷òî ðàçíûå èíäèâèäû à è b

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

ôè÷åñêîé ýêâèâàëåíòíîñòè, êàê ðàâåíñòâî, ýòîãî áûòü íå ìî-

æåò! Ïîëó÷èëîñü áû, ÷òî à = b (ïîòîìó ÷òî à è b ïîïàëè â îäèí

è òîò æå ÷ëåí äåëåíèÿ) è îäíîâðåìåííî à ≠ b, ÷òî ïðîòèâîðå÷è-

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

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

ãîâîðÿ óæå î áîëüøåì êîëè÷åñòâå) èíäèâèäà. Íî è ïóñòûìè ÷ëåíû

äåëåíèÿ áûòü íå ìîãóò. Ñëåäîâàòåëüíî, îñòà¸òñÿ îäíà åäèíñòâåí-

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

êîòîðîãî ñîäåðæèò ðîâíî îäèí èíäèâèä.

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

ñàìîìó ñåáå è íå ðàâåí íèêàêîìó äðóãîìó èíäèâèäó, òîãäà êàê

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

íî. Òàêèì îáðàçîì, ðàâåíñòâî – ýòî òàêîå îòíîøåíèå ýêâèâà-

ëåíòíîñòè íà óíèâåðñóìå, êîòîðîå äà¸ò ìàêñèìàëüíî äðîáíîå

åãî ðàçáèåíèå. Ïðîöåññ äàëüíåéøåãî ðàçáèåíèÿ çäåñü íåâîçìî-

æåí. Âñå îñòàëüíûå, îòëè÷íûå îò ðàâåíñòâà, îòíîøåíèÿ ýêâèâà-

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

êîòîðûõ äåëèìà äàëåå.

Àêñèîìàòè÷åñêàÿ òåîðèÿ ðàâåíñòâà èãðàåò îñîáóþ ðîëü ïðè

ïîñòðîåíèè äðóãèõ òåîðèé. ×àùå âñåãî íîâûå àêñèîìàòè÷åñêèå

òåîðèè ñòðîÿòñÿ êàê ðàñøèðåíèå òåîðèè ðàâåíñòâà. Íåïëîõî, â

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

èìåòü âîçìîæíîñòü ðåøàòü, ðàâíû äðóã äðóãó èíäèâèäû à è b,

èëè íå ðàâíû. Íà ýòîì îñíîâàíèè òåîðèþ ðàâåíñòâà íåðåäêî

îòíîñÿò ê ÷èñòîé ëîãèêå, à íå ê ïðèêëàäíîé å¸ ÷àñòè. Òîãäà

ìèíèìàëüíîé òåîðèåé äîëæíî ñ÷èòàòüñÿ íå ÷èñòîå èñ÷èñëåíèå

ïðåäèêàòîâ, – â íàøåì êîíêðåòíîì ñëó÷àå K

, – à èñ÷èñëåíèå

ïðåäèêàòîâ ñ ðàâåíñòâîì – K

+ À1 + À2. Îäíàêî, êàê

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

òåîðèè ìîãóò îáõîäèòüñÿ áåç îòíîøåíèÿ ðàâåíñòâà. À âîò ñî-

çäàòü òåîðèþ áåç òåîðèè ëîãè÷åñêîãî âûâîäà (K

èëè êàêîé-òî

åù¸) íåâîçìîæíî.

238

§3. Òåîðèè ïîðÿäêà

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

êèå òåîðèè ÷àùå ñòðîÿòñÿ íà áàçå èñ÷èñëåíèÿ ïðåäèêàòîâ ñ ðà-

âåíñòâîì K

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

. Òåîðèè ïîðÿäêà òîæå ñòðîÿòñÿ, èñõîäÿ èç K

. Åñòü äâå ðàç-

íîâèäíîñòè ïîðÿäêà – ñòðîãèé è íåñòðîãèé. Êîãäà ìû çàïèñû-

âàåì õ < ó, òî ïîäðàçóìåâàåì, ÷òî õ ñòðîãî ìåíüøå ó, íî êîãäà

èñïîëüçóåòñÿ çàïèñü õ ≤ ó, òî, íàðÿäó ñ õ < ó, íå èñêëþ÷àåòñÿ

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

ê äèçúþíêöèè: õ ≤ ó ↔

õ < ó ∨ õ = ó. Ìîæíî, íàîáîðîò, îïðå-

äåëèòü ñòðîãèé ïîðÿäîê ÷åðåç íåñòðîãèé è ðàâåíñòâî: õ < ó ↔

õ ≤ ó & ¬(õ = ó). (Âìåñòî ¬(õ = ó) óäîáíåå èñïîëüçîâàòü õ ≠ ó).

Îäíàêî ýòî íå ïðèáëèçèëî íàñ ê óÿñíåíèþ òîãî, ÷òî ïîíè-

ìàåòñÿ ïîä îòíîøåíèåì ïîðÿäêà. Çäåñü òðåáóåòñÿ ïðåäúÿâèòü

ñîîòâåòñòâóþùèå àêñèîìû, êîòîðûå ìû äàäèì îòäåëüíî äëÿ ñòðî-

ãîé è íåñòðîãîé ðàçíîâèäíîñòè ðàññìàòðèâàåìîãî ïîíÿòèÿ. (Âû

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

íå îçíà÷àåò «íåòî÷íûé» èëè «ïðèáëèçèòåëüíûé», ïîñêîëüêó îáà

ïîðÿäêîâûõ îòíîøåíèÿ áóäóò îïðåäåëåíû ïðåäåëüíî ñòðîãî.)

Àêñèîìû òåîðèè íåñòðîãîãî ÷àñòè÷íîãî ïîðÿäêà Ò

≤

À1. ∀õ(õ ≤ õ)

À2. ∀õ∀ó((õ ≤ ó & ó ≤ õ) → õ = ó)

À3. ∀õ∀y∀z((x ≤ y & y ≤ z)→ x ≤ z)

Ïåðâàÿ è òðåòüÿ àêñèîìû – ýòî õîðîøî çíàêîìûå àêñèîìû

ðåôëåêñèâíîñòè è òðàíçèòèâíîñòè. Âòîðàÿ àêñèîìà íàçûâàåòñÿ

àêñèîìîé àíòèñèììåòðè÷íîñòè.

Àêñèîìû òåîðèè ñòðîãîãî ÷àñòè÷íîãî ïîðÿäêà Ò

Â1. ∀õ¬(õ < õ)

B2. ∀õ∀y∀z((x < y & y < z)→ x < z)

Àêñèîìà Â2 – âñ¸ òà æå òðàíçèòèâíîñòü, à àêñèîìà Â1 íàçû-

âàåòñÿ àêñèîìîé àíòèðåôëåêñèâíîñòè.

Ìåæäó òåîðèÿìè Ò

≤

è Ò

ñóùåñòâåííîé ðàçíèöû íåò. ×òî-

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

ÿì ñîîòâåòñòâóþùèå ÿâíûå îïðåäåëåíèÿ îäíîãî îòíîøåíèÿ

ïîðÿäêà ÷åðåç äðóãîå â êà÷åñòâå íîâûõ àêñèîì. Òîãäà â ðàñ-

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

âûâîäèìî â òåîðèè ñòðîãîãî ïîðÿäêà, è, íàîáîðîò, â ðàñøè-

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

íåñòðîãîãî ïîðÿäêà.

239

Óòî÷íèì ñêàçàííîå. Äîáàâèì ê Ò

≤

íîâóþ àêñèîìó

À4. ∀õ∀ó(õ < ó ↔ (õ ≤ ó & õ ≠ ó)),

à ê òåîðèè Ò

– íîâóþ àêñèîìó

Â3. ∀õ∀ó(õ ≤ ó ↔ (õ < ó ∨ õ = ó)).

Ïðè ýòîì ïðèíèìàåì îïðåäåëåíèå: ôîðìóëà (À ↔ Â) åñòü

ñîêðàùåíèå ôîðìóëû ((À → Â) & (Â → À)). Ïîñêîëüêó â K

èìåþòñÿ ïðàâèëà &ó1 è &ó2, â ñèëó êîòîðûõ ((À → Â) & (Â →

À)) ⎟⎯ (À → Â) è ((À → Â) & (Â → À)) ⎟⎯ (Â → À), ñ ýêâèâàëåí-

öèåé (À ↔ Â) â âûâîäàõ ìîæíî îáðàùàòüñÿ èëè êàê ñ èìïëèêà-

öèåé (À → Â), èëè êàê ñ èìïëèêàöèåé (Â → À) (â çàâèñèìîñòè

îò ñèòóàöèè).

Ìû óòâåðæäàåì, ÷òî èç òåîðèè Ò

≤

+ À4 âûâîäèìà òåîðèÿ Ò

à èç òåîðèè Ò

+ Â3 âûâîäèìà òåîðèÿ Ò

≤

. ×òîáû äîêàçàòü, ÷òî èç

àêñèîìàòè÷åñêîé òåîðèè Ò

âûâîäèòñÿ àêñèîìàòè÷åñêàÿ òåîðèÿ

, íåîáõîäèìî è äîñòàòî÷íî âûâåñòè â Ò

âñå àêñèîìû Ò

. Çíà-

÷èò, òðåáóåòñÿ â Ò

≤

+ À4 äîêàçàòü Â1 è Â2, à â Ò

+ Â3 äîêàçàòü

À1, À2 è À3. Âûâåäåì, íàïðèìåð, â òåîðèè Ò

≤

+ À4 ôîðìóëó Â1.

Â Ò

≤

+ À4 ⎟⎯ ∀õ¬(õ < õ).

1. õ < õ – äîï.

2.∀õ∀ó(õ < ó ↔ (õ ≤ ó & õ ≠ ó)) – À4

3.∀ó(õ < ó ↔ (õ ≤ ó & õ ≠ ó)) – 2, ∀ó

4. (õ < õ ↔ (õ ≤ õ & õ ≠ õ)) – 3, ∀ó

5. (õ ≤ õ & õ ≠ õ) – 1, 4, →ó

6. õ ≠ õ – 5, &ó2

7. õ < õ ⎟⎯ õ ≠ õ – 1-6, ⎟⎯â

8.∀õ(õ = õ) – àêñ. ðàâåíñòâà

9. õ = õ – 8, ∀ó

10. õ < õ ⎟⎯ õ = õ – 1, 8, 9, ⎟⎯â

11. ⎟⎯ ¬(õ < õ) – 10,→â

12. ⎟⎯ ∀õ¬(õ < õ) – 11, ∀â

Îñòàâøèåñÿ äîêàçàòåëüñòâà â Ò

≤

+ À4 è â Ò

+ Â3 ïîïûòàé-

òåñü ïîñòðîèòü ñàìîñòîÿòåëüíî.

Ïîëó÷åííûé âûøå ðåçóëüòàò ïîçâîëÿåò áåç óùåðáà äëÿ ñóòè

äåëà ñîñðåäîòî÷èòüñÿ ëèøü íà îäíîì ïîíÿòèè ïîðÿäêà. Ìû ïðåä-

ïî÷èòàåì ïîíÿòèå ñòðîãîãî ïîðÿäêà.

Ïðèâåä¸ì íåñêîëüêî êîíêðåòíûõ ðåàëèçàöèé ñòðîãîãî ïî-

ðÿäêîâîãî îòíîøåíèÿ <. Åñëè â àêñèîìàõ Â1 è Â2 çàìåíèòü ñèì-

âîë «<» íà ñëîâî «ìëàäøå», òî óíèâåðñóì ëþäåé áóäåò óïîðÿäî-

÷åí îòíîøåíèåì «õ ìëàäøå ó». Äåéñòâèòåëüíî, íèêòî íå ìîæåò

áûòü ìëàäøå ñàìîãî ñåáÿ, òàê ÷òî Â1 âûïîëíåíà. È âñÿêèé ðàç,

240

êîãäà õ ìëàäøå ó, à ó ìëàäøå z, õ îêàæåòñÿ ìëàäøå z, ÷òî îáåñ-

ïå÷èâàåò òðàíçèòèâíîñòü, ò.å. Â2. Áèíàðíûå îòíîøåíèÿ «õ ëåã÷å

ó», «õ êîðî÷å ó», «õ ãëóïåå ó», «õ ñëàáåå ó» òàêæå ÿâëÿþòñÿ îòíî-

øåíèåì ïîðÿäêà.

Âîçìîæíî, äëÿ êîãî-òî ïîêàæåòñÿ íåîæèäàííûì, ÷òî àêñè-

îìàì ïîðÿäêà áóäóò óäîâëåòâîðÿòü è îáðàòíûå ê ïðèâåä¸ííûì

îòíîøåíèÿ «ñòàðøå», «òÿæåëåå», «äëèííåå», «óìíåå», «ñèëüíåå».

Êîíå÷íî, åñëè ôîðìóëó (à < b) ïðîèíòåðïðåòèðîâàòü êàê «a ãëó-

ïåå b», òî óæå íåëüçÿ óòâåðæäàòü, ÷òî (b < a), ò.å. ÷òî «b ãëóïåå

à». Äëÿ îáðàòíûõ îòíîøåíèé íåîáõîäèìî ââåñòè äðóãîé ñèìâîë.

Åñëè îòíîøåíèå ïîðÿäêà îáîçíà÷åíî ñèìâîëîì «<», òî îáû÷íî

îáðàòíîå îòíîøåíèå îáîçíà÷àþò ñèìâîëîì «>».

Íåòðóäíî äîêàçàòü, èñïîëüçóÿ ñåìàíòè÷åñêèå ñîîáðàæåíèÿ,

÷òî åñëè îòíîøåíèå (õ < ó) åñòü îòíîøåíèå ïîðÿäêà, òî è îáðàò-

íîå îòíîøåíèå (ó > õ) òàêæå áóäåò îòíîøåíèåì ïîðÿäêà. Â ñà-

ìîì äåëå, îáðàòíîå îòíîøåíèå > ïîëó÷àåòñÿ èç îòíîøåíèÿ <

çàìåíîé êàæäîé óïîðÿäî÷åííîé ïàðû <a, b> ∈ < íà óïîðÿäî-

÷åííóþ ïàðó <b, a> ∈ >. Íî â ñèëó ∀õ¬(õ < x), â < íåò ïàð âèäà

<a, à>, òàê ÷òî òàêèì ïàðàì ïðîñòî íåîòêóäà âçÿòüñÿ è â >. Îò-

ñþäà ∀õ¬(õ > x) èñòèííî. Ïóñòü òåïåðü âûïîëíåíî <a, b> ∈ <,

<b, c> ∈ <. Ïî òðàíçèòèâíîñòè ïîëó÷àåì, ÷òî ïàðà <a, ñ> ∈ <.

Çíà÷èò, îáðàòíûå ïàðû <b, a>, <c, b> è <ñ, a> ∈ >, à ýòî è äà¸ò

òðàíçèòèâíîñòü <c, b>, <b, a>, <ñ, a>. Ïîñêîëüêó äàííîå ðàñ-

ñóæäåíèå âåðíî äëÿ ëþáûõ èíäèâèäîâ, âûñêàçûâàíèå ∀õ∀y∀z((x

> y & y > z)→ x > z) òàêæå èñòèííî.

Òåîðèÿ ëèíåéíîãî ïîðÿäêà ïîëó÷àåòñÿ èç òåîðèè ÷àñòè÷íîãî

ïîðÿäêà äîáàâëåíèåì ñëåäóþùåé àêñèîìû ñâÿçíîñòè Â3.

Â3. ∀õ∀ó(õ < ó ∨ ó < õ ∨ õ = ó)

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

êàæäîé ïàðû èíäèâèäîâ õ è ó èç óíèâåðñóìà èìååòñÿ òðè âîç-

ìîæíîñòè: ëèáî õ < ó, ëèáî ó < õ, ëèáî õ = ó. Â ýòîì ñëó÷àå

èíäèâèäû óíèâåðñóìà äåéñòâèòåëüíî âûñòðîÿòñÿ â ëèíèþ.

Ïðåäñòàâèì, íàïðèìåð, ÷òî â ðîòå äëÿ ëþáîé ïàðû ñîëäàò õ

è ó âûïîëíåíî ñëåäóþùåå óñëîâèå: ëèáî õ íèæå ó, ëèáî ó íèæå

õ, ëèáî õ = ó. Â òàêîì ñëó÷àå ñîëäàò ýòîé ðîòû ìîæíî îäíîçíà÷-

íî âûñòðîèòü ïî ðîñòó â îäíó ëèíèþ. Â ñëó÷àå, åñëè åñòü äâà

èëè áîëåå ñîëäàò îäèíàêîâîãî ðîñòà, òî îäíîçíà÷íîãî ïîñòðîå-

íèÿ ïî ðîñòó íå ïîëó÷èòñÿ. Ýòèì, ñîáñòâåííî ãîâîðÿ, ïðîèëëþ-

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

â êîòîðîì íàðóøàåòñÿ àêñèîìà ñâÿçíîñòè. Ïîñëåäíÿÿ ñèòóàöèÿ