XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 37
Текст из файла (страница 37)
Тогда для любого и > О, а также любых (не обязательно различных) а1, ..., а„Е В1 О Вг элемент ю(ам ..., а„), какова бы ни была операция ы Е Й~">, снова будет принадлежать пересечению В1 ПВг, так как в силу замкнутости каждого вз множеств В1 и Вг одновременно о(ам ..., а„)ЕВ1 им(а1, ..., а„) ЕВг. > Рассмотрим алгебру А = (А, й) и подмножество В С А, не обязательно Й-замкнутое.
Из теоремы 4.1 следует, что существует й-замкнутое подмножество, совпадающее с пересечением всех Й-замкнутых подмножеств, содержащих В. Его называют эамынанием подмножества В относительно операций из Й (или Й-эамынанием подмножества В) и обозначают [В]п. Хотя бы одно й-замкнутое подмножество, содержащее В, обязательно найдется — весь носитель А.
В том случае, когда [В]п = А, подмножество В называют системой обраэиюи4иэ алгебры А = (А,й), а ее саму называют алееброй, порожденной множеспгаом В. Алгебру, которая имеет конечную систему образующих, называют нонечно порожденной. Замечание 4.3. Определение замыкания можно представить и в несколько иной форме, которая содержательно ассоциируется с некоторой процедурой построения множества [В]п по шагам.
233 4.3. Подсистемы Определим семейство множеств (В;);>е, полагая Вг = В, а В.+1 = В<И (х: х = ы(Ьм ..., Ьп), и ) О, ю Е Й~п~,Ьм..., 6 Е В<) . Таким образом, множество В1 состоит из всех элементов Ве = В, и к ним добавляются все элементы, которые могут быть получены как результат применения операций сигнатуры Й к аргументам операции из Во.
Множество Вз точно так же содержит все элементы множества В1 плюс все результаты применения операций из Й к аргументам из В1 и т.д. По определению, В = Во С В1 С Вз С ... С В; С В1+1 С ..., т.е. для любого 4 > О имеют место включения В; С Вьь| и В; С [В]п С А. Можно показать, что [В]п = (.] В;. а)О Замкнутость В означает с точки зрения такого определения, что все множества В; совпадают с множеством В.
Кроме того, может оказаться, что процесс образования множеств В; „оборвется на некотором шаге", т.е. найдется такое 1, что В;+1 = В;. Тогда В; = [В]п. Для конечной алгебры описанную вьппе процедуру можно рассматривать как алгоритм построения замыкания исходного множества (при том, что каждой операции сопоставлен некий алгоритм ее вычисления).
На первом шаге алгоритма в замыкание [В]п помещают все элементы множества В, а затем применяют операции сигнатуры Й к исходным и вновь получаемым элементам до тех пор, пока не перестанут появляться новые элементы. Иначе это можно описать так: 1) все элементы множества Ве считаются и элементами замыкания [В]п; 2) каковы бы ни были элементы Ь1, ..., Ь„, относительно которых известно, что они принадлежат [В]п (т.е. какому-то множеству В; из определенного вьппе семейства), к имеющимся элементам замыкания [В]п добавляют все элементы ы(Ь1, ..., Ьп) для произвольной и-арной операции ы сигнатуры Й.
234 4. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Никакие другие элементы, кроме тех, что могут быть получены рассмотренным выше способом, замыканию [В)п не принадлежат. Образно говоря,  — это „детали конструктора", а [В]ив все, что можно собрать ю этих деталей по некоторым заранее оговоренным „правилам сборки" (каковыми являются операции сигнатуры й) У Рассмотрим примеры построения й-замыкания.
Пример 4.2. а. В алгебре (М, +) возьмем одноэлементное множество В = [Ц =ВО. Тогда В1 = 11,2), Вз = (1,2,3,4), Вз = (1,2, 3,4,5,6,7,8) и т.д. Множество В; при 1> 1 состоит из всех сумм вида пь+ н, где нз, и Е В; 1. Несложно заметить, что В;=(1,2,...,й,...,2Ц, где я=2' 1, з>0. Ясно, что в данном случае О В; = г1, и, таким образом, множество (Ц з)0 является системой образующих этой алгебры. б. В мультинлинашивноб группе вычетов по модулю 23 (т.е.
в группе Езз) построим замыкание множества В = (3), полагал, что сигнатура группы состоит из единственной опе. рации умножения (по модулю 23). Поскольку в этой алгебре сигнатура состоит ю одной операции, а исходное множество В также одноэлементно, то замыкание В будет состоять ю всех степеней элемента 3. Итак, для построения замыкания множества В в данном случае достаточно вычислять последовательно степени (по модулю 23) элемента 3. Имеем Зз 9 Зз 4 34 4.3 12 Зз 12.3 13 Зв 133 16 Зт 163 2 Зз 23 6 30 6.3 18 310 18.3 8 Зы 8.3 1 Так как получена единица, то „круг замкнулся", и тем самым вычислено замыкание множества [3). Заметим, что в этом случае множество В1 состоит из всех степеней тройки, начинал с первой и кончая второй, множество Вз — ю всех степеней, начиная с первой и кончая четвертой, множество Вз — из 4.3.
Подсистемы 235 всех степеней с первой по восьмую, а множество В4 — из всех степеней с первой по 16-ю, но поскольку начиная с 12-й степени элементы повторяются, т.е. Зш = 3, 31з = Зо, 314 = Зз, Зш = 34 и, наконец, Зш = З~, то уже множество Вь совпадет с множеством .34 так что в данном случае [В]0) В4 ° Порожденнзл множеством (3) группа совпала с ццклической подгруппой группы Езз с образуюц4им элементом 3. Этот результат легко обобщить, доказав, что для произвольной конечной группы м' = (О, ), рассматриваемой как алгебра с сигнатурой, состоящей только из операции умножения, ее циклическая подгруппа с образующим элементом а совпадает с подгруппой, порожденной множеством (а).
ф Циклическая группа есть один из важнейших примеров конечно порожденной алгебры. В этой связи обратим внимание на одну тонкость. Если м — циклическая группа с образующим элементом а, то ее, вообще говоря, нельзя рассматривать как алгебру с системой образующих [а). Все зависит от конкретной сигнатуры группы. Действительно, если в сигнатуру группы включить только умножение, то для бесконечной циклической группы 1 ф а" для любого положительного и. Поэтому замыкание множества (а) относительно умножения не содержит единицу. Если же сигнатуру группы как алгебры дополнить унарной операцией взятия обратного, т.е. возведения в степень -1, то циклическая группа с образующим элементом а будет алгеброй с системой образующих (а).
При таком подходе аддиитиекаи ерукаа целых чисел, рассматриваемая как алгебра (Е, +, —, О), есть бесконечнзл циклическал группа, порожденная множеством (1). Пример 4.3. а. Алгебра (Е,, 1) (мультикликатпиокыб мокоид кольца целых чисел) не является конечно порожденной.
Действительно, в этом моноиде в систему образующих необходимо включить все простые числа, поскольку ни одно из них нельзя представить как произведение других чисел. Но множество простых чисел бесконечно. 236 4. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ б. Любая конечная алгебра будет, разумеется, и конечно порожденной. В частности, любое кольцо вычетов по модулю й (поле вычетов при простом Й) — конечно порожденная алгебра, даже если в сигнатуре нет операции нахождения обратного элемента. в. Свободный моноид, порожденный конечным множеством (алфавитом) А есть конечно порожденная (и бесконечнал) алгебра, система образующих которой равна А 0 (Л), где Л— пусп1ой кортеок.
г. Хорошим примером замыкания служит линейная оболочка заданного множества векторов произвольного линейного пространства (1Ч]. Как известно, линейная оболочка Ч множества векторов хы ..., х,„линейного пространства Ь есть т множество всех линейных комбиниций вида 2 сих,, где х; Е У, М1 1 = 1, т, т ) 1. Линейная оболочка замкнута относительно операций сюжения векторов и умножения вектора на чисю, так как линейная оболочка множества векторов является линейным подпространством. Более того, линейная оболочка У множества векторов хы ..., хы — зто наименьшее (относительно отношения включения множеств) замкнутое множество, содержащее заданное множество векторов, поскольку любое замкнутое множество, содержащее векторы хы ..., х,н, содержит и все их линейные комбинации, т.е.
включает в себя У. Отметим, что конечномерноелинейноепространство — конечнопорожденная алгебра, так как оно является линейной оболочкой любого из своих базисов. 4.3. Конгрузнции и фактор-системы В этой главе нам будет удобно использовать „бесскобочную" запись для обозначения результата применения и-арной операции м к элементам аы ..., а„и писать а1...а„о вместо ы(ам ° ° ° ~ ан). 237 4.3. Коигруэиции и фиктор-системы Отпношенив эквивалгнтпностпи р на носителе алгебраической систпемы А называют конгруэнцией на алгебраической системе А, если выполняются условия: 1) для любой п-аркой (и > 1) операции ьт и любых элементов аы ..., а„, Ьм ..., 6„Е А из того, что а; р 6; для каждого 1 = 1, и, следует (а1 ...а ьт) р(Ь|...Ьиы); 2) для любого и-арного (и > 1) отпношенил к и для любых элементов аы ..., а„, Ьм ..., Ь„Е А из того, что а; р Ь; для каждого 1 = Т, и и (ам ..., а„) Е к, следует (Ьы ..., Ь„) Е к.
Первое условие означает, что результаты применения любой операции из Й к попарно эквивалентным аргументам должны быть эквивалентными, а второе — что любое отношение из П содержит или не содержит кортеж (Ьы ..., Ь„) независимо от того, какие именно элементы 6; выбираются в соответствующем классе эквивалвнтпностпи по отпношенито р.
Пример 4.4. а. Рассмотрим (й, +т ч О, 1) — поле двйстпвитпвльныя чисел. Докажем, что отношение равенсшва по модулю 1 (см. пример 1.14) не является конгруэнцией на этом поле, но является конгруэнцией на (К, +, 0) — его аддишивной группе, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
