Лекция 23. Как устроена математика. Исчисление предикатов первого порядка. Аксиоматические теории... (1161893)
Текст из файла
Îñíîâûìàòåìàòè÷åñêîéëîãèêèèëîãè÷åñêîãîïðîãðàììèðîâàíèÿËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 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 .Òåîðèÿ ìíîæåñòâÇíà÷èò, â íàèâíîé òåîðèè ìíîæåñòâ ñóùåñòâóþòìàòåìàòè÷åñêèå óòâåðæäåíèÿ, êîòîðûå íåëüçÿ ïðèçíàòü íèèñòèííûìè, íè ëîæíûìè.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
