Подсистемы

Пусть A = (A, Ω, П) — произвольная алгебраическая система и В ⊆ А — непустое множество.

Множество В называют замкнутым относительно операций из Ω (Ω-замкнутым множеством), если результат применения любой n-арной операции из Ω к любым элементам из В принадлежит В, т.е. для любой n-арной операции ω и любых элементов а₁, ..., а_n ∈ В элемент ω(a₁, ..., a_n) ∈ B.

Например, в полугруппе (ℕ, +) подмножество четных чи- чисел замкнуто относительно операции сложения, а подмножество нечетных чисел не замкнуто. В кольце целых чисел подмно- подмножество натуральных чисел замкнуто относительно операциий сложения и умножения, но не замкнуто относительно операции взятия противоположного элемента.

Алгебраическую систему В = (B, Ω, П|_B), где В ⊆ А, называют подсистемой алгебраической системы A, если В Ω-замкнуто и П|_B есть множество ограничений на В всех отношений из П: П|_B = {р|_B: p ∈ П}.

Очевидно, что алгебраические системы A и В однотипны, и часто вместо П|_B будем в таком случае писать просто П.

Если A — алгебра, то любую ее подсистему называют ее подалгеброй (точнее, Ω-подалгеброй).

Замечание 4.2. В определении Ω -подалгебры требуется лишь замкнутость относительно операций из Ω. Если же мы хотим, чтобы при переходе к подалгебре „наследовались" какие-либо специальные свойства операций исходной алгебры, то это нужно специально оговаривать. Именно так мы и поступали, определяя понятия подгруппы, подкольца, подполя и т.п. Впрочем, подгруппу можно определить и через свойство замкнутости, но лишь в том случае, если в сигнатуру группы включить не только одну бинарную операцию „умножения" (которая обладает специальными „групповыми свойствами", см. 2.2), но также унарную операцию взятия обратного элемента и нульарную операцию — единицу группы.

Аналогично, исключительно через требование замкнутости, можно определить понятие подмоноида. Следовательно, таким образом можно определить и подкольцо.

Сложнее обстоит дело с телом и полем. Мы не можем опре- определить поле как алгебру с сигнатурой {+,*, -,^-1,0,1}, где операция — есть операция вычисления противоположного элемента (обратного по сложению), а операция ¹ — операция вычисления обратного элемента по умножению, так как последняя операция есть частичное отображение и не определена для элемента 0. Поэтому она не может быть введена в сигнатуру алгебры, по определению содержащей только всюду определен- определенные операции.

Обратим внимание и на то, что переходя к Ω-замкнутому подмножеству, мы можем получить алгебру как обогащенную новыми свойствами операций сигнатуры Ω, так и утратившую некоторые из свойств. Например, моноид (ℕ₀, +, 0) будет только подмоноидом группы (ℤ, +, 0) (но не подгруппой), а подмоноид биекций в симметрическом моноиде некоторого бесконечного множества будет уже группой (это не подгруппа, а именно подмоноид, являющийся группой!). #

В следующей теореме сформулировано простое, но очень важное свойство замкнутых подмножеств.

Теорема 4.1. Непустое пересечение произвольного семейства Ω-замкнутых подмножеств Ω-замкнуто.

◀Для простоты рассмотрим доказательство для пересечения двух Ω-замкнутых подмножеств.

Пусть в алгебре (А, Ω) Ω-замкнутые подмножества В₁ и B₂ имеют непустое пересечение. Тогда для любого n ≥ 0, а также любых (не обязательно различных) a₁, ..., а_n ∈ В₁ ∩ B₂ элемент ω(a₁, ..., а_n), какова бы ни была операция ω ∈ Ω⁽ⁿ⁾, снова будет принадлежать пересечению В₁ ∩ B₂, так как в силу замкнутости каждого из множеств В₁ и B₂ одновременно ω(a₁, ..., а_n) ∈ В₁ и ω(a₁, ..., а_n) ∈ В₂. ▶

Рассмотрим алгебру A = (А, Ω) и подмножество B ⊆ A, не обязательно Ω-замкнутое.

Из теоремы 4.1 следует, что существует Ω-замкнутое подмножество, совпадающее с пересечением всех Ω-замкнутых подмножеств, содержащих В. Его называют замыканием подмножества В относительно операций из Ω (или Ω-за- мыканием подмножества В) и обозначают [B]_Ω. Хотя бы одно Ω-замкнутое подмножество, содержащее В, обязательно найдется — весь носитель А. В том случае, когда [B]_Ω = А, подмножество В называют системой образующих алгебры А=(А,Ω), а ее саму называют алгеброй, порожденной множеством В. Алгебру, которая имеет конечную систему образующих, называют конечно порожденной.

Замечание 4.3. Определение замыкания можно представить и в несколько иной форме, которая содержательно ассоциируется с некоторой процедурой построения множества [B]_Ω по шагам.

Определим семейство множеств (B_i)_i≥0, B₀ = B, a

B_i+1 = B_i ∪ {x: x = ω (b₁, ..., b_n), n ≥ 0,ω ∈ Ω⁽ⁿ⁾, b₁, ..., b_n ∈ B_i}.

Таким образом, множество B₁ состоит из всех элементов B₀ = , и к ним добавляются все элементы, которые могут быть получены как результат применения операций сигнатуры Ω к аргументам операции из В₀. Множество В₂ точно так же содержит все элементы множества В₁ плюс все результаты применения операций из Ω к аргументам из В₁ и т.д. По определению, В = В₀ ⊆ В₁ ⊆ В₂ ⊆ ... ⊆ В_i ⊆ В_i+1 ⊆ ..., т.е. для любого i ≥ 0 имеют место включенияВ_i ⊆ В_i+1 и В_i ⊆ [B]_Ω ⊆ A. Можно показать, что

Замкнутость В означает с точки зрения такого определения, что все множества В_i совпадают с множеством В. Кроме того, может оказаться, что процесс образования множеств В_i „оборвется на некотором шаге", т.е. найдется такое i, что В_i+1 = В_i. Тогда В_i = [B]_Ω.

Для конечной алгебры описанную выше процедуру можно рассматривать как алгоритм построения замыкания исходного множества (при том, что каждой операции сопоставлен некий алгоритм ее вычисления). На первом шаге алгоритма в за- замыкание [B]_Ω помещают все элементы множества В, а затем применяют операции сигнатуры Ω к исходным и вновь получаемым элементам до тех пор, пока не перестанут появляться новые элементы.

Иначе это можно описать так:

1) все элементы множества В₀ считаются и элементами замыкания Ω;

2) каковы бы ни были элементы b₁, ..., b_n, относительно которых известно, что они принадлежат [B]_Ω (т.е. какому-то множеству B_i из определенного выше семейства), к имеющимся элементам замыкания [B]_Ω добавляют все элементы ω(b₁, ..., b_n) для произвольной n-арной операции ω сигнатуры Ω.

Никакие другие элементы, кроме тех, что могут быть получены рассмотренным выше способом, замыканию [B]_Ω не принадлежат.

Образно говоря, В — это „детали конструктора", a [B]_Ω — все, что можно собрать из этих деталей по некоторым заранее оговоренным „правилам сборки" (каковыми являются операции сигнатуры Ω). #

Рассмотрим примеры построения Ω-замыкания.

Пример 4.2. а. В алгебре (ℕ, +) возьмем одноэлементное множество В = {1} = В₀. Тогда В₁ = {1,2}, В₂ = {1,2,3,4}, В₃ = {1, 2,3,4,5,6,7,8} и т.д. Множество В_i при i ≥ 1 состоит из всех сумм вида m + m, где m, n ∈ B_i-1. Несложно заметить, что B_i = {1,2,..., k,..., 2k}, где k = 2^i-1, i ≥ 0. Ясно, что в данном случае и, таким образом, множество {1} является системой образующих этой алгебры.

б. В мультипликативной группе вычетов по модулю 23 (т.е. в группе Z^*23) построим замыкание множества В = {3}, полагая, что сигнатура группы состоит из единственной операции умножения (по модулю 23).

Поскольку в этой алгебре сигнатура состоит из одной операции, а исходное множество В также одноэлементно, то замыкание В будет состоять из всех степеней элемента 3. Итак, для построения замыкания множества В в данном случае достаточно вычислять последовательно степени (по модулю 23) элемента 3. Имеем

3² = 9, 3³ = 4,  3⁴ = 4⋅3 = 12, 3⁵ = 12⋅3 = 13,

З⁶ = 13⋅3 = 16,  3⁷ = 16⋅3 = 2,  З⁸ = 2⋅3 = 6,

З⁹ = 6⋅3 = 18,  3¹⁰ = 18⋅3 = 8,  3¹¹ = 8⋅3 = 1.

Так как получена единица, то „круг замкнулся", и тем самым вычислено замыкание множества {3}. Заметим, что в этом случае множество В₁ состоит из всех степеней тройки, начиная с первой и кончая второй, множество В₂ — из всех степеней, начиная с первой и кончая четвертой, множество В₃ — из всех степеней с первой по восьмую, а множество В₄ — из всех степеней с первой по 16-ю, но поскольку начиная с 12-й степени элементы повторяются, т.е. 3¹² = 3, 3¹³ = 32, З¹⁴ = 33, 3¹⁵ = 34 и, наконец, 3¹⁶ = 35, то уже множество В₅ совпадет с множеством B₄, так что в данном случае [B]_{⋅} = В₄ .

Порожденная множеством {3} группа совпала с циклической подгруппой группы ℤ₂₃ с образующим элементом 3. Этот результат легко обобщить, доказав, что для произвольной конечной группы g = (G, ⋅), рассматриваемой как алгебра с сигнатурой, состоящей только из операции умножения, ее циклическая подгруппа с образующим элементом а совпадает с подгруппой, порожденной множеством {а}. #

Циклическая группа есть один из важнейших примеров конечно порожденной алгебры.

В этой связи обратим внимание на одну тонкость. Если g — циклическая группа с образующим элементом а, то ее, вообще говоря, нельзя рассматривать как алгебру с системой образующих {а}. Все зависит от конкретной сигнатуры груп- группы. Действительно, если в сигнатуру группы включить только умножение, то для бесконечной циклической группы 1 ≠ аⁿ для любого положительного n. Поэтому замыкание множества {а} относительно умножения не содержит единицу. Если же сигнатуру группы как алгебры дополнить унарной операцией взятия обратного, т.е. возведения в степень —1, то циклическая группа с образующим элементом а будет алгеброй с системой образующих {а}. При таком подходе аддитивная группа целых чисел, рассматриваемая как алгебра (ℤ, +, -, 0), есть бесконечная циклическая группа, порожденная множеством {1}.

Пример 4.3. а. Алгебра (ℤ, ⋅, 1) (мультипликативный моноид кольца целых чисел) не является конечно порожденной. Действительно, в этом моноиде в систему образующих необходимо включить все простые числа, поскольку ни одно из них нельзя представить как произведение других чисел. Но множество простых чисел бесконечно.

б. Любая конечная алгебра будет, разумеется, и конечно порожденной. В частности, любое кольцо вычетов по модулю к (поле вычетов при простом k) — конечно порожденная алгебра, даже если в сигнатуре нет операции нахождения обратного элемента.

в. Свободный моноид, порожденный конечным множеством (алфавитом) А есть конечно порожденная (и бесконечная) алгебра, система образующих которой равна А ∪ {λ}, где А — пустой кортеж.

г. Хорошим примером замыкания служит линейная оболочка заданного множества векторов произвольного линейного пространства [IV]. Как известно, линейная оболочка V мно- множества векторов x₁, ..., х_m линейного пространства L есть множество всех линейных комбиниций вида , где x_i ∈ V, i = 1, m, m ≥ 1. Линейная оболочка замкнута относительно операций сложения векторов и умножения вектора на число, так как линейная оболочка множества векторов является линейным подпространством. Более того, линейная оболочка V множества векторов x₁, ..., х_m — это наименьшее (относительно отношения включения множеств) замкнутое множество, содержащее заданное множество векторов, поскольку любое замкнутое множество, содержащее векторы x₁, ..., х_m, содержит и все их линейные комбинации, т.е. включает в себя V. Отметим, что конечномерное линейное пространство — конечно порожденная алгебра, так как оно является линейной оболочкой любого из своих базисов.