Краткие лекции по алгебре (1078545)
Текст из файла
.1.2ÏðåäèñëîâèåÍå âûçûâàåò ñîìíåíèÿ, ÷òî çíàêîìñòâî ñ îñíîâàìè àëãåáðû, â÷àñòíîñòè òåîðèè ãðóïï, íåîáõîäèìî êàæäîìó êâàëèôèöèðîâàííîìó ñïåöèàëèñòó â îáëàñòè ïðèêëàäíîé ìàòåìàòèêè. Òåîðèÿãðóïï íàóêà î÷åíü àáñòðàêòíàÿ, è óñëåäèòü çà âñåìè òîíêîñòìèíåèñêóøåííîìó ÷åëîâåêó ñëîæíî. Íàøåé öåëüþ ÿâëÿåòñÿ ïðîäåìîíñòðèðîâàòü ïîëüçó ýòîé íàóêè, ïðèâåäÿ êîíêðåòíûå åå ïðèìåíåíèÿ ê çàäà÷àì êîìáèíàòîðèêè, èìåþùèì ïðàêòè÷åñêîå çíà÷åíèå. Îñíîâíîé ðåçóëüòàò òåîðåìà Ïîéà (G.
Polya) îòëè÷àåòñÿ êàê ìàòåìàòè÷åñêîé êðàñîòîé, òàê è ïîëåçíûìè ïðèëîæåíèÿìè.1. Ìíîæåñòâà è îòîáðàæåíèÿÏîä ìíîæåñòâîì ìû ïîíèìàåì ëþáóþ ñîâîêóïíîñòü îáúåêòîâ, íàçûâàåìûõ ýëåìåíòàìè ìíîæåñòâà. Çàïèñüx ∈ X îçíà÷àåò, ÷òî ýëåìåíò x ïðèíàäëåæèò ìíîæåñòâó X .Ìíîæåñòâà ñ êîíå÷íûì ÷èñëîì ðàçëè÷íûõ ýëåìåíòîâ ìîãóò áûòüîïèñàíû ïóòåì ïåðå÷èñëåíèÿ èõ ýëåìåíòîâ. Íàïðèìåð, J5 ={1, 2, 3, 4, 5} ìíîæåñòâî ïåðâûõ ïÿòè íàòóðàëüíûõ ÷èñåë.
Ìûáóäåì òàêæå èñïîëüçîâàòü çàïèñüÌíîæåñòâà.M = {x|P (x)}.Ýòî îçíà÷àåò, ÷òî ìíîæåñòâî M ñîñòîèò èç âñåõ ýëåìåíòîâ x,îáëàäàþùèõ ñâîéñòâîì P .Ìû èñïîëüçóåì ñòàíäàðòíîå îáîçíà÷åíèå Z äëÿ ìíîæåñòâàâñåõ öåëûõ ÷èñåë.Íàïîìíèì, ÷òî X åñòü ïîäìíîæåñòâî ìíîæåñòâà Y , X ⊆ Y ,åñëè ëþáîé ýëåìåíò X ïðèíàäëåæèò Y . Ïóñòîå ìíîæåñòâî ∅ñ÷èòàåòñÿ ïîäìíîæåñòâîì ëþáîãî ìíîæåñòâà. Ìíîæåñòâà X èY íàçûâàþòñÿ ðàâíûìè, åñëè X ⊆ Y è Y ⊆ X .
Ïåðåñå÷åíèåìäâóõ ìíîæåñòâ X è Y íàçûâàåòñÿ ìíîæåñòâîX ∩ Y = {x|x ∈ X è x ∈ Y },à èõ îáúåäèíåíèåì ìíîæåñòâîX ∪ Y = {x|x ∈ X èëè x ∈ Y }.Àíàëîãè÷íî îïðåäåëÿþòñÿ ïåðåñå÷åíèå è îáúåäèíåíèå ïðîèçâîëüíûõ ñîâîêóïíîñòåé ìíîæåñòâ.3Ñêàæåì, ÷òî ñèñòåìà Yα(α ∈ A) ïîäìíîæåñòâ ìíîæåñòâà Xîáðàçóåò åãî ðàçáèåíèå, åñëè∪X=Yα , Yα ∩ Yβ ïðè (α ̸= β).α∈AÏóñòü X è Y ìíîæåñòâà. ÌíîæåñòâîX × Y = {(x, y) | x ∈ X, y ∈ Y }óïîðÿäî÷åííûõ ïàð ýëåìåíòîâ èç X è Y íàçûâàåòñÿ ïðÿìûì(èëè äåêàðòîâûì) ïðîèçâåäåíèåì ýòèõ ìíîæåñòâ.Îòîáðàæåíèåì f : X → Y ìíîæåñòâà Xâ ìíîæåñòâî Y íàçûâàåòñÿ ïðàâèëî, ñîïîñòàâëÿþùåå êàæäîìóýëåìåíòó x ∈ X ýëåìåíò f (x) ∈ Y .
ÌíîæåñòâîÎòîáðàæåíèÿ.f (X) = {f (x)|x ∈ X} ⊆ Yíàçûâàåòñÿ îáðàçîì îòîáðàæåíèÿ f . Îòîáðàæåíèå f : X → Yíàçûâàåòñÿ ñþðúåêòèâíûì, åñëè f (X) = Y . Îíî íàçûâàåòñÿèíúåêòèâíûì, åñëè èç x ̸= x′ ñëåäóåò f (x) ̸= f (x′). Íàêîíåö,f : X → Y áèåêòèâíî, êîãäà îíî îäíîâðåìåííî ñþðúåêòèâíî èèíúåêòèâíî.ÏÐÈÌÅÐ 1.1. Ïóñòü X = {1, 2, 3}, Y = {1, 2, 3, 4}. Îòîáðàæåíèå f , çàäàííîå ôîðìóëîé f (i) = i + 1, i = 1, 2, 3 èíúåêòèâíî,íî íå ñþðúåêòèâíî.
Îòîáðàæåíèå g : Y → X , äëÿ êîòîðîãîf (i) = i, i = 1, 2, 3 è f (4) = 3, ñþðúåêòèâíî, íî íå èíúåêòèâíî.Îòîáðàæåíèå h : X → X , ãäå h(1) = 2, h(2) = 3, h(3) = 1,áèåêòèâíî. .Îòîáðàæåíèÿ f : X → X íàçûâàþòñÿ ïðåîáðàçîâàíèÿìè ìíîæåñòâà X . Ïðåîáðàçîâàíèå, çàäàííîå ôîðìóëîé idX (x) = x äëÿâñåõ x ∈ X , íàçûâàåòñÿ òîæäåñòâåííûì.Ïðîèçâåäåíèåì (èëè êîìïîçèöèåé) îòîáðàæåíèé f : X → Yè g : Y → Z íàçûâàåòñÿ îòîáðàæåíèå g ◦ f : X → Z , çàäàííîåôîðìóëîé(g ◦ f )(x) = g(f (x)),ßñíî, ÷òî äëÿ ëþáîãî f : X → Y èìååìf ◦ idX = f,ÒÅÎÐÅÌÀ 1.1. Ïóñòü fîòîáðàæåíèÿ. Òîãäàx ∈ X.idY ◦ f = f.: X → Y, g : Y → Z, h : Z → Vh ◦ (g ◦ f ) = (h ◦ g) ◦ f.4ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Èìååì(h ◦ (g ◦ f ))(x) = h((g ◦ f )(x)) = h(g(f (x)) == (h ◦ g)(f (x) = ((h ◦ g) ◦ f )(x).
Ïóñòü f : X → Y è g : Y → X îòîáðàæåíèÿ. Îïðåäåëåíûèõ êîìïîçèöèè f ◦ g è g ◦ f . Åñëèf ◦ g = idY ,g ◦ f = idX ,(1.1)òî îòîáðàæåíèÿ f è g íàçûâàþòñÿ âçàèìíî îáðàòíûìè.Íå êàæäîå îòîáðàæåíèå èìåò îáðàòíîå. Íî åñëè îòáðàòíîåîòîáðàæåíèå ñóùåñòâóåò, òî îíî åäèíñòâåííî.  ñàìîì äåëå,ïóñòü h åùå îäíî îòîáðàæåíèå, îáðàòíîå ê f . Òîãäàf ◦ h = idY ,h ◦ f = idX .(1.2)Èç ðàâåíñòâ (1.1) è (1.2) ñ ïîìîùüþ òåîðåìû 1 ïîëó÷àåìh = idX ◦ h = (g ◦ f ) ◦ h = g ◦ (f ◦ h) = g ◦ idY = g.Îòîáðàæåíèå, îáðàòíîå ê f , îáîçíà÷àåòñÿ ÷åðåç f −1.ÒÅÎÐÅÌÀ 1.2. Îòîáðàæåíèå f : X → Y òîãäà è òîëüêîòîãäà èìååò îáðàòíîå, êîãäà îíî áèåêòèâíî.ÄÎÊÀÇÀÒÅËÜÑÒÂÎ.
Äëÿ ëþáîãî y ∈ Y îïðåäåëåí ýëåìåíò−1f (y) = x ∈ X . Çíà÷èò, f (x) = y , ò. å. f ñþðúåêòèâíî. Åñëèf (x) = f (x′ ), òî x = f −1 (f (x)) = f −1 (f (x′ )) = x′ è f èíúåêòèâíî.Îáðàòíî, ïóñòü f áèåêòèâíî.  ñèëó ñþðúåêòèâíîñòè f äëÿëþáîãî y ∈ Y íàéäåòñÿ òàêîé x ∈ X , ÷òî f (x) = y; â ñèëóèíúåêòèâíîñòè òàêîé ýëåìåíò ðîâíî îäèí. Ïîëîæèì g(y) = x.Ìû ïîëó÷èëè îòîáðàæåíèå g : Y → X . Òàê êàê f (g(y)) = f (x) =y , òî f ◦ g = idY . Òàê êàê g(f (x)) = g(y) = x, èìååì g ◦ f = idX .Çíà÷èò, îòîáðàæåíèÿ f è g âçàèìíî îáðàòíû. ÑËÅÄÑÒÂÈÅ.
Èç áèåêòèâíîñòè îòîáðàæåíèÿ f : X → Yâûòåêàåò áèåêòèâíîñòü f −1, ïðè÷åì(f −1 )−1 = f.Ïóñòü, äàëåå, f : X → Y, h : Y → Z áèåêòèâíûå îòîáðàæåíèÿ.Òîãäà áèåêòèâíà è èõ êîìïîçèöèÿ h ◦ f , ïðè÷åì(h ◦ f )−1 = f −1 ◦ h−1 .5(1.3)ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Ïî òåîðåìå 1.2 áèåêòèâíîñòü f âëå÷åòñóùåñòâîâàíèå f −1. Ïî òîé æå òåîðåìå ïðåîáðàçîâàíèå f −1 èìååòîáðàòíîå. Ðàâåíñòâà (1.1) ïîêàçûâàþò, ÷òî (f −1)−1 = f . Èçðàâåíñòâ(h ◦ f ) ◦ (f −1 ◦ h−1 ) = ((h ◦ f ) ◦ f −1 ) ◦ h−1 == h ◦ (f ◦ f −1 ) ◦ h−1 = h ◦ h−1 = idZ ,(f −1 ◦ h−1 ) ◦ (h ◦ f ) = f −1 ◦ (h−1 ◦ h) ◦ f −1 == f −1 ◦ idY ◦ f = f −1 ◦ f = idX .âûòåêàåò, ÷òî f −1 ◦ h−1 ïðåîáðàçîâàíèå, îáðàòíîå ê h ◦ f .
Ìíîæåñòâî íàçûâàåòñÿ êîíå÷íûì,åñëè ñóùåñòâóåò åãî áèåêòèâíîå îòîáðàæåíèå íà îäíî èç ìíîæåñòâJn = {1, 2, ..., n}. ×èñëî ýëåìåíòîâ êîíå÷íîãî ìíîæåñòâà Máóäåò îáîçíà÷àòüñÿ ÷åðåç |M |.Ïóñòü M è N êîíå÷íûå ìíîæåñòâà, |M | = m, |N | = n.Òîãäà ÿñíî, ÷òîÊîíå÷íûå ìíîæåñòâà.|M × N | = mn,|M ∪ N | = m + n − |M ∩ N |.Ïóñòü R è M êîíå÷íûå ìíîæåñòâà.
Ðàññìîòðèì ìíîæåñòâîâñåõ îòîáðàæåíèé f : M → R.ÒÅÎÐÅÌÀ 1.3. Èìååò ìåñòî ôîðìóëàRM MR = |R||M | .ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Ìîæíî ñ÷èòàòü, ÷òî M = Jm, R = Jq .Îòîáðàæåíèå f : R → M ñòàâèò â ñîîòâåòñòâèå ýëåìåíòó i ∈ Mýëåìåíò f (i) ∈ R. Òàêèì îáðàçîì, ìíîæåñòâî RM íàõîäèòñÿ âáèåêòèâíîì ñîîòâåòñòâèè ñ ìíîæåñòâîì öåëî÷èñëåííûõ âåêòîðîâ(y1 , y2 , ..., ym ), ãäå yi = f (i) è yi ïðèíèìàåò îäíî èç çíà÷åíèé1, 2, ..., q . Òàêèõ âåêòîðîâ, êàê ëåãêî âèäåòü, q m . Ðàññìîòðèì ìíîæåñòâî Sn âñåõ áèåêòèâíûõïðåîáðàçîâàíèé ìíîæåñòâà Jn (n = 1, 2, ...).
Åãî ýëåìåíòû σ ∈Sn íàçûâàþòñÿ ïîäñòàíîâêàìè (íà n ýëåìåíòàõ). Èõ óäîáíîçàïèñûâàòü â âèäåÏîäñòàíîâêè.(σ=)12...n.σ(1) σ(2) ... σ(n)(1.4)Òàê êàê ïîäñòàíîâêè ÿâëÿþòñÿ ïðåîáðàçîâàíèÿìè îäíîãî ìíîæåñòâà, èõ ìîæíî ïåðåìíîæàòü. Äëÿ σ, τ ∈ Sn èõ êîìïîçèöèÿ6òàêæå ÿâëÿåòñÿ ïîäñòàíîâêîé. Ýòî âûòåêàåò èç ñëåäñòâèÿê òåîðåìå 1.2. Ðåçóëüòàòîì ïðèìåíåíèÿ ýòîé ïîäñòàíîâêè ê ýëåìåíòó i ñëóæèò (σ ◦ τ )(i) = σ(τ (i)).ÏÐÈÌÅÐ 1.2. Ïóñòüσ◦τ(σ=)1 2 3,3 1 2()1 2 3τ=3 2 1Òîãäàσ(τ (1)) = σ(3) = 2, σ(τ (2)) = σ(2) = 1, σ(τ (3)) = σ(1) = 3.Àíàëîãè÷íî,τ (σ(1)) = τ (3) = 1, τ (σ(2)) = τ (1) = 3, τ (σ(3)) = τ (2) = 2.Çíà÷èò,()1 2 3σ◦τ =,2 1 3()1 2 3τ ◦σ =1 3 2 ÷àñòíîñòè, ìû âèäèì, ÷òî σ ◦ τ ̸= τ ◦ σ. Äàëåå ìû âìåñòî σ ◦ τ áóäåì ïèñàòü ïðîñòî στ .Ïóñòü σ(i1) = i2, σ(i2) = i3, ..., σ(il−1) = il , σ(il ) = i1,è σ(j) = j , åñëè j ̸= i1, ..., il .
Òàêàÿ ïîäñòàíîâêà íàçûâàåòñÿöèêëîì (äëèíû l) è îáîçíà÷àåòñÿ (i1 i2 ... il ).ÏÐÈÌÅÐ 1.3. Äëÿ äàííîé ïîäñòàíîâêè σ ∈ S9 èìååì()1 2 3 4 5 6 7 8 9σ== (193)(26)(48)(5)(7).9 6 1 8 5 2 7 4 3Ýòà ïîäñòàíîâêà ðàçëîæåíà â ïðîèçâåäåíèå íåçàâèñèìûõ (ò. å.íå ñîäåðæàùèõ îäèíàêîâûõ ýëåìåíòîâ) öèêëîâ. Öèêëû äëèíû 1îáû÷íî îïóñêàþò, ò. å. ïèøóò σ = (193)(26)(48). ßñíî, ÷òî æå ñàìîå ìîæíî ñäåëàòü ñ ëþáîé ïîäñòàíîâêîé èìû ïðèõîäèì ê ñëåäóþùåìó ðåçóëüòàòó.ÒÅÎÐÅÌÀ 1.4. Êàæäàÿ ïîäñòàíîâêà σ ̸= e â Sn ÿâëÿåòñÿïðîèçâåäåíèåì íåçàâèñèìûõ öèêëîâ äëèíû ≥ 2.
Ýòî ðàçëîæåíèåâ ïðîèçâåäåíèå îïðåäåëåíî îäíîçíà÷íî ñ òî÷íîñòüþ äî ïîðÿäêàñëåäîâàíèÿ öèêëîâ. Öèêë äëèíû 2 íàçûâàåòñÿ òðàíñïîçèöèåé. Ëþáàÿ òðàíñïîçèöèÿ èìååò, òàêèì îáðàçîì, âèä τ = (ij).ÑËÅÄÑÒÂÈÅ 1. Êàæäàÿ ïîäñòàíîâêà σ ∈ Sn ÿâëÿåòñÿïðîèçâåäåíèåì òðàíñïîçèöèé.7ÄÎÊÀÇÀÒÅËÜÑÒÂÎ.  ñèëó òåîðåìû 1.4 ïîäñòàíîâêà σ ̸= eðàçëàãàåòñÿ â ïðîèçâåäåíèå öèêëîâ.
Ïîýòîìó äîñòàòî÷íî ðàçëîæèòü öèêë â ïðîèçâåäåíèå òðàíñïîçèöèé. Ýòî äåëàåòñÿ òàê:(1 2 ... l − 1 l) = (1 l)(1 l − 1) ... (13)(12).Íàêîíåö, e = (12)(12). ÑËÅÄÑÒÂÈÅ 2. Êàæäàÿ ïîäñòàíîâêà ðàçëàãàåòñÿ â ïðîèçâåäåíèå òðàíñïîçèöèé âèäà (i, i + 1).ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Èìååì(13) = (23)(12)(23), (14) = (34)(13)(34) è ò. ä. Ðàññìîòðèì ïîäñòàíîâêó (1.4). Ïóñòü i < j . Ñêàæåì, ÷òîýëåìåíòû σ(i) è σ(j) îáðàçóþò èíâåðñèþ, åñëè σ(i) > σ(j). ×èñëîèíâåðñèé â ïîäñòàíîâêå σ îáîçíà÷èì ÷åðåç l(σ) è ïîëîæèì ε(σ) =(−1)l(σ) .
Åñëè ε(σ) = +1, ïîäñòàíîâêà íàçûâàåòñÿ ÷åòíîé, åñëèε(σ) = −1 íå÷åòíîé.ÏÐÈÌÅÐ 1.4.  ìíîæåñòâå S3 ïîäñòàíîâêè e, (123), (132) ÷åòíûå, ïîäñòàíîâêè (12), (13), (23) íå÷åòíûå. ÒÅÎÐÅÌÀ 1.5. ×åòíîñòü ïîäñòàíîâêè ìåíÿåòñÿ ïðè óìíîæåíèè íà òðàíñïîçèöèþ:ε(στ ) = −ε(σ),ãäå σ, τ ∈ Sn, τ òðàíñïîçèöèÿ.ÄÎÊÀÇÀÒÅËÜÑÒÂÎ.
Ïóñòü σ èìååò âèä (1.4), à τ = (i, i+1).Òîãäà()στ =1...ii + 1 ...n.σ(1) ... σ(i + 1) σ(i) ... σ(n)Êàê ëåãêî ïîíÿòü, ÷èñëî èíâåðñèé â ïîäñòàíîâêàõ σ è στ îòëè÷àåòñÿ íà åäèíèöó. Çíà÷èò, ýòè ïîäñòàíîâêè èìåþò ðàçíóþ ÷åòíîñòü. Äîêàçàòåëüñòâî ñëåäñòâèÿ 2 èç òåîðåìû 1.4 ïîêàçûâàåò,÷òî ëþáàÿ òðàíñïîçèöèÿ ðàçëàãàåòñÿ â ïðîèçâåäåíèå íå÷åòíîãî÷èñëà òðàíñïîçèöèé âèäà (i, i + 1). Çíà÷èò, ïðè óìíîæåíèè íàïðîèçâîëüíóþ òðàíñïîçèöèþ çíàê ïîäñòàíîâêè ìåíÿåòñÿ íå÷åòíîå ÷èñëî ðàç, ò. å. ìåíÿåòñÿ. ÑËÅÄÑÒÂÈÅ.
Äëÿ ëþáûõ σ, τ ∈ Sn èìååìε(στ ) = ε(σ) · ε(τ ),8ε(σ −1 ) = ε(σ).ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Ïðåäñòàâèì ïîäñòàíîâêè σ è τ â âèäåïðîèçâåäåíèÿ òðàíñïîçèöèé: σ = σ1 ... σk , τ = τ1 ... τm. Òîãäàστ = σ1 ... σk τ1 ... τm ,σ −1 = σk ... σ1 .Íà îñíîâàíèè òåîðåìû 1.5 èìååì ε(σ) = (−1)k , ε(τ ) = (−1)m,ε(στ ) = (−1)k+m , ε(σ −1 ) = (−1)k , îòêóäà è ïîëó÷àåòñÿ òðåáóåìîåóòâåðæäåíèå. Áèíàðíûì îòíîøåíèåì íàìíîæåñòâå X íàçûâàåòñÿ ïîäìíîæåñòâî B ⊆ X × X . Òî, ÷òî(x, y) ∈ B , îáîçíà÷àåòñÿ ÷åðåç xBy .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
