algebra (лекции Щетинина)

ËÅÊÖÈÈ ÏÎ ÊÓÐÑÓ"ÀËÃÅÁÐÀ"Ïðåäìåòîì àëãåáðû áûëî ñíà÷àëà ðåøåíèå óðàâíåíèé. Êâàäðàòíûå óðàâíåíèÿ óìåëè ðåøàòü åùå â Äðåâíåé Ãðåöèè, íî ñïîñîá ðåøåíèÿ óðàâíåíèé òðåòüåé è ÷åòâåðòîé ñòåïåíåé ñòàë èçâåñòåí òîëüêî â XVI âåêå. Ñàì òåðìèí "àëãåáðà" ïîÿâèëñÿ âòðàêòàòå àëü-Õîðåçìè (IX âåê).

Ïîä îïåðàöèåé "àëü-äæåáð" ïîíèìàëàñü îïåðàöèÿ ïåðåíåñåíèÿ ÷ëåíà óðàâíåíèÿ â äðóãóþ ñ îáðàòíûì çíàêîì. Ýòîò òåðìèí è ïðåâðàòèëñÿ âïîñëåäñòâèè â íàçâàíèå íàóêè.Áåçóñïåøíûå ïîïûòêè ðåøåíèÿ â îáùåì âèäå óðàâíåíèé áîëåå âûñîêèõ ñòåïåíåé ïðèâåëè ê ïîíèìàíèþ òîãî, ÷òî ñëåäóåò èçó÷àòü íå ñàìè óðàâíåíèÿ, à ñâÿçàííûå ñ íèìè àáñòðàêòíûå àëãåáðàè÷åñêèå ñòðóêòóðû ãðóïïû. Ýòè àëãåáðàè÷åñêèåñòðóêòóðû íàøëè âïîñëåäñòâèè ñâîå ïðèëîæåíèå â ðàçëè÷íûõðàçäåëàõ ìàòåìàòèêè è ôèçèêè. Î íåêîòîðûõ êîíêðåòíûõ ïðèëîæåíèÿõ, â ÷àñòíîñòè, ê êîìáèíàòîðèêå, ðå÷ü áóäåò èäòè íèæå. Äàëüíåéøåå ðàçâèòèå àëãåáðû øëî ïî ïóòè èçó÷åíèÿ ýòèõè äðóãèõ ñòðóêòóð, òàêèõ, êàê êîëüöà, ïîëÿ è ò.

ä. Îíè òàêæåíàõîäÿò ñâîå ïðèìåíåíèå íà ïðàêòèêå, íàïðèìåð, â âåñüìà àêòóàëüíîé òåîðèè êîäèðîâàíèÿ, ñâÿçàííîé ñ ïðîáëåìàìè çàùèòûèíôîðìàöèè â êîìïüþòåðíûõ ñèñòåìàõ. Íåçàâèñèìî îò ðåøåíèÿ ïðàêòè÷åñêèõ çàäà÷ ðàçâèâàþòñÿ è óæå âåñüìà îòâëå÷åííûåðàçäåëû ñîâðåìåííîé àëãåáðû. Îäíó èç òàêèõ òåîðèé åå àâòîðíàçûâàåò "àáñòðàêòíàÿ ÷åïóõà", ïðè÷åì ýòîò òåðìèí â ëèòåðàòóðå èñïîëüçóåòñÿ âïîëíå ñåðüåçíî. Ìû ýòèìè âîïðîñàìè, ðàçóìååòñÿ, â äàííîì êóðñå çàíèìàòüñÿ íå áóäåì.1ÃËÀÂÀ I. ÃÐÓÏÏÛ0.

Ïðåäâàðèòåëüíûå ñâåäåíèÿ ýòîì ðàçäåëå ìû ïðèâåäåì íåêîòîðûå âñïîìîãàòåëüíûå ñâåäåíèÿ, ïîëåçíûå â äàëüíåéøåì.0.1. Ìíîæåñòâà è îòîáðàæåíèÿÌû ñ÷èòàåì èçâåñòíûìè ïîíÿòèÿ ìíîæåñòâà, ïîäìíîæåñòâà,äåéñòâèé íàä ïîäìíîæåñòâàìè äàííîãî ìíîæåñòâà è ò. ä. ×èñëî ýëåìåíòîâ êîíå÷íîãî ìíîæåñòâà X áóäåì îáîçíà÷àòü ÷åðåç|X|. Ñ÷èòàåòñÿ òàêæå èçâåñòíûì ïîíÿòèå îòîáðàæåíèÿ ìíîæåñòâ è ýëåìåíòàðíûå ñâîéñòâà îòîáðàæåíèé. Íàïîìíèì âñåæå òåðìèíîëîãèþ. Ïóñòü X è Y ìíîæåñòâà. Îòîáðàæåíèåf : X → Y íàçûâàåòñÿ îòîáðàæåíèåì "íà", èëè ñþðúåêòâíûì,åñëè äëÿ ëþáîãî ýëåìåíòà y ∈ Y íàéäåòñÿ òàêîé ýëåìåíò x ∈ X ,÷òî f (x) = y . Îòîáðàæåíèå íàçûâàåòñÿ èíúåêòèâíûì, åñëè èçóñëîâèÿ f (x) = f (x0 ) ñëåäóåò, ÷òî x = x0 .

Îòîáðàæåíèå, êîòîðîåîäíîâðåìåííî ñþðúåêòèâíî è èíúåêòèâíî, íàçûâàåòñÿ áèåêòèâíûì. Îòîáðàæåíèå f : X → X , çàäàííîå ôîðìóëîé f (x) = x,íàçûâàåòñÿ òîæäåñòâåííûì è áóäåò îáîçíà÷àòüñÿ ÷åðåç idX .Âîîáùå, îòîáðàæåíèÿ ìíîæåñòâà â ñåáÿ íàçûâàþòñÿ ïðåîáðàçîâàíèÿìè ýòîãî ìíîæåñòâà.Ïóñòü g : Y → Z åùå îäíî îòîáðàæåíèå. Êîìïîçèöèåéîòîáðàæåíèé f è g íàçûâàåòñÿ îòîáðàæåíèå g ◦ f , çàäàííîå ôîðìóëîé (g ◦ f )(x) = g(f (x)) (x ∈ X).

Êîìïîçèöèÿ îòîáðàæåíèéîáëàäàåò ñâîéñòâîì àññîöèàòèâíîñòè: (h ◦ g) ◦ f = h ◦ (g ◦ f ).Îòîáðàæåíèå g : Y → X íàçûâàåòñÿ îáðàòíûì ê îòîáðàæåíèþ f , åñëè f ◦ g = idY , g ◦ f = idX . Êàê õîðîøî èçâåñòíî,îòîáðàæåíèå îáëàäàåò îáðàòíûì òîãäà è òîëüêî òîãäà, êîãäà îíîáèåêòèâíî.0.2. Ïåðåñòàíîâêè è ïîäñòàíîâêèÏîíÿòèå ïåðåñòàíîâêè è ïîäñòàíîâêè ñ÷èòàåòñÿ èçâåñòíûì.Èçâåñòíûì òàêæå ñ÷èòàåòñÿ ïîíÿòèå ÷åòíîñòè ïîäñòàíîâêè èòåîðåìà î òîì, ÷òî ëþáàÿ ïîäñòàíîâêà ðàçëàãàåòñÿ â ïðîèçâåäåíèå òðàíñïîçèöèé.2 ìíîæåñòâå ïîäñòàíîâîê ìíîæåñòâà {1, 2, ..., n} îïðåäåëåíàîïåðàöèÿ óìíîæåíèÿ, êàê êîìïîçèöèÿ ïðåîáðàçîâàíèé. Íàïðèìåð,µ ¶µ ¶ µ ¶123 123123στ ==.231 132213 ñàìîì äåëå, (στ )(1) = σ(τ (1)) = σ(1) = 2 è ò.

ä.ÇÀÄÀ×À 0.1. Âû÷èñëèòå ïîäñòàíîâêó τ σ .Öèêëîì äëèíû k íàçûâàåòñÿ òàêàÿ ïîäñòàíîâêà, çàïèñûâàåìàÿ â âèäå σ = (i1 , i2 , ..., ik ), ÷òî σ(i1 ) = i2 , σ(i2 ) = i3 , ...,σ(ik ) = i1 .  ÷àñòíîñòè, òðàíñïîçèöèÿ öèêë äëèíû 2. Äâàöèêëà íàçûâàþòñÿ íåçàâèñèìûìè, åñëè îíè íå ñîäåðæàò îäèíàêîâûõ ýëåìåíòîâ.Êàê ëåãêî ïîíÿòü, ëþáóþ ïîäñòàíîâêó ìîæíî ðàçëîæèòü âïðîèçâåäåíèå íåçàâèñèìûõ öèêëîâ. Íàïðèìåð,¶µ1 2 3 4 5 6 7 8 9 10= (1257)(689)(3)(4)(10) = (1257)(689).2 5 3 4 7 8 1 9 6 100.3. Áèíàðíûå îòíîøåíèÿÁèíàðíûì îòíîøåíèåì íà ìíîæåñòâå X íàçûâàåòñÿ ïðîèçâîëüíîå ïîäìíîæåñòâî R ⊆ X × X . Òîò ôàêò, ÷òî ýëåìåíòû x èy íàõîäÿòñÿ â îòíîøåíèè R, ò.

å. (x, y) ∈ R, áóäåì çàïèñûâàòü ââèäå xRy .Ñðåäè âñåâîçìîæíûõ áèíàðíûõ îòíîøåíèé âûäåëÿþòñÿ íåêîòîðûå, îáëàäàþùèå ñïåöèàëüíûìè ñâîéñòâàìè.Áèíàðíîå îòíîøåíèå íàçûâàåòñÿ ðåôëåêñèâíûì, åñëè xRx äëÿâñåõ x.Áèíàðíîå îòíîøåíèå íàçûâàåòñÿ ñèììåòðè÷íûì, åñëè xRy ⇐⇒yRx.Áèíàðíîå îòíîøåíèå íàçûâàåòñÿ àíòèñèììåòðè÷íûì, åñëèèç xRy è yRx ñëåäóåò x = y .Áèíàðíîå îòíîøåíèå íàçûâàåòñÿ òðàíçèòèâíûì, åñëè èç xRyè yRz ñëåäóåò xRz .Ðåôëåêñèâíîå, ñèììåòðè÷íîå è òðàíçèòèâíîå áèíàðíîå îòíîøåíèå íàçûâàåòñÿ ýêâèâàëåíòíîñòüþ è îáîçíà÷àåòñÿ x ∼ y .Ïðèìåðàìè îòíîøåíèé ýêâèâàëåíòíîñòè ñëóæàò: îòíîøåíèå ðàâåíñòâà ÷èñåë; îòíîøåíèå ïîäîáèÿ òðåóãîëüíèêîâ; îòíîøåíèåïàðàëëåëüíîñòè ïðÿìûõ è ò.

ä.3ÏÐÈÌÅÐ 0.1. Íàçîâåì äâà ÷èñëà m, k ∈ Z ñðàâíèìûìè ïîìîäóëþ íàòóðàëüíîãî ÷èñëà n è çàïèøåìm ≡ k(mod n),åñëè èõ ðàçíîñòü m−k äåëèòñÿ íà n. Ïðîâåðüòå ñàìîñòîÿòåëüíî,÷òî ýòî îòíîøåíèå åñòü îòíîøåíèå ýêâèâàëåíòíîñòè. ¤Ïóñòü â ìíîæåñòâå X ââåäåíî îòíîøåíèå ýêâèâàëåíòíîñòè.Ïîäìíîæåñòâî[x] = {y ∈ X | y ∼ x}ñîñòîÿùåå èç ýëåìåíòîâ, ýêâèâàëåíòíûõ äàííîìó, íàçûâàåòñÿêëàññîì ýêâèâàëåíòíîñòè, ñîäåðæàùèì x. Ëþáîé ýëåìåíò y ∈[x] íàçûâàåòñÿ ïðåäñòàâèòåëåì ýòîãî êëàññà.ÒÅÎÐÅÌÀ 0.1. Ìíîæåñòâî êëàññîâ ýêâèâàëåíòíîñòè ïîîòíîøåíèþ ýêâèâàëåíòíîñòè íà ìíîæåñòâå X åñòü ðàçáèåíèå ýòîãî ìíîæåñòâà.

Îáðàòíî, åñëè çàäàíî ðàçáèåíèå ìíîæåñòâà X íà ïîïàðíî íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà, òîýòè ïîäìíîæåñòâà áóäóò êëàññàìè ýêâèâàëåíòíîñòè ïî íåêîòîðîìó îòíîøåíèþ ýêâèâàëåíòíîñòè íà X .ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Òàê êàê x ∈ [x], òî X åñòü îáúåäèíåíèå êëàññîâ ýêâèâàëåíòíîñòè. Ïîêàæåì, ÷òî äâà êëàññà ëèáî íåïåðåñåêàþòñÿ, ëèáî ñîâïàäàþò. Â ñàìîì äåëå, ïóñòü z ∈ [x] ∩ [y].Òîãäà x ∼ z, z ∼ y . Ââèäó òðàíçèòèâíîñòè èìååì x ∼ y . Ïóñòüòåïåðü t ïðîèçâîëüíûé ýëåìåíò èç [x].

Òîãäà t ∼ x, à òàêêàê x ∼ y , òî t ∼ y . Çíà÷èò, t ∼ y , ò. å. t ∈ [y] è [x] ⊆ [y].Àíàëîãè÷íî, [y] ⊆ [x] è [x] = [y].Îáðàòíî, ïóñòü ïîäìíîæåñòâà Cα (α ∈ A) îáðàçóþò ðàçáèåíèåìíîæåñòâà X . Ïîëîæèì x ∼ y òîãäà è òîëüêî òîãäà, êîãäà x èy ëåæàò â îäíîì êëàññå Cα . Ïîëó÷åííîå îòíîøåíèå, êàê ëåãêîâèäåòü, ðåôëåêñèâíî, òðàíçèòèâíî è ñèììåòðè÷íî, ò. å. ÿâëÿåòñÿ îòíîøåíèåì ýêâèàâàëåíòíîñòè.

ßñíî, ÷òî ïîäìíîæåñòâà Cαñîâïàäàþò ñ êëàññàìè ýêâèâàëåíòíîñòè ïî ýòîìó îòíîøåíèþ ýêâèâàëåíòíîñòè. ¤ÏÐÈÌÅÐ 0.2. Ðàññìîòðèì îòíîøåíèå ñðàâíèìîñòè ïî ìîäóëþ n èç ïðèìåðà 0.1. Êëàññàìè ýêâèâàëåíòíîñòè ïî ýòîìó îòíîøåíèþ ñëóæàò êëàññû [0], [1], [2], ..., [n − 1]. Ïðè ýòîì êëàññ [k]ñîñòîèò â òî÷íîñòè èç ÷èñåë, äàþùèõ ïðè äåëåíèè íà n îñòàòîêk. ¤Ðåôëåêñèâíîå, àíòèñèììåòðè÷íîå è òðàíçèòèâíîå áèíàðíîåîòíîøåíèå íàçûâàåòñÿ îòíîøåíèåì ïîðÿäêà. Ïðèìåðàìè îòíî4øåíèé ïîðÿäêà ñëóæàò îáû÷íîå îòíîøåíèå ïîðÿäêà íà ìíîæåñòâå öåëûõ ÷èñåë, îòíîøåíèå âêëþ÷åíèÿ ìåæäó ïîäìíîæåñòâàìè äàííîãî ìíîæåñòâà.Äëÿ îòíîøåíèÿ ïîðÿäêà èñïîëüçóåòñÿ îáû÷íî çíàê ≤. Åñëèx ≤ y , òî ãîâîðÿò, ÷òî x íå ïðåâîñõîäèò y .

Èñïîëüçóåòñÿ òàêæåçíàê <: ïèøóò x < y , åñëè x ≤ y è x 6= y . Ìíîæåñòâî ñ îòíîøåíèåì ïîðÿäêà íàçûâàåòñÿ ÷àñòè÷íî óïîðÿäî÷åííûì. Òåðìèí"÷àñòè÷íî" óïîòðåáëÿåòñÿ ïîòîìó, ÷òî íå äëÿ ëþáûõ äâóõ ýëåìåíòîâ âåðíî x ≤ y èëè y ≤ x. Åñëè ýòî âåðíî, òî ìíîæåñòâîíàçûâàåòñÿ ëèíåéíî óïîðÿäî÷åííûì, à ïîðÿäîê ëèíåéíûì.×àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî óäîáíî áûâàåò èíîãäàèçîáðàæàòü â âèäå òàê íàçûâàåìîé äèàãðàììû Õàññå. Ïðè ýòîìýëåìåíòû èçîáðàæàþòñÿ òî÷êàìè. Òî÷êè, îòâå÷àþùèå ýëåìåíòàì x y , ñîåäèíÿþòñÿ ñòðåëêîé, âåäóùåé îò x ê y , åñëè x < y èíå ñóùåñòâóåò òàêîãî ýëåìåíòà z , òî x < z < y .ÏÐÈÌÅÐ 0.3.

Äèàãðàììà Õàññå ìíîæåñòâà N îáû÷íûì îòíîøåíèåì ïîðÿäêà åñòü1 → 2 → 3 → 4 → ... ¤ÏÐÈÌÅÐ 0.4. Ïóñòü A íåêîòîðîå ïîäìíîæåñòâî ìíîæåñòâàN. Ââåäåì â ýòîì ìíîæåñòâå îòíîøåíèå ïîðÿäêà, ïîëàãàÿ m ≤ nòîì ñëó÷àå, åñëè n äåëèòñÿ íà m. Òî, ÷òî ýòî äåéñòâèòåëüíîîòíîøåíèå ïîðÿäêà, ïðîâåðÿåòñÿ ýëåìåíòàðíî (óáåäèòåñü â ýòîìñàìîñòîÿòåëüíî).ÏÐÈÌÅÐ 0.5. Ðàññìîòðèì ìíîæåñòâî äåëèòåëåé ÷èñëà 24è óïîðÿäî÷èì åãî ïî îòíîøåíèþ äåëèìîñòè. Äèàãðàììà Õàññåïîëó÷åííîãî óïîðÿäî÷åííîãî ìíîæåñòâà èçîáðàæåíà íèæå.1 −→ 2 −→ 4 −→ 8↓↓↓↓ ¤3 −→ 6 −→ 12 −→ 240.4.

Àëãåáðàè÷åñêèå îïåðàöèèÏóñòü X ìíîæåñòâî. Áèíàðíîé àëãåáðàè÷åñêîé îïåðàöèåéíàçûâàåòñÿ ïðîèçâîëüíîå îòîáðàæåíèå f : X × X → X . Ìîæíîðàññìàòðèâàòü òàêæå n-àðíûå îïåðàöèèè ïðè ëþáîì íàòóðàëüíîì n, à òàêæå ïðè n = 0 òàêàÿ îïåðàöèÿ ïðîñòî âûäåëÿåò âìíîæåñòâå X ôèêñèðîâàííûé ýëåìåíò. Èíîãäà ðàññìàòðèâàþò5÷àñòè÷íûå îïåðàöèè, ò.