XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 41
Текст из файла (страница 41)
Как известно (см. 2.2), нулевая декартова степень произвольно- 4.5. Прямые произведения алгебрантесклх систем 255 го множества А есть, по определению, одноэлементное множество (Л) и его элемент Л называется пустым кортежем. Тогда нулевая декартова степень Ао алгебраической системы А есть алгебраическая система (1Л), й, П), где Л...Лш = Л для всех юбйи(Л, ..., Л)ЕядлявсехнЕП. Итак, операции и отношения исходньп~ однотипных алгебраических систем переносятся на декартово произведение их носителей покомпонентно. Пример 4.9. Рассмотрим алгебраическую систему 1с= = (1с, +,, О, 1, <), сигнатура которой состоит из обычных операций сложения, умножения (бинарные операции), 0 и 1 (нульарные операции) и есшесшвекного числового порядка (бикаркое ошношекие).
Распространим эти операции и отношения на декартов квадрат Ж х Ж = 1с~ множества действительных чисел согласно определению, данному выше. Сложение упорядоченных кар действительных чисел определяется тогда равенством (ам Ь1)+(ат, Ьз) = (а1+аз, 61+Ьз), а умножение — равенством (ам 61) (аз, Ьз) = (ц1 аз, 61 Ьз). При этом легко понять, что упорядоченная пара (О, 0) будет нейшральным злеменшом по сложению в К~, а упорядоченная пара (1, 1) — нейтральным элементом по умножению. Кроме того, для любых действительных чисел а, 6 будем иметь (а, Ь) . (О, 0) = (О, 0), т.е.
пара (О, 0) играет роль нуля относительно умножения в Й~. Ошкошекие порядка на множестве упорядоченных пар вводится по правилу' (ам 61) < (аз, Ьз) оо (а~ < аз и Ь1 < Ьз). 'Купно, рааумеетсл, проверить, что построено действительно отнопмние порядка, но эта проверка легко выполиветсл. 256 4. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Заметим, что мы уже ранее многократно пользовались подобным определением отношения порядка на множестве упорядоченных пар (и, в более общем случае, кортежей). Для каждого 1 = 1, п определим проекцию рг;: В -+ А;, полагая рг;(х) = х;. Можно показать, что рг; есть строгий гомоморфизм, называемый проектирующим гомоморфизмом.
Из определения декартова произведения алгебраических систем априори не следует, что в нем сохраняются все свойства операций и отношений перемножаемых алгебраических систем. Разберем в этой связи такой пример. Пример 4.10. Пусть К1 и Кз — поля. Их произведение К1 х Кз не будет полем, так как в этом произведении возникают делители нуля. В самом деле, если а Е К1 ~ (О), Ь Е Кз ~ (01, то (а, 0) (0,6) = (0,0) — элемент, являющийся нулем произведения К1 х Кз. Таким образом, алгебра К1 х Кз будет, как нетрудно убедиться, только кольцом.
Этот пример показывает, что в декартовом произведении могут теряться некоторые свойства исходных алгебраических систем. В частности, декартово произведение полей не будет полем. Здесь уместно вспомнить о поле комплекскыя чисел, носителем которого является декартов квадрат ж~. Но если сложение в этом поле определяется покомпонентно, т.е. по правилам декартова произведения алгебр, то умножение введено по более сложному правилу, позволяющему сохранить аксиомы полл. Теорема 4.11. 1. Прямое произведение полугрупп (моноидов, групп) есть полугруппа (моноид, группа).
2. Прямое произведение полуколец (идемпотентных полуколец, колец) есть полукольцо (идемпотентное полукольцо, кольцо). 3. Прямое произведение полурешеток, решеток, симметричных полуколец, булевых алгебр есть соответственно полурешетка, решетка, симметричное полукольцо, булеза алгебра. 4.е. Прееиие произведении аегеереических систем 257 4. Прямое произведение (индуктивных) упорядоченных множеств есть (индуктивное) упорядоченное множество. < Для простоты будем рассматривать доказательство для произведения двух алгебраических систем.
1. Если 81 = (8м ) и 8г = (8г, .) — две полугруппы, то, вводя на множестве 81 х 8г операцию так, что для любых а1, 61 Е 8г аг Ьг Е 8г справедливо (ам аг) (61, Ьг) =(а1.61, аг Ьг), получим полугруппу, поскольку в силу ассоциативности опера; ции . на множествах 81 и 8г будем иметь (ам аг) ((Ь1, Ьг) (см сг)) = (ам аг) (Ь|.см Ьг сг) = = (а1. (Ь1 с1), аг (Ьг сг)) = ((а1 Ь1).с1, (аг Ьг) сг) = =((ам аг) (Ьм Ьг)) (с1, сг). Если в каждой из указанных вьппе полугрупп существует нейтральный элемент е1 и ег соответственно, то легко проверить, что упорядоченная пара (е1, ег) является нейтральным элементом по операции на декартовом произведении 81 х 8г.
Если же моноиды 81 и 8г суть группы, то элемент из 8г х 8г, обратный к (ам аг), равен (а1 1, аг1). 2. Доказательство для полукольца и кольца проводится аналогично предыдущему. 3. Точно так же, совершенно аналогично доказательству для групп, проводится доказательство для полурешеток, реше ток, симметричных полуколец и булевых алгебр. 4.
Пусть теперь М1 = (М1, () и Мг = (Мг> () — индуктивные упорядоченные множества, какмекьшие злемеккгы которых суть 01 и Ог. Определяя отношение порядка ( на декартовом произведении М1 х Мг покомпонентно, так же как это сделано в примере 4.9, получаем, что упорядоченная пара (01, Ог) является на указанном произведении наименьшим элементом. е меж 258 4. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Далее, произвольной неубывающей последовательности упорядоченных пар (ам Ь1) ~< (аз, Ьз) < ..
< (а„, Ь„) < <.. соответствуют две неубывающие последовательности а1 <аз( ..(а~<... и Ь1<Ьз<" <Ь1<". в множествах М1 и Мз, каждая из которых имеет шочвую верхнюю грань — элементы с1 и сз. Нетрудно показать, что упорядоченная пара (с~, сз) есть точная верхняя грань записанной вьппе последовательности упорядоченных пар. 1ь Рассмотрим теперь конструкцию, во многом аналогичную прямому произведению алгебраических систем.
Пусть А = (А, й, П) — некоторая алгебраическая система, а Х вЂ” произвольное множество. Распространим операции и отношения алгебраической системы А на множество А~ всех отображений из Х в А. Это осуществляется следующим образом: 1) для любого п ) )О, любой операции и Е й~") и любых отображений ум ..., Д„е А~ полагаем (у1...~„о)(х) = ~~(х)...
~„(х)и, где х е Х; тем самым определено отображение ~1...~„м Е А как результат применения операции ы к отображениям ум ..., ~„(в частности, для нульарной операции а е А соответствующая нульарная операция на А~ есть отображение у„, такое, что Ях) =а для любого х Е Х); 2) для любого и > 1, любого отношения н Е П(") и любых отображений ум ..., У„Е А~ полагаем Построенную таким образом алгебраическую систему с носителем Ал, однотипную с А, обозначим А». Докажем, что 4.5. Прямые произведении алгебраических систем 259 в случае конечного множества Х = (1,...,п) алгебраическая система А» изоморфна алгебраической системе А".
Действительно, в этом случае каждому отображению У Е б А» можно однозначно сопоставить кортеж (ам ..., а„) Е А" таким образом, что а; = У(1), 1 = 1, п. В то же время каждый кортеж (ам ..., а„) Е А" однозначно определяет отображение У Е А, для которого У(1) = а,, 1= 1, и. Тем самым построена биекция <р множества А» на множество А". Докажем, что она „сохраняета операции и отношения (в том смысле, как зто определено вьппе, см. 4.4). Для произвольных отображений Ум ..., У„, е А и проювольной операции ьт е Й~та~ имеем р(Л" У )=ИЛ" У И1) " (Л" У Нп))= =(Л(1)."У (1)ат," Ут(тт) "У (и) ) = = (Л(1), "., Л( ))."(У (1), " У (и)) = = р(Л)".р(У ) с, что и требовалось доказать.
„Сохранение" отношений доказывается аналогично. Тем самым изоморфизм А» м А" доказан полностью. Пример 4.11. а. Для аддитпивнод группы дебстпвитпельных чисел на множестве всех функций из К в К по приведенной выше конструкции строится аддитивная группа функций ю К в К. В этой группе сумма функций У и д есть функция У+ 9, такая, что для любого х Е К выполняется равенство (У+ 9) (х) = У(х) + д(х). Функция, противоположная к У, определяется так: (-У)(х) = = -У(х). Нейтральный элемент есть нулевая функция О, т.е.
для любого х е К имеет место О(х) = О. Аналогично можно построить кольцо функций из К в К на базе кольца действительных чисел. Несмотря на то что действительные числа образуют поле, кольцо функций, как можно легко показать, полем не будет. Этот „отрицательный" результат вполне соответствует ранее доказанному результату, согласно которому прямое произведение полей не является полем. 260 4.
АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ б. Если А = (А, <) — упорядоченное множество, то упорядоченное множество всех функций иэ Х в А строится так: полагаем т < д тогда и только тогда, когда т(х) < д(х) для любого х Е Х. Если порядок на А индуктивен, то и порядок на Ах индуктивен, что доказывается твк же, как в п. 4 теоремы 4.11. 4.6.
Конечные булевы алгебры Покажем применение понятия прямого произведения алгебраических систпем к теории булевых алгебр. Мы докажем здесь интересный факт, состоящий в том, что мощностпь любой конечной булевой алгебры есть некоторая степень двойки. Отсюда будет следовать, например, что в конечной булевой алгебре может быть 1, 2, 8, 16, 32, 64 и т.д. элементов, но не может быть, скажем, 100 или 75 элементов. Чтобы доказать сформулированное утверждение о конечных булевых алгебрах, необходимо ввести некоторые вспомогательные определения и доказать некоторые утверждения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
