Лекция 23. Как устроена математика. Исчисление предикатов первого порядка. Аксиоматические теории... (Лекции 2014)

Îñíîâûìàòåìàòè÷åñêîéëîãèêèèëîãè÷åñêîãîïðîãðàììèðîâàíèÿËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 23.Êàê óñòðîåíà ìàòåìàòèêà.Èñ÷èñëåíèå ïðåäèêàòîâïåðâîãî ïîðÿäêà.Àêñèîìàòè÷åñêèå òåîðèè.Ýëåìåíòàðíàÿ ãåîìåòðèÿ.Òåîðèÿ ìíîæåñòâÖåðìåëîÔðåíêåëÿ.Àðèôìåòèêà Ïåàíî.Òåîðåìà Ãåäåëÿ î íåïîëíîòå.ìîäàëüíûåëîãèêèyèíòóèöèîíèñòñêàÿëîãèêàyI@@òåîðèÿäîêàçàòåëüñòâ6yäðóãèåëîãè÷åñêèåîïåðàöèè@äðóãàÿ@ñåìàíòèêàëîãè÷åñêèõ@@ñâÿçîêäðóãèåôîðìûëîãè÷åñêîãîâûâîäà@@y äðóãèå êâàíòîðûëîãèêèâûñøèõ ïîðÿäêîâ@ i ñïåöèàëüíûå èíòåðïðåòàöèè- yÊËÀÑÑÈ×ÅÑÊÀßËÎÃÈÊÀàêñèîìàòè÷åñêèåòåîðèèÊàê óñòðîåíà ìàòåìàòèêàÌàòåìàòèêà ýòî ñïåöèôè÷åñêàÿ íàóêà.Îíà íå îòíîñèòñÿ ê ÷èñëó åñòåñòâåííûõ íàóê (ôèçèêà,áîòàíèêà, ãåîëîãèÿ, è ïð.), ò.

ê. îíà íå èìååò äåëà íè ñïðèðîäíûìè ÿâëåíèÿìè, íè ñ ýìïèðè÷åñêèìè çíàíèÿìè.Îíà íå îòíîñèòñÿ ê ÷èñëó ãóìàíèòàðíûõ íàóê (ôèëîñîôèÿ,èñòîðèÿ, ïîëèòîëîãèÿ è ïð. áîëòîëîãèÿ), ò. ê îíà íå çàíèìàåòñÿíè ëþäñêîé äåÿòåëüíîñòüþ, íè ëþäñêèìè âîççðåíèÿìè.Îíà çàíèìàåòñÿ ñîçäàíèåì, ðàçâèòèåì è èçó÷åíèåììàòåìàòè÷åñêèõ òåîðèé óìîçðèòåëüíûõ êîíñòðóêöèé,êîòîðûå ñòðîÿòñÿ ïî ñòðîãèì îáúåêòèâíûì çàêîíàìôîðìàëüíîé ëîãèêè .Êàê óñòðîåíà ìàòåìàòèêàÑòàíèñëàâ Ëåì ñðàâíèâàëìàòåìàòèêó ñ áåçóìíûì ïîðòíûì,êîòîðûé øüåò îäåæäó äëÿíåâåäîìûõ ñóùåñòâ.Ïîðòíîãî íå áåñïîêîèò, êîìóïðèäåòñÿ âïîðó åãî îäåæäà.Îí ëèøü õî÷åò, ÷òîáû ïëàòüåáûëî ñøèòî ïðî÷íî.Êàê óñòðîåíà ìàòåìàòèêàÑ ÷åãî íà÷èíàåòñÿ ðàññêàç î êàæäîì ðàçäåëå ìàòåìàòèêè?IIIIÂíà÷àëå óñëàâëèâàþòñÿ î ñèñòåìå îáîçíà÷åíèé,îïðåäåëÿþò ÿçûê, íà êîòîðîì áóäóò çàïèñûâàòüìàòåìàòè÷åñêèå óòâåðæäåíèÿ (îïðåäåëÿåòñÿ ñèíòàêñèñìàòåìàòè÷åñêîãî ÿçûêà ).Çàòåì ïðèõîäÿò ê ñîãëàøåíèþ îá îñíîâîïîëàãàþùèõñâîéñòâàõ, çàêîíàõ, êîòîðûì äîëæíû óäîâëåòâîðÿòüèíòåðåñóþùèå íàñ îïåðàöèè è îòíîøåíèÿ íàäâîîáðàæàåìûìè îáúåêòàìè (ôîðìóëèðóþòñÿ àêñèîìûìàòåìàòè÷åñêîé òåîðèè ).Äàëåå äîãîâàðèâàþòñÿ î òîì, êàêèå ñðåäñòâà îáîñíîâàíèÿèñòèííîñòè ìàòåìàòè÷åñêèõ óòâåðæäåíèé ñ÷èòàþòñÿäîïóñòèìûìè (îïðåäåëÿåòñÿ àïïàðàò ëîãè÷åñêîãî âûâîäà ).È ïîñëå ýòîãî ïðèñòóïàþò ê ïîëó÷åíèþ ëîãè÷åñêèîáîñíîâàííûõ óòâåðæäåíèé ñôîðìóëèðîâàííîéìàòåìàòè÷åñêîé òåîðèè (âûâîä òåîðåì ).Âîò òàê ñòðîÿòñÿ ôîðìàëüíûå àêñèîìàòè÷åñêèå òåîðèè .Êëàññè÷åñêîå èñ÷èñëåíèå ïðåäèêàòîâÊàê ìîæíî àêñèîìàòèçèðîâàòü òåîðèþ îáùåçíà÷èìûõóòâåðæäåíèé (ôîðìóë)? Íàïðèìåð, òàê:ÀÊÑÈÎÌÛ.1.

Ax1. ϕ1 → (ϕ2 → ϕ1 ),2. Ax2. (ϕ1 → (ϕ2 → ϕ3 )) → ((ϕ1 → ϕ2 ) → (ϕ1 → ϕ3 )),3. Ax3. (ϕ1 & ϕ2 ) → ϕ1 ,4. Ax4. (ϕ1 & ϕ2 ) → ϕ2 ,5. Ax5. ϕ1 → (ϕ2 → (ϕ1 & ϕ2 )),6. Ax6. ϕ1 → (ϕ1 ∨ ϕ2 ),7. Ax7. ϕ2 → (ϕ1 ∨ ϕ2 ),8. Ax8. (ϕ1 → ϕ0 ) → ((ϕ2 → ϕ0 ) → ((ϕ1 ∨ ϕ2 ) → ϕ0 )),9. Ax9. ϕ1 → (¬ϕ1 → ϕ0 ),10.

Ax10. ϕ1 ∨ ¬ϕ1 ,Êëàññè÷åñêîå èñ÷èñëåíèå ïðåäèêàòîâÀÊÑÈÎÌÛ.1. Ax11. ∀X ϕ(X ) → ϕ(t),2. Ax12. ϕ(t) → ∃X ϕ(X ),3. Ax13. ∀X (ϕ1 → ϕ2 (X )) → (ϕ1 → ∀X ϕ2 (X )),4. Ax14. ∀X (ϕ1 (X ) → ϕ2 ) → (∃X ϕ1 (X ) → ϕ2 ).ÏÐÀÂÈËÀ ÂÛÂÎÄÀ.1. Ïðàâèëî îòäåëåíèÿ (modus ponens)2.

Ïðàâèëî îáîáùåíèÿϕ∀X ϕϕ, ϕ → ψ,ψÊëàññè÷åñêîå èñ÷èñëåíèå ïðåäèêàòîâËÎÃÈ×ÅÑÊÈÉ ÂÛÂÎÄ.Ïóñòü çàäàíî íåêîòîðîå ìíîæåñòâî ôîðìóë (ãèïîòåç) Γ .Òîãäà ëîãè÷åñêèì âûâîäîì èç ìíîæåñòâà ãèïîòåç Γíàçûâàåòñÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ôîðìóëϕ1 , ϕ2 , . . . , ϕn ,â êîòîðîé êàæäàÿ ôîðìóëà ϕi óäîâëåòâîðÿåò îäíîìó èçñëåäóþùèõ óñëîâèé:1. ëèáî ϕi ÿâëÿåòñÿ àêñèîìîé,2. ëèáî ϕi ÿâëÿåòñÿ ãèïîòåçîé, ò.

å. ϕi ∈ Γ ,3. ëèáî ϕi ïîëó÷àåòñÿ èç ïðåäøåñòâóþùèõ ôîðìóë ýòîéïîñëåäîâàòåëüíîñòè ïî ïðàâèëó îòäåëåíèÿ èëè ïî ïðàâèëóîáîáùåíèÿ. ýòîì ñëó÷àå ôîðìóëà ϕn íàçûâàåòñÿ âûâîäèìîé èçìíîæåñòâà Γ , è ýòîò ôàêò îáîçíà÷àåòñÿ Γ ` ϕnÔîðìóëà ϕ íàçûâàåòñÿ òåîðåìîé , åñëè ∅ ` ϕ , è ýòîò ôàêòîáîçíà÷àåòñÿ ` ϕ .Êëàññè÷åñêîå èñ÷èñëåíèå ïðåäèêàòîâÈñ÷èñëåíèå ïðåäèêàòîâ ñ ðàâåíñòâîì.Ââåäåì ñïåöèàëüíûé äâóõìåñòíûé ïðåäèêàòíûé ñèìâîë = èäîáàâèì ê àêñèîìàì ÊÈÏ ñëåäóþùèå àêñèîìû ðàâåíñòâà:1.

Ax15. ∀X (X = X ),2. Ax16 ∀X , Y (X = Y → (ϕ(X , X ) → ϕ(X , Y ))).Ïîëó÷åííóþ ñèñòåìó àêñèîì íàçûâàþò êëàññè÷åñêèìèñ÷èñëåíèåì ïðåäèêàòîâ ñ ðàâåíñòâîì ÊÈÏ= .Àëãåáðàè÷åñêàÿ ñèñòåìà I íàçûâàåòñÿ íîðìàëüíîéèíòåðïðåòàöèåé , åñëè äëÿ ëþáîé ïàðû ðàçëè÷íûõ ïðåäìåòîâd1 , d2 èç îáëàñòè èíòåðïðåòàöèè DI âåðíî ñîîòíîøåíèåI 6|= d1 = d2 .Àêñèîìàòè÷åñêèå òåîðèè ïåðâîãî ïîðÿäêàÝëåìåíòàðíàÿ àêñèîìàòè÷åñêàÿ òåîðèÿ îáðàçóåòñÿ èçèñ÷èñëåíèÿ ïðåäèêàòîâ ñ ðàâåíñòâîì çà ñ÷åòIîãðàíè÷åíèÿ ñèãíàòóðû ÿçûêà ëîãèêè ïðåäèêàòîâôèêñèðîâàííûì êîíå÷íûì íàáîðîì êîíñòàíò,ôóíêöèîíàëüíûõ è ïðåäèêàòíûõ ñèìâîëîâ, îáîçíà÷àþùèõáàçîâûå îáúåêòû, îïåðàöèè è îòíîøåíèÿ òåîðèè,Iäîáàâëåíèÿ ê ìíîæåñòâó àêñèîì èñ÷èñëåíèÿ ïðåäèêàòîâñïåöèàëüíûõ (íåëîãè÷åñêèõ) àêñèîì, îïèñûâàþùèõáàçîâûå ïðèíöèïû òåîðèè.Òàêèì îáðàçîì îáðàçóþòñÿ ýëåìåíòàðíàÿ òåîðèÿ ðàâåíñòâà,ýëåìåíòàðíàÿ òåîðèÿ ãðóïï, ýëåìåíòàðíàÿ òåîðèÿ ïîëåé,ýëåìåíòàðíàÿ ãåîìåòðèÿ, ýëåìåíòàðíàÿ àðèôìåòèêà,ýëåìåíòàðíàÿ òåîðèÿ ìíîæåñòâ, è äð.Ôîðìóëû ϕ , ëîãè÷åñêè âûâîäèìûå èç àêñèîì ýëåìåíòàðíîéàêñèîìàòè÷åñêîé òåîðèè T , íàçûâàþòñÿ òåîðåìàìè òåîðèè Tè îáîçíà÷àþòñÿ çàïèñüþ T ` ϕ .Àêñèîìàòè÷åñêèå òåîðèè ïåðâîãî ïîðÿäêàÝëåìåíòàðíàÿ àêñèîìàòè÷åñêàÿ òåîðèÿ T íàçûâàåòñÿIíåïðîòèâîðå÷èâîé , åñëè íå âñå ôîðìóëû ÿâëÿþòñÿòåîðåìàìè òåîðèè T , ò.

å. ñóùåñòâóåò òàêàÿ ôîðìóëà ϕ ,äëÿ êîòîðîé T 6` ϕ ;Iïîëíîé , åñëè äëÿ âñÿêîé çàìêíóòîé ôîðìóëû ëèáî îíàñàìà, ëèáî åå îòðèöàíèå ÿâëÿåòñÿ òåîðåìîé òåîðèè T , ò. å.äëÿ ëþáîé ôîðìóëû ϕ ëèáî T ` ϕ , ëèáî T ` ¬ϕ ;Iêàòåãîðè÷íîé , åñëè ëþáûå äâå íîðìàëüíûå ìîäåëèòåîðèè T èçîìîðôíû, ò. å. äëÿ ëþáîé ïàðû íîðìàëüíûõèíòåðïðåòàöèé I1 , I2 âåðíîI1 |= T è I2 |= T =⇒ I1 ∼= I2 ;Iðàçðåøèìîé , åñëè ñóùåñòâóåò àëãîðèòì, ïðîâåðÿþùèé,ÿâëÿåòñÿ ëè ïðîèçâîëüíàÿ ôîðìóëà òåîðåìîé òåîðèè T .Óòâåðæäåíèå.Âñÿêàÿ ïîëíàÿ êîíå÷íî àêñèîìàòèçèðóåìàÿ òåîðèÿ ðàçðåøèìà.Àêñèîìàòè÷åñêîå óñòðîéñòâî ãåîìåòðèèÂïåðâûå ïîïûòêó àêñèîìàòèçèðîâàòü ãåîìåòðèþ ïðåäïðèíÿëÅâêëèä (3 â. äî í.

ý.). Ãåîìåòðè÷åñêàÿ òåîðèÿ Åâêëèäàîïèðàëàñü íà 5 àêñèîì.Ê ñîæàëåíèþ, ñèñòåìà ãåîìåòðè÷åñêèõ àêñèîì èç ¾Íà÷àë¿Åâêëèäà íåïîëíà.Âîò ïðèìåð èñòèííîãî óòâåðæäåíèÿ, êîòîðîå íåëüçÿ âûâåñòè èçàêñèîì è ïîñòóëàòîâ Åâêëèäà.Åñëè ïðÿìàÿ ïåðåñåêàåò îäíó èç ñòîðîí òðåóãîëüíèêà â òî÷êå,îòëè÷íîé îò âåðøèíû òðåóãîëüíèêà, òî ýòà ïðÿìàÿ òàêæåïåðåñåêàåò åùå îäíó ñòîðîíó òðåóãîëüíèêà.tt@@@@@@tÀêñèîìàòè÷åñêîå óñòðîéñòâî ãåîìåòðèèÑèñòåìàòè÷åñêîå è îñíîâàòåëüíîå ïîñòðîåíèå ãåîìåòðè÷åñêîéñèñòåìû àêñèîì áûëî îñóùåñòâëåíî Ä.

Ãèëüáåðòîì (40 àêñèîì)â 1899 ã. Áîëåå áîëåå êðàòêóþ àêñèîìàòèêó óäàëîñü ïîñòðîèòüÀ. Òàðñêîìó è åãî ó÷åíèêà (12 àêñèîì).Àêñèîìû ÒàðñêîãîÁóäåì ðàññìàòðèâàòü ãåîìåòðè÷åñêèé ìèð, âñå îáúåêòûêîòîðîãî òî÷êè .Íà ìíîæåñòâå òî÷åê åñòü âñåãî ëèøü äâà áàçîâûõ ïðåäèêàòà:B(x, y, z)òî÷êà y ëåæèò ìåæäó òî÷êàìè x è z íàîäíîé ïðÿìîéD(x, y, z, u)òî÷êà x îòñòîèò îò òî÷êè y íà òàêîå æåðàññòîÿíèå, ÷òî è òî÷êà z îò òî÷êè uÀêñèîìàòè÷åñêîå óñòðîéñòâî ãåîìåòðèèÀêñèîìû T1T51).

∀x, y , z (B(x, y , z) → B(z, y , x))( àêñèîìà ñèììåòðè÷íîñòè ïðåäèêàòà B )2). ∀x, y , z, u (B(x, y , u)&B(y , z, u) → B(x, y , z))(àêñèîìà òðàíçèòèâíîñòè ïðåäèêàòà B )3). ∀x, y D(x, y , y , x)(àêñèîìà ñèììåòðè÷íîñòè ðàâåíñòâà äëèí îòðåçêîâ )4). ∀x, y , z (D(x, y , z, z) → x = y )(àêñèîìà íóëåâîãî îòðåçêà )5). ∀x1 , y1 , x2 , y2 , x3 , y3(D(x1 , y1 , x2 , y2 )&D(x2 , y2 , x3 , y3 ) → D(x1 , y1 , x3 , y3 ))(àêñèîìà òðàíçèòèâíîñòè ðàâåíñòâà äëèí îòðåçêîâ )Àêñèîìàòè÷åñêîå óñòðîéñòâî ãåîìåòðèèÀêñèîìà T66). ∀x1 , y1 , z1 , u1 , x2 , y2 , z2 , u2(x1 6= y1 &y1 6= z1 &B(x1 , y1 , z1 )&B(x2 , y2 , z2 )&D(x1 , y1 , x2 , y2 )&D(y1 , z1 , y2 , z2 )&D(y1 , u1 , y2 , u2 )&D(x1 , u1 , x2 , u2 ) →→ D(z1 , u1 , z2 , u2 ))(àêñèîìà ïÿòè îòðåçêîâ )tx1AtZu1AZA ZA ZZAZZAtZty1z1tx2t u2AZAZA ZA ZZAZZZtAty2z2Àêñèîìàòè÷åñêîå óñòðîéñòâî ãåîìåòðèèÀêñèîìû T7T107).

∀x, y , z, u ∃v (B(x, y , v ) & D(y , v , z, u))(àêñèîìà îòêëàäûâàíèÿ îòðåçêà )8). ∀x, y ∃z (B(x, z, y )&D(x, z, z, y ))(àêñèîìà äåëåíèÿ îòðåçêà ïîïîëàì )9). ∃x, y , z (¬B(x, y , z) & ¬B(x, z, y ) & ¬B(z, x, y ))(àêñèîìà ñóùåñòâîâàíèÿ íåêîëëèíåàðíûõ òî÷åê )10). ∀x, y , z (¬B(x, y , z) & ¬B(x, z, y ) & ¬B(z, x, y ) →→ ∃v (D(v , x, v , y )&D(v , x, v , z)))(àêñèîìà öåíòðà îïèñàííîé îêðóæíîñòè )Àêñèîìàòè÷åñêîå óñòðîéñòâî ãåîìåòðèèÀêñèîìà T1111). ∀x, y , z, u, v(D(x, u, x, v )&D(y , u, y , v )&D(z, u, z, v ) →→ (B(x, y , z) ∨ B(y , z, x) ∨ B(z, y , x)))(àêñèîìà ïåðïåíäèêóëÿðà ê ñåðåäèíå îòðåçêà )t x@@@t yQQ @Q @QQ@Q@Qt@QtHu HH vHHHHHztÀêñèîìàòè÷åñêîå óñòðîéñòâî ãåîìåòðèèÀêñèîìà T1212).

∀x, y , z, u, v(B(x, u, z)&B(y , z, v ) →→ ∃w (B(y , u, w )&B(x, w , v )))(àêñèîìà Ïàøà )t v@t w@@t t@tzxu@@ @t@yÀêñèîìàòè÷åñêîå óñòðîéñòâî ãåîìåòðèèÀêñèîìà T1313). ∃x ∀y , z (ϕ(y )&ψ(z) → B(x, y , z)) →→ ∃x 0 ∀y , z (ϕ(y )&ψ(z) → B(y , x 0 , z))(ñõåìà àêñèîì íåïðåðûâíîñòè )Àêñèîìàòè÷åñêîå óñòðîéñòâî ãåîìåòðèèÎñíîâíûå ñâîéñòâà ôîðìàëüíîé ãåîìåòðèè ÒàðñêîãîÒåîðåìàÀêñèîìàòè÷åñêàÿ òåîðèÿ T1T13 (ôîðìàëüíàÿ ãåîìåòðèÿÒàðñêîãî)Iíåïðîòèâîðå÷èâà,Iïîëíà,Iêàòåãîðè÷íà,Iàëãîðèòìè÷åñêè ðàçðåøèìà.Ê ñîæàëåíèþ äëÿ øêîëüíèêîâ, ðàçðåøàþùàÿ ïðîöåäóðà,ñïîñîáíàÿ äîêàçûâàòü ëþáóþ ãåîìåòðè÷åñêóþ òåîðåìó, èìååòíåâåðîÿòíî áîëüøóþ âû÷èñëèòåëüíóþ ñëîæíîñòü.Òåîðèÿ ìíîæåñòâÌÍÎÆÅÑÒÂÎ ýòî îñíîâîïîëàãàþùåå ïîíÿòèå ñîâðåìåííîéìàòåìàòèêè. Ïîíÿòèå ìíîæåñòâà ïðåäëîæèë âî âòîðîéïîëîâèíå 19 â.

íåìåöêèé ìàòåìàòèê Ãåîðã Êàíòîð.À ÷òî æå òàêîå ìíîæåñòâî?Ïîñêîëüêó ýòî îñíîâîïîëàãàþùåå ïîíÿòèå, ñòðîãîãîîïðåäåëåíèÿ äàòü íåëüçÿ. Ýòî êîëëåêöèÿ (ñåìåéñòâî,ñîâîêóïíîñòü, ñîáðàíèå) ðàçëè÷íûõ ïðåäìåòîâ (îáúåêòîâ,ýëåìåíòîâ ).Ìîæåò ëè ìàòåìàòèêà ñïîêîéíî ðàçâèâàòüñÿ, îïèðàÿñü íà ñòîëüçûáêîå îñíîâàíèå?Òåîðèÿ ìíîæåñòâÏàðàäîêñ ÐàññåëàÝëåìåíòàìè ìíîæåñòâ ìîãóò áûòü ìíîæåñòâà. Ðàññìîòðèìêîëëåêöèþ âñåõ ìíîæåñòâ, êàæäîå èç êîòîðûõ íå ÿâëÿåòñÿñâîèì ñîáñòâåííûì ýëåìåíòîì: A = {x : x ∈/ x} .Ó íàñ íåò äîñòàòî÷íûõ îñíîâàíèé íå ïðèçíàâàòü ýòóñîâîêóïíîñòü ìíîæåñòâ A ìíîæåñòâîì.Íî òîãäà ìû äîëæíû óìåòü äàâàòü îòâåò íà âîïðîñ:ñîäåðæèò ëè ìíîæåñòâî A â êà÷åñòâå ýëåìåíòà ñàìî ìíîæåñòâîA (ò. å.

âåðíî ëè ÷òî A ∈ A ?)Îòâåò îáåñêóðàæèâàþùèé:IIåñëè A ∈ A , òî ïî îïðåäåëåíèþ A âåðíî A ∈/ A,à åñëè A ∈/ A , òî ïî îïðåäåëåíèþ A âåðíî A ∈ A .Òåîðèÿ ìíîæåñòâÇíà÷èò, â íàèâíîé òåîðèè ìíîæåñòâ ñóùåñòâóþòìàòåìàòè÷åñêèå óòâåðæäåíèÿ, êîòîðûå íåëüçÿ ïðèçíàòü íèèñòèííûìè, íè ëîæíûìè.