Algebra3

Действительно, из леммы 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.

Пример 3.4. Множество {0, 1} с операциями сигнатуры FBoole, заданными очевидным образом, является булевой алгеброй, которая обозначается 2.

Пример 3.5. Дистрибутивная решетка P(X) всех подмножеств данного множества X является булевой алгеброй с естественным дополнением

Y ′ = X \ Y, Y X.

Пример 3.6. Алгебра 2X булевозначных функций на множестве X относительно операций

= «или», = «и», ′ = «не»,

является булевой алгеброй.

Заметим, что булева алгебра из примера 3.6 изоморфна

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,

Символ · в дальнейшем будем опускать.

Предложение 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 алгебраические операции , , ′ по правилу

Предложение 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

Теорема 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 определяет конгру-

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′,

Следствие 3.13. Если B — прямо неразложимая булева алгебра, то B 2.

Следствие 3.14 (теорема Стоуна). Если B — конечная булева алгебра, то B P(X) для некоторого конечного множества X.

Доказательство. По теореме 1.18 конечная булева алгебра B изоморфна прямому произведению (конечного числа) прямо неразложимых, каждая из которых, в свою очередь, изоморфна 2. Следовательно,

Упражнение. Докажите, что свободная булева алгебра, по-

рожденная конечным множеством из 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. Следовательно,

(

( ) Если фильтр F не является максимальным по включению собственным фильтром, т. е. найдется фильтр F1 такой, что F F1 B, то для любого элемента a F1 \ F , его дополнение лежит в F . Если a′ F F1, то F1 a, a′, следовательно, 0 = a a′ F1 и F1 = B, — противоречие.

80