1610906281-8f040f4ba05ddb69404458d6cdcbceff (Теоретико-множественное введение Морозов)
Описание файла
PDF-файл из архива "Теоретико-множественное введение Морозов", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 1 семестр, которые можно найти в файловом архиве НГУ. Не смотря на прямую связь этого архива с НГУ, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Òåîðåòèêîìíîæåñòâåííîå ââåäåíèåÌíîæåñòâî ýòî îäíî èç íàèáîëåå ôóíäàìåíòàëüíûõ ìàòåìàòè÷åñêèõïîíÿòèé, íà êîòîðîì ñòðîèòñÿ çäàíèå ïî÷òè âñåé ñîâðåìåííîé ìàòåìàòèêè. Äîñòàòî÷íî ñêàçàòü, ÷òî âñå ÷èòàåìûå â íàñòîÿùåå âðåìÿ óíèâåðñèòåòñêèå ìàòåìàòè÷åñêèå êóðñû âïîëíå óñïåøíî ôîðìàëèçóåìû â ðàìêàõìèðà ìíîæåñòâ.Èíòóèòèâíî, ìíîæåñòâà ïðåäñòàâëÿþò ñîáîé ñåìåéñòâà, ñîâîêóïíîñòè, êîëëåêöèè îáúåêòîâ, êîòîðûå ìû ìûñëèì, ïðåäñòàâëÿåì ñåáå êàêåäèíûå îáúåêòû.Ïðèìåðàìè ìíîæåñòâ ìîãóò ÿâëÿòüñÿ ìíîæåñòâî âñåõ ñòóäåíòîâ âäàííîé àóäèòîðèè, ìíîæåñòâî âñåõ ïëàíåò ñîëíå÷íîé ñèñòåìû, ìíîæåñòâî âñåõ íàòóðàëüíûõ ÷èñåë0, 1, 2, . .
.è ò.ï.Îñíîâíûì îòíîøåíèåì íà ìíîæåñòâàõ ÿâëÿåòñÿ îòíîøåíèå ïðèíàä-ëåæíîñòè, òî åñòü áûòü ýëåìåíòîì, îáîçíà÷àåìîå çíà÷êîìîçíà÷àåò, ÷òîaÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà∈. Òàê a ∈ BB.Âîçìîæíî, íå ñîâñåì ïðàâèëüíî áûëî áû ïðåäñòàâëÿòü ñåáå ìíîæåñòâî, êàê íàáîð åãî ýëåìåíòîâ, ñëîæåííûõ â íåêèé ìåøîê. Êàæäîå ìíîæåñòâî ýòî íîâûé îòäåëüíûé àáñòðàêòíûé îáúåêò, ñâÿçàííûé ñî ñâîèìè ýëåìåíòàìè îòíîøåíèåì∈.Ïðèìåðû. Còóäåíò Èâàíîâ ïðèíàäëåæèò ìíîæåñòâó âñåõ ñòóäåíòîâ âäàííîé àóäèòîðèè; Èâàí Ãðîçíûé íå ïðèíàäëåæèò ìíîæåñòâó âñåõ ñòóäåíòîâ â äàííîé àóäèòîðèè; êàðàíäàø íå ïðèíàäëåæèò ìíîæåñòâó âñåõïëàíåò ñîëíå÷íîé ñèñòåìû; 2002 ïðèíàäëåæèò ìíîæåñòâó âñåõ íàòóðàëü-√íûõ ÷èñåë;2 íå ïðèíàäëåæèò ìíîæåñòâó âñåõ íàòóðàëüíûõ ÷èñåë è ò.ï.Ñâîéñòâà ìíîæåñòâ â ìàòåìàòèêå çàäàþòñÿ àêñèîìàòè÷åñêè, òî åñòüìû èõ ÿâíî ôîðìóëèðóåì è äîãîâàðèâàåìñÿ â äàëüíåéøåì íå ïîäâåðãàòüíèêàêîìó ñîìíåíèþ.
Çäåñü ìû ñôîðìóëèðóåì è îáñóäèì ëèøü íåêîòîðûåèç ýòèõ ñâîéñòâ, êîòîðûå íàì áóäóò íóæíû â äàëüíåéøåì.Ðàâåíñòâî ìíîæåñòâ. Ñ÷èòàåòñÿ, ÷òî ìíîæåñòâî ïîëíîñòüþ îïðåäåëÿåòñÿ ñâîèìè ýëåìåíòàìè. Ýòî îçíà÷àåò, ÷òî äâà ìíîæåñòâà ðàâíû â òîìè òîëüêî â òîì ñëó÷àå, êîãäà îíè ñîäåðæàò îäíè è òå æå ýëåìåíòû.Èíà÷å ãîâîðÿ,A = Bæåñòâàòîãäà è òîëüêî òîãäà, êîãäà âñÿêèé ýëåìåíò ìíî-Aÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâàâñÿêèé ýëåìåíò ìíîæåñòâàñòâàBA.1B,è íàîáîðîò,ÿâëÿåòñÿ ýëåìåíòîì ìíîæå-Ñïîñîáû çàäàíèÿ ìíîæåñòâ.Ìíîæåñòâà ìîæíî çàäàâàòü íåñêîëü-êèìè ñïîñîáàìè. Îäèí èç íèõ ÿâíîå ïåðå÷èñëåíèå âñåõ åãî ýëåìåíòîâ,çàêëþ÷åííûõ â ôèãóðíûå ñêîáêè.
Íàïðèìåð:{0}, {a, b, c}, {0, 1, 2, . . .}.Äðóãèì ñïîñîáîì çàäàíèÿ ìíîæåñòâ ÿâëÿåòñÿ çàäàíèå óñëîâèÿ, êîòîðîìó óäîâëåòâîðÿþò âñå ýëåìåíòû äàííîãî ìíîæåñòâà è íå óäîâëåòâîðÿåòíè îäèí ýëåìåíò íå èç äàííîãî ìíîæåñòâà. Íàïðèìåð, ìíîæåñòâîA âñåõ÷åòíûõ ÷èñåë ìîæíî çàäàòü êàêA = {x | x ÷åòíîå íàòóðàëüíîå ÷èñëî.}. îáùåì ñëó÷àå, êîãäà èìååòñÿ óñëîâèåΦ,êîòîðîå áûâàåò ëèáî èñòèí-íûì ëèáî ëîæíûì äëÿ äàííîãî ýëåìåíòà, ìîæåò áûòü îáðàçîâàíî ìíî-æåñòâî âñåõx,óäîâëåòâîðÿþùèõ óñëîâèþΦ1 .Ýòî ìíîæåñòâî îáû÷íîçàïèñûâàåòñÿ â âèäå{x | xîáëàäàåò ñâîéñòâîìÄëÿ îáîçíà÷åíèÿ ìíîæåñòâà âñåõâëåòâîðÿþùèõ óñëîâèþΦ,Φ}.x, ïðèíàäëåæàùèõ ìíîæåñòâó A è óäî-òàêæå óïîòðåáëÿåòñÿ çàïèñü âèäà{x ∈ A | xîáëàäàåò ñâîéñòâîìΦ}.Ïðèìåðû.{a, a} = {a},{x | xíàòóðàëüíîå ÷èñëî íå áîëåå 2}= {0, 1, 2}.Ïóñòîå ìíîæåñòâî. Ñóùåñòâóåò ìíîæåñòâî, íå ñîäåðæàùåå âîîáùå íè2îäíîãî ýëåìåíòà.
Ñóùåñòâóåò âñåãî îäíî ìíîæåñòâî ñ òàêèì ñâîéñòâîì.Îíî íàçûâàåòñÿ ïóñòûì ìíîæåñòâîì. Ó ïóñòîãî ìíîæåñòâà èìååòñÿñîáñòâåííîå îáîçíà÷åíèå:∅.{∅} =6 ∅, ïîñêîëüêó â ïåðâîì èç ýòèõ ìíîæåñòâýëåìåíò (à èìåííî ∅), à âî âòîðîì íè îäíîãî.Çàìåòèì, ÷òîæèòñÿ îäèí1ñîäåð-Çàìåòèì îäíàêî, ÷òî íåîãðàíè÷åííîå èñïîëüçîâàíèå òàêîãî ñïîñîáà îáðàçîâàíèÿìíîæåñòâ ïðèâîäèò ê ïðîòèâîðå÷èÿì è ïàðàäîêñàì. Ïðè èçó÷åíèè ìàòåðèàëà äàííîãî ó÷åáíèêà ýòà ïðîáëåìà íå âîçíèêàåò è ïîýòîìó çäåñü íå îáñóæäàåòñÿ.
Ñîîòâåòñòâóþùèå âîïðîñû îáñóæäàþòñÿ â ëèòåðàòóðå ïî ìàòåìàòè÷åñêîé ëîãèêå è òåîðèèìíîæåñòâ.2Ïîñëåäíåå ñâîéñòâî âûâîäèìî èç ïðèâåäåííîãî âûøå ñâîéñòâà ðàâåíñòâà ìíî-æåñòâ, íî äëÿ ïîíèìàíèÿ ýòîãî òðåáóåòñÿ îáñóæäåíèå íåêîòîðûõ ïðèíöèïîâ ìàòåìàòè÷åñêîé ëîãèêè, âûõîäÿùåå çà ðàìêè ýòîé êíèãè.2Ïîíÿòèå ïîäìíîæåñòâà.
ÏóñòüA è B äâà ìíîæåñòâà. Ìû ãîâîðèì,A ÿâëÿåòñÿ ïîäìíîæåñòâîì B , åñëè âñÿêèé ýëåìåíò èç A ÿâëÿåòñÿýëåìåíòîì èç B . Ýòîò ôàêò îáîçíà÷àåòñÿ òàê: A ⊆ B . Åñëè íåîáõîäèìîïîä÷åðêíóòü, ÷òî A ⊆ B è ïðè ýòîì A 6= B , òî óïîòðåáëÿåòñÿ òàêæåçàïèñü A ⊂ B . Ïóñòîå ìíîæåñòâî ∅ ÿâëÿåòñÿ ïîäìíîæåñòâîì ëþáîãî÷òîìíîæåñòâà.Ïðèìåðû.∅ ⊆ A, {0, 1} ⊆ {0, 1}, {0, 1} ⊆ {0, 1, 2, 3}.Óïðàæíåíèå. Äîêàæèòå, ÷òî ìíîæåñòâàA⊆Bòîãäà, êîãäà îäíîâðåìåííîèAB ⊆ A.èBðàâíû òîãäà è òîëüêîÍà ìíîæåñòâàõ îïðåäåëÿþòñÿ íåêîòîðûå îïåðàöèè, îïèñûâàåìûå íèæå.Îïåðàöèÿ îáúåäèíåíèÿ. Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâîîáúåäèíåíèåì ìíîæåñòâBC,èåñëèAAÿâëÿåòñÿñîäåðæèò òå è òîëüêî òå ýëå-B, C .B ∪ C , òîìåíòû, êîòîðûå ñîäåðæàòñÿ õîòÿ áû â îäíîì èç ìíîæåñòâîáúåäèíåíèÿ ìíîæåñòâBèCèñïîëüçóåòñÿ îáîçíà÷åíèåÄëÿåñòüA = B ∪ C.Ïîíÿòèå îáúåäèíåíèÿ îïðåäåëÿåòñÿ òàêæå è äëÿ ñåìåéñòâ ìíîæåñòâ.ÏóñòüA ìíîæåñòâî, êàæäûé ýëåìåíò êîòîðîãî åñòü ìíîæåñòâî.
Òî-ãäà îáúåäèíåíèåì ñåìåéñòâàAíàçûâàåòñÿ ìíîæåñòâî, ñîäåðæàùåå òå èòîëüêî òå ýëåìåíòû, êîòîðûå ñîäåðæàòñÿ õîòÿ áû â îäíîì èç ìíîæåñòâB ∈ A.Îáúåäèíåíèå ñåìåéñòâàAîáîçíà÷àåòñÿ îáû÷íî, êàêSA.Ïðèìåðû.[{A, B} = A ∪ B,[{{0}, {0, 1}, {1, 2}} = {0, 1, 2}.Îïåðàöèÿ ïåðåñå÷åíèÿ. Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâîA ÿâëÿåòñÿC , åñëè A ñîäåðæèò òå è òîëüêî òå ýëåìåíòû, êîòîðûå ñîäåðæàòñÿ â êàæäîì èç ìíîæåñòâ B , C . Äëÿ ïåðåñå÷åíèÿìíîæåñòâ B è C èñïîëüçóåòñÿ îáîçíà÷åíèå B ∩ C , òî åñòü A = B ∩ C .ïåðåñå÷åíèåì ìíîæåñòâBèÏîíÿòèå ïåðåñå÷åíèÿ àíàëîãè÷íî îïðåäåëÿåòñÿ è äëÿ ñåìåéñòâ ìíî-A ìíîæåñòâî, êàæäûé ýëåìåíò êîòîðîãî åñòü ìíîæåñòâî.A íàçûâàåòñÿ ìíîæåñòâî, ñîäåðæàùåå òåè òîëüêî òå ýëåìåíòû, êîòîðûå ñîäåðæàòñÿ â êàæäîì èç ìíîæåñòâ B ∈ A.TÏåðåñå÷åíèå ñåìåéñòâà A îáîçíà÷àåòñÿ îáû÷íîA.æåñòâ.
ÏóñòüÒîãäà ïåðåñå÷åíèåì ñåìåéñòâà3Ïðèìåðû.\{A, B} = A ∩ B,\Åñëè äëÿ ìíîæåñòâ{{0}, {0, 1}, {0, 1, 2}} = {0}.A è B âûïîëíåíî A∩B = ∅, òî A è B íàçûâàþòñÿíåïåðåñåêàþùèìèñÿ ìíîæåñòâàìè.Ðàçíîñòü ìíîæåñòâ. ÏóñòüA\BAèB äâà ìíîæåñòâà. Èõ ðàçíîñòüþA{0, 1, 2} \ {2, 3, 4} = {0, 1}.íàçûâàåòñÿ ìíîæåñòâî âñåõ ýëåìåíòîâ, êîòîðûå ïðèíàäëåæàòîäíîâðåìåííî íå ïðèíàäëåæàòB.Ïðèìåð:èÄîïîëíåíèå ìíîæåñòâà.  ñëó÷àå, êîãäà ÿâíî èëè íåÿâíî ïîäðàçóìåâàåòñÿ, ÷òî âñå ýëåìåíòû, ñ êîòîðûìè ìû èìååì äåëî â äàííûé ìîìåíò,ÿâëÿþòñÿ ýëåìåíòàìè íåêîòîðîãî îáúåìëþùåãî ìíîæåñòâàR,è âñå ðàñ-ñìàòðèâàåìûå íàìè â äàííûé ìîìåíò ìíîæåñòâà ÿâëÿþòñÿ ïîäìíîæå-R,A ìíîæåñòâà A, ïîä êîòîðûìïîäðàçóìåâàåòñÿ íà ñàìîì äåëå ðàçíîñòü R \ A, èíà÷å ãîâîðÿ, A = R \ A.ñòâàìèìîæíî ãîâîðèòü î äîïîëíåíèèÏðè óïîòðåáëåíèè ïîíÿòèÿ äîïîëíåíèÿ íóæíî âñåãäà ÷åòêî ïðåäñòàâëÿòü, îòíîñèòåëüíî êàêîãî ìíîæåñòâàRðàññìàòðèâàåòñÿ ýòî äîïîëíå-íèå.Ïîíÿòèå ðàçáèåíèÿ ìíîæåñòâà.
Ñåìåéñòâîæåñòâ, íàçûâàåòñÿ ðàçáèåíèåì ìíîæåñòâàAR,åñëèñîñòîÿùåå èç ìíî-A =SRè ëþáûåB, C ∈ R ëèáî ñîâïàäàþò ëèáî èìåþò ïóñòîå ïåðåñå÷åíèå, òîB, C ∈ R âåðíî â òî÷íîñòè îäíî èç äâóõ óñëîâèé: ëèáîB = C ëèáî B ∩ C = ∅.ýëåìåíòûåñòü äëÿ ëþáûõÏðèìåð. Ïóñòü ðàçáèåíèåR = {{0, 1}, {2}, {3, 4, 5}}èA = {0, 1, 2, 3, 4, 5}.ÒîãäàRA.Óïîðÿäî÷åííûå ïàðû. Êàê óæå îòìå÷àëîñü, â òåîðèè ìíîæåñòâ ìîæíî ïðîèíòåðïðåòèðîâàòü ïî÷òè âñþ ñîâðåìåííóþ ìàòåìàòèêó.
Íà ýòîìïóòè âàæíî óìåòü èíòåðïðåòèðîâàòü ðàçíûå ìàòåìàòè÷åñêèå êîíñòðóêöèè. Îäíà èç íèõ ýòî óïîðÿäî÷åííûå ïàðû.Äëÿ ëþáûõ ýëåìåíòîâìåíòîâaèbaèêàê ìíîæåñòâîb îïðåäåëèì óïîðÿäî÷åííóþ ïàðó èç ýëå{{a, b}, {a}}, îáîçíà÷àåìîå îáû÷íî (a, b).Ýòî îïðåäåëåíèå ñïåöèàëüíî âûáðàíî òàêèì îáðàçîì, ÷òîáû óäîâëåòâîðÿëîñü ñëåäóþùåå îñíîâíîå ñâîéñòâî óïîðÿäî÷åííûõ ïàð:4Ïðåäëîæåíèå 0.1 Èç ðàâåíñòâà óïîðÿäî÷åííûõ ïàðñëåäóåò, ÷òîa0 = a1è(a0 , b0 ) = (a1 , b1 )b0 = b1 .Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî(a0 , b0 ) = (a1 , b1 ).Ýòî îçíà÷àåò,÷òî{{a0 , b0 }, {a0 }} = {{a1 , b1 }, {a1 }}.(1)Âîçìîæíû äâà ñëó÷àÿ:Ñëó÷àé 1.a0 = b0 .Òîãäà ìíîæåñòâî â ëåâîé ÷àñòè (1) ñîäåðæèò ðîâíî{{a0 }}).
Çíà÷èò è ìíîæåñòâî â ïðàâîé ÷àñòè ñîäåðæèò ðîâíî îäèí ýëåìåíò. Îòñþäà ïîëó÷èì ðàâåíñòâî {a1 , b1 } = {a1 }.Èç ýòîãî âûâîäèì, ÷òî a1 = b1 , è (1) ïåðåïèøåòñÿ â âèäåîäèí ýëåìåíò (à èìåííî{{a0 }} = {{a1 }},Îòêóäà ïîëó÷àåìa1 = b1 ,{a0 } = {a1 }a0 = a1 .è íàêîíåöÝòî âëå÷åòb0 = a0 =÷òî è äîêàçûâàåò óòâåðæäåíèå.Ñëó÷àé 2.a0 6= b0 .Òîãäà ìíîæåñòâî â ëåâîé ÷àñòè (1) ñîäåðæèò äâàýëåìåíòà, îäèí èç êîòîðûõ äâóõýëåìåíòíîå ìíîæåñòâî, à âòîðîé îäíîýëåìåíòíîå ìíîæåñòâî. Ýòî îçíà÷àåò, ÷òî òàêèìè æå ñâîéñòâàìè îáëàäàåò è ìíîæåñòâî â ïðàâîé ÷àñòè (1). Åäèíñòâåííî âîçìîæíûì ñëó÷àåìçäåñü ÿâëÿåòñÿ îäíîâðåìåííîå âûïîëíåíèå ðàâåíñòâa0 = a1èb0 = b1 .Íà÷èíàÿ ñ ýòîãî ìîìåíòà ìîæíî çàáûòü êîíêðåòíóþ òåîðåòèêîìíîæåñòâåííóþ ñòðóêòóðó óïîðÿäî÷åííûõ ïàð(a, b)è ïîìíèòü òîëüêî îñ-íîâíûå ñâîéñòâà ýòèõ ìíîæåñòâ, âûðàæàåìûå ïðåäëîæåíèåì 0.1.Óïîðÿäî÷åííûåïî èíäóêöèènêè. Ïî àíàëîãèè ñ óïîðÿäî÷åííûìè ïàðàìè ìîæíîââåñòè è óïîðÿäî÷åííûå nêè äëÿ ëþáîãî n = 2, 3, 4, .
. .,ïîëàãàÿ(a1 , a2 , . . . , an , an+1 ) = ((a1 , a2 , . . . , an ), an+1 ).Èç ñâîéñòâ óïîðÿäî÷åííûõ ïàð ñëåäóåò ñëåäóþùåå îñíîâíîå ñâîéñòâîóïîðÿäî÷åííûõnîê:äâå óïîðÿäî÷åííûånêè (a1 , a2 , . . . , an )è(b1 , b2 , . . . , bn )ðàâíûòîãäà è òîëüêî òîãäà, êîãäà ïîïàðíî ðàâíû èõ ñîîòâåòñòâóþùèå êîîðäèíàòû:a1 = b1 , a2 = b2 ,. . .