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

Íà îñíîâå òàêîé ðàñïëûâ÷àòîéòåîðèè õîðîøåé ìàòåìàòèêè íå ïîñòðîèòü.Ìîæåò áûòü ñòîèëî áû èñêëþ÷èòü ýòó ñòðàííóþ êîëëåêöèþ Aèç ÷èñëà ìíîæåñòâ?Ìîæíî. Íî òîãäà ïðèäåòñÿ ñîçäàòü ¾êîäåêñ òåîðèè ìíîæåñòâ¿,â êîòîðîì äîëæíî áûòü óêàçàíî, êàêèå èìåííî êîíñòðóêöèèïðèçíàþòñÿ ìíîæåñòâàìè, è êàêèìè ñâîéñòâàìè îíè äîëæíûîáëàäàòü.Ïîïûòêó ñîçäàíèÿ òàêîãî ¾êîäåêñà òåîðèè ìíîæåñòâ¿ àêñèîìàòè÷åñêîé òåîðèè ìíîæåñòâ ïðåäïðèíÿë ÝðíåñòÖåðìåëî â 1908 ã.. Àêñèîìàòèêó Öåðìåëî ïîïîëíèëè ÀáðàõàìÔðåíêåëü, Òîðàëüô Ñêîëåì, Äæîí ôîí Íåéìàí.Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏîíÿòèå ìíîæåñòâà è ñâîéñòâà ìíîæåñòâ ìîæíî îïèñàòü ñèñïîëüçîâàíèåì åäèíñòâåííîãî ïðåäèêàòíîãî ñèìâîëà ∈ ,îáîçíà÷àþùåãî îòíîøåíèå ïðèíàäëåæíîñòè îäíîãî ìíîæåñòâàâ êà÷åñòâå ýëåìåíòà äðóãîãî ìíîæåñòâà.Ïðåäñòàâèì ñåáå ìàòåìàòè÷åñêèé ìèð, ñîñòîÿùèé òîëüêî èçìíîæåñòâ. Ýòîò ìèð ìîæåò áûòü îïèñàí ñëåäóþùèìèàêñèîìàìè.Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿ1) ∀x, y , u, v (x = y & u = v ) → (x ∈ u ≡ y ∈ v )(Àêñèîìà ðàâåíñòâà ìíîæåñòâ )2) ∀x, y (∀z (z ∈ x ≡ z ∈ y ) ≡ x = y )(Àêñèîìà îáúåìíîñòè )3) ∀x∀u1 , .

. . , un ∃y ∀z (z ∈ y ≡ (z ∈ x & ϕ(z, u1 , . . . , un )))(Ñõåìà àêñèîì âûäåëåíèÿ )çäåñü ϕ(x, u1 , . . . , un ) ïðîèçâîëüíàÿ ôîðìóëàëîãèêè ïðåäèêàòîâ ñèãíàòóðû σ = h∈i .Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏðèìåðû ïðèìåíåíèÿ àêñèîìû âûäåëåíèÿ1. Ñóùåñòâóåò åäèíñòâåííîå ïåðåñå÷åíèå äâóõ ìíîæåñòâîÑóùåñòâîâàíèå ïåðåñå÷åíèÿ äâóõ ìíîæåñòâ ñëåäóåò èç àêñèîìûâûäåëåíèÿ∀x1 , x2 ∃y ∀z (z ∈ y ≡ (z ∈ x1 & z ∈ x2 )),à åäèíñòâåííîñòü ïåðåñå÷åíèÿ ñëåäóåò èç àêñèîìû îáúåìíîñòè∀x, y (∀z (z ∈ x ≡ z ∈ y ) ≡ x = y ).Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏðèìåðû ïðèìåíåíèÿ àêñèîìû âûäåëåíèÿ2.

Ñóùåñòâóåò åäèíñòâåííîå ïóñòîå ìíîæåñòâîÑóùåñòâîâàíèå ïóñòîãî ìíîæåñòâà ñëåäóåò èç àêñèìûâûäåëåíèÿ∀x ∃y ∀z(z ∈ y ≡ (z ∈ x & z 6= z)),à åäèíñòâåííîñòü ïóñòîãî ìíîæåñòâà ñëåäóåò èç àêñèîìûîáúåìíîñòè∀x, y (∀z (z ∈ x ≡ z ∈ y ) ≡ x = y ).Íî çäåñü åñòü îäèí íþàíñ. À îòêóäà áåðåòñÿ ìíîæåñòâî X íàîñíîâàíèè êîòîðîãî îïðåäåëÿåòñÿ ïóñòîå ìíîæåñòâî?Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏðèìåðû ïðèìåíåíèÿ àêñèîìû âûäåëåíèÿ2.

Ñóùåñòâóåò åäèíñòâåííîå ïóñòîå ìíîæåñòâîÑóùåñòâîâàíèå ïóñòîãî ìíîæåñòâà ñëåäóåò èç àêñèìûâûäåëåíèÿ∀X ∃y ∀z(z ∈ y ≡ (z ∈ X & z 6= z)),à åäèíñòâåííîñòü ïóñòîãî ìíîæåñòâà ñëåäóåò èç àêñèîìûîáúåìíîñòè∀x, y (∀z (z ∈ x ≡ z ∈ y ) ≡ x = y ).Íî çäåñü åñòü îäèí íþàíñ.

À îòêóäà áåðåòñÿ ìíîæåñòâî X íàîñíîâàíèè êîòîðîãî îïðåäåëÿåòñÿ ïóñòîå ìíîæåñòâî?Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏðèìåðû ïðèìåíåíèÿ àêñèîìû âûäåëåíèÿÏîýòîìó ïðèõîäèòñÿ ââîäèòü ñïåöèàëüíóþ àêñèîìó.4). ∃y ∀z ¬(z ∈ y )(Àêñèîìà ïóñòîãî ìíîæåñòâà )Ââåäåì ñïåöèàëüíûé ñèìâîë ∅ äëÿ îáîçíà÷åíèÿ ïóñòîãîìíîæåñòâà, à çàïèñü y = ∅ áóäåì ðàññìàòðèâàòü êàêñîêðàùåííîå îáîçíà÷åíèå ôîðìóëû∀z ¬(z ∈ y ) .Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏðèìåðû ïðèìåíåíèÿ àêñèîìû âûäåëåíèÿ3. Ñóùåñòâóåò åäèíñòâåííîå îáúåäèíåíèå äâóõ ìíîæåñòâÊàçàëîñü áû, îáúåäèíåíèå ìíîæåñòâ ëåãêî ââåñòè òàê æå, êàêýòî áûëî ñäåëàíî äëÿ ïåðåñå÷åíèÿ:∀x1 , x2 ∃y ∀z (z ∈ y ≡ (z ∈ x1 ∨ z ∈ x2 )) .Íî ýòà ôîðìóëà íå ïîäïàäàåò ïîä ñõåìó àêñèîì âûäåëåíèÿ∀x∀u1 , .

. . , un ∃y ∀z (z ∈ y ≡ (z ∈ x & ϕ(z, u1 , . . . , un ))) .Ìîæíî áûëî áû çàïèñàòü îïðåäåëåíèå îáúåäèíåíèÿ òàê:∀X, x1 , x2 ∃y ∀z (z ∈ y ≡ (z ∈ X & (z 6= x1 ∨ z ∈ x2 ))) .Íî ñîâåðøåííî íåïîíÿòíî, îòêóäà âçÿòü ïîäõîäÿùåå ìíîæåñòâîX . Ìîæåò áûòü, â êà÷åñòâå X âçÿòü x1 ∪ x2 ? Íî ìû âåäü åùå íåÒåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏðèìåðû ïðèìåíåíèÿ àêñèîìû âûäåëåíèÿÏîýòîìó ïðèõîäèòñÿ ââîäèòü äâå ñïåöèàëüíûå àêñèîìû.5). ∀y , z ∃x ∀u (u ∈ x ≡ (u = y ∨ u = z))(Àêñèîìà ïàðû )Ìíîæåñòâî x , ñóùåñòâîâàíèå êîòîðîãî óòâåðæäàåò àêñèîìàïàðû, òðàäèöèîííî îáîçíà÷àåòñÿ {y , z}.6). ∀y ∃x ∀u (u ∈ x ≡ ∃z (z ∈ y & u ∈ z))(Àêñèîìà îáúåäèíåíèÿ )Ìíîæåñòâî x , ñóùåñòâîâàíèå êîòîðîãî óòâåðæäàåòàêñèîìàSîáúåäèíåíèÿ, òðàäèöèîííî îáîçíà÷àåòñÿz èëè áîëååz∈yêîðîòêî ∪y . Òàêèì îáðàçîì x1 ∪ x2 ýòî ∪{x1 , x2 }.Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏðèìåðû ïðèìåíåíèÿ àêñèîìû âûäåëåíèÿ4.

À ÷òî äåëàòü, åñëè íàì íóæíî ìíîæåñòâî, ñîñòîÿùåå èçîäíîãî-åäèíñòâåííîãî ýëåìåíòà?Äëÿ ýòîãî äîñòàòî÷íî âûäåëåíèÿ è àêñèîìû ïàðû:ìíîæåñòâî, ñîñòîÿùåå èç îäíîãî ýëåìåíòà u ýòî ìíîæåñòâî{u,u}.5. À ÷òî äåëàòü, åñëè íàì íóæíû óïîðÿäî÷åííûå íàáîðûýëåìåíòîâ?Äëÿ ýòîãî äîñòàòî÷íî àêñèîìû âûäåëåíèÿ è àêñèîìû ïàðû:óïîðÿäî÷åííàÿ ïàðà hy , zi ýòî ìíîæåñòâî {y , {y , z}}.Äàëåå àíàëîãè÷íî ìîæíî îïðåäåëÿòü óïîðÿäî÷åííûå íàáîðû(êîðòåæè), ôóíêöèè, èíúåêòèâíûå îòîáðàæåíèÿ, áèåêòèâíûåîòîáðàæåíèÿ, îòíîøåíèÿ âêëþ÷åíèÿ, ðàâíîìîùíîñòè è ò. ä.Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÍî òàêèì îáðàçîì èç ïóñòîãî ìíîæåñòâà ∅, åäèíñòâåííîãîìíîæåñòâà, ñóùåñòâîâàíèå êîòîðîãî ãàðàíòèðóþò àêñèîìû, ìîæíî ïîëó÷èòü òîëüêî êîíå÷íûå ìíîæåñòâà. À îòêóäàâîçüìóòñÿ áåñêîíå÷íûå ìíîæåñòâà?7). ∃x (∅ ∈ x & ∀y (y ∈ x → y ∪ {y } ∈ x))(Àêñèîìà áåñêîíå÷íîñòè )Ôàêòè÷åñêè, àêñèîìà áåñêîíå÷íîñòè îïðåäåëÿåò ìíîæåñòâîíàòóðàëüíûõ ÷èñåë:no∅,∅,{∅},{∅,{∅}},...,{∅},{∅,{∅}}|{z} |{z} | {z } |{z}0123Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÀ îòêóäà âîçüìóòñÿ íåñ÷åòíûå ìíîæåñòâà?8).

∀y ∃x ∀z (z ∈ x ≡ ∀u (u ∈ z → u ∈ y ))(Àêñèîìà ñòåïåíè )Àêñèîìà ñòåïåíè îïðåäåëÿåò ìíîæåñòâî âñåõ ïîäìíîæåñòâçàäàííîãî ìíîæåñòâà (ìíîæåñòâî-ñòåïåíü, powerset). Çíà÷èò,ìíîæåñòâà ìîãóò íàðàñòàòü íåîãðàíè÷åííî ¾âûñîêî¿.Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÀ ÿâëÿþòñÿ ëè ìíîæåñòâàìè îáðàçû ìíîæåñòâ îòíîñèòåëüíîçàäàííûõ ôóíêöèé, îïðåäåëÿåìûõ ïðè ïîìîùè ôîðìóë ëîãèêèïðåäèêàòîâ?9). ∀x ∀y , z, u (y ∈ x & ϕ(y , z) & ϕ(y , u) → z = u) →→ ∃v ∀w (w ∈ v ≡ ∃t (t ∈ x & ϕ(t, w )))(Ñõåìà àêñèîì çàìåíû )Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÀ íàñêîëüêî ¾ãëóáîêî¿ ìîãóò îïóñêàòüñÿ ìíîæåñòâà? Íå ìîãóòëè ó íàñ îáðàçîâûâàòüñÿ òàêèå ìíîæåñòâà, êîòîðûå âõîäÿò âñîñòàâ ñàìèõ ñåáÿ â êà÷åñòâå ýëåìåíòîâ?10).

∀x (x 6= ∅ → ∃y (y ∈ x & x ∩ y = ∅))(Àêñèîìà ôóíäèðîâàíèÿ (ðåãóëÿðíîñòè) )Ýòà àêñèîìà èãðàåò ðîëü ïðåäîõðàíèòåëÿ, îáåðåãàþùåãîòåîðèþ ìíîæåñòâ îò ïàðàäîêñîâ. Àêñèîìà ôóíäèðîâàíèÿîáúÿâëÿåò, ÷òî ñåìåéñòâà ìíîæåñòâ âèäànoX1 , X2 , X3 , . . . ,ó êîòîðûõ X2 ∈ X1 , X3 ∈ X2 , . . . , Xn+1 ∈ Xn , · · · è ò. ä.ìíîæåñòâàìè íå ÿâëÿþòñÿ .Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏðèìåðû ïðèìåíåíèÿ àêñèîìû ôóíäèðîâàíèÿZF ` ∀u(u ∈/ u)Èç àêñèîìû ôóíäèðîâàíèÿ∀x (x 6= ∅ → ∃y (y ∈ x & x ∩ y = ∅))ñëåäóåò (åñëè â êà÷åñòâå x âûáðàòü {u})ZF ` ∃y (y ∈ {u} & {u} ∩ y = ∅) .Ïîñêîëüêó åäèíñòâåííûì ýëåìåíòîì y â ìíîæåñòâå {u}ÿâëÿåòñÿ u , ïîëó÷àåìZF ` {u} ∩ u = ∅ .Ñëåäîâàòåëüíî, ZF ` u ∈/ u.Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÏðèìåðû ïðèìåíåíèÿ àêñèîìû ôóíäèðîâàíèÿÏîïðîáóéòå ñàìîñòîÿòåëüíî óáåäèòüñÿ, ÷òî èç àêñèîì òåîðèèìíîæåñòâ ÖåðìåëîÔðåíêåëÿ ñëåäóåò íåâîçìîæíîñòüñóùåñòâîâàíèÿ ¾ïàðàäîêñàëüíûõ ìíîæåñòâ¿:ZF ` ∀u, v (u ∈/ v ∨v ∈/ u)ZF ` ¬∃x ∀y (y ∈ x ≡ y ∈/ y)Íóæíû ëè åùå êàêèå-íèáóäü äðóãèå àêñèîìû?Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÊ ñîæàëåíèþ, äëÿ ðåøåíèÿ íåêîòîðûõ çàäà÷ ïðèõîäèòñÿââîäèòü äîïîëíèòåëüíûå àêñèîìû.Íàïðèìåð, èíòóèöèÿ ïîäñêàçûâàåò, ÷òî ëþáûå äâà ìíîæåñòâàäîëæíû áûòü ñðàâíèìû ïî ìîùíîñòè.

Äâà ìíîæåñòâà A è Bíàçûâàþòñÿ ðàâíîìîùíûìè (A ∼ B ), åñëè ñóùåñòâóåòáèåêòèâíàÿ ôóíêöèÿ, îòîáðàæàþùàÿ îäíî ìíîæåñòâî íàäðóãîå. Ñïðàâåäëèâî ëè ñëåäóþùåå óòâåðæäåíèå?Òåîðåìà òðèõîòîìèè. Äëÿ ëþáûõ äâóõ ìíîæåñòâ A è B âåðíîîäíî èç òðåõ:IIIëèáî A ∼ B ,ëèáî A ∼6 B , íî ñóùåñòâóåò òàêîå A0 , A0 ⊂ A, ÷òî A0 ∼ B ,ëèáî A 6∼ B , íî ñóùåñòâóåò òàêîå B 0 , B 0 ⊂ B , ÷òî A ∼ B 0 .Ýòó òåîðåìó ìîæíî äîêàçàòü, íî ëèøü ïðè òîì óñëîâèè, åñëè óíàñ åñòü õîòü êàêîé-íèáóäü ñïîñîá, ïîçâîëÿþùèé âûáðàòü èçïðîèçâîëüíîãî íåïóñòîãî ìíîæåñòâà õîòü êàêîé-íèáóäü ýëåìåíò.×òîáû ýòîò ñïîñîá âûáîðà ñòàë ëåãàëüíûì ñðåäñòâîìäîêàçàòåëüñòâà, íóæíî ââåñòè ñïåöèàëüíóþ àêñèîìó âûáîðà .Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÀêñèîìà âûáîðà (CA)Êàêîâî áû íè áûëî ìíîæåñòâî ïîïàðíî íåïåðåñåêàþùèõñÿìíîæåñòâ U = {X1 , X2 , .

. . }, ñóùåñòâóåò ìíîæåñòâî Y ,ñîäåðæàùåå â òî÷íîñòè ïî îäíîìó ïðåäñòàâèòåëþ èç êàæäîãîìíîæåñòâà X1 , X2 , . . . ñåìåéñòâà U .Àêñèîìà âûáîðà èñïîëüçóåòñÿ ïðè äîêàçàòåëüñòâå î÷åíüáîëüøîãî ÷èñëà òåîðåì ìàòåìàòèêè. Ñ åå ïîìîùüþ ìîæíîäîêàçàòü âåñüìà íåîæèäàííûå óòâåðæäåíèÿ. Ê èõ ÷èñëóîòíîñèòñÿÒåîðåìà ÖåðìåëîËþáîå ìíîæåñòâî ìîæíî âïîëíå óïîðÿäî÷èòü, ò. å. îïðåäåëèòüíà ýòîì ìíîæåñòâå òàêîå îòíîøåíèå ëèíåéíîãî ïîðÿäêà, ïðèêîòîðîì íå ñóùåñòâóåò áåñêîíå÷íî óáûâàþùèõïîñëåäîâàòåëüíîñòåé ýëåìåíòîâ.Òåîðèÿ ìíîæåñòâ ÖåðìåëîÔðåíêåëÿÀ íå ïðèâíåñåò ëè àêñèîìà âûáîðà êàêîå-íèáóäü ïðîòèâîðå÷èåâ òåîðèþ ZF? Ýòîò âîïðîñ îñòàåòñÿ îòêðûòûì è ïî ñåé äåíü.Åñòü â òåîðèè ìíîæåñòâ è äðóãèå çàäà÷è, äëÿ ðåøåíèÿ êîòîðûõíåäîñòàòî÷íî àêñèîì òåîðèè ìíîæåñòâ ZF.Êîíòèíóóì-ãèïîòåçà (CH)Ëþáîå ïîäìíîæåñòâî ìíîæåñòâà âåùåñòâåííûõ ÷èñåë ëèáîÿâëÿåòñÿ ñ÷åòíûì, ëèáî ðàâíîìîùíî ìíîæåñòâó âåùåñòâåííûõ÷èñåë (ÿâëÿåòñÿ êîíòèíóàëüíûì). 1939 ã.

Ê. Ãåäåëü äîêàçàë òåîðåìó:Åñëè òåîðèÿ ìíîæåñòâ ZF+CA íåïðîòèâîðå÷èâà, òî òåîðèÿZF+AC+CH òàêæå íåïðîòèâîðå÷èâà . 1963 ã. Ï. Êîýí äîêàçàë òåîðåìó:Åñëè òåîðèÿ ìíîæåñòâ ZF+CA íåïðîòèâîðå÷èâà, òî òåîðèÿZF+AC+¬CH òàêæå íåïðîòèâîðå÷èâà .Ôîðìàëüíàÿ àðèôìåòèêàÀ ìîæíî ëè ïîëíîñòüþ àêñèîìàòèçèðîâàòü àðèôìåòèêóíàòóðàëüíûõ ÷èñåë? 1889 ã. èòàëüÿíñêèé ìàòåìàòèê Ä. Ïåàíî ïðåäëîæèë ñïèñîêàêñèîì, ïðè ïîìîùè êîòîðûõ ìîæíî äîêàçûâàòü óòâåðæäåíèÿ îñâîéñòâàõ íàòóðàëüíûõ ÷èñåë.Àðèôìåòèêà Ïåàíî (PA) îáðàçóåòñÿ çà ñ÷åò äîáàâëåíèÿ êÊÈÏ= ñèãíàòóðû h0, s, +, ×i ñëåäóþùèõ àêñèîì.Çäåñü s(x) íóæíî ðàññìàòðèâàòü êàê îäíîìåñòíóþ îïåðàöèþ,ðåàëèçóþùóþ ôóíêöèþ âû÷èñëåíèÿ ñëåäóþùåãî íàòóðàëüíîãî÷èñëà x + 1 .Ôîðìàëüíàÿ àðèôìåòèêà1.

∀x, y (s(x) = s(y ) → x = y );2. ∀x (s(x) 6= 0);3. ∀x ∃y (x 6= 0 → x = s(y ));4. ∀x (x + 0 = x);5. ∀x, y (x + s(y ) = s(x + y ));6. ∀x (x × 0 = 0);7. ∀x, y (x × s(y ) = x × y + x);8. ϕ(0) & ∀x (ϕ(x) → ϕ(s(x))) → ∀x ϕ(x).Âîïðîñ î íåïðîòèâîðå÷èâîñòè è ïîëíîòå ýòîé àêñèîìàòè÷åñêîéòåîðèè äîëãîå âðåìÿ îñòàâàëñÿ öåíòðàëüíîé ïðîáëåìîéìàòåìàòèêè.  1931 ã. Ê. Ãåäåëü äîêàçàë òåîðåìó, êîòîðàÿ äàëàñîâåðøåííî íåîæèäàííûé îòâåò íà ýòîò âîïðîñ.Ôîðìàëüíàÿ àðèôìåòèêàÍóìåðàëû è àðèôìåòèçóåìûå îòíîøåíèÿÍóìåðàëîì n̄ íàòóðàëüíîãî ÷èñëà n íàçûâàåòñÿ òåðìs(s(. .

. s( 0) . . . ))| {z }n ðàçÍàïðèìåð, 4̄ ýòî òåðì s(s(s(s(0)))) .Îòíîøåíèå P (k) íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë íàçûâàåòñÿàðèôìåòèçóåìûì , åñëè ñóùåñòâóåò òàêàÿ ôîðìóëàϕ(x1 , x2 , . . . , xk ) , ÷òî äëÿ âñÿêîãî íàáîðà íàòóðàëüíûõ ÷èñåë(n1 , n2 , . . . , nk ) âåðíû ñîîòíîøåíèÿIP (k) (n1 , n2 , . . . , nk ) = true ⇐⇒ PA ` ϕ(n̄1 , n̄2 , . . .