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

UptoLike

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

Доказательство. По принципу двойственности достаточно доказать данное утвержде-
ние относительно фильтров.
Пусть F некоторый собственный фильтр булевой алгебры. Рассмотрим произволь-
ную последовательность фильтров, начинающуюся с F, где каждый следующий фильтр
содержит предыдущий. Получим цепь, причём объединение всех её элементов есть так-
же фильтр, который будет являться верхней гранью данной цепи. Применяя лемму
Куратовского-Цорна получаем, что каждый элемент любой такой цепи содержится в
некотором максимальном. Этот максимальный элемент и будет искомым максимальным
фильтром, содержащим F.
Утверждение данной теоремы относительно фильтров часто называют теоремой об
ультрафильтрах. Собственный фильтр булевой алгебры совпадает с пересечением всех
ультрафильтров, в которых он содержится.
Пример 39. Если a атом булевой алгебры B, то фильтр x
M
(главный) ультрафильтр
в B. Пересечение всех элементов такого фильтра есть a. В конечных булевых алгебрах
ультрафильтры других видов, очевидно, отсутствуют.
Главные ультрафильтры алгебры множеств, фиксированные в соответствующей точ-
ке, называют тривиальными. Совместно с фильтрами Фреше они играют важную роль
при исследовании сходимости в анализе (топологическая система окрестностей данной
точки является фиксированным в ней тривиальным ультрафильтром). Главные ультра-
фильтры также используют, например, при исследованиях полноты логических систем в
алгебрах L
Линденбаума-Тарского, порождённых соответствующей логической теорией
L.
19
Пример 40. Рассмотрим множество A = {A, B, . . .} формул алгебры логики (формул
над высказваниями). Если A B есть тождественно истинная формула, то говорят, что
формулы A и B логически эквивалентны или равносильны, что записывают как A B.
Ясно, что есть отношение эквивалентности на A. Класс эквивалентности, порождае-
мой формулой A будем обозначать [A], классы тождественно истинных формул T, а
тождественно ложных формул F.
На фактор-множестве A/ классов эквивалентности формул алгебры логики
[A] = [¬A], [A] [B] = [A B], [A] [B] = [A B] .
Легко видеть, что введённые операции над классами эквивалентностей имеют следу-
ющие свойства:
1) операции и коммутативны и взаимно дистрибутивны;
2) выполняются соотношения [A] F = [A] и [A] T = [A];
3) справедливы законы [A] [A] = T и [A] [A] = F.
Указанное означает, что АС L
= h A/, , ,
, T, F i является булевой алгеброй, ко-
торую называют фактор-алгеброй логических формул. Для классической алгебры выска-
зываний она совпадает с соответствующей алгеброй Линденбаума-Тарского. С каждым
элементом A/ связана соответствующая функция алгебры логики.
Обозначим через A
n
множество формул алгебры логики над n элементарными вы-
сказываниями. Очевидно, A
n
бесконечно, а фактор-множество A
n
/ конечно содер-
жит 2
2
n
элементов).
19
См., например, [11] или С.И. Гуров. Системы пропозициональной логики. www.cs.msu.ru Учеб-
ная работа Материалы по учебным курсам.
64
Доказательство. По принципу двойственности достаточно доказать данное утвержде-
ние относительно фильтров.
   Пусть F — некоторый собственный фильтр булевой алгебры. Рассмотрим произволь-
ную последовательность фильтров, начинающуюся с F , где каждый следующий фильтр
содержит предыдущий. Получим цепь, причём объединение всех её элементов есть так-
же фильтр, который будет являться верхней гранью данной цепи. Применяя лемму
Куратовского-Цорна получаем, что каждый элемент любой такой цепи содержится в
некотором максимальном. Этот максимальный элемент и будет искомым максимальным
фильтром, содержащим F .
   Утверждение данной теоремы относительно фильтров часто называют теоремой об
ультрафильтрах. Собственный фильтр булевой алгебры совпадает с пересечением всех
ультрафильтров, в которых он содержится.
Пример 39. Если a — атом булевой алгебры B, то фильтр xM — (главный) ультрафильтр
в B. Пересечение всех элементов такого фильтра есть a. В конечных булевых алгебрах
ультрафильтры других видов, очевидно, отсутствуют.
    Главные ультрафильтры алгебры множеств, фиксированные в соответствующей точ-
ке, называют тривиальными. Совместно с фильтрами Фреше они играют важную роль
при исследовании сходимости в анализе (топологическая система окрестностей данной
точки является фиксированным в ней тривиальным ультрафильтром). Главные ультра-
фильтры также используют, например, при исследованиях полноты логических систем в
алгебрах L∗ Линденбаума-Тарского, порождённых соответствующей логической теорией
L.19
Пример 40. Рассмотрим множество A = {A, B, . . .} формул алгебры логики (формул
над высказваниями). Если A ≡ B есть тождественно истинная формула, то говорят, что
формулы A и B логически эквивалентны или равносильны, что записывают как A ∼ B.
Ясно, что ∼ есть отношение эквивалентности на A. Класс эквивалентности, порождае-
мой формулой A будем обозначать [A], классы тождественно истинных формул — T, а
тождественно ложных формул — F.
   На фактор-множестве A/ ∼ классов эквивалентности формул алгебры логики

                 [A] = [¬A],    [A] ∪ [B] = [A ∨ B],     [A] ∩ [B] = [A ∧ B] .

  Легко видеть, что введённые операции над классами эквивалентностей имеют следу-
ющие свойства:
 1) операции ∪ и ∩ коммутативны и взаимно дистрибутивны;

 2) выполняются соотношения [A] ∪ F = [A] и [A] ∩ T = [A];

 3) справедливы законы [A] ∪ [A] = T и [A] ∩ [A] = F.
Указанное означает, что АС L∗ = h A/∼, ∪, ∩, − , T, F i является булевой алгеброй, ко-
торую называют фактор-алгеброй логических формул. Для классической алгебры выска-
зываний она совпадает с соответствующей алгеброй Линденбаума-Тарского. С каждым
элементом A/ ∼ связана соответствующая функция алгебры логики.
   Обозначим через An множество формул алгебры логики над n элементарными вы-
сказываниями. Очевидно, An бесконечно, а фактор-множество An / ∼ конечно (и содер-
      n
жит 22 элементов).
 19
    См., например, [11] или С.И. Гуров. Системы пропозициональной логики. — www.cs.msu.ru → Учеб-
ная работа → Материалы по учебным курсам.

                                               64