Электронный курс лекций (1078552), страница 2
Текст из файла (страница 2)
2. ÏîäñòàíîâêèSÐàññìîòðèì ìíîæåñòâî n âñåõ áèåêòèâíûõ ïðåîáðàçîâàíèéìíîæåñòâà Jn (n = 1, 2, ...). Åãî ýëåìåíòû σ ∈ n íàçûâàþòñÿ(íà n ýëåìåíòàõ). Èõ óäîáíî çàïèñûâàòü â âèäå()12...nσ=.(2.1)σ(1) σ(2) ... σ(n)SïîäñòàíîâêàìèÒàê êàê ïîäñòàíîâêè ÿâëÿþòñÿ ïðåîáðàçîâàíèÿìè îäíîãî ìíîæåñòâà, èõ ìîæíî ïåðåìíîæàòü. Äëÿ σ, τ ∈ n èõ êîìïîçèöèÿσ ◦ τ òàêæå ÿâëÿåòñÿ ïîäñòàíîâêîé. Ýòî âûòåêàåò èç ñëåäñòâèÿê òåîðåìå 1.2. Ðåçóëüòàòîì ïðèìåíåíèÿ ýòîé ïîäñòàíîâêè ê ýëåìåíòó i ñëóæèò (σ ◦ τ )(i) = σ(τ (i)).ÏÐÈÌÅÐ 2.1. Ïóñòü()()1 2 31 2 3σ=, τ=3 1 23 2 1SÒîãäàσ(τ (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 ).ÏÐÈÌÅÐ 2.2. Äëÿ äàííîé ïîäñòàíîâêè σ ∈ 9 èìååì()1 2 3 4 5 6 7 8 9σ== (193)(26)(48)(5)(7).9 6 1 8 5 2 7 4 3öèêëîìS7Ýòà ïîäñòàíîâêà ðàçëîæåíà â ïðîèçâåäåíèå íåçàâèñèìûõ (ò. å.íå ñîäåðæàùèõ îäèíàêîâûõ ýëåìåíòîâ) öèêëîâ.
Öèêëû äëèíû 1îáû÷íî îïóñêàþò, ò. å. ïèøóò σ = (193)(26)(48). ßñíî, ÷òî æå ñàìîå ìîæíî ñäåëàòü ñ ëþáîé ïîäñòàíîâêîé èìû ïðèõîäèì ê ñëåäóþùåìó ðåçóëüòàòó.ÒÅÎÐÅÌÀ 2.1.σ ̸= en≥2Êàæäàÿ ïîäñòàíîâêàâ S ÿâëÿåòñÿïðîèçâåäåíèåì íåçàâèñèìûõ öèêëîâ äëèíû . Ýòî ðàçëîæåíèåâ ïðîèçâåäåíèå îïðåäåëåíî îäíîçíà÷íî ñ òî÷íîñòüþ äî ïîðÿäêàñëåäîâàíèÿ öèêëîâ. Öèêë äëèíû 2 íàçûâàåòñÿ òðàíñïîçèöèåé. Ëþáàÿ òðàíñïîçèöèÿ èìååò, òàêèì îáðàçîì, âèä τ = (ij).ÑËÅÄÑÒÂÈÅ 1.
Êàæäàÿ ïîäñòàíîâêà σ ∈ Sn ÿâëÿåòñÿïðîèçâåäåíèåì òðàíñïîçèöèé.ÄÎÊÀÇÀÒÅËÜÑÒÂÎ.  ñèëó òåîðåìû 2.1 ïîäñòàíîâêà σ ̸= 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 .ÏÐÈÌÅÐ 2.3.  ìíîæåñòâå 3 ïîäñòàíîâêè e, (123), (132) ÷åòíûå, ïîäñòàíîâêè (12), (13), (23) íå÷åòíûå. ÒÅÎÐÅÌÀ 2.2.èíâåðñèþ÷åòíîéíå÷åòíîéS×åòíîñòü ïîäñòàíîâêè ìåíÿåòñÿ ïðè óìíîæåíèè íà òðàíñïîçèöèþ:ε(στ ) = −ε(σ),ãäå σ, τ ∈ Sn, τ òðàíñïîçèöèÿ.ÄÎÊÀÇÀÒÅËÜÑÒÂÎ.
Ïóñòü σ èìååò âèä (1.4), à τ = (i, i+1).Òîãäà()1...ii + 1 ...nστ =.σ(1) ... σ(i + 1) σ(i) ... σ(n)8Êàê ëåãêî ïîíÿòü, ÷èñëî èíâåðñèé â ïîäñòàíîâêàõ σ è στ îòëè÷àåòñÿ íà åäèíèöó. Çíà÷èò, ýòè ïîäñòàíîâêè èìåþò ðàçíóþ ÷åòíîñòü. Äîêàçàòåëüñòâî ñëåäñòâèÿ 2 èç òåîðåìû 2.1 ïîêàçûâàåò,÷òî ëþáàÿ òðàíñïîçèöèÿ ðàçëàãàåòñÿ â ïðîèçâåäåíèå íå÷åòíîãî÷èñëà òðàíñïîçèöèé âèäà (i, i + 1). Çíà÷èò, ïðè óìíîæåíèè íàïðîèçâîëüíóþ òðàíñïîçèöèþ çíàê ïîäñòàíîâêè ìåíÿåòñÿ íå÷åòíîå ÷èñëî ðàç, ò. å. ìåíÿåòñÿ. ÑËÅÄÑÒÂÈÅ.σ, τ ∈ nS èìååìÄëÿ ëþáûõε(στ ) = ε(σ) · ε(τ ),ε(σ −1 ) = ε(σ).ÄÎÊÀÇÀÒÅËÜÑÒÂÎ. Ïðåäñòàâèì ïîäñòàíîâêè σ è τ â âèäåïðîèçâåäåíèÿ òðàíñïîçèöèé: σ = σ1 ...
σk , τ = τ1 ... τm . Òîãäàστ = σ1 ... σk τ1 ... τm ,σ −1 = σk ... σ1 .Íà îñíîâàíèè òåîðåìû 2.2 èìååì ε(σ) = (−1)k , ε(τ ) = (−1)m ,ε(στ ) = (−1)k+m , ε(σ −1 ) = (−1)k , îòêóäà è ïîëó÷àåòñÿ òðåáóåìîåóòâåðæäåíèå. 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 .Ïðèìåðàìè îòíîøåíèé ýêâèâàëåíòíîñòè ñëóæàò: îòíîøåíèå ðàâåíñòâà ÷èñåë; îòíîøåíèå ïîäîáèÿ òðåóãîëüíèêîâ; îòíîøåíèåïàðàëëåëüíîñòè ïðÿìûõ è ò.
ä.ðåôëåêñèâíûìñèììåòðè÷íûìàíòèñèììåòðè÷íûìòðàíçèòèâíûìýêâèâàëåíòíîñòüþ9ÏÐÈÌÅÐ 3.1. Íàçîâåì äâà ÷èñëà m, k ∈ Zn è çàïèøåììîäóëþ íàòóðàëüíîãî ÷èñëàñðàâíèìûìè ïîm ≡ k(mod n),åñëè èõ ðàçíîñòü m−k äåëèòñÿ íà n. Ïðîâåðüòå ñàìîñòîÿòåëüíî,÷òî ýòî îòíîøåíèå åñòü îòíîøåíèå ýêâèâàëåíòíîñòè. Ïóñòü â ìíîæåñòâå X ââåäåíî îòíîøåíèå ýêâèâàëåíòíîñòè.Ïîäìíîæåñòâî[x] = {y ∈ X | y ∼ x}ñîñòîÿùåå èç ýëåìåíòîâ, ýêâèâàëåíòíûõ äàííîìó, íàçûâàåòñÿ, ñîäåðæàùèì x.
Ëþáîé ýëåìåíò y ∈[x] íàçûâàåòñÿýòîãî êëàññà.ÒÅÎÐÅÌÀ 3.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α ñîâïàäàþò ñ êëàññàìè ýêâèâàëåíòíîñòè ïî ýòîìó îòíîøåíèþ ýêâèâàëåíòíîñòè. ÏÐÈÌÅÐ 3.2. Ðàññìîòðèì îòíîøåíèå ñðàâíèìîñòè ïî ìîäóëþn èç ïðèìåðà 3.1. Êëàññàìè ýêâèâàëåíòíîñòè ïî ýòîìó îòíîøåíèþ ñëóæàò êëàññû [0], [1], [2], ..., [n − 1]. Ïðè ýòîì êëàññ [k]ñîñòîèò â òî÷íîñòè èç ÷èñåë, äàþùèõ ïðè äåëåíèè íà n îñòàòîêk. Ðåôëåêñèâíîå, àíòèñèììåòðè÷íîå è òðàíçèòèâíîå áèíàðíîåîòíîøåíèå íàçûâàåòñÿ. Ïðèìåðàìè îòíî-îòíîøåíèåì ïîðÿäêà10øåíèé ïîðÿäêà ñëóæàò îáû÷íîå îòíîøåíèå ïîðÿäêà íà ìíîæåñòâå öåëûõ ÷èñåë, îòíîøåíèå âêëþ÷åíèÿ ìåæäó ïîäìíîæåñòâàìèäàííîãî ìíîæåñòâà.Äëÿ îòíîøåíèÿ ïîðÿäêà èñïîëüçóåòñÿ îáû÷íî çíàê ≤. Åñëèx ≤ y , òî ãîâîðÿò, ÷òî x íå ïðåâîñõîäèò y .
Èñïîëüçóåòñÿ òàêæåçíàê <: ïèøóò x < y , åñëè x ≤ y è x ̸= y . Ìíîæåñòâî ñîòíîøåíèåì ïîðÿäêà íàçûâàåòñÿ ÷àñòè÷íî óïîðÿäî÷åííûì. Òåðìèí "÷àñòè÷íî" óïîòðåáëÿåòñÿ ïîòîìó, ÷òî íå äëÿ ëþáûõ äâóõýëåìåíòîâ âåðíî x ≤ y èëè y ≤ x. Åñëè ýòî âåðíî, òî ìíîæåñòâîíàçûâàåòñÿ ëèíåéíî óïîðÿäî÷åííûì, à ïîðÿäîê ëèíåéíûì.×àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî óäîáíî áûâàåò èíîãäàèçîáðàæàòü â âèäå òàê íàçûâàåìîé äèàãðàììû Õàññå.
Ïðè ýòîìýëåìåíòû èçîáðàæàþòñÿ òî÷êàìè. Òî÷êè, îòâå÷àþùèå ýëåìåíòàìx y , ñîåäèíÿþòñÿ ñòðåëêîé, âåäóùåé îò x ê y , åñëè x < y è íåñóùåñòâóåò òàêîãî ýëåìåíòà z , òî x < z < y .ÏÐÈÌÅÐ 3.3. Äèàãðàììà Õàññå ìíîæåñòâà N îáû÷íûì îòíîøåíèåì ïîðÿäêà åñòü1 → 2 → 3 → 4 → ... ÏÐÈÌÅÐ 3.4. Ïóñòü A íåêîòîðîå ïîäìíîæåñòâî ìíîæåñòâàN. Ââåäåì â ýòîì ìíîæåñòâå îòíîøåíèå ïîðÿäêà, ïîëàãàÿ m ≤ nòîì ñëó÷àå, åñëè n äåëèòñÿ íà m. Òî, ÷òî ýòî äåéñòâèòåëüíîîòíîøåíèå ïîðÿäêà, ïðîâåðÿåòñÿ ýëåìåíòàðíî (óáåäèòåñü â ýòîìñàìîñòîÿòåëüíî).ÏÐÈÌÅÐ 3.5.
Ðàññìîòðèì ìíîæåñòâî äåëèòåëåé ÷èñëà 24è óïîðÿäî÷èì åãî ïî îòíîøåíèþ äåëèìîñòè. Äèàãðàììà Õàññåïîëó÷åííîãî óïîðÿäî÷åííîãî ìíîæåñòâà èçîáðàæåíà íèæå.1 −→ 2 −→ 4 −→ 8↓↓↓↓ 3 −→ 6 −→ 12 −→ 244. Àëãåáðàè÷åñêèå îïåðàöèèÁèíàðíîé àëãåáðàè÷åñêîé îïåðàöèåéÏóñòü X ìíîæåñòâî.íàçûâàåòñÿ ïðîèçâîëüíîå îòîáðàæåíèå f : X × X → X . Ìîæíîðàññìàòðèâàòü òàêæå n-àðíûå îïåðàöèèè ïðè ëþáîì íàòóðàëüíîìn, à òàêæå ïðè n = 0 òàêàÿ îïåðàöèÿ ïðîñòî âûäåëÿåò âìíîæåñòâå X ôèêñèðîâàííûé ýëåìåíò. Èíîãäà ðàññìàòðèâàþò÷àñòè÷íûå îïåðàöèè, ò. å.
îïðåäåëåííûå íå íà âñåì X × X , à11òîëüêî íà íåêîòîðîì åãî ïîäìíîæåñòâå. Îáû÷íî âìåñòî çàïèñèz = f (x, y) ïèøóò z = x ∗ y, z = x ◦ y èëè åùå êàê-íèáóäü,åñëè òîëüêî ó îïåðàöèè íåò èíîãî òðàäèöèîííîãî îáîçíà÷åíèÿ,íàïðèìåð, z = x + y . ×àñòî èñïîëüçóåòñÿ ìóëüòèïëèêàòèâíàÿçàïèñü îïåðàöèè: z = xy . Ìíîæåñòâî X ñ îïåðàöèåé ∗ áóäåòîáîçíà÷àòüñÿ ÷åðåç (X, ∗). Ðàçóìååòñÿ, ìîæíî ðàññìàòðèâàòü èìíîæåñòâà ñ äâóìÿ îïåðàöèÿìè (X, ∗, ◦) (è ñ áîëüøèì ÷èñëîìîïåðàöèé).Ïóñòü (X, ∗) êîíå÷íîå ìíîæåñòâî ñ îïåðàöèåé. Ðåçóëüòàòûîïåðàöèè, çàäàííîé íà òàêîì ìíîæåñòâå, óäîáíî çàïèñûâàòü ââèäå òàê íàçûâàåìîé òàáëèöû Êýëè. Ñëåâà è ââåðõó êâàäðàòíîéòàáëèöû âûïèñûâàþò âñå ýëåìåíòû ìíîæåñòâà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
