Algebra3
.pdfДействительно, из леммы 3.1 следует, что если B — булева алгебра в смысле определения 3.2, то для любого a B элемент a′ B однозначно определен. Следовательно, существует алгебраическая операция ′ : B → B. Выполнение тождеств (Б2) и (Б3) очевидно из определений.
Предложение 3.3. Пусть B — булева алгебра. Тогда для любых a, b B выполняются равенства
(1)(a′)′ = a;
(2)(a b)′ = a′ b′, (a b)′ = a′ b′.
Доказательство. (1) Вытекает из единственности дополнения.
(2) Проверим, что c = a′ b′ является дополнением для a b:
(a b) c = (a b) (a′ b′) = (a b a′) (a b b′) = 1 1 = 1, (a b) c = (a c) (b c) = (a a′ b′) (b a′ b′) = 0 0 = 0.
Следовательно, c = (a b)′. |
Второе равенство проверяется |
аналогично. |
|
Пример 3.4. Множество {0, 1} с операциями сигнатуры FBoole, заданными очевидным образом, является булевой алгеброй, которая обозначается 2.
Пример 3.5. Дистрибутивная решетка P(X) всех подмножеств данного множества X является булевой алгеброй с естественным дополнением
Y ′ = X \ Y, Y X.
Пример 3.6. Алгебра 2X булевозначных функций на множестве X относительно операций
= «или», = «и», ′ = «не»,
является булевой алгеброй.
Заметим, что булева алгебра из примера 3.6 изоморфна
прямому произведению |
Y |
|
|
2 |
x X
двухэлементных булевых алгебр из примера 3.4.
71
Кроме того, алгебры из примеров 3.5 и 3.6 изоморфны. Действительно, отображение
χ : P(X) → 2X ,
которое подмножеству Y X ставит в соответствие его характеристическую функцию
(
χ(Y ) : x 7→
1, x Y,
0, x / Y,
является изоморфизмом булевых алгебр.
Предложение 3.7. Любая булева алгебра изоморфна под- алгебре в булевой алгебре P(X) подмножеств некоторого множества X.
Доказательство. Пусть B — булева алгебра. Согласно теореме 2.10 существует инъективный гомоморфизм ϕ решетки (B, , ) в решетку P(X) для некоторого множества X. Конструкция этого гомоморфизма такова, что ϕ(0) = , ϕ(1) = X. Отсюда следует, что ϕ является гомоморфизмом булевых алгебр. Действительно, поскольку ϕ — гомоморфизм решеток, то
X = ϕ(a a′) = ϕ(a) ϕ(a′), = ϕ(a a′) = ϕ(a) ∩ ϕ(a′)
для любого a B. Так как дополнение в P(X) определено единственным образом, ϕ(a′) = X \ ϕ(a).
Для конечных булевых алгебр верен гораздо более тонкий результат: любая такая алгебра изоморфна булевой алгебре вида P(X) для некоторого конечного множества X. Мы приведем два подхода к доказательству этого утверждения (известного как теорема Стоуна для булевых алгебр), использующие связи булевых алгебр с кольцами и топологическими пространствами.
72
3.2. Булевы кольца. Пусть B = (B, , , ′, 0, 1) — бу-
лева алгебра. Определим на множестве B новые алгебраи-
ческие операции
+ : B × B → B,
· : B × B → B, |
|
− : B → B |
|
следующим образом: для любых a, b B |
|
a + b = (a′ b) (a b′), |
|
a · b = a b, |
(3.1) |
− a = a. |
|
Символ · в дальнейшем будем опускать.
Предложение 3.8. Если B — булева алгебра, то алге- браическая система B = (B, +, ·, −, 0, 1) является комму- тативным кольцом с единицей, причем B |= x2 ≈ x.
Доказательство. Проверка всех аксиом кольца для операций +, ·, − и констант 0, 1 проводится непосредственно. Для примера покажем, почему выполняется условие ассоциативности сложения.
Из определения операции + очевидно, что a+b = b+a для любых a, b B. Пользуясь предложением 3.3 и тождеством дистрибутивности, для любых a, b, c B получаем
a+ (b + c) = a + (b′ c) (b c′)
=[a′ ((b′ c) (b c′))] [a ((b′ c) (b c′))′]
=[(a′ b′ c) (a′ b c′)] [a (b′ c)′ (b c′)′] = x y,
где
x = (a′ b′ c) (a′ b c′), y = a (b′ c)′ (b c′)′.
Продолжим вычисление y:
a(b′ c)′ (b c′)′ = a (b c′) (b′ c)
=((a b) (a c′)) (b′ c) = (a b (b′ c)) (a c′ (b′ c))
=(a b b′) (a b c) (a c′ b′) (a c′ c)
=(a b c) (a c′ b′).
73
Таким образом,
a + (b + c) = (a′ b′ c) (a′ b c′) (a b c) (a c′ b′).
С другой стороны,
(a + b) + c = c + (a + b)
= (c′ a′ b) (c′ a b′) (c a b) (c b′ a′).
Как видим, a + (b + c) = (a + b) + c.
Остальные аксиомы кольца, нейтральность константы 1 по умножению и выполнение тождества x2 ≈ x проверяются аналогично.
Кольцо с единицей
R = (R, +, ·, −, 0, 1)
называется булевым, если
R |= x2 ≈ x.
Заметим, что любое булево кольцо коммутативно и операция − действует на его элементах тождественно. Действительно, для любых a, b R
a + a = (a + a)2 = a2 + a2 + a2 + a2 = a + a + a + a,
откуда a + a = 0;
a + b = (a + b)2 = a2 + ab + ba + b2 = a + ab + ba + b2,
откуда следует, что ab + ba = 0 и ab = ba.
Пусть R = (R, +, ·, −, 0, 1) — булево кольцо. Введем на множестве R алгебраические операции , , ′ по правилу
a b = a + b + ab, |
|
a b = ab, |
(3.2) |
a′ = 1 + a. |
|
Предложение 3.9. Если R — булево кольцо, то алгебра- ическая система R = (B, , , ′, 0, 1) является булевой ал- геброй.
74
Доказательство. Достаточно проверить все аксиомы булевой алгебры, т. е. показать, что на R выполняются тождества решетки (Р1)–(Р4) из предложения 2.2, тождество дистрибутивности (Д1) или (Д2) из п. 2.2, а также условия (Б1)–(Б3), характеризующие булеву алгебру. Проверим, например, дистрибутивность:
a (b c) = a(b + c + bc) = ab + ac + abc,
(a b) (a c) = ab ac = ab + ac + (ab)(ac) = ab + ac + abc
для любых a, b, c R. |
|
Теорема 3.10. (1) Для любой булевой алгебры B выпол- няется равенство (B ) = B.
(2) Для любого булева кольца R выполняется равенство
(R ) = R.
Доказательство. (1) Согласно конструкции, булева ал-
гебра
B = (B, , , ′, 0, 1),
булево кольцо
B = (B, +, ·, −, 0, 1)
и булева алгебра
|
|
|
˜ |
˜ ˜ |
˜ |
˜ |
′ |
(B ) = (B, , , , 0, 1),
являются алгебраическими системами с одним и тем же мно-
жеством элементов Кроме того ˜ ˜ Остается
B. , 0 = 0, 1 = 1.
показать, что операции ˜, ˜, ˜′ совпадают соответственно с
, , ′.
Действительно, a ˜ b = ab = a b для любых a, b B по
(3.1), (3.2). Кроме того,
a˜′ = 1 + a = (1′ a) (1 a′) = 0 a′ = a′.
Наконец,
a ˜ b = a + b + ab = a + (b′ (a b)) (b (a b)′)
=a + 0 (b (a′ b′)) = a + a′ b = (a′ a′ b) (a (a′ b)′)
=(a′ b) (a (a b′)) = (a′ b) (a a) (a b′)
=(a′ b) a (a b′) = (a′ b) a = (a′ a) (b a) = a b
75
Доказательство утверждения (2) полностью аналогично.
Из определения операций (3.1) следует, что если ϕ : B1 → B2 — гомоморфизм булевых алгебр, то ϕ является гомоморфизмом булевых колец B1 → B2 . Обратно, из (3.2) легко видеть, что любой гомоморфизм булевых колец является гомоморфизмом булевых алгебр.
В частности, если B — булева алгебра, θ B × B — бинарное отношение, то θ Cong B в том и только том случае, когда θ Cong B . Действительно, если θ — отношение эквивалентности, являющееся конгруэнцией булевой алгебры или кольца, то отображение τθ : B → B/θ является естественным гомоморфизмом и булевых алгебр, и колец. Следовательно, Ker τθ = θ является конгруэнцией и булевой алгебры, и кольца.
Предложение 3.11. Пусть B — булева алгебра, 6= I B. Тогда I является идеалом кольца B в том и только том случае, когда I — идеал дистрибутивной решетки B, т. е.
(i)a b I для всех a, b I,
(ii)a x I для всех a I, x B,
Доказательство. ( ) Пусть I E B . Тогда a + b I
для любых a, b I. Но
a b = a + b + ab, ab I a b I.
Далее, a x = ax I для любых a I, x B.
( ) Достаточно проверить замкнутость относительно сложения:
a+ b = (a′ b) (a b′) = (a′ a) (a′ b′) (b a) (b b′)
=(a′ b′) (a b) I,
поскольку a b I.
Таким образом, для любой конгруэнции θ булевой алгебры B существует идеал I E B такой, что
(a, b) θ a + b I.
76
Верно и обратное: любой идеал I E B определяет конгру-
энцию булевой алгебры B. |
|
|
|
|||
|
|
Пусть B — булева алгебра, a B. Рассмотрим множе- |
||||
|
|
|
|
|
|
˜ |
ство [0, a] B как алгебру сигнатуры FBoole с операциями , |
||||||
|
′ |
˜ |
˜ |
|
|
|
˜ |
˜ |
|
|
|
|
|
|
, 0, 1, где |
|
|
|
||
, |
|
|
′ ˜ |
˜ |
||
|
|
|
|
′ |
||
|
˜ |
˜ |
˜ |
|
|
x y = x y, x y = x y, x = a x , 0 = 0, 1 = a.
Легко убедиться, что отображение
πa : B → [0, a], πa(x) = a x,
является гомоморфизмом алгебр сигнатуры FBoole, следова-
˜ ˜ ˜′ ˜ ˜
тельно, ([0, a], , , , 0, 1) — булева алгебра, которую мы будем обозначать через B|a.
Булева алгебра B|a является гомоморфным образом булевой алгебры B при гомоморфизме πa. Отображение πa является также гомоморфизмом колец, поэтому идеал Ia, определяющий конгруэнцию Ker πa, состоит из всех таких x B, что πa(x) = 0.
Проверим, что
Ia = {x B | x ≤ a′}.
( ) Если πa(x) = a x = 0, то a′ = 0 a′ = (a x) a′ = (a a′) (x a′) = x a′, т. е. a′ ≥ x.
( ) Если x ≤ a′, то a x ≤ a a′ = 0, т. е. πa(x) = a x = 0.
Теорема 3.12. Пусть B — булева алгебра, причем |B| > 2. Тогда для любого a B, a 6= 0, 1,
B B|a × Ba′ .
Доказательство. Ввиду теоремы 1.15 достаточно показать, что пара конгруэнций πa, πa′ образует полную независимую систему конгруэнций. Полнота означает
Ker πa ∩ Ker πa′ = B.
Действительно, пересечение ядер гомоморфизмов πa и πa′ определяется пересечением соответствующих идеалов Ia и Ia′ . Но
Ia ∩ Ia′ = {x B | x ≤ a, x ≤ a′} = {0},
77
так как для любого x ≤ a, x ≤ a′ имеем
x = x x ≤ a x ≤ a a′ = 0.
Независимость означает, что для любых a1, a2 B найдется b B такое, что (a1, b) Ker πa, (a2, b) Ker πa′ . Возьмем
b = a2 + aa1 + aa2.
Тогда
b+a1 = (a1+a2)+a(a1+a2) = (a1+a2)(1+a) = (a1+a2) a′ ≤ a′,
b + a2 = a2 + a2 + aa1 + aa2 = a(a1 + a2) ≤ a, |
|
т. е. b + a1 Ia, b + a2 Ia′ , что и требовалось. |
|
Следствие 3.13. Если B — прямо неразложимая булева алгебра, то B 2.
Следствие 3.14 (теорема Стоуна). Если B — конечная булева алгебра, то B P(X) для некоторого конечного множества X.
Доказательство. По теореме 1.18 конечная булева алгебра B изоморфна прямому произведению (конечного числа) прямо неразложимых, каждая из которых, в свою очередь, изоморфна 2. Следовательно,
B 2n = 2 × · · · × 2. |
|
Мы уже отмечали, что 2n P({1, . . . , n}). |
|
Упражнение. Докажите, что свободная булева алгебра, по-
рожденная конечным множеством из n элементов, изоморфна
2n = 2 × · · · × 2.
3.3. Фильтры и ультрафильтры булевых алгебр.
Пусть B — булева алгебра. Подмножество F B называется фильтром булевой алгебры B, если
(Ф1) a b F для любых a, b F ; (Ф2) a x F для любых a F , x B.
Фильтр F называется собственным, если F 6= B, т. е. 0 / F . Максимальный по включению собственный фильтр называется ультрафильтром.
78
Предложение 3.15. Множество F B является (соб- ственным) фильтром или ультрафильтром булевой алге- бры B тогда и только тогда, когда
F ′ = {x′ | x F } B
является (собственным) идеалом или соответственно мак- симальным идеалом булева кольца B .
Доказательство. Легко заметить, что определяющие свойства идеала и фильтра двойственны друг другу (см. предложения 3.3 и 3.11).
Сохранение максимальности по включению вытекает из монотонности операции ′ на множествах:
F1 ( ) F2 F1′ ( ) F2′.
Предложение 3.16. Пусть F — собственный фильтр бу- левой алгебры B, a / F . Тогда существует такой ультра- фильтр U B, что F U, a / U.
Доказательство. Рассмотрим множество MF,a, состоящее из всех собственных фильтров алгебры B, включающих F и не содержащих a. Рассмотрим произвольную цепь относительно включения в этом множестве:
F1 F2 . . . .
Очевидно, что объединение возрастающей цепи фильтров снова является фильтром. Поскольку a / Fk для всех k ≥ 1, то a / Sk≥1 Fk. Следовательно, любая цепь в множестве MF,a имеет верхнюю грань в этом же множестве. По лемме Цорна множество MF,a содержит максимальный по включению элемент U.
Покажем, что U является ультрафильтром булевой алгебры B. Достаточно убедиться в том, что идеал J = U′ является максимальным в B .
Если x, y / J = U′, U MF,a максимальный в этом множестве, то xy / J.
Действительно, допустим, найдутся такие x, y / J, что xy J. Если x / J, то J1 = J + xB — идеал кольца B ,
79
причем J J1. Следовательно, фильтр J1′ / MF,a, т. е.
a J1′ . Следовательно, a′ J1:
a′ = z1 + xb1, z1 J, b1 B.
Аналогично,
a′ J + yB a′ = z2 + yb2, z2 J, b2 B.
Отсюда
a′ = a′a′ = (z1 + xb1)(z2 + yb2)
= z1z2 + z1yb2 + z2xb1 + (xy)(b1b2) J,
— противоречие.
Таким образом, B /J — булево кольцо без делителей нуля. Но для любого x B
x2 − x = 0 = x(x − 1),
откуда x = 0 или x = 1. Следовательно, B /J 2 — простое кольцо, и поэтому J — максимальный идеал.
Предложение 3.17. Множество F B является ультра- фильтром булевой алгебры B тогда и только тогда, когда для любого a B либо a F , либо a′ F .
Доказательство. ( ) Пусть F — ультрафильтр, тогда I = F ′ — максимальный идеал в кольце B . Тогда кольцо B /I является простым булевым кольцом. Простое коммутативное кольцо с единицей, очевидно, является полем. Но так как B /I |= x2 ≈ x, то в этом поле только два
элемента 0 + I и 1 + I. Следовательно,
(
a + F = |
0 + I a I = F ′ a′ F, |
||
1 + I a + 1 |
I = F ′ a′ F ′ a F. |
||
|
( ) Если фильтр F не является максимальным по включению собственным фильтром, т. е. найдется фильтр F1 такой, что F F1 B, то для любого элемента a F1 \ F , его дополнение лежит в F . Если a′ F F1, то F1 a, a′, следовательно, 0 = a a′ F1 и F1 = B, — противоречие.
80