Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
, . . . , a k )) определяется по индукции: 1) если t есть переменная x i (константный символ c), то значение t есть a i (соответственно c); 2) если терм t есть f (t 1 , . . . , t n ), а значения t 1 , . . . , t n суть b 1 , . . . , b n , то зна- чение терма t есть f (b 1 , . . . , b n ). Теорема 2.3.2. Если B = hB; Σi — алгебраическая система, ∅ 6= X ⊆ B, то носитель подсистемы B(X) равен {t(a 1 , . . . , a n ) | t ∈ T (Σ), a 1 , . . . , a n ∈ X}. Доказательство. Индукцией по числу шагов построения терма t по- лучаем, что если t(x 1 , . . . , x n ) ∈ T (Σ) и a 1 , . . . , a n ∈ X, то t(a 1 , . . . , a n ) ∈ X для любой подсистемы A ⊆ B, содержащей X. Поэтому достаточно пока- зать, что множество Y {t(a 1 , . . . , a n ) | t ∈ T (Σ), a 1 , . . . , a n ∈ X} замкнуто относительно операций системы B. Пусть f (m) ∈ T (Σ), t 1 , . . . , t m ∈ T (Σ), b i = t i (a 1 , . . . , a n ) ∈ Y , i = 1, . . . , m. Тогда f (b 1 , . . . , b m ) ∈ Y , поскольку f (t 1 , . . . , t m ) ∈ T (Σ). ¤ 62 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Таким образом, носитель подсистемы B(X) состоит из всех элементов, которые получаются при подстановке элементов из X в термы. Пример 2.3.4. 1. Найдем носитель подсистемы B(X) системы B = hQ \ {0}; ·i для множества X = { 1 2 }. Так как сигнатура Σ системы B есть {·}, то T (Σ) = {x 1 , x 1 · x 2 , (x 1 · x 2 ) · x 3 , x 1 · (x 2 · ·x 3 ), . . .}. По теореме 2.3.2 получаем B(X) = { 1 2 , 1 2 · 1 2 , 1 2 · 1 2 · 1 2 , . . .} = { 1 2 , 1 4 , 1 8 , 1 16 , . . .} = { 1 2 n | n > 1}. 2. Если B = hQ \ {0}; ·, :i, X = { 1 2 }, то, поскольку по сравнению с предыдущим примером сигнатура дополняется операцией деления x : y, множество B(X) содержит также числа 1 2 n : 1 2 m = 2 m−n , m, n > 1, т. е. C = {2 n | n ∈ Z} ⊆ B(X). Так как множество C замкнуто относительно операций умножения и деления, т. е. hC; Σi является подсистемой системы B и содержит множество X, то B(X) ⊆ C. Следовательно, B(X) = C. 3. Найдем носитель подсистемы B(X) системы B = hC; +, . ıi для множе- ства X = {−2, 2}. Так как все термы из T (Σ) являются переменными, кон- стантой . ı или образуются из переменных и константы . ı с помощью операции сложения, то каждый элемент из B(X) получается подстановкой элементов из X в некоторый терм x 1 + x 2 + . . . + x m + . ı + . ı + . . . + . ı. Следовательно, B(X) = {2m + ni | m ∈ Z, n ∈ ω}. ¤ § 2.4. Конгруэнции. Фактор-алгебры. Теорема о гомоморфизме Конгруэнцией на алгебре A = hA; Σi называется такое отношение эквива- лентности θ ⊆ A 2 , при котором для любого n ∈ ω, любого n-местного симво- ла f ∈ Σ (напомним, что сигнатура алгебры состоит только из функциональ- ных символов), произвольных наборов (a 1 , a 2 , . . . , a n ), (b 1 , b 2 , . . . , b n ) ∈ A n , если a 1 θ b 1 , a 2 θ b 2 , . . . , a n θ b n , то f (a 1 , a 2 , . . . , a n ) θ f (b 1 , b 2 , . . . , b n ). Это означает, что все операции согласованы с отношением эквивалент- ности θ. Например, для операции сложения это выглядит так: для любых элементов x, y ∈ A, любых a ∈ θ(x), b ∈ θ(y) элемент a + b принадлежит классу θ(x + y). Рассмотрим фактор-множество множества A по конгруэнции θ: A/θ = {θ(x) | x ∈ A}. Определим на этом множестве алгебру сигнатуры Σ. Константе c алгебры A поставим в соответствие элемент θ(c), который в A/θ 2.4. КОНГРУЭНЦИИ. ФАКТОР-АЛГЕБРЫ. ТЕОРЕМА О ГОМОМОРФИЗМЕ 63 будет интерпретировать константный символ c. Если f — n-местный символ из Σ, то зададим на множестве A/θ действие функции f по правилу f (θ(x 1 ), . . . , θ(x n )) θ(f (x 1 , . . . , x n )). Убедимся, что для любых x 1 , . . . , x n ∈ A это определение корректно, т. е. не зависит от выбора представителей классов эквивалентности. Действи- тельно, если θ(x i ) = θ(y i ), i = 1, 2, . . . , n, то x i θ y i , откуда в силу свойства конгруэнции имеем f (x 1 , . . . , x n ) θf (y 1 , . . . , y n ), т. е. θ(f (x 1 , . . . , x n )) = θ(f (y 1 , . . . , y n )). Получившаяся алгебра A/θ hA/θ; Σi называется фактор-алгеброй ал- гебры A по конгруэнции θ. Очевидно, что отображение A → A/θ, при котором элементу x ∈ A ста- вится в соответствие класс θ(x), является эпиморфизмом алгебры A на фактор-алгебру A/θ. Этот эпиморфизм называется естественным гомо- морфизмом. Если ϕ: A → B — гомоморфизм алгебр, то множество Ker ϕ {(a, a 0 ) | ϕ(a) = ϕ(a 0 )} оказывается конгруэнцией на алгебре A и называется ядром гомомор- физма ϕ. Докажем теорему, согласно которой гомоморфный образ алгебры изо- морфен фактор-алгебре по ядру гомоморфизма. Теорема 2.4.1 (теорема о гомоморфизме). Если ϕ: A → B — эпи- морфизм, ψ: A → A/Ker ϕ — естественный гомоморфизм, то существует изоморфизм χ: B ∼ → A/Ker ϕ такой, что ϕ ◦ χ = ψ. Доказательство. Положим χ(b) = ψ(a), где a ∈ A выбрано так, что b = ϕ(a). Если b = ϕ(a 0 ), то (a, a 0 ) ∈ Ker ϕ, откуда ψ(a) = ψ(a 0 ). Следо- вательно, отображение χ определено корректно. Равенство ϕ ◦ χ = ψ оче- видно. Из него вытекает, что χ — сюръекция. Непосредственно проверяется, что χ — гомоморфизм. Если χ(b) = χ(b 0 ), то ψ(a) = ψ(a 0 ), где b = ϕ(a), b 0 = ϕ(a 0 ). Отсюда (a, a 0 ) ∈ Ker ϕ, следовательно, b = b 0 , что доказывает взаимную однозначность отображения χ. Так как сигнатура функциональ- на, из существования функции χ −1 и того, что χ — гомоморфизм, следует, что χ является изоморфизмом. ¤ 64 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ - • ? ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ ½ = • • A B A/Ker ϕ ϕ ψ χ ' Рис. 2.1 Отображения ϕ, ψ и χ из теоремы 2.4.1 можно представить диаграммой, показанной на рис. 2.1. § 2.5. Декартовы произведения алгебр. Теорема Биркгофа Пусть A i , i ∈ I, — семейство множеств. Декартовым произведением мно- жеств A i , i ∈ I, называется множество Y i∈I A i {f | f : I → ∪ i∈I A i , где f (i) ∈ A i для всех i}. Отметим, что если I = {1, 2, . . . , n} — конечное множество индексов, де- картово произведение Y i∈I A i = {f | f : I → n ∪ i=1 A i , где f (1) ∈ A 1 , . . . , f (n) ∈ A n } можно взаимно однозначно рассматривать как множество n Y i=1 A i = {(f (1), . . . , f (n)) | f : I → n ∪ i=1 A i , где f (1) ∈ A 1 , . . . , f (n) ∈ A n }. Таким образом, данное определение согласуется с введенным ранее опреде- лением декартова произведения конечного числа множеств. 2.5. ДЕКАРТОВЫ ПРОИЗВЕДЕНИЯ АЛГЕБР. ТЕОРЕМА БИРКГОФА 65 Пусть A i = hA i ; Σi, i ∈ I, — некоторые алгебры сигнатуры Σ. Декарто- вым произведением алгебр A i , i ∈ I, называется алгебра Y i∈I A i * Y i∈I A i ; Σ + , в которой функциональные символы F (n) ∈ Σ интерпретируются по сле- дующему правилу: для любых функций f 1 , . . . , f n ∈ Q i∈I A i полагаем F (f 1 , . . . , f n ) f , где f (i) = F A i (f 1 (i), . . . , f n (i)) для любого i ∈ I. Если I = {1, 2, . . . , n}, то декартово произведение алгебр Q i∈I A i будем, как и для множеств, обозначать через A 1 × A 2 × . . . × A n Пример 2.5.1. Для алгебр A 1 = hA 1 ; + 1 i, A 2 = hA 2 ; + 2 i операция + декартова произведения A 1 × A 2 = hA 1 × A 2 ; +i задается соотношением (a 1 , a 2 ) + (a 0 1 , a 0 2 ) = (a 1 + 1 a 0 1 , a 2 + 2 a 0 2 ). ¤ Пусть t 1 , t 2 — термы сигнатуры Σ. Запись t 1 ≈ t 2 называется тожде- ством сигнатуры Σ. Эта запись означает, что любые значения, вычислен- ные по терму t 1 , совпадают с соответствующими значениями, вычисленными по терму t 2 Пример 2.5.2. Если t 1 = x + y, t 2 = y + x — термы сигнатуры Σ = {+}, то тождество x + y ≈ y + x означает, что для символа + выполняется закон коммутативности. ¤ Класс K алгебр сигнатуры Σ называется многообразием, если существует множество тождеств T = {t j 1 ≈ t j 2 | j ∈ J} сигнатуры Σ такое, что алгеб- ра сигнатуры Σ принадлежит классу K тогда и только тогда, когда в ней выполняются все тождества из множества T . Пример 2.5.3. Множеством тождеств {x · (y · z) ≈ (x · y) · z, x · e ≈ x, e · x ≈ x} сигнатуры Σ = {· (2) , e (0) } определяется многообразие, состоящее из всех моноидов. ¤ Теорема 2.5.1 (теорема Биркгофа). Непустой изоморфно замкнутый класс алгебр K сигнатуры Σ тогда и только тогда является многообрази- ем, когда K замкнут относительно подалгебр, фактор-алгебр и декартовых произведений, т. е. класс K вместе с каждой алгеброй содержит любую ее подалгебру, фактор-алгебру, а также вместе с любым семейством алгебр содержит их декартово произведение. ¤ 66 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ § 2.6. Решетки и булевы алгебры Следующей нашей целью является определение и изучение понятия бу- левой алгебры, но сначала рассмотрим более общее понятие — понятие ре- шетки. Решеткой называется ч.у.м. A = hA; 6i, в котором каждая пара эле- ментов имеет супремум и инфимум. Для заданных элементов x, y ∈ A эле- мент inf{x, y} называется пересечением элементов x и y (обозначается x∧y), а sup{x, y} называется объединением элементов x и y (обозначается x ∨ y). Заметим, что если в системе A введены операции ∧ и ∨, то от- ношение 6 можно по этим операциям восстановить следующим образом: x 6 y ⇔ x ∧ y = x, а также x 6 y ⇔ x ∨ y = y. Наименьший (наибольший) элемент решетки, если он существует, назы- вается нулем (единицей). Обозначаются эти элементы соответственно через 0 и 1. В конечных решетках всегда имеются нуль и единица. Пример 2.6.1. 1. Любое линейно упорядоченное множество является решеткой. 2. Рассмотрим ч.у.м. A = h{a, b, c, d, e}; 6i, в котором a < b, a < c, a < d, b < e, c < e, d < e, а элементы b, c, d попарно несравнимы. Система A образует решетку, показанную на рис. 2.2. В этой решетке a = 0, e = 1. 3. Если |A| > 1, то ч.у.м. hA; id A i не является решет- • • • • • ¡ ¡ ¡ ¡ @ @ @ @ ¡ ¡ ¡ ¡ @ @ @ @ a e c b d Рис. 2.2 кой, поскольку для любых различных элементов x и y не определены операции inf{x, y} и sup{x, y} по отно- шению id A . ¤ Определим решетку подсистем системы B = hB; Σi, содержащих непустое множество X ⊆ B. Рассмотрим множество L(B, X) {A | A = hA; Σi ⊆ B и X ⊆ A} и зададим на нем частичный порядок 6 по следующему правилу: A 1 6 A 2 ⇔ A 1 ⊆ A 2 . Пара hL(B, X); 6i образует решетку подсистем. В этой решетке для любых систем A 1 = hA 1 ; Σi, A 2 = hA 2 ; Σi из L(B, X) пересечение A 1 ∧ A 2 есть подсистема hA 1 ∩ A 2 ; Σi, а объединение A 1 ∨ A 2 — подсистема, порожденная множеством A 1 ∪ A 2 : B(A 1 ∪ A 2 ). Пример 2.6.2. Рассмотрим линейное пространство V и множе- ство L(V, {0}) подпространств пространства V . Система hL(V, {0}); 6i, где V 1 6 V 2 ⇔ V 1 — подпространство V 2 , образует решетку подпространств, в которой V 1 ∧ V 2 = V 1 ∩ V 2 , V 1 ∨ V 2 = L(V 1 ∪ V 2 ). ¤ 2.6. РЕШЕТКИ И БУЛЕВЫ АЛГЕБРЫ 67 Пусть A = hA; Σi — алгебра, Con A {θ | θ — конгруэнция на A}. На множестве конгруэнций Con A зададим отношение 6 по следующему правилу: θ 1 6 θ 2 ⇔ для любых элементов a, b ∈ A из условия a θ 1 b выте- кает a θ 2 b. Это означает, что каждый θ 2 -класс состоит из θ 1 -классов. Систе- ма hCon A; 6i образует решетку конгруэнций. В этой решетке пересечение θ 1 ∧ θ 2 конгруэнций θ 1 и θ 2 удовлетворяет следующему условию: для любых a, b ∈ A тогда и только тогда a (θ 1 ∧ θ 2 ) b, когда a θ 1 b и a θ 2 b. Объединение θ 1 ∨ θ 2 конгруэнций θ 1 и θ 2 определяется следующим отношением: для лю- бых |