А.А. Михалёв, А.В. Михалёв - Начала алгебры часть 1 (1108725), страница 2
Текст из файла (страница 2)
е. это полугруппа) и в (111,ш) существует нейтральный элемент е..Замечания1.2.9.1) Подгруппсип (L, w) полугруппы (I1J, w) является полугруппой иназывается подполигриппой.71.2. Группоиды, ПОЛУГрУППbl, мононды2)Гомоморфизм (изоморфизм) группоидов, ЯВЛЯЮШ,ихся полугруппами, называется гомоморфизмом (изоморфизмом) полугрупп,3)Подмоноидам моноила(L, w,носительно операции4)Если(lV1, w,ем) называется подполугруппаем) (таким образом, подмножество(111, "',ем) иLс:;111замкнуто отсодержащая нейтральный элемент ем,w),(!VI', w', ем,) -моноилы.
ТО под гомоморфизмом моноидов пони мается гомоморфизм полугрупп/: (lVI,w, ем)---> (M',w',eM')такой, что /(ем) = ем'. Ясно, что произведение гомоморфиэмов моноидовгомоморфизм моноидов, обратное отображение-к изоморфизму моноидовОпределение1.2.10.-изоморфизм моноидов.Пусть (М,,, ем)-моноид и т Е М.1) Элемент т' Е lV1, для которого тт' = ем, называется правымобратным элемента т.2) Элемент т" Е 111, для которого m."m. = ем, называется левымобратным элемента т ..3)Элемент'/7' Е 111та тn, если П"711.называется двисторонним обратным элемен=еА1=1'11171 (В этом случае элемент rn называется обратимым),Лемма1.2.11.Если в моноиде(!V1,',ем) элементЕ М имеетm.гтравый обратный т' и левый обратный 'т,", то 71/ = т" и 171, является'Jбратнмым элементом.Доказательство'т.'= еЛln/ = (Тn'//7П)Тn' = m,"(m,m") = 1TI'" eM = 11/',Следствие1)1.2.12.Двусторонний(111·, см)Dобратныйэлемент1"элементатмоноидаопрелелён (если он существует) однозначно, для негоиспользуется мультилликативное обозначение m,-l.Глава2)1.Введение: основные алгебраическиеЕсли для элемента т нононлгэлемент тn ~ 1, ТОCTPYI\TypbI(lv1,', ем) существует обратный= '(n,.3) Если элементы У;, у моноида (Лl.·, ем) обратимы с обратными:1:-1иу-1, ТО(:J;y)-I = у- 1 :г - 1Действительно (при этом см.
теорему(y-I:J:-1)(:I;y) = y-l:т - l :J:У=у-l ем н= yy-l = уему-I1.3.=1.3.2),= н-1!/ =хуу- 1 у: - 1=ем =(:су)(у-l",-I).Обобщённая ассоциативность(применение ассоциативной операциикnn ?: 3)сомножителям приРассмотрим*' М х М --' 1\11,ассоциативную(о., Ь) ь-, о.(0.* Ь)операцию* Ь Е М для*с =0.*(Ь*с)на0., Ь Емножествел1,1\;1, при этомVo.,b, cЕМ.Для одного или двух сомножителей нет вопроса о различных расстановках скобок: а, о.* Ь.ДЛЯ трёх сомножителей а, Ь, с существуетвсего две расстановки скобок (о.применение бинарной операции**Ь)* соа*(Ь* с),обозначающие(каждый раз применяемой к двумэлементам). На множестве из четырех элементов а1, Й2, аз, (ч расстановок скобок уже значительно больше: ((О[* (2) * аз) * 04(регу*лярная слева расстановка), (0.1 * 0'2) * (аз * 04), (0.1 (а2 * аз)) * а4,"1 * ((а2 *аэ) *<'''4), Щ * (а2 * (а.э *04)) (регулярная справа расстановка).Задача1,3.1(трудная).
Найти число всех различных расстансВО1\ скобок для применечия бинарной операции наОпределениеа* (11 * с)nсомножителях.бинарной операции ((и. * 11) * С =11, с Е 1\1) озиачает, что для трёх сомноассоциативнойдли всех а"жителей результат применекия операции не зависит от расстановкискобок (т. е.
порядка её применения). Наша ближайшая цель- показать, что дли ассоциативной бинарной операции это утверждение1.3.9Обо6щённая ассоциативностьверно и для п. сомножителей 0,1,0,2, ... , а n (при всех расстановках*скобок после соответствующего примененив операциимы получаем один и тот же элемент, который можно обозначить 0-1 *0,2*. .*0,,,,,без указания расстановки скобок).1.3.2. Пусть * - бинарная ассоциативная(*: м х М -> М, (а.,Ь) ;-, а.
* Ь дЛЯТеоремамножестве А!* Ь) * с(о.п.? 3.(}.1,= а* (Ь * С)дЛЯ всех а,Ь,с Е jИ), aj,0.2,.··,a n Е 111,Тогда результат применения операции0,21'"1операция нао..Ь Е М, и*кnсомножителямне зависит ОТ расстановки скобок0,1),Доказательство проведем индукцией по п. по вполне упорядоченному множествуЕ{n!\!In;? 3}, это означает, что любое Heny-сто е подмножество этого множества имеет наименьший элемент.Начало индукцииобеспечено определением ассоциативнойn = 3операции.Допустим,чтоутверждениевернодля", 3 ,;; k <всехРассмотрим произвольную расстановку скобок на{I.j,"2, ... , "п,nсоответствующую применениям бинарной операции(каждый раз к двум элементам).
Наша цель*тат применения операциидля-/1..сомножителях*доказать, что резульпроизвольной расстановки скобоксовпадает с результатом прнменения для регулярной слева расстановки скобока!* а2,(...а для n((а!=1* «э) * аз) * ...)* а n .При этом дляnимеем2=имеем 0,1.В· каждой расстановке скобок есть последнее применение операции* (например:здесь®(аЬ)@с; (аj*а2)®(u,З*О'4); ((Щ *CJ.2) *аЗ)®(Щ*С1.5),обозначает последнее применение операциипривелённыхоперации*происходит к произведениюkrч;+ 1: ...1 ,;; 1.: <в левомн:ив каждой изсомножителей 0-1: 0.2:· ..
: {},/;ОС некогорой расстановкой скобок и к произведениюжителей*расстановок). Таким образом, последнее применениеJ1 ,;;правомаnn -Снекогоройk<блокерасстановкой(11- - ")скобок.сомноприэтомп; Результат произведения операциине зависит ОТ расстановки скобокk = 1 или k = 2; возможно, n - k3 ,;; k < Т/" ТО В силу индуктивного,;; n - k < п, то также в силу индуктивного*(возможно,= 1- k= 2;еслипредположения;еслиЗпредположения). Выили п.берем в левом произведении регилярнию слева расстановку скобок,а в правом произведении-регулярную справа расстановку скобок.10ГлаваТогдаимеем, при меняяВееяенне: основные алгебраические структуры1.последовательно ассоциативность для трёхсомножигелей.[(...
((0.1 * 0.2)* 0.:1)= [(( ... ((0.1* щ] *o.k_l)* [о.Нl * (о.Н2 * ((0."-1 * 0.,,) .. .))] =* 0.2) * аз)··· Ok- ') * Щ) * о.Нl] ** [ОН2 * (... (Оn-] * оп) .. . )] =(в наших обозначениях, если kn - k= 1, то= 1,=то [щ]= аn ) .[о..nl*Итак, результат применения операциищ; аналогично, еслив соответствии с исходной (проиавольной) расстановкой скобок совпал с результатом примененив при регулярной слева расстановке скобок.
Таким образом,результат применении ассоциативной операции не зависит от расстановки скобок.1.4.ООтображения множествПусть И,непустые множества,V -'/1. Е И сопоставляется элементЗамечание1).f('I1.)ЕИ -; V - (однозначное)V, т. е. каждому элементу.f:отображение из множества И в множество1/.1.4.1.Сохраняя единообразие с курсом анализа, мы обозначаем примененив отображения.fпишем слева отn.Iк элементу."Е И через /('и) , т. е .Возможно (а иногда и удобнее) было быиспользовать обозначение н],2)ЕслиI':--;иV, то .f = Г, если для любого'ILЕ И имеем/('11) = /'(n)З) КатегорияSet,в которой объекты-множества, морфизмыотображения множеств, является одной из ОСНОВНЫХ категорийвматематике.1.5.11Иньеклньные, сюръсхгчвмые. бнгк-ченые отображения1.5.Инъективные, сюръективные, биективныеотображенияРассмотрим образ отображенияГш /Е V= {'"и ~/:1'" = {(/I,),VЕ И},/1,Можно рассмотреть также полезное отношение эквивалентности 7}"на множестве И, определяемое отображениемОпределение1)1.5.1.инъективным,женииеслиf11,2f:разныепереходят/11,1,11,2 Е И, 11,12)Отображениев==>1i ,называется:вИэлементыпривVотобра(т.е.f /(11,2)),сюръективным, если каждый элемент вV является образомV 3н Е [Т, 'и = /(11,),некоторого элемента нз И (Т.
е, "и Е= V),другими словами, 1т/З) биективным, если отображение(т, е,/инъективно и сюръективноVv Е V 3!11" Е И, v = /(11,)).Замечание1)Vэлементыразные/(щ)И ~И ~f:1.5.2.В более раннейматематической литературе для биективногоотображения использовалась более длинная комбинация слов:«взаимно однозначное отображение на»,2)иногда для сюръективного отображенияговорить, чтоЗадачи{(1отобр.ажает множествоJ:И ~V мы будеми на миожес-во 1i>).1,5.3.1) ПустьIUI = щ IVI =2) ПустьIUI =жестваИт,L(U) -(включаяIL(U)I = 2'".n. доказать, чтоIU:и ~V}j = п'":совокупность всех подмножеств мнопустоеподмножество),Доказать,что12Глава1.Введение: основные алгебраические структурыУказание.
для подмножества Т,;;И рассмотреть его характеристическую функциюСт: И --+ {О,Следствие. 1 + С,,\3)Найтиf: ИПри мер1)число--+V. где1},+ ... +C~·Ст(") ==инъективныхи. Е т,n(j. Т.1.'{ О,211.(сюръективных)отображенийIUI = т, IVI = n.1.5.4.Отображение.f: N--+N,лn) = п:+ 1,является инъективным,НО не является сюръективным.2) Отображение f: N--+N, Л1) = 1 и f(n) = n ~ 1 для n, НО не является инъективным.>1,является сюръективным3) Тождественное отображение 1u: И--+и,1u(-u) = и для всех'и, Е и, очевидно. является биекцией.Лемма1.5.5.Пусть И-конечное множество ..f:И --+ТогдаU.равносильны условия:1)J-инъективное отображение;2) .f - сюрьеклненое отображениеДоказательство.=1)2) ПУСТЬ IUI = n < ос.
Так как .f - инъективное отображение, то Iш/l =n. ПОС"ОЛЬКУ 1ш/ с; И, Iш/l = n =тоIm.f = U. т. е . .f - сюр ъекти вное отображение.=2)II1) Допустим противное, т. е. чтоным отображением. Тогда'11.,f"2. Следовательно,отображениеJ./("1) = ./("2)I Im/I <л. =Jне является инъективдля некоторыхIUI,IUI.поэтому 1ш/'0'1,<"2не является сюръективным. что приводит к противоречию.ЗамечаниеЕ И,И, т. е.О1.5.6.Условие конечности множества И в леммесущественно, как показывает пример1.5.4.1.5.5Более того, это соображение может быть использовано для харак гсризации конечных множеств в терминах отображений.13Пронзееиенне отображений1.6.-1.6.Произведение отображенийОпределение1.6.1.Для диаграммы отображенийULV~И!определимпроизведениеnерnозuu,uеii)дляu11, = gl(иногда называемоекомпоэициейили сиотображений 1 и 9 следующим образом:Е И,Замечание1.6.2.Не любые два отображения можно перемноЖИТЬ!Примеры1)1.6.3.Если lи:1 v: VU->U - тождественное отображение множестваV - тождественное отображение множества->И,У,1:И->У,тоf1u =2)ЕслиJ: {1,2"j'(n)=Теорема..
,n}1, то j'"'1,6.4->= lи ,1 = lv [,{1,2,.,. ,n}, J(k)где U= А+l для1~ k <п.,Р,2", "n}.=(об ассоциативности произведения отображений). Для диаграммы отображенийимеем 11.(g.f) = (I'я)J.Доказательство.Ясно, чтоII(g.f): UДля любогоu ЕU->Z,(llg).f: U->Zимеем(iJ(g/))(u)= 11,«g/)(u)) = 11,(g(j(,,))),«(11.[1)/)(/1) = (l1.g)(f(u)) = II(g(f(n))),таким образом, (l1(g/))(,,)но, 11,(gЛ= (1'9)/= ((hg)Л(u)для всех" Е И, следовательD14Глава1.Введение: основные алгебраические структурыМоно ИД отображений множества1.7.ПустьU - множество, Т(С) = и: U---> И}- СОВОКУПНОСТЬ отображений с операцией произведения отображений. В силу доказанной теоремы16.4эта операция ассоциативна.
Нейтральным элеменТОМ относительно этой операции является тождественное отображениеИтак, Т(И) -110лугРУ11110 с единицей, т. е. моноид.1u.Задача1.7.1.Моноид отображений Т(И) множества и коммутьтивен тогда и только тогда, когдаIUI= 1 (т. е. множествоUсостоитиз одного элемента).Указание. Если а Е[', то рассмотрим отображение 1а: U --->U Если а i' Ь, то 1а1ь = 1а i' [ь = 16101а(-U)=1.8.Характеризация инъективных,а для всех а Е[',сюръективных и биективных отображений(в терминах произведений отображений)Теорема1.8.1.Пусть1:U--->V -отображение непустых множеств. Тогда:1)1-инъективное отображение тогда и только тогда, когда существует отображение у:V---> [jтакое, что91 = 1u(Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
