Глухов М. М. Алгебра том 1 (1016678), страница 40
Текст из файла (страница 40)
с П~"~ = П„. С л е д с т в и е 2. Если М естпь систпема образующих элементпов полугруппы П„, тпо множестпво М' всех подстпановок из М порождаетп ее подполугруппу Я„. Таким образом, по следствию 2 любая система образующих полу- группы П„содержит систему образующих группы Я„. В связи с этим естественно возникает вопрос: какие преобразования следует добавить к Я„, чтобы получить систему образующих полугруппы П„? На этот вопрос отвечает Т е о р е м а 4. Множестпво А = М 0 Б„из П„тпогда и тполько тогда порождаетп полугруппу П„, когда М содержитп хотпя бы одно преобразование ранга и — 1. П Если в А нет преобразований ранга и — 1, то в любом произведении д|...д„, = д преобразований д, Е А,т Е 1,т, или все сомножители— подстановки или есть сомножитель ранга т ( и — 1. В первом случае д— подстановка, во втором — гапя (д) ( и — 1.
Следовательно, в полугруппе [А) нет преобразований ранга п — 1, и потому [А) ф П„. Обратно, пусть до Е А и гапя (до) = и — 1. Докажем, что [А) = П„. Для этого достаточно доказать импликацию: д е П„=» д ~ [А). (10) д'(х) = д(х), если х ф 1 и д'(8) = ~. (11) Так как с1е1(д') = с1е1(д) — 1 = й — 1, то по предположению индукции д' е [А). Теперь найдем такое д" Е [А), что д"д' = д. Для этого воспользуемся содержащимися в А подстановками из Я„и преобразованием до.
Докажем ее индукцией по с1е1(д). Если с1е1(д) = О, то д Е Я„, и утверждение (10) очевидно. Предположим, что оно верно для любого д Е П„ при условии с1еГ(д) ( Й, где Й Е 1,п — 1, и рассмотрим случай, когда с1еГ(д) = й. Так как й ) О, то существуют такие з, ~, т' Е 1, п, что з ф ~, д(з) = д(т), т' ф д(1, и). Возьмем из П„следующее преобразование д'. Так как гапя(до) = п — 1, то существуют такие и, и Е 1, п, что и ф и и до(и) = до(и). Домножив до слева на подстановку 61 со свойством 61(з) = и,п1(1) = и, получим преобразование д1 — — 61дв, такое, что д1(з) = д1(~). Кроме того, по утверждению 7 гапя(д1) = п — 1, и потому существует лишь один элемент т е 1,п~д1(1,п).
Следовательно, преобразование д1(п) 1 п (д1(1) д1(2) д1(з) ... д1(~ — 1) т д1(~ + 1) з ... 1 — 1 1 1+1 является подстановкой из Я„, и для д" = д162 имеем: д (х) = х, если х ф 1, и д (1) = з. (12) Теперь из (12) и (11) находим: (д"д')(х) = д(х) для любого х Е 1,п, т. е. д"д' = д, или подробнее, Ь1доЬгд' = д.
Так как 61, до, й2,д' б [А), и [А) — полугруппа, то д Е [А). П ~ 5. Полугруппы бинарных отношений Рассмотрим множество В(й) всех бинарных отношений на фиксированном множестве й. В ~ 1.П1 была определена операция умножения бинарных отношений р|р2. Ча, 6 Е й: (а(р|р2) о С» 3 с Е й: ар|с, ср2Ь), и показано, что эта операция ассоциативна. Следовательно, (В(й), )— полугруппа. Очевидно, что эта полугруппа конечна (и имеет порядок й' 2~~~ ), если [й~ ( оо, и бесконечна в противном случае. В полугруппе В(й) есть единичный элемент, им является отношение равенства.
(Проверьте!) Укажем на связь полугруппы В(й) с рассмотренной в ~ 4 полугруппой П(й). У т в е р ж д е н и е 7. Полугруппа (П(й);.) всех преобразований множества й изоморфно вложима в полугруппу (В(й);.). 232 233 П Зададим отображение у: П(й) — + В(й), сопоставив каждому преобразованию д Е П(й) отношение рд, определенное следующим образом: Ча, 6 Е Й: (ард6 4Ф д(а) = 6). Покажем, что у — мономорфизм. Во-первых, отображение ~р инъективно. Действительно, если д, й Е П(й) и д ф 6, то существуют такие а,6 Е Й, что д(а) = 6 ф 6(а). Следовательно, (а, 6) Е рд и (а,6) ф р~„ т. е.
рд ~ р~. Во-вторых, у — гомоморфизм, т. е. для любых д, 6 из П(й) выполняется равенство: ~р(дп) = у(д)у(п), или рдт, —— рдрл. Справедливость последнего равенства доказывает следующая последо- вательность равносильностей: ардлЬ сФ (дй)(а) = 6 сФ Зс Е й: д(а) = с, 6(с) = Ь сФ сФ 3с е Й: (ардс, ср~Ь) сФ а(рдрл)6. П Из утверждения 7 и теоремы 3 получаем С л е д с т в и е. Любая полугруппа изоморфно вложима в пол угруппу бинарных отпношений В(й) на подходящем множестпве й. Рассмотрим еще ряд других используемых в практике операций над бинарными отношениями.
Так как В(й) есть множество всех подмножеств декартова квадрата й х й, то на В(й) определены ассоциативные бинарные операции пересечения й и объединения О. Следовательно, имеем еще две полугруппы бинарных отношений на множестве В(й): (В(й); й), (В(й); 0). Обе эти полугруппы коммутативны и имеют нейтральные элементы — соответственно универсальное отношение Й х Й и пустое отношение Я. В том случае, когда множество й конечно, с полугруппами (В(й); й) и (В(й); 0) естественным образом связаны изоморфные им полугруппы матриц над У2 — — (О, 1). О п р е д е л е н и е 10.
Матприцей инциденций бинарного отношения р на множестве й = (ю1,..., и~„) называется матрица Ар — — (а, )„„„, в которой для любых т,~ Е 1, и: 1 , если (щ,ш;) Е р, О, если (ю,,и~;) ф р. Заметим, что матрица Ар зависит от упорядочивания элементов множества й, однако при фиксированном порядке соответствие р ~ А задает биективное отображение <т множества В(й) на множество В„всех п х и-матриц над Жг, или булевых матриц порядка п.
Выясним, как выражаются матрицы инциденций отношений р1р2, р1 П рг, р1 0 р2 через матрицы Ар,,Ар,. С этой целью введем сначала на множестве матриц В„три новые операции. При их определении элементы 1, 0 рассматриваются как истина и ложь в математической логике, и потому становится возможным использование логических операций конъюнкции Й и дизъюнкции Ч (см. ~ 2.1).
Далее для а,6 Е (1, 0) вместо ай 6 будем писать а6. О п р е д е л е н и е 11. Пусть А = (а; )„„„, В = (6; )„„„две матрицы с элементами из множества (1, 0). Пересечением, объединением и логическим (или булевским) произведением матриц А, В называются соответственно матрицы: А Л В = (сат)аха, А Ч В = (4~)аха, Ай В = (за )ахи, где для всех т, т' е 1, и: с1т = ац61т 4~ — — а;~ Ч6;, с; = ~/ а1,6~ . й=1 Очевидно, что введенные определением 11'операции на множестве В„ассоциативны и мы имеем три полугруппы матриц: Т е о р е м а 5.
Если й = (ш1,..., и„), тпо отпображение ~т: В(й) В„, определенное формулой: Чр Е В(й): (т(р) = А„, являетпся изоморфизмом полугрупп (В(й); й), (В(й); 0), (В(й), ) бинарных отпношений соотпветпстпвенно на полугруппы матприц (В„; Л), (В„; Ч), (В„; й). П Выше уже отмечалось, что отображение ~т — биективно. Чтобы показать, что ~т является гомоморфизмом в каждом из указанных в 234 235 теореме трех случаев, достаточно для любых р1, р2 Е В(Й) доказать равенства: Ар,пр =А, ЛАр„Ар,ир, = Ар, ЧАщ, Ар,р —— А,йАр,.
(13) Доказываются эти равенства сходным образом. Докажем для примера последнее равенство Пусть Ар, — — (а; )„„„, А, = (6; )„„„, Ар,, — — (с; )„„„. Используя определения соответствующих понятий, получим цепочку эквивалентностей с~~ = 1 4Ф щ(Р1Р2) 06' Фю' Эшц Е Й: (шфр1ш/с, шцэ2ш~) 4Ф и ~ Эй Е 1,п;(ац, =1,6у, = 1) с ~/ а;,Ь,~ —— 1. Таким образом, имеем: %,~ Е 1,п: с, = ~/ а,,6,, т. е.
Ар,р, —— Ар,3сАр,. П Задачи 1. Будут ли подполугруппами полугруппы (Р„,„; ) всех п х и-матриц над полем Р множества: а) всех матриц ранга т; б) всех матриц рангов, не превосходящих т (т — любое число из множества О, и)? 2. Пусть  — коммутативное кольцо с единицей и В1 С В. При каком условии множество всех матриц из В„„с определителями из В1 образует подполугруппу полугруппы (В„ „; )? 3.
Найти все элементы подполугруппы [А) полугруппы (У;+), если: а) А = (3, 5); б)А = (4, 6, 10); в)А = (2, — 3). 4. Пусть Š— множество всех элементарных матриц размеров п х и над полем Р. Доказать: а) Е порождает полугруппу (Р„' „; ), при любых п е Я и Р; б) Е порождает полугруппу (Р„„;+) тогда и только тогда, когда Р ф СР(2) или Р = СР(2) и и =1; в) подмножество М = Е 0 Р из Р„,„порождает полугруппу (Р„,„; ) тогда и только тогда, когда в Р содержится хота бы одна матрица ранга и — 1. 5. Доказать, что для любых а, 6, а1,..., а~ е Е,„в полугруппе (Е,„; +) справедливы утверждения: а) [а) с [6) с=~ (Ь,т)](а,т); б) [а) = [6) ~ (Ь,т) = (а, т); в) [а1,...,ас) = [сХ1) = [сХ), где 4 = (а1,...,ас), сГ= (а1,...,ас,т).
6. Описать все подполугруппы полугруппы (Е~;+) при т = р, р", 100, где р — простое число. 7. Описать с точностью до изоморфизма все циклические полугруп- пы. 8. Является ли отображение у: С вЂ” + С гомоморфизмом полугруппы (С; *) в себя, если * есть + или ., а у определяется одним из следующих равенств (при любом а = а+ Ьг Е С и фиксированном и Е Я): а) у(а) = ]а[; б) у(а) = атда; в) у(а) = па; г) у(а) = а"; д) у(а) = а; е) у(а) = а — Ы? 9. Пусть В[х] — кольцо многочленов над кольцом В.
Является ли отображение ~р: В[х] — + В гомоморфизмом полугруппы (В[х]; е), в полу- группу (В;*) если е есть+ или, ау определяется одним из следующих способов (при любом а(х) Е В[х] и фиксированном и Е Я): а) у(а(х)) есть свободный член а(х); б) у(а(х)) есть старший коэффициент а(х), если а(х) ф О, и 0 если а(х) =0; в) ~р(а(х)) = а(т), для некоторого фиксированного т Е В? 10. Является ли гомоморфизмом полугруппы (В„„; *) на себя отображение <р: В„„— + В„„, если  — любое кольцо, * есть + или °, а ~р каждую матрицу А отображает в транспонированную к ней матрицу Ат 11. Являются ли конгруэнциями отношения: а) "иметь равные действительные части" на полугруппах (С; +), (С; ); б) "иметь равные ранги" на полугруппе матриц (Р„„; ) над полем Р; в) "иметь одно и то же множество простых делителей" на полугруппе(Я; ); г) "иметь равные значения в фиксированной точке т из кольца В" на полугруппах многочленов (В[х];+), В[х]; ); д) "иметь равные дефекты" на полугруппе (П„; )? 236 237 239 12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
