Упорядоченные множества и универсальная алгебра (вводный курс). Гуров С.И. - 11 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

Множество всех атомов, содержащихся в элементе x булевой алгебры будем обозна-
чать At(x). Без доказательства укажем два утверждения относительно конечных буле-
вых алгебр.
Лемма 1.6. Всякий ненулевой элемент конечной булевой алгебры может быть пред-
ставлен в виде объединения содержащихся в нём атомов:
x =
G
a∈At(x)
a .
Например, в тотальной алгебре над множеством {1, 2, 3, 4} элемент x = {1, 2, 3}
содержит атомы {1}, {2}, {3} и равен их объединению: x = {1} ∪ {2} ∪ {3}.
Лемма 1.7. Конечная булева алгебра является атомной.
Для конечного случая теорема Стоуна допускает следующее усиление.
Теорема 1.8. Всякая конечная булева алгебра изоморфна подходящей тотальной алгеб-
ре множеств.
Доказательство. Пусть B — конечная булева алгебра. Обозначим через At(B) мно-
жество всех её атомов. Построим тотальную алгебру множеств над At(B) и покажем,
что она изоморфна B.
Рассмотрим функцию ϕ, сопоставляющую каждому элементу x из B множество
At(x) содержащихся в нём атомов. Покажем, что ϕ является искомым изоморфизмом
между B и h P(At(B)), ∪, ∩,
−
, ∅, At(B) i.
Убедимся сначала, что ϕ(x) = At(x) — биекция
5
между B и P(At(B)). Действитель-
но, если ϕ(b
1
) = ϕ(b
2
), то
b
1
=
G
a∈At(b
1
)
a =
G
a∈ϕ(b
1
)
a =
G
a∈ϕ(b
2
)
a =
G
a∈At(b
2
)
a = b
2
,
и, значит, ϕ — инъективно. Далее, пусть A — произвольное подмножество атомов бу-
левой алгебры B. Определим x соотношением x =
F
a∈A
a. Тогда ϕ(x) = At(x) = A, т.е.
ϕ — сюръективно. Таким образом, биективность отображения ϕ показана.
Теперь удостоверимся, что для ϕ выполнены свойства (1)–(3) определения 1.3 (ни-
жеприведённые выкладки проведены для произвольных атома a и элементов x, y из
B ).
Во-первых, ясно, что At(x t y) = At(x) ∪ At(y), и поэтому
ϕ(x t y) = At(x t y) = At(x) ∪ At(y) = ϕ(x) ∪ ϕ(y)) .
Таким образом, показано выполнение свойства 1).
Во-вторых, законы дистрибутивности обеспечивают равенство
x u y =
G
a∈At(x)
a u
G
b∈At(y)
b =
G
a∈At(x)
b∈At(y)
a u b =
G
a∈At(x)∩At(y)
a ,
т.е. ϕ(x u y) = ϕ(x) ∩ ϕ(y), и поэтому свойство 2) выполнено.
В-третьих,
ϕ(x
0
) = At(x
0
) = At(B) r At(x) = ϕ(x) ,
т.е. свойство 3) выполнено.
5
Надеемся, читателю известны свойства инъективности, сюръективности и биективности отображе-
ний. Их определения даны в п. 1.4.2.
11
   Множество всех атомов, содержащихся в элементе x булевой алгебры будем обозна-
чать At(x). Без доказательства укажем два утверждения относительно конечных буле-
вых алгебр.
Лемма 1.6. Всякий ненулевой элемент конечной булевой алгебры может быть пред-
ставлен в виде объединения содержащихся в нём атомов:
                                        G
                                  x =       a.
                                               a∈At(x)

   Например, в тотальной алгебре над множеством {1, 2, 3, 4} элемент x = {1, 2, 3}
содержит атомы {1}, {2}, {3} и равен их объединению: x = {1} ∪ {2} ∪ {3}.
Лемма 1.7. Конечная булева алгебра является атомной.
      Для конечного случая теорема Стоуна допускает следующее усиление.
Теорема 1.8. Всякая конечная булева алгебра изоморфна подходящей тотальной алгеб-
ре множеств.
Доказательство. Пусть B — конечная булева алгебра. Обозначим через At(B) мно-
жество всех её атомов. Построим тотальную алгебру множеств над At(B) и покажем,
что она изоморфна B.
    Рассмотрим функцию ϕ, сопоставляющую каждому элементу x из B множество
At(x) содержащихся в нём атомов. Покажем, что ϕ является искомым изоморфизмом
между B и h P(At(B)), ∪, ∩, − , ∅, At(B) i.
    Убедимся сначала, что ϕ(x) = At(x) — биекция5 между B и P(At(B)). Действитель-
но, если ϕ(b1 ) = ϕ(b2 ), то
                           G       G         G         G
                  b1 =       a =       a =       a =       a = b2 ,
                        a∈At(b1 )   a∈ϕ(b1 )        a∈ϕ(b2 )         a∈At(b2 )

и, значит, ϕ — инъективно. Далее, пусть A — произвольное
                                                F         подмножество атомов бу-
левой алгебры B. Определим x соотношением x =      a. Тогда ϕ(x) = At(x) = A, т.е.
                                                               a∈A
ϕ — сюръективно. Таким образом, биективность отображения ϕ показана.
   Теперь удостоверимся, что для ϕ выполнены свойства (1)–(3) определения 1.3 (ни-
жеприведённые выкладки проведены для произвольных атома a и элементов x, y из
B ).
   Во-первых, ясно, что At(x t y) = At(x) ∪ At(y), и поэтому
                  ϕ(x t y) = At(x t y) = At(x) ∪ At(y) = ϕ(x) ∪ ϕ(y)) .
Таким образом, показано выполнение свойства 1).
   Во-вторых, законы дистрибутивности обеспечивают равенство
                        G        G         G              G
              xuy =         au       b =        aub =                                    a,
                         a∈At(x)    b∈At(y)         a∈At(x)              a∈At(x)∩At(y)
                                                    b∈At(y)


т.е. ϕ(x u y) = ϕ(x) ∩ ϕ(y), и поэтому свойство 2) выполнено.
    В-третьих,
                       ϕ(x 0 ) = At(x 0 ) = At(B) r At(x) = ϕ(x) ,
т.е. свойство 3) выполнено.
  5
   Надеемся, читателю известны свойства инъективности, сюръективности и биективности отображе-
ний. Их определения даны в п. 1.4.2.

                                               11

Страницы