Упорядоченные множества и универсальная алгебра (вводный курс): Учебное пособие

Московский Государственный университет им. М.В. Ломоносова Факультет Вычислительной математики и кибернетики

С.И. Гуров

Упорядоченные множества и универсальная алгебра (вводный курс) учебное пособие Электронная версия

Москва 2005

УДК 512 (075.8) В пособии рассмотрены основные понятия и теоремы булевой алгебры, отношений множеств, причем особое внимание уделено частично упорядоченным множествам и решёткам. Изучаются свойства модулярных и дистрибутивных решёток и решёток с дополнениями. Указанным разделам посвящены две первые главы. Заключительная третья глава посвящена универсальной алгебре. Вводится понятие алгебраической системы, рассматриваются различные типы таких систем и доказываются основные теоремы об их изоморфизме и гомоморфизме. Пособие есть результат существенной переработки и дополнения вышедшего в 2002 г. в Издательском отделе ф-та ВМиК МГУ пособия «Элементы теории упорядоченных множеств и универсальной алгебры». В ходе его подготовки были, в частности, упрощены формулировки многих теорем и определений, добавлены новые разделы и исправлены замеченные неточности. Пособие предназначено для студентов, изучающих соответствующие разделы алгебры и может быть использовано при самообразовании. Данное электронная версия отличается от брошюры «Гуров С.И. Упорядоченные множества и универсальная алгебра (вводный курс): Учебное пособие. — М.: Издательский отдел ф-та ВМиК МГУ, 2004 г. — 104 с.» тем, что в ней исправлены замеченные опечатки и неточности, сделаны добавления и уточнения, а также изменено форматирование на более удобное для распечатки. Подготовлено при поддержке Intel Technologies, Inc. ©

С.И. Гуров, 2005.

Оглавление 1

Булевы алгебры. Отношения и соответствия . . . . . . . . . . . . . . . . . . 1.1 Булева алгебра как алгебраическая система . . . . . . . . . . . . . . 1.1.1 Определение булевой алгебры. Алгебраические системы . . 1.1.2 Алгебры множеств . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 Изоморфизмы булевых алгебр . . . . . . . . . . . . . . . . . 1.1.4 Теорема Стоуна . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Декартово произведение множеств. Отношения. Однородные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Основные определения . . . . . . . . . . . . . . . . . . . . . 1.2.2 Псевдообращение и произведение соответствий . . . . . . . 1.2.3 Однородные отношения . . . . . . . . . . . . . . . . . . . . 1.3 Отношение эквивалентности и его свойства . . . . . . . . . . . . . . 1.3.1 Классы эквивалентности . . . . . . . . . . . . . . . . . . . . 1.3.2 Устойчивость эквивалентности . . . . . . . . . . . . . . . . 1.4 Соответствия и отображения . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Основные типы соответствий . . . . . . . . . . . . . . . . . 1.4.2 Отображения . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.3 Основные свойства отображений . . . . . . . . . . . . . . . 2 Порядки и решётки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Отношение порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Предпорядки и порядки . . . . . . . . . . . . . . . . . . . . 2.1.2 Частично упорядоченные множества . . . . . . . . . . . . . 2.1.3 Изотонные отображения и порядковые идеалы . . . . . . . 2.1.4 Вполне упорядоченные множества и смежные вопросы . . 2.2 Алгебраические решётки . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Решёточно упорядоченные множества и решётки . . . . . . 2.2.2 Основные свойства решёток . . . . . . . . . . . . . . . . . . 2.3 Специальные виды решёток . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Модулярные решётки . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Дистрибутивные решётки . . . . . . . . . . . . . . . . . . . 2.3.3 Решётки с дополнениями . . . . . . . . . . . . . . . . . . . . 2.4 Булевы алгебры (продолжение) . . . . . . . . . . . . . . . . . . . . . 2.4.1 Безатомные булевы алгебры. Булевы гомоморфизмы, кольца и структуры . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Булевы идеалы и фильтры . . . . . . . . . . . . . . . . . . . 3 Алгебраические системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Модели и алгебры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Основные определения . . . . . . . . . . . . . . . . . . . . . 3.1.2 Подсистемы и прямое произведение алгебраических систем 3.2 Гомоморфизмы алгебраических систем . . . . . . . . . . . . . . . . . 3.2.1 Согласованность отображений АС с операциями и отношениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Типы гомоморфизмов АС . . . . . . . . . . . . . . . . . . . 3.3 Конгруэнции и гомоморфные системы . . . . . . . . . . . . . . . . . 3.3.1 Конгруэнции и фактор-системы . . . . . . . . . . . . . . . . 3.3.2 Теоремы о гомоморфизмах и изоморфизмах АС . . . . . . 3.4 Многоосновные системы . . . . . . . . . . . . . . . . . . . . . . . . . Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

4 4 4 5 7 10 12 12 14 15 16 16 18 21 21 22 25 28 28 28 29 33 36 39 39 43 46 47 49 57 59 59 62 68 68 68 71 73 73 74 75 75 77 81 83

1 1.1 1.1.1

Булевы алгебры. Отношения и соответствия Булева алгебра как алгебраическая система Определение булевой алгебры. Алгебраические системы

Определение 1.1. Булевой алгеброй B называется содержащее по крайней мере два элемента — нуль (o ) и единица — (ι ) множество B с заданными на нём бинарными операциями объединения (t ), пересечения (u ) и унарной операцией дополнения ( 0 ). При этом для любых x, y и z из B выполняются следующие законы (аксиомы) булевой алгебры: Com t : x t y = y t x Com u : x u y = y u x Dtr1 : (x t y) u z = (x u z) t (y u z) Dtr2 : (x u y) t z = (x t z) u (y t z) to : x t o = x uι : x u ι = x 0 0 Cmp : x t x = ι Isl 0 : x u x 0 = o Inv 0 : (x 0 )0 = x 0 0 ι : ι = o o0 : o0 = ι DeM 1 : (x t y)0 = x 0 u y 0 DeM 2 : (x u y)0 = x 0 t y 0 tι : x t ι = ι uo : x u o = o Ass t : x t (y t z) = (x t y) t z Ass u : x u (y u z) = (x u y) u z Id t : x t x = x Id u : x u x = x Abs1 : x u (x t y) = x Abs2 : x t (x u y) = x Множество B называется носителем булевой алгебры B. Таким образом, в булевой алгебре для объединения и пересечения выполняются законы коммутативности, первый и второй дистрибутивные законы, законы ассоциативности, идемпотентности и поглощения. Отметим, что законы ассоциативности обеспечивают эквивалентность произвольных скобочных структур для t и u. Далее при выводе соотношений мы не будем специально отмечать применение законов ассоциативности и коммутативности. Законы t o, u ι, t ι и u o описывают свойства особых элементов o и ι (в частности, o 6= ι ) по отношению к объединению и пересечению, а ι 0 , o 0 — их взаимную дополнительность. Законы Cmp 0 и Isl 0 постулируют полноту и обособленность дополнения (это основные законы, описывающие свойства дополнения), а Inv 0 — его инволютивность. Взаимные свойства бинарных операций и дополнения описываются законами Де Моргана (DeM 1 и DeM 2 ). Введённые операции называют абстрактными, поскольку ни они сами, ни носитель, на котором они определены никак не конкретизируются, и никаких иных требований, кроме удовлетворения вышеприведённым законам, к ним не предъявляется. В приложениях элементы носителя B (или просто элементы булевой алгебры) интерпретируются как подмножества некоторых множеств, события, высказывания, сигналы и т.д. Следствием очевидной самодвойственности законов булевой алгебры является важный Принцип двойственности (для булевой алгебры). Любое утверждение, истинное в булевой алгебре, остаётся истинным, если в нём произвести замены символов u ↔ t, ι ↔ o и/или x ↔ x 0 , где x — имя элемента булевой алгебры. Последнее замечание важно: если им пренебречь, то, например, из DeM 1 можно получить неверное равенство x 0 u y 0 = x t y вместо верного (x 0 u y 0 )0 = x t y. Нетрудно обнаружить, что приведённая система из 21-ой аксиом избыточна. 4

Inv 0 . Инволютивность дополнения есть прямое следствие симметричности его основных свойств Cmp 0 и Isl 0 . DeM 1 и DeM 2. Используя законы дистрибутивности, ассоциативности, свойства дополнения и единицы показывается, что для любых x, y ∈ B (x u y) t (x 0 t y 0 ) = ι

и

(x u y) u (x 0 t y 0 ) = o .

Это означает, что x 0 t y 0 — дополнение к x u y, т.е. выведен закон DeM 1. Выводимость DeM 2 следует из принципа двойственности. Id t и Id u. Законы идемпотентности вытекают из законов поглощения. Действительно, для любого x ∈ B имеет место Abs1

Abs2

x t x = x t (x u (x t x)) = x . Идемпотентность пересечения следует из только что доказанного по принципу двойственности. Избыточность системы аксиом обычно не является помехой в практической работе. С другой стороны, в определении булевой алгебры удобно задавать именно приведённый набор аксиом, содержащий все основные характерные для неё соотношения. Вопрос о неизбыточной системе аксиом для булевой алгебры оказался не таким простым, как могло бы показаться на первый взгляд. В ходе его исследования был обнаружен ряд интересных фактов, и с некоторыми из них мы встретимся в п. 2.3. Здесь же отметим восходящую к работе Э. Хантингтона1 часто используемую систему, содержащую только первые восемь из приведенных выше аксиом. Однако и указанная совокупность не является независимой: можно показать, что каждый из законов t o, u ι выводим из остальных семи. Единственная известная на сегодняшний день (2005 г.) безызбыточная самодвойственная система аксиом булевой алгебры содержит пары законов поглощения, дистрибутивности и основных свойств операции дополнения. Булева алгебра является примером алгебраической системы (АС), точнее, частного случая АС — алгебры. Произвольная АС A задается парой множеств A и σA , т.е. A = h A, σA i. Здесь A — носитель, а σA — сигнатура АС. Носитель АС есть некоторое непустое множество. В зависимости от его мощности различают конечные и бесконечные АС. Сигнатура σA алгебры с носителем A есть упорядоченная совокупность символов операций и особых элементов из A. Если результат некоторой операции над элементами множества всегда лежит в этом множестве, то говорят, что множество устойчиво относительно данной операции, а операция устойчива на данном множестве. В определении алгебры требуется, чтобы все операции были устойчивы на её носителе. В случае булевой алгебры с носителем B имеем σB = h t, u, 0 , o, ι i, и свойства указанных операций и выделенных элементов носителя описываются указанными выше законами. Если рассматриваются АС заданной сигнатуры, то, стремясь к краткости, для её обозначения часто используют просто символ носителя. Мы будем так поступать, когда это не приводит к недоразумениям. 1.1.2

Алгебры множеств

Рассмотрим непустое множество A и произвольную совокупность S(A) его подмножеств, устойчивую относительно операций их объединения ( ∪ ), пересечения ( ∩ ) и дополнения ( − ) до A. Множество всех подмножеств (булеан) A будем обозначать P(A). 1

Huntington E.V. Sets of independent postulates for algebra of logic. — Amer. Math. Soc., 1904, 5, p. 288-309.

5

Понятно, что S(A) ⊆ P(A). Алгебраическая система h S(A), ∪, ∩, − , ∅, A i называется алгеброй или полем множеств. Алгебру множеств с носителем P(A) будем называть тотальной (над A ), а с двухэлементным носителем {A, ∅} — тривиальной алгебрами множеств. Нетрудно показать, что имеет место Теорема 1.1. Всякая алгебра множеств есть булева алгебра. Доказательство. Достаточно убедиться, что в алгебре множеств произведены подстановки t 7→ ∩, u 7→ ∩, 0 7→ − , ι 7→ A, o 7→ ∅. Законы коммутативности, t o, u ι и Cmp 0 , Isl 0 описывают элементарные свойства теоретико-множественных операций. В силу принципа двойственности достаточно доказать справедливость для алгебры множеств первого закона дистрибутивности: (x ∪ y) ∩ z = (x ∩ z) ∪ (y ∩ z) для любых подмножеств x, y, z из S(A). Для этого рассмотрим произвольный элемент a ∈ (x ∪ y) ∩ z. Ясно, что a ∈ z, и либо a ∈ x, либо x ∈ y. В первом случае a ∈ x ∩ z, а во втором — a ∈ y ∩ z. Следовательно, в любом случае a ∈ x ∩ z или a ∈ y ∩ z, что эквивалентно a ∈ (x ∩ z) ∪ (y ∩ z). Справедливость второго дистрибутивного закона будет следовать отсюда по принципу двойственности. Пример 1. σ-алгебра подмножеств пространства Ω элементарных событий, используемая, например, при аксиоматическом обосновании теории вероятностей, есть алгебра множеств и, следовательно, булева алгебра. Замечание. Проверку соотношений Dtr1, Dtr2 и им подобных легче всего проводить, используя известные читателю диаграммы Эйлера-Венна2 , в которых множество A изображается прямоугольником, а его подмножества — различными кругами или овалами общего положения в этом прямоугольнике. При этом объединению элементов соответствует объединение, а пересечению — общая часть фигур, связанных с данными элементами. Такие диаграммы строят отдельно для левых и правых частей проверяемого соотношения. Интересующую при данной проверке область заштриховывают. Если заштрихованными оказались одинаковые области, то, рассматривая различные подобласти A, получающиеся в результате пересечения овалов, можно провести формальное доказательство, подобное приведённому выше. В большинстве практических случаев (когда рассматриваемая булева алгебра изоморфна некоторой алгебре множеств — см. ниже определения и теорему1.9 о представлении) для доказательств булевых равенств можно ограничиться рассмотрением “правильно построенных” диаграмм Эйлера-Венна. Определение 1.2. Пусть дана система множеств X = {X1 , . . . , Xn }. Составляющие { s1 , . . . , sk } = S данной системы множеств задаются следующим индуктивным определением. 1◦ Составляющие {X1 } суть X1 и X 1 . 2◦ Если S — совокупность составляющих системы {X1 , . . . , Xn−1 }, то S ∩Xn и S ∩X n — составляющие системы {X1 , . . . , Xn }. Система множеств X называется независимой, если все её составляющие непусты. Пример 2. Рассмотрим множество U = { a, b, c, d }. 2

См., например, Р. Фор, А. Кофман, М. Дение-Папен. Современная математика. — М.: Мир, 1966.

6

1. Составляющими системы X1 = {a, b}, X2 = {b} суть {b}, ∅, {a}, {c, d} и, следовательно, данная система множеств не является независимой; 2. Составляющими системы X1 = {a, b}, X2 = {b, c}, суть {b}, {c}, {a}, {d}, и, следовательно, данная система множеств независима. Для σ ∈ {0, 1} и множества X введём обозначение X σ : X σ есть X, если σ = 1 и X, если σ = 0. Лемма 1.2. 1. Произвольная составляющаяT s ∈ S системы множеств σj n X , где σj ∈ {0, 1}, и, следова{X1 , . . . , Xn } представима в виде s = j j=1 тельно, две составляющие либо совпадают, либо не пересекаются. 2. Независимая система из n множеств имеет 2n различных составляющих. Доказательство. Доказательство п. 1) легко проводится по индукции. Утверждение 2) следует из 1). Из леммы следует, что получаемая в соответствии с определением совокупность составляющих некоторой системы множеств не зависит от порядка выбора этих множеств и, таким образом, определение набора составляющих корректно. Теорема 1.3 (Венна). Если булево равенство выполнено для некоторой независимой системы множеств, то оно справедливо для любой системы множеств. Доказательство. Рассмотрим множество F , представимое некоторой булевой формулой над независимой системой множеств X = {X1 , . . . , Xn } и s — составляющая этой системы. Тогда либо s ⊆ F , либо s ∩ F = ∅. Первый случай имеет место если и только если x ∈ s ⇒ x ∈ F . Это S означает, что множество F может быть представлено в виs. Такое разложение останется справедливым и для завиде объединения F = x∈s ⇒ x∈F

симой системы множеств перестав, однако, быть единственным. Таким образом, если в независимой системе множеств две булевы теоретико-множественные формулы F1 и F2 представляются в виде объединения одних и тех же составляющих, истинность x ∈ F1 и x ∈ F2 будет одинакова в любой другой системе. Из теоремы следует, что булево равенство достаточно проверить на одной диаграмме Эйлера-Венна для независимых систем множеств (их обычно и называют множествами общего положения). Заметим, что система подмножеств некоторого множества может оказаться булевой алгеброй, не являясь при этом алгеброй множеств. Это будет, когда хотя бы одна из операций на данной системе не совпадает с соответствующей теоретико-множественной (ниже будут приведены подобные примеры). 1.1.3

Изоморфизмы булевых алгебр

Хотя алгебры множеств являются, как мы увидим, в определённом смысле, основными примерами булевых алгебр, последние ими не исчерпываются. Пример 3. 1. Рассмотрим двоичное множество истинностных значений B = { 1, 0 } и сигнатуру σB = h ∨, ∧, ¬, 0, 1 i, состоящую из логических операций дизъюнкции, конъюнкции и отрицания, а также символов элементов B : логического нуля

7

0 («ложь») и логической единицы 1 («истина»). Полученная АС h B, σB i является, как нетрудно видеть, булевой алгеброй. Эта простая алгебра играет фундаментальную роль в логике. Она называется алгеброй логики или алгеброй высказываний. Заметим, что в логике Cmp 0 и Isl 0 называются соответственно законами «исключенного третьего» и «непротиворечия». 2. АС h B n , ∨, ∧, ¬, ˜0, ˜1 i, где B n — булев n-мерный куб, ˜0 = (0, . . . , 0), ˜1 = (1, . . . , 1), а сигнатурные операции применяются к булевым векторам покомпонентно, называют булевой алгеброй n-мерных двоичных векторов. 3. Обозначим через P2 множество всех (двузначных) булевых функций, через 0 — тождественный нуль и через 1 — тождественную единицу. Тогда АС h P2 , ∨, ∧, ¬, 0, 1 i есть булева алгебра. Её называют булевой алгеброй логических функций. 4. Пусть N свободное от квадратов натуральное число. Это означает, что справедливо представление N = p1 . . . pk , где p1 , . . . , pk — различные простые числа. Совокупность всех делителей N обозначим D(N ). Например, для N = 30 = 2 · 3 · 5 имеем D(30) = { 1, 2, 3, 5, 6, 10, 15, 30 }. Наименьшее общее кратное чисел m и n обозначим m ∨ n, а их наибольший общий . Тогда АС h D(N ), ∨, ∧, 0 , 1, N i, как нетрудно делитель — m∧n. Положим m0 = N m проверить, есть булева алгебра. 5. Рассмотрим множество электрических выключателей, или контактов, которые могут находиться в одном из двух состояний — замкнутом (проводящем) или разомкнутом (не проводящем). Операцию переключения контакта из одного состояния в другое будем обозначать чертой ( − ) над ним. У таких контактов различают входной и выходной полюсы, которые можно соединять с полюсами других контактов. Из данных контактов можно строить электрические двухполюсные (один вход и один выход) цепи. Если соединять друг с другом только входные и выходные полюсы, то имеется только два способа объединения таких цепей: последовательное и параллельное. Таким образом получают класс т.н. параллельно-последовательных контактных схем. Их ещё называют П-схемами. Под произведением A · B будем понимать цепь, образованную из сетей A и B путём присоединения выходного полюса цепи A к входному полюсу цепи B с сохранением входного полюса A в качестве входного полюса всей полученной цепи, в выходного полюса B в качестве её выходного полюса. Под суммой A + B будем понимать цепь, полученную объединением соответственно входных и выходных полюсов цепей A и B. Обозначим через I постоянно замкнутый, а через O — постоянно разомкнутый контакты. При этом проводимость получаемых цепей будут описываться т.н. безповторными формулами, в которых каждому контакту цепи соответствует выражающая его проводимость единственная пропозициональная переменная, встречающаяся в формуле ровно один раз. Две цепи будем считать одинаковыми, если можно так сопоставить контактам переменные, что при одном и том же состоянии контактов, соответствующим одной переменной и всех произвольных состояниях остальных контактов, обе рассматриваемые цепи являются одновременно либо проводящими, либо не проводящими. Введенное отношение, очевидно, является отношением эквивалентности на множестве цепей. Обозначим через C множество всех попарно неэквивалентных П-схем. Тогда АС h C, +, ·, − , O, I i есть, как нетрудно видеть, булева алгебра. 8

Применение формульного аппарата булевых алгебр для анализа и синтеза электрических схем имеет огромное прикладное значение. Однако кроме параллельнопоследовательных, существует ещё т.н. “мостиковые” схемы, когда входные или выходные контакты одной цепи присоединяется к внутреннему полюсу другой, образуя, тем не менее, двухполюсную цепь (см. рис. 1).

[[x   • [x • [ x x ◦

x1

3

5

2

◦

4

Рис. 1: Мостиковая схема (входной и выходной полюсы обозначены • ). Для описания таких цепей язык булевой алгебры оказывается недостаточным: «не удаётся так усовершенствовать обычный булев аппарат алгебры логики, добавив к нему ещё несколько (конечное число!) операций так, чтобы он стал содержать средства для описания строения не только параллельно-последовательных, но и мостиковых схем, притом описания адекватного, т.е. такого, при котором каждому контакту в схеме соответствует ровно одна буква в формуле, выражающая проводимость данной схемы»3 . Действительно, проводимость мостиковой схемы на рис. 1 описывается булевой функцией, которая задается формулой (x1 ∧ (x3 ∨ (x4 ∧ x5 ))) ∨ (x2 ∧ (x4 ∨ (x3 ∧ x5 ))), не являющейся, однако, безповторной, и никакое её эквивалентное преобразование не приведёт, как нетрудно убедится, к безповторной форме4 . Приведенные выше системы являются представлениями или реализациями булевой алгебры. Пример 4. Для любых действительных чисел a, b из отрезка [0, 1] положим a ⊕ b = max {a, b},

a ⊗ b = min {a, b},

ªa = 1 − a .

Система h [0, 1], ⊕, ⊗, ª, 0, 1 i не будет являться булевой алгеброй, поскольку в ней не выполняются, скажем, законы Де Моргана. Определение 1.3. Пусть даны две булевы алгебры B1 и B2 и взаимнооднозначная функция ϕ : B1 → B2 такая, что равенства 1) ϕ(x t y) = ϕ(x) t ϕ(y) 2) ϕ(x u y) = ϕ(x) u ϕ(y) 3) ϕ(x 0 ) = ϕ(x)0 справедливы для всех x и y из B1 . Тогда говорят, что ϕ — булев изоморфизм между B1 и B2 , данные алгебры (булево) изоморфны и пишут B1 ∼ = B2 . Замечание. Легко показать, что из 1) – 3) следует 4) ϕ(o) = o

и

3

5) ϕ(ι) = ι .

А.В. Кузнецов. О безповторных контактных схемах и безповторных суперпозициях функций алгебры логики // Труды матем. ин-та им. В.А. Стеклова, т. LI. — М.: 1958. 4 Попытка построения подобного булевой алгебре формализованного формульного языка, пригодного для адекватного описания двухполюсных цепей общего вида, предпринята в работе Е.К. Войшвилло. Алгебра двухполюсных сетей / Формальная логика и методология науки. — М.: Наука, 1964.

9

Действительно, ϕ(o) = ϕ(x u x 0 ) = ϕ(x) u ϕ(x 0 ) = ϕ(x) u ϕ(x)0 = o и аналогично по двойственности — для ϕ(ι). Мы видим, что булев изоморфизм — это взаимнооднозначная функция, сохраняющая операции и особые элементы o и ι булевой алгебры. В записи булевых алгебр B1 и B2 мы использовали одинаковые обозначения и для соответствующих операций, и для выделенных элементов. Стремясь не усложнять обозначения, так обычно и поступают. При внимательном чтении путаницы относительно принадлежности операций и выделенных элементов к одной или другой алгебре возникнуть не должно. Пример 5. Тотальная алгебра над n-элементным множеством Булевым изоморфизмом здесь будет является отображение ϕ : B n → P(A), ставящее в соответствие вектору (α1 , . . . , αn ) множество { ai1 , . . . , aik | αik = 1, k = 1, n }. Алгебра высказываний, очевидно, изоморфна тривиальной алгебре множеств. Существует простой критерий изоморфности тотальных алгебр множеств. Теорема 1.4. Для того, чтобы тотальные алгебры множеств P(A) и P(B) были изоморфны, необходимо и достаточно, чтобы A и B имели одинаковую мощность. Доказательство. (⇐, необходимость) Пусть существует изоморфизм ϕ между алгебрами P(A) и P(B). Тогда ϕ — взаимнооднозначное соответствие между множествами A и B, откуда следует их равномощность. (⇒, достаточность) Пусть множества A и B равномощны. Тогда между их элементами можно установить взаимнооднозначное соответствие ϕ. Распространим отображение ϕ на подмножества множеств A и B, поставив S в соответствие произвольному подмножеству X множества A его образ ϕ(X) = a∈X ϕ(a) в B. Простая проверка показывает, что полученное расширение ϕ не только устанавливает взаимнооднозначное соответствие между подмножествами A и B, но и является булевым изоморфизмом между P(A) и P(B). 1.1.4

Теорема Стоуна

Справедлива следующая основная теорема о представлении произвольных булевых алгебр алгебрами множеств. Теорема 1.5 (Стоуна). Всякая булева алгебра изоморфна подходящей алгебре множеств. Иными словами, теорема Стоуна утверждает существование вложения произвольной булевой алгебры в некоторую алгебру множеств. Мы докажем эту теорему для конечного случая. Для этого нам потребуются ввести понятие атома булевой алгебры. Определение 1.4. Ненулевой элемент a булевой алгебры называется атомом, если для любого её элемента x справедливо либо a u x = o, либо a u x = a. В последнем случае то говорят, что элемент x содержит атом a. В булевой алгебре всех n-мерных двоичных векторов атомы суть двоичные наборы единичного веса. В тотальной (конечной или бесконечной) алгебре множеств атомами будут являться все одноэлементные подмножества носителя. Булева алгебра, в которой каждый ненулевой элемент содержит атом, называется атомной. Обе рассмотренные алгебры — атомные. Булеву алгебру, не содержащую ни одного атома называют безатомной или непрерывной. Пример безатомной булевой алгебры будет приведён в п. 2.3. 10

Множество всех атомов, содержащихся в элементе 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 a = b2 , a = a = a = b1 = a∈At(b1 )

a∈At(b2 )

a∈ϕ(b2 )

a∈ϕ(b1 )

и, значит, ϕ — инъективно. Далее, пусть 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 aub = xuy = au b = a∈At(x)

b∈At(y)

a∈At(x) b∈At(y)

a,

a∈At(x)∩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

Доказанная теорема имеет следующие простые Следствия. 1. Если конечная булева алгебра имеет n атомов, то общее число её элементов равно 2n . 2. Любые две конечные булевы алгебры с одинаковым числом элементов изоморфны. 3. Любая конечная булева алгебра изоморфна подходящей алгебре n-мерных двоичных векторов. В некоторых булевых алгебрах удается определить объединение и пересечение произвольной совокупности её элементов. Такая булева алгебра называется полной. Ясно, например, что тотальная алгебра множеств является полной булевой алгеброй, а σ-алгебра, где операции объединения и пересечения могут браться по счётной совокупности множеств, является “промежуточной” между обычной и полной булевыми алгебрами. Оказывается возможным распространить доказанный вариант теоремы Стоуна на случай всех полных атомных алгебр, и справедливой является следующая Теорема 1.9 (О представлении полных атомных булевых алгебр). Пусть B — полная атомная булева алгебра с носителем B и At(B) — множество всех её атомов. Тогда B ∼ = P(At(B)) .

1.2 1.2.1

Декартово произведение множеств. Отношения. Однородные отношения Основные определения

Пусть I = { i1 , i2 , . . . } — произвольное конечное или бесконечное подмножество натурального ряда, которое мы будем называть множеством индексов и каждому i ∈ I сопоставлено множество Xi . Декартовым (или прямым) произведением непустых множеств {Xi }i∈I называют множество последовательностей ( ai1 , ai2 , . . . ), где ai ∈ Ai . Декартово произведение обычно определяют для произвольной совокупности индексов. Нам, однако, будет достаточно данного определения. Более того, в дальнейшем мы будем, как правило, рассматривать конечный случай I = {1, . . . , k}, обозначая декартово произведение k Y A1 × A2 × . . . × Ak или Ai . i =1

Считается, что Ai ⊂

k Q

Ai . Заметим, что A×B 6= B ×A. Также A×B ×C, (A×B)×C

i =1

и A × (B × C) суть разные множества. В частном случае A1 = . . . = Ak = A декартово произведение обозначают Ak и называют k-ой декартовой степенью множества A. Под A0 понимают некоторое одноэлементное подмножество из A. Ясно, что A1 = A и Am × An 6= Am+n . Определение 1.5. Отношения суть подмножества декартовых произведений множеств. Число множеств в соответствующем декартовом произведении определяет местность или арность отношения. Говорят об унарных (одноместных), бинарных (двуместных), тренарных (трёхместных) и т.д. отношениях.

12

Пусть ρ ⊆

n Q

Ai = A. Отношение ρ = A называют полным; мы будем обозначать его

i=1

OA . Через P r1 ρ обозначают совокупность всех таких элементов a1 ∈ A1 для которых найдутся такие a2 ∈ A2 , . . . , ak ∈ Ak , что (a1 , a2 , . . . , ak ) ∈ ρ. P r1 ρ называют проекцией отношения ρ на множество A1 или первой проекцией. Аналогично определяются вторые, третьи и т.д. проекции. Отношение на A1 × A2 × . . . × Ak называется полным, если его первая проекция совпадает с A1 , вторая — с A2 и т.д. Отношения можно рассматривать как предикаты, т.е. функции, принимающие два значения: «истина» и «ложь»: считают, что ρ (a1 , . . . , an ) истинно, если (a1 , . . . , an ) ∈ ρ и ложно в противном случае. Поэтому к отношениям можно применять операции алгебры логики: дизъюнкции ( ∨ ), конъюнкции ( ∧ ), отрицания ( ¬ ), тождества ( ≡ ), импликации ( ¡¢ ) и др. При чтении соответствующих формул следует иметь в виду, что, поскольку приоритет отношений выше приоритета операций алгебры логики, скобки вокруг отношений, как правило, опускают. Унарные отношения на некотором множестве определяют те или иные свойства его элементов. Бинарные отношения на декартовом произведении множеств A и B называют отношениями между A и B или соответствиями между данными множествами. Для соответствия ρ ⊆ A × B удобно пользоваться обозначением aρb, если (a, b) ∈ ρ. Поскольку отношения суть подмножества, то для бинарных отношений определена тотальная алгебра h P(A × B), ∪, ∩, − , ∅, A × B i. Ясно, что теоретико-множественные операции, применённые к соответствиям α, β ⊆ A × B, имеют следующие свойства: 1) a(α ∪ β)b ⇔ aαb ∨ aβb ⇔ (a, b) ∈ α или (a, b) ∈ β ; 2) a(α ∩ β)b ⇔ aαb ∧ aβb ⇔ (a, b) ∈ α и (a, b) ∈ β ; 3) aαb ⇔ ¬(aαb) ⇔ (a, b) ∈ / α. Существует удобный способ представления соответствий конечных множеств в виде (0,1)-матриц M (ρ). Пусть A = { a1 , . . . , am }, B = { b1 , . . . , bn } и ρ ⊆ A × B. Зафиксируем указанный порядок следования элементов в множествах A и B. Тогда матрица отношения ρ имеет размеры m × n и определяется следующим образом: её элемент mi,j равен 1, если справедливо ai ρbj и 0, если иначе. Множество всех (0,1)-матриц размера m×n будем обозначать Mm×n , опуская индекс, когда соответствующий размер подразумевается. Во введённом множестве выделяются матрица, у которой всё элементы равны 1 и матрица, у которой всё элементы равны 0. Их называют универсальной и нуль-матрицей и обозначают I и O соответственно. К матрицам из M можно поэлементно применять логические операции ∨, ∧, ¬. Легко видеть, что АС h M, ∨, ∧, ¬, O, I i является булевой алгеброй, изоморфной тотальной алгебре h P(A × B), ∪, ∩, − , ∅, A × B i. Изоморфизм следует из следующих равенств, очевидно справедливых для любых соответствий α и β между A и B : 1) M (α ∪ β) = M (α) ∨ M (β) ; 2) M (α ∩ β) = M (α) ∧ M (β) ; 3) M (α) = ¬ M (α) .

13

1.2.2

Псевдообращение и произведение соответствий

В данном разделе вводятся новые операции для бинарных отношений (соответствий): унарная псевдообращения и бинарная произведения. Определение 1.6. Пусть ρ ⊆ A × B. Операция (# ) псевдообращения соответствия ρ def задаёт псевдообратное к нему отношение ρ# ⊆ B × A, определяемое как bρ# a = aρb для любых a ∈ A, b ∈ B. Часто употребляют также термины обратное, транспонированное, инверсное или симметричное отношение и пользуются обозначениями ρ−1 , ρ 0 и др. Легко установить следующие свойства псевдообращения относительно теоретико-множественных операций и отношения включения: (ρ# )# = ρ , ρ# = (ρ)# , α ⊆ β ⇒ α# ⊆ β # , (α ∪ β)# = α# ∪ β # , (α ∩ β)# = α# ∩ β # . Покажем, например, справедливость последнего равенства (a и b — произвольные элементы из A и B соответственно): b(α ∩ β)# a = a(α ∩ β)b = aαb ∧ aβb = bα# a ∧ bβ # a = b(α# ∩ β # )a . Определение 1.7. Пусть A, B и C — непустые множества и α ⊆ A × B, β ⊆ B × C. Тогда произведение α ¦ β (или сокращённо αβ ) соответствий α и β определяется как def

a(α ¦ β)c = ∃ b (aαb ∧ bβc) B

для произвольных a ∈ A, c ∈ C. Можно показать, что произведение соответствий обладает свойствами α(βγ) = (αβ)γ , (αβ)# = β # α# , α(β ∪ γ) = αβ ∪ αγ , (α ∪ β)γ = αγ ∪ βγ , но α(β ∩ γ) 6= αβ ∩ αγ ,

(α ∩ β)γ 6= αγ ∩ βγ .

Пусть M1 ∈ Mm×n , M2 ∈ Mn×r . Определим произведение M1 · M2 данных матриц: k M1 · M2 ki,j =

n _

k M1 ki,k ∧ k M2 kk,j ,

i = 1, m, j = 1, r .

k=1

Легко показывается, что если α ⊆ A × B и β ⊆ B × C, где A, B, C — конечные множества, то справедливо равенство M (α ¦ β) = M (α) · M (β) .

14

Далее нам понадобится ещё одно свойство произведения отношений. Пусть α, β ⊆ A × B и γ, δ ⊆ B × C. Тогда для любых a ∈ A и c ∈ C имеем a[(α ∩ β) ¦ (γ ∩ δ)]c = ∃ x [a(α ∩ β)x ∧ x(γ ∩ δ)c] = B

= ∃ x [aαx ∧ aβx ∧ xγc ∧ xδc] ⇒ B

= a(α ¦ γ)c ∧ a(β ¦ δ)c = a[(α ¦ γ) ∩ (β ¦ δ)]c . Таким образом, показано, что для указанных выше отношений (α ∩ β) ¦ (γ ∩ δ) ⇒ (α ¦ γ) ∩ (β ¦ δ)

(1.1)

(обратное, вообще говоря, не верно). 1.2.3

Однородные отношения

Отношение ρ ⊆ A2 называется бинарным на A или однородным. Понятно, что если ρ — отношение на A и B ⊆ A, то ρ ∩ B 2 — отношение на B. Множество P(A2 ) всех бинарных на A отношений обозначим R(A). Для элементов R(A) произведение всегда определено, поэтому в силу ассоциативности произведения соответствий алгебра h R(A), ¦ i есть полугруппа. Мы будем всегда предполагать, что A 6= ∅. Для натурального k вводят естественное обозначение α . . ¦ α} = αk . | ¦ .{z k раз

Проиллюстрируем действие введённых выше операций из R(A) на простом примере. Пример 6 (Мальцев). Рассмотрим отношение α =< на множестве N.6 Тогда справедливо следующее. 1. α# : (a < # b = b < a) ⇒ (< # = >). Таким образом, псевдообращением отношения «меньше» будет отношение «больше». 2. α2 :

a <2 b

=

∃ x (a < x ∧ x < b) N

=

a + 1 < b. Отсюда следует, что

a 1. 3. α ¦ α# : a(< ¦ >)b = ∃ x ( a < x ∧ x > b ) = N

∃ x ( x > max {a, b} ) = ON . N

4. α# ¦ α : a(> ¦ <)b = ∃ x ( a > x ∧ x < b ) = N

= ∃ x ( x < min {a, b} ) = 1 (0), если min {a, b} > 1 (иначе) . N

Мы видели, что, вообще говоря, αβ 6= βα. Отношения α, β ∈ R(A) называются перестановочными, если αβ = βα. Выделим некоторые типы однородных отношений на A. Отношения ∅ и OA называют несобственными. Очевидно, что для любого отношения ρ ∈ R(A) имеет место ∅ ⊆ ρ ⊆ OA . 6

Мы используем стандартные обозначения N, Z, Q и R для множеств натуральных, целых, рациональных и действительных чисел соответственно. N0 = N ∪ {0} — пополненный натуральный ряд.

15

Единичное 1A (иначе — диагональное MA ) отношение есть { (a, a) ∈ A2 }. Это отношение тождества. Ясно, что 1A — единица в полугруппе однородных отношений на множестве A, и АС h R(A), ¦, 1A i и есть моноид. С другой стороны, например, ρρ# может быть не равно 1A . Это объясняет выбор термина “псевдообратное” для отношения ρ# . В обозначениях 1A , MA , когда это не приводит к недоразумениям, обычно опускают подстрочный символ. Определение 1.8. Пусть отношение ρ ∈ R(A) называется R: рефлексивным, если M ⊆ ρ, что означает справедливость aρa; AR: антирефлексивным, если ρ∩ M= ∅, означает, что a¯ ρa; S: симметричным, если ρ# ⊆ ρ. Из свойства (ρ# )# = ρ сразу следует, что симметричность отношения ρ эквивалентна свойству ρ# = ρ, или что aρb = bρa; AS: антисимметричным, если ρ ∩ ρ# =M, что означает aρb ∧ bρa ⇒ a = b; T: транзитивным, если ρ2 ⊆ ρ, что означает aρb ∧ bρc ⇒ aρc. Здесь a, b и c — произвольные элементы множества A. Утверждение 1.1. Пусть α, β ∈ R(A). Тогда 1. Если β — рефлексивно, то α ⊆ αβ. Если α — рефлексивно, то β ⊆ αβ. 2. Если α ∪ β — транзитивно, то αβ ⊆ α ∪ β. Доказательство. ведливо

1. Для произвольных a и b из A, если β — рефлексивно, спраaαb ⇒ aαb ∧ bβb ⇒ aαβb .

Первое включение доказано, второе доказывается аналогично. 2. Для произвольных a и b из A, если α ∪ β — транзитивно, справедливо a(αβ)b = ∃x (aαx ∧ xβb) ⇒ ∃x (a(α ∪ β)x ∧ x(α ∪ β)b) = a(α ∪ β)2 b ⇒ a(α ∪ β)b , что эквивалентно требуемому.

1.3

Отношение эквивалентности и его свойства

Исключительную роль в математике играют отношения эквивалентности. Определение 1.9. Однородные рефлексивные, симметричные и транзитивные отношения называют отношениями эквивалентности. 1.3.1

Классы эквивалентности

Множество всех эквивалентностей на непустом множестве A будем обозначать E(A). Очевидно, любая эквивалентность на A содержит MA и содержится в OA . Последнее отношение называют иногда аморфной эквивалентностью. Ясно, что эквивалентность элементов какого-либо множества, вообще говоря, не означает их тождества. Эквивалентностями являются, например, отношение параллельности

16

на множестве прямых обычного пространства (если считать прямую параллельной самой себе), отношение подобия геометрических фигур, отношение равенства по модулю n целых чисел и др. Отношения эквивалентности часто обозначают знаком ∼. По определению, эквивалентность ∼ описывается соотношением M⊆∼ ∧ ∼ = ∼# ∧ ∼2 ⊆ ∼. Ниже будет показано, что ∼2 = ∼, и, таким образом, справедливо соотношение M ⊆ ∼ = ∼# = ∼2 .

(1.2)

При данной эквивалентности ∼ на множестве A каждому a ∈ A можно сопоставить множество [a]∼ эквивалентных ему элементов — классов эквивалентности или смежных def классов: [a]∼ = { x ∈ A | x ∼ a }. Если эквивалентность фиксирована, то смежный класс элемента a обозначают [a]. Формирование смежных классов происходит в ходе выполнения т.н. операции абстракции отождествления по данной эквивалентности. Понятно, что при этом каждый x ∈ A попадает в один и только один класс эквивалентности, и классы эквивалентности или совпадают, или не пересекаются, накрывая в совокупности всё множество A. Отсюда, в частности следует, что ∼2 = ∼ и справедливо (1.2). Говорят, что совокупность непустых множеств {Ai }i∈I образует разбиение множества A, если [ Ai = A и Ai ∩ Aj = ∅ при i 6= j; i, j ∈ I . i∈I

Пусть задано разбиение множества A. Тогда можно определить отношение эквивалентности так, что элементы A эквивалентны, если входят в один класс. Ясно, что такая эквивалентность единственна. Таким образом, между отношением эквивалентности и разбиениями A существует взаимнооднозначное соответствие. Приведённые рассуждения можно оформить в виде очень простой, но очень важной теоремы. Теорема 1.10 (О классах эквивалентности). Пусть A — непустое множество. Если на A задана эквивалентность, то множество классов эквивалентности образует разбиение A. Если задано разбиение A на классы, то можно единственным образом определить эквивалентность ∼ на A так, что для любой пары a, b элементов A a ∼ b ⇔ «a и b находятся в одном классе разбиения». «Теорема о классах эквивалентности находит в математике широчайшее применение, и её по праву можно считать одной из главных (а то и самой главной) теоремой».7 Множество, элементами которого являются классы эквивалентности множества A по отношению эквивалентности ∼ называется фактор-множеством и обозначается A/ ∼. Пример 7. 1. Если A — множество зёрен, насыпанных в мешки, и для зёрен a и b положить a ∼ b, если они лежат в одном мешке, то классами эквивалентности являются множества зёрен, лежащих в одном мешке, а фактор-множеством A/ ∼ — множество мешков. 2. Если W — множество слов русского языка и для слов u и v положить u ∼ v, если они начинаются с одной и той же буквы (в русском языке 33 буквы), то классами эквивалентности являются множества слов, начинающихся на данную букву, а фактор-множеством W/∼ — множество соответствующих букв ( |W/∼ | = 31 ). 7

Успенский В.А. Что такое аксиоматический метод? — Ижевск: Издательский дом «Удмуртский университет», 2000.

17

1.3.2

Устойчивость эквивалентности

Будем говорить, что отношение эквивалентности устойчиво относительно некоторой операции над множествами, если результат применения этой операции к эквивалентностям есть эквивалентность. Ясно, например, эквивалентность не устойчива относительно взятия дополнения. Теорема 1.11. Отношение эквивалентности устойчиво относительно пересечения множеств. Доказательство. Покажем рефлексивность, симметричность и транзитивность пересечения эквивалентностей. Поскольку α и β — эквивалентности, то для них справедливо соотношение (1.2). Тогда R:

M⊆ α ∧ M⊆ β ⇒ M ⊆ α ∩ β ;

S:

(α ∩ β)# = α# ∩ β # = α ∩ β ;

T:

(α ∩ β)2 ⇒ α2 ∩ β 2 = α ∩ β.

При доказательстве транзитивности мы воспользовались соотношением (1.1). Замечание. Из доказанной теоремы следует, что пересечение эквивалентностей из произвольной непустой (возможно бесконечной) совокупности есть эквивалентность. Теорема 1.12. Пусть α и β — эквивалентности. Тогда если для любой пары смежных классов по α и, соответственно, по β справедливо утверждение: «либо один из классов лежит в другом, либо они не пересекаются», то α ∪ β есть эквивалентность. Если α ∪ β — эквивалентность, то α ∪ β = αβ. Доказательство. Пусть приведённое утверждение неверно, т.е. имеются смежные классы [a]α и [b]β не лежат один в другом и имеют общий элемент c. Можно считать, что a ∈ [a]α r [b]β и b ∈ [b]β r [a]α . [a]α '$ [b]β '$ a

c

b

&% &%

A Пары (a, c) и (c, b) содержатся в α ∪ β. Если бы это отношение было эквивалентностью, то оно, в силу транзитивности, содержало бы и пару (a, b). Последнее означает справедливость либо aαb, либо aβb. Это, однако, не имеет места, и, следовательно, α ∪ β — не эквивалентность. C другой стороны, (a, b) ∈ αβ. Если же приведённое утверждение верно, то любой класс [a]α есть элемент разбиения некоторого класса [b]β , либо наоборот, и классы эквивалентности α∪β суть “объемлющие классы”. Пример 8. Пусть α и β — эквивалентности на множестве A = {a, b, c, d} со смежными классами A/α = {{a}, {b}, {c, d}}

и

A/β = {{a, b}, {c}, {d}} .

Тогда α ∪ β есть эквивалентность и A/(α ∪ β) = {{a, b}, {c, d}}. 18

Мы уже отмечали, что отношения могут быть, а могут и не быть перестановочными. Покажем, что то же справедливо и для эквивалентностей. Пусть α и β — эквивалентности на множестве A = {a, b, c, d} со смежными классами {a, b}, {c, d}

и

{a, c}, {b, d}

соответственно. Тогда αβ и βα — аморфные эквивалентности на A и, значит, α и β перестановочны. Если же A = { a, b, c }, а смежные классы по эквивалентностям α, β суть соответственно {a, b}, {c} и {a}, {b, c} , то a(αβ)c, но неверно, что a(βα)c, и данные эквивалентности не перестановочны. При этом, ни αβ, ни βα не являются эквивалентностями. Теорема 1.13. Произведение эквивалентностей будет эквивалентностью, если и только если они перестановочны. Доказательство. Пусть α и β — эквивалентности. (⇐) Если αβ — эквивалентность, то αβ = (αβ)# = β # α# = βα. (⇒) Если αβ = βα, то иммем R:

для произвольного a ∈ A имеем aαa ∧ aβa, откуда a(αβ)a, т.е. M⊆ αβ;

S:

(αβ)# = β # α# = βα = αβ ;

T:

(αβ)2 = αβαβ = ααββ = α2 β 2 = αβ .

Теорема 1.14. Пусть α, β и γ — эквивалентности. Тогда 1) α ⊆ αβ,

β ⊆ αβ;

2) α ⊆ γ ∧ β ⊆ γ ⇒ αβ ⊆ γ. Доказательство.

1) Данные включения следуют из п. 1) утверждения 1.1.

2) Включение следуют из п. 2) утверждения 1.1, если заметить, что α ∪ β ⊆ γ. Таким образом, произведение эквивалентностей содержит каждую их них и содержится в любой эквивалентности, которая их порознь содержит. Заметим, что здесь αβ может и не быть эквивалентностью. Если S — некоторое свойство элементов множества A, то наименьшим подмножеством множества A, обладающим свойством S называется пересечение всех подмножеств A, элементы которых обладают этим свойством. В случае, когда можно взять γ = αβ, теорема 1.14 имеет важное Следствие. Для перестановочных эквивалентностей произведение является наименьшей эквивалентностью, их содержащей. Ниже мы укажем процедуру построения наименьшей эквивалентности, содержащую данное отношение. Определение 1.10. Наименьшая эквивалентность ρ e , содержащая отношение ρ, называется эквивалентным замыканием ρ. Наименьшее транзитивное отношение ρ t , содержащее отношение ρ, называется транзитивным замыканием ρ. 19

Заметим, что h ρt , ¦ i есть моногенная полугруппа hρi, порождённая отношением ρ. Транзитивное замыкание данного отношения легко строится. Введём обозначение ∞ S ρ+ = ρn . По определению произведения отношений, справедливость aρ+ b означаn=1

ет существование таких элементов x0 = a, x1 , . . . , xn = b соответствующего множества, что x0 ρx1 ∧ . . . ∧ xn−1 ρxn . Ясно, что ρ+ транзитивно, и если ρ уже транзитивно, то ρ+ = ρ. Утверждение 1.2. Для произвольного однородного отношения ρ справедливо ρ t = ρ+ . Доказательство. С одной стороны, ρ ⊆ ρ+ и ρ+ транзитивно. С другой, из ρ ⊆ ρ t следует ρ+ ⊆ (ρt )+ = ρ t и, по определению транзитивного замыкания, ρ+ = ρ t . Следствия. 1. Для произвольного e ρ = { ρ ∪ ρ# ∪ M }t .

однородного

отношения

ρ

справедливо

Действительно, обозначим σ = { ρ ∪ ρ# ∪ M }. Отношение ρ e должно, кроме ρ, содержать M и ρ# , поэтому σ ⊆ ρ e . В силу транзитивности ρ e имеем σ t ⊆ ρ e , откуда σ t = ρ e по определению эквивалентного замыкания. 2. Эквивалентное замыкание совокупности эквивалентностей совпадает с объединением всевозможных произведений этих эквивалентностей. Действительно, с одной стороны, данное объединение содержит все эквивалентности из рассматриваемой совокупности, а с другой — содержится во всех из них (см. теорему 1.14.) В частности, для двух эквивалентностей α и β их эквивалентное замыкание совпадает с объединением всевозможных произведений вида αβ, βα, αβα, βαβ . . .. Отсюда следует, что если α и β перестановочны, то { α, β }e = αβ = α ∪ β (см. следствие из теоремы 1.14). Рефлексивным замыканием ρ∗ однородного на множестве A отношения ρ называют ∞ S . Ясно, отношение MA ∪ρ+ . Обычно по определению полагают ρ0 = MA и тогда ρ∗ = n=0

что ρe = ρ∗ .

Пример 9. 1. Если α — отношение на множестве натуральных чисел, определяемое def правилом mαn = m + 1 = n, то αt = <. 2. Пусть на множестве A = { 1, 2, 3, 4, 5, 6, 7, 8 } заданы эквивалентности α и β со смежными классами соответственно {1, 2}, {3, 4}, {5, 6, 7}, {8}

и

{1, 4}, {2, 3}, {5, 6}, {7}, {8} .

Тогда эквивалентность (α ∪ β)e порождает смежные классы {1, 2, 3, 4}, {5, 6, 7} и {8}. 3. Если на множестве A = { a, b, c, d, e, f } заданы эквивалентности α и β со смежными классами соответственно {a, b}, {c}, {d}, {e, f }

и

{a}, {b, c}, {d, e}, {f } ,

тогда ни αβ, ни βα не есть эквивалентность, а эквивалентное замыкание { α, β }e , совпадающее с { αβ ∪ βα }, порождает смежные классы {a, b, c} и {d, e, f }. 20

Пусть α и β — две эквивалентности на множестве A. Отношение включения β ⊆ α для них означает, что любой смежный класс по β лежит в некотором смежном классе по α. Иными словами, разбиение множества A на смежные классы по β есть подразбиение его разбиения на смежные классы по α. Говорят также, что разбиение по β есть измельчение разбиения по α. Для таких эквивалентностей определим на фактор-множестве A/β дробную эквивалентность α/β по правилу def

[x]β (α/β) [y]β = xαy

(x, y ∈ A) .

Таким образом, два смежных класса по β эквивалентны по α/β, если они находятся в одном смежном классе по α.

1.4 1.4.1

Соответствия и отображения Основные типы соответствий

Рассмотрим соответствие ρ ⊆ A × B между непустыми множествами A и B. Ясно, что MA ρ = ρ = ρ MB . Кроме того, всегда справедливо включение ρ ⊆ ρρ# ρ. Действительно, aρb = aρb ∧ bρ# a ∧ aρb ⇒ a(ρρ# ρ)b. Для соответствия ρ первая проекция называется областью определения, а вторая — областью значений отношения ρ, которые обозначаются Dom ρ и Im ρ соответственно. Для a ∈ A множество ρ(a) = { b ∈ B | aρb } называется образом элемента a при S соответствии ρ. Если X ⊆ A, то множество ρ(X) = x∈X ρ (x) называется образом множества X при соответствии ρ. Если b ∈ B то множество ρ# (b) = { a ∈ A | aρb } называется прообразом элемента b при соответствии ρ. В связи с введёнными понятиями рассмотрим ещё одно свойство произведения соответствий. Теорема 1.15. Пусть α ⊆ A × B и β ⊆ B × C. Тогда P r1 (αβ) = α# (P r1 β) ,

P r2 (αβ) = β(P r2 α) .

Доказательство. Заметим, что через проекции соответствия могут быть записаны образ и прообраз соответствующих множеств: P r1 β = β # (C)

и

P r2 α = α(A) .

Пользуясь свойствами соответствий и их псевдообращений получим P r1 (αβ) = (αβ)# (C) = (β # α# )(C) = α# (β # (C)) = α# (P r1 β) ; P r2 (αβ) = (αβ)(A) = β(α(A)) = β(P r2 α) .

Если ρ — соответствие между множествами A и B и A0 ⊆ A, то соответствие ρ |A0 = ρ ∩ (A0 × B) = { (a, b) ∈ ρ | a ∈ A0 } называется ограничением или сужением соответствия ρ на подмножество A0 . Понятие сужения очевидным образом распространяется на произвольные отношения. Выделим основные типы соответствий между A и B, обладающие особыми свойствами. 21

Определение 1.11. Соответствие ρ между A и B называется • многозначным отображением или всюду определённым соответствиями, если MA ⊆ ρρ# (что эквивалентно Dom ρ = A ); • частичным отображением A в B , если ρ# ρ aρb1 ∧ aρb2 ⇒ b1 = b2 для a ∈ A );

⊆MB

(что эквивалентно

• функциональным или отображением A в B , если MA ⊆ ρρ# ∧ ρ# ρ ⊆MB (что эквивалентно существованию для всех a ∈ A единственного b ∈ B такого, что aρb ); • дифункциональным или квазиоднозначным, если ρρ# ρ ⊆ ρ или, с учётом доказанного выше, ρρ# ρ = ρ (что эквивалентно ρ(a1 ) ∩ ρ(a2 ) 6= ∅ ⇒ ρ(a1 ) = ρ(a2 ) для всех a1 , a2 ∈ A или ρ# (b1 ) ∩ ρ# (b2 ) 6= ∅ ⇒ ρ# (b1 ) = ρ# (b2 ) для всех b1 , b2 ∈ B ). Данные соотношения указывают, что как образы, так и прообразы дифункциональных отношений либо совпадают, либо не пересекаются. Это означает, что дифункциональные отношения задают разбиения множеств Dom ρ и Im ρ на одинаковое число классов, причём эти разбиения обладают тем свойством, что образы элементов из одного класса разбиения Dom ρ лежат в одном и том же классе разбиения Im ρ. 1.4.2

Отображения

Наибольшее применение на практике находят функциональные соответствия. Рассмотрим их подробнее. Отображение ϕ из A в B называют также функцией из A в B .8 При этом испольϕ зуют обозначения ϕ : A → B или A → B. Тот факт, что aϕb записывают как ϕ(a) = b ϕ или a 7→ b ; при теоретических выкладках удобна запись aϕ = b или даже aϕ = b. Множество всех отображений A → B будем обозначать F un (A, B). При A = B будем пользоваться обозначением F un (A). Рассмотрим специальные классы отображений множества A в множество B. Если окажется, что ϕ(x) = b ∈ B для всех x ∈ A, то отображение ϕ называют постоянным или константой. Единичное отношение MA , рассматриваемое как отображение A на себя, называют тождественным. Для тождественного отображения будем употреблять обозначение idA . Легко показать, что для отображений ϕ ∈ A × B и ψ ∈ B × C произведение ϕψ также является отображением. Действительно, для ϕ и ψ справедливо MA ⊆ ϕϕ# ∧ ϕ# ϕ ⊆MB

и

MB ⊆ ψψ # ∧ ψ # ψ ⊆MC .

Но тогда MA ⊆ ϕϕ# = ϕ MB ϕ# ⊆ ϕ(ψψ # )ϕ = (ϕψ)(ϕψ)# . Включение (ϕψ)# (ϕψ) ⊆MC показывается аналогично. Таким образом, ϕψ — отображение. Также понятно, что произведение функций как отображений совпадает с их композицией (∗) и, в силу ассоциативности произведения соответствий, имеет место def (ϕ ¦ ψ)(x) = ψ(ϕ(x)) = (ϕ ∗ ψ)(x)9 . Определение 1.12. Отображение ϕ : A → B называется 8

Таким образом, мы не различаем понятия функционального отображения и функции, хотя они не тождественны друг другу. Пример для знакомых с теорией алгоритмов: невычислимые функции, строго говоря, являются лишь функциональными отображениями, а не функциями. 9 Здесь становится очевидным удобство записи ψ(ϕ(x)) = xϕψ.

22

• вложением или инъективным отображением A в B , если idA = ϕϕ# . Легко видеть, что при вложении различные элементы A переходят в различные элементы B и прообраз ϕ# (y) элемента y ∈ Y — не более, чем одноэлементное множество. ϕ Тот факт, что ϕ — вложение A в B записывают A ,→ B. Если A ⊂ B, то вложение ϕ(x) = x называется естественным вложением A в B; • наложением или сюръективным отображением A в B , если ϕ# ϕ = idB . Легко видеть, что при наложении каждый элемент множества B имеет свой прообраз. π

Ясно, что для A = A1 × . . . × An отображения A →i Ai , определяемые как π (a1 , . . . , ai , . . . , ak ) 7→i ai , i = 1, n сюръективны. Они называются отображениями проектирования; • биекцией, биективным, взаимнооднозначным отображением, если idA = ϕϕ# ∧ ϕ# ϕ = idB , т.е. оно является одновременно и вложением, и наложением. Множество всех биективных отображений из A в B будем обозначать Bij (A, B). В случае A = B будем пользоваться обозначением Bij (A). Отображение ψ : B → A называется обратным отображению ϕ : A → B, если idA = ϕψ ∧ ψϕ = idB . Ясно, что обратное отображение существует только для биекций, и при этом оно единственно. Если ψ — отображение, обратное к ϕ, то используется обозначение ψ = ϕ−1 , и ϕ−1 = ϕ# . Моноид h F un (A), ∗, idA i называют моноидом эндоморфизмов множества A и обозначают End A. Группу h Bij (A), ∗, −1 , idA i называют группой автоморфизмов множества A и обозначают Aut A. Поскольку отображения являются отношениями, к ним можно применять все теоретико-множественные операции. Однако ясно, что если ϕ, ψ ∈ F un (A, B), то ϕ ∪ ψ и ϕ ∩ ψ будет от отображениями лишь при ϕ = ψ. Поэтому интересной здесь будет лишь операция произведения (композиции) отображений. Нетрудно показать, что произведение двух вложений, наложений или биекций также является, соответственно, вложением, наложением или биекцией. Отметим, что для конечного множества A инъективность, сюръективность и биективность функций из F un (A) — равносильные условия. Следующие две теоремы характеризуют вложение и наложение через свойства их произведений (композиций). Теорема 1.16. Отображение f : X → Y — инъекция если и только если для любых двух отображений g1 , g2 из некоторого множества Z в X g1 ¦ f = g2 ¦ f ⇔ g1 = g2 . Доказательство. (⇒) Пусть f — инъекция из множества X в Y и для любых двух отображений g1 , g2 из Z в X справедливо g1 ¦ f = g2 ¦ f . Но тогда же справедливо g1 ¦ f ¦ f # = g2 ¦ f ¦ f # или g1 ¦ idX = g2 ¦ idX , откуда g1 = g2 . (⇐) Пусть для любых двух отображений g1 , g2 из Z в X справедлива равносильность g1 ¦ f = g2 ¦ f ⇔ g1 = g2 , но f не является вложением. Тогда найдутся x1 и x2 из X, что x1 6= x2 , но f (x1 ) = f (x2 ). Возьмём в качестве Z одноэлементное множество z0 и построим два отображения g1 , g2 из Z в X такие, что g1 (z0 ) = x1 , g2 (z0 ) = x2 . Поскольку f (g1 (z0 )) = f (g2 (z0 )), а других значений аргумента нет, то g1 ¦ f = g2 ¦ f , g1 = g2 и x1 = x2 . Противоречие. 23

Теорема 1.17. Отображение f : X → Y — сюръекция если и только если для любых двух отображений g1 , g2 из Y в некоторое множество Z f ¦ g1 = f ¦ g2 ⇔ g1 = g2 . Доказательство. (⇒) Пусть f — сюръекция из множества X в Y и для любых двух отображений g1 , g2 из Y в Z справедливо f ¦ g1 = f ¦ g2 . Из того, что f — наложение следует непустота f # (y) для любого y ∈ Y . Пусть x ∈ f # (y).10 Тогда g1 (y) = g1 (f (x)) = g2 (f (x)) = g2 (y) , что в виду произвольности элемента y влечёт g1 = g2 . (⇐) Пусть для любых двух отображений g1 , g2 из Y в Z справедлива равносильность f ¦ g1 = f ¦ g2 ⇔ g1 = g2 , но f не является наложением. Тогда найдётся элемент y из области Y r Im(f ). Зафиксируем в Y элемент y0 6= Y и рассмотрим отображение g2 : Y → Y , определяемое условием ½ t, если t 6= y , g1 (t) = y0 , если t = y . Ясно, что g1 6= idY , в силу чего f ¦ g1 6= f ¦ idY . Однако для всех x ∈ X имеем g1 (f (x)) = f (x) = idY (f (x)) . Противоречие. Свойства биекции позволяют описывать фундаментальные свойства множеств. Теорема 1.18 (Кантора-Шрёдера-Бернштейна11 ). Если для двух множеств A и B существуют биекции θ1 между A и подмножеством B и θ2 между B и подмножеством A, то существует биекция между A и B. Доказательство. Обозначим A0 = A и Im(θ2 ) = A1 . Ясно, что можно считать A0 ⊃ A1 и Im(θ1 ) ⊂ B, иначе теорема тривиально справедлива. Также ясно, что в этом случае A и B — бесконечные множества. Последовательное применение отображений, указанных в формулировке теоремы, даёт взаимно однозначное отображение θ = θ1 ∗ θ2 множества A0 на своё подмножество A2 и A1 ⊃ A2 . Обозначим θ(Ai ) = Ai+2 , i = 0, 1, 2 . . .. Получим цепочку строго содержащихся друг в друге подмножеств A: A = A0 ⊃ A1 ⊃ T A2 ⊃ . . .. Обозначим Ci = Ai r Ai+1 , i = 0, 1, 2 . . . и C = i>0 Ai . По построению между множествами C0 , C2 , . . . существует взаимно однозначное соответствие θ; то же и для множеств C1 , C3 , . . .. Построим теперь взаимно однозначное отображение ϕ между A0 и A1 . Положим ½ θ(x), если x ∈ C2i , i = 0, 1, . . . , ϕ(x) = (см. рис. 2). x, иначе ϕ

θ −1

2 Таким образом, имеем взаимно однозначные соответствия A → A1 → B и ϕ ∗ θ2−1 — искомая биекция.

10

Заметим, что возможность указания такого x эквивалентна принятию аксиомы выбора (см. п. 2.1.4). Теорема была приведена без доказательства в работе Кантора 1883 г. и доказана позднее Шрёдером и Бернштейном. 11

24

A0

=

A1

=

C0

+

C1 + C2  +

C3 + C4 +

. . . 



u

 u

 u

C1

u

+

C2

+

C3

+

C4

+

...

+

+

Cu

u

C

Рис. 2: Схема соответствия между A0 и A1 (символ + подчёркивает дизъюнктивность разбиения множеств) 1.4.3

Основные свойства отображений

Пусть ∼ — эквивалентность на A. Тогда существует функция π : A → A/∼, ставящая в соответствие каждому элементу a ∈ A его класс эквивалентности, т.е. π(a) = [a]∼ . Такое отображение называется естественным (каноническим, натуральным). Каноническое отображение мы будем обозначать nat(A, ∼) или просто nat(∼), если множество A фиксировано при данном рассмотрении. Понятно, что nat(∼) — наложение. Пример 10. Для примера 7 имеем: 1. π(a) — мешок, в котором лежит зерно a; 2. π(u) — все слова, имеющие общую первую букву со словом u. Пусть дано отображение ϕ, определённое на множестве A. Его ядром называется отношение Ker ϕ ∈ R(A), заданное как def

a1 (Ker ϕ)a2 = ϕ(a1 ) = ϕ(a2 ) . Очевидно, что ядро ϕ — эквивалентность на своей области определения и подчеркивая это, Ker ϕ называют ядерной эквивалентностью. С ядерной эквивалентностью отображения ϕ из A связано фактор-множество A/Ker ϕ и натуральное отображение nat(A, Ker ϕ). Заметим, что отображения ϕ : A → B и nat(A, Ker ϕ) имеют общую ядерную эквивалентность, но отображают A в разные множества: соответственно в B и в A/Ker ϕ. Также нетрудно видеть, что Ker ϕ = ϕ ¦ ϕ# . Ясно, что если ядро отображения ϕ из A в B есть единичное отношение на A, то ϕ — вложение A в B : действительно, Ker ϕ = 1A означает, что a1 6= a2 , то ϕ(a1 ) 6= ϕ(a2 ). Далее мы будем пользоваться следующим удобным изображением соответствий. Если A, B, C, D — некоторые множества и α : A → B, β : B → C, γ : A → C, δ : B → D, ε : C → D , то указанные отображения на них наглядно задают в виде диаграмм, приведённых на рис. 3. Говорят, что эти диаграммы коммутативны, если γ = αβ и αδ = γε соответственно. Аналогично определяется коммутативность и для более сложных диаграмм. Биективные отображения будем обозначать на диаграммах двунаправленными стрелками ←→. Сформулируем теперь основную теорему о разложении отображений.

25

A

α

[

[[ ][ 

γ

wB 

A γ

β

C

u

C

α

ε

wB u

δ

wD

Рис. 3: Диаграммы отображений на множествах Теорема 1.19 (О разложении отображений). Пусть даны непустые множества A, B и отображение ϕ : A → B. Тогда для отображения ϕ справедливо разложение ϕ = π ∗ ϕ0 ∗ µ,

(1.3)

где π = nat(Ker ϕ), ϕ 0 — взаимнооднозначное соответствие между A/Ker ϕ и Im ϕ и µ — вложение Im ϕ в B. Доказательство. Теорема утверждает, что диаграмма

π

wB

ϕ

A

u

µ

u

ϕ0

A/Ker ϕ

w Im ϕ

коммутативна. Ясно, что Im ϕ есть подмножество B и в качестве µ возьмём естественное вложение. Из определения Ker ϕ следует, что отображение ϕ 0 : A/Ker ϕ → Im ϕ биективно. Отсюда следует справедливость разложения (1.3 ), если в качестве π взять nat(Ker ϕ). При этом все элементы разложения (1.3) определены однозначно. Следующая теорема является следствием только что доказанной. Теорема 1.20 (Основное свойство отображений). Пусть даны непустые множества A, B и отображение ϕ : A → B. Тогда имеется единственное отображение ψ : A/Ker ϕ → B являющееся вложением, и такое, что диаграмма A

ϕ

[[

nat (Kerϕ)

[]

wB 

ψ

A/Kerϕ коммутативна.

Доказательство. Положим в (1.3 ψ = ϕ 0 ∗ µ ). Тогда ψ([a]Kerϕ ) = ϕ(a) — однозначно определённое вложение Kerϕ в B. Из данной теоремы следует, что для любого отображения ϕ : A → B справедливо каноническое разложение ϕ = π ∗ ψ, где π = nat(A, Kerϕ) — наложение, а ψ — вложение. Такое разложение, очевидно, единственно. Это свойство и называют основным свойством отображений. Основное свойство отображений можно обобщить, если заметить, что для произвольной эквивалентности ∼, содержащийся в Ker ϕ существует единственное отображение χ : A/ ∼ → B. 26

Теорема 1.21 (О фактормножествах). Пусть даны непустые множества A, B с отображением ϕ : A → B и эквивалентность ∼ на A такая, что ∼ ⊆ Ker ϕ. Тогда имеется единственное отображение χ : A/∼ → B такое, что диаграмма

[[ [] nat (∼) A

ϕ

wB  χ

A/ ∼ коммутативна.

Доказательство. Коммутативность диаграммы обеспечивается при задании χ правилом χ([a]∼ ) = ϕ(a), a ∈ A. Такое задание корректно, поскольку, в силу ∼ ⊆ Kerϕ, всем элементам x из [a]∼ соответствует единственное значение χ(x) = ϕ(a). Ядерная эквивалентность отображения χ — единичное отношение на A/ ∼ лишь при ∼ = Kerϕ, и поэтому χ, вообще говоря, не есть вложение. Единственность χ следует из теоремы о классах эквивалентности. Из данной теоремы следует, что для любого отображения ϕ : A → B и эквивалентности ∼ на A такой, что ∼ ⊆ Ker ϕ, справедливо обобщённое разложение ϕ = π ∗ χ, где π = nat(A, ∼) — наложение. Такое разложение, очевидно, не единственно, поскольку возможны, вообще говоря, различные измельчения классов эквивалентностей по Kerϕ. Иногда данную теорему коротко формулируют как утверждение о возможности факторизации любого отображения по эквивалентности, содержащийся в его ядре. Из основного свойства отображений вытекает Теорема 1.22 (О дробных эквивалентностях). Пусть дано множество A и эквивалентности α, β на нём такие, что β ⊆ α. Тогда существуют отображение ε : A/β → A/α и биекция ψ : (A/β)/(α/β) → A/α такие, что диаграмма A ' [ ''nat α [ [ '') [^[ ε w A/α A/β '' ][ [ ' ) ' [ nat (α/β) [^ ψ nat β

(A/β)/(α/β)

коммутативна. Доказательство. Зададим функцию ε правилом ε([a]β ) = [a]α . Нетрудно видеть, что такое задание корректно. Далее применим теорему 1.20 к нижней части диаграммы. Поскольку ε, как легко видеть, накрытие, то ψ([[a]β ]α/β ) = ε([a]β ) = [a]α — биекция.

27

2

Порядки и решётки

2.1 2.1.1

Отношение порядка Предпорядки и порядки

Определение 2.1. Предпорядками называют рефлексивные и транзитивные бинарные отношения. Пример 11. рядок.

1. Отношение делимости ( | ) на множестве целых чисел Z есть предпо-

2. Отношение ρ на множестве действительных функций, задаваемое условием f ρh ⇔ «множество нулей функции f содержится во множестве нулей функции h». является предпорядком. Из определения следует, что если ρ — предпорядок то одновременная справедливость xρy и yρx может быть как при x = y, так и при x 6= y. Определение 2.2. Рефлексивные, антисимметричные и транзитивные бинарные отношения называют отношениями частичного порядка. Отношения частичного порядка будем обозначать v. Антисимметричность v определяет равенство x = y, при x v y и y v x. Когда x v y и x 6= y, то будем писать x @ y. Пример 12. 1. Оба предпорядка из примера 11 не являются частичными порядками ввиду отсутствия антисимметричности: (1) из m | n и n | m следует не m = n, а лишь |m| = |n|; (2) совпадение множеств нулей функций не означает равенства последних. 2. Важнейшим примером частичного порядка является отношение включения на совокупности подмножеств некоторого множества. При этом говорят, что такая совокупность упорядочена по включению. 3. Диагональное отношение на произвольном множестве является частичным порядком. Множество с таким порядком называют тривиально упорядоченным. Из предпорядка rho всегда можно построить порядок, если отождествить элементы, x и y, для которых одновременно xρy и yρx. Теорема 2.1. 1. Если ¹ — предпорядок на множестве P , то отношение ε, определяемое условием def

aεb = a ¹ b ∧ b ¹ a является эквивалентностью. 2. Отношение ¹ на фактор-множестве P/ε, определяемое условием def

[a]ε ≤ [b]ε = a ¹ b является частичным порядком. 28

Доказательство. 1. Вследствие определения, отношение ε приобретает свойство симметричности в дополнение к свойствам рефлексивности и транзитивности, наследуемых от ¹. 2. Если [a] = [a 0 ], [b] = [b 0 ] и [a] ≤ [b], то a 0 ≤ a ≤ b ≤ b 0 , т.е. [a 0 ] ≤ [b 0 ] и отношение ≤ на P/ε определено корректно. Свойства рефлексивности и транзитивности ≤ наследуются от отношения ≺. Если [a] ≤ [b] и [b] ≤ [a], то [a] ≤ [b] ≤ [a], т.е. [a] = [b], так что отношение ≤ оказывается и антисимметричным. Пример 13. Для примера 11 имеем: 1. [n]ε = { n, −n } Z/ε = { 0, 1, . . . }.

и

≤

есть отношение делимости на фактор-множестве

2. (a) f εh ⇔ «множество нулей функций f и h совпадают». (b) [f ]ε ≤ [h]ε ⇔ «множество нулей любой функции из [f ]ε содержится во множестве нулей любой функции из [h]ε ». Элементы a и b сравнимы, если либо a v b, либо b v a, и несравнимы в противном случае. Нетрудно видеть, что отношение сравнимости есть эквивалентность. Если a v b, то говорят, что a предшествует b или b следует за a, содержит a. Множество { x | a v x ∧ x v b } называют интервалом и обозначают [a, b]. Интервал [a, b] непуст, если a v b. Если [a, b] = {a, b}, то говорят, что a непосредственно предшествует b, и что b непосредственно следует за a . 2.1.2

Частично упорядоченные множества

Пару P = h P, v i, где P — множество, а v — частичный порядок на нём, называют частично упорядоченным множеством (сокращённо «ч.у. множеством»). P представляет собой пример нового типа алгебраической системы, а именно модели. АС является моделью, если в ней отсутствуют операции на носителе, но имеются отношения на нём. Пример 14.

1. Модели h R, 6 i, h N, | i, h B n , 4 i и h P(M ), ⊆ i суть ч.у. множества.

2. Пусть A 6= ∅. Модель h E(A), ⊆ i есть ч.у. множество, состоящее из разбиений множества A, упорядоченных по измельчению. Ясно, что если h P, v i — ч.у. множество и Q ⊆ P , то и h Q, v 0 i — ч.у. множество, где v 0 — сужение отношения v на Q . Для наглядного представления конечных ч.у. множеств, имеющих небольшое число элементов, используют диаграммы Хассе. На этих диаграммах изображают элементы ч.у. множеств, причём если элемент a предшествует элементу b, то a рисуют ниже b, и соединяют их отрезком, если a непосредственно предшествует b. На рис. 4 для примера приведены диаграммы Хассе для ч.у. множеств h { 0, 1, 2, 3 }, 6 i и h P({ 1, 2, 3 }), ⊆ i. Легко видеть, если v — отношение частичного порядка, то и псевдообратное к нему отношение v# , обозначаемое w, также будет являться частичным порядком. Ч.у. множества с порядками v и w называют дуальными или двойственными друг к другу. Всякому выражению x v y в дуальном ч.у. множестве соответствует выражение x w y. Ясно, что к ч.у. множествам применим следующий принцип двойственности.

29

3

AAA

{1, 2, 3}



0

A A

A {1, 2}

AA {1, 3}

AA {2, 3}

A A

A

A

A A

A A A A {1} {2} {3}

A AA

A A

AAA ∅

a)

b)

2

1

Рис. 4: Диаграммы Хассе двух ч.у. множеств Принцип двойственности (для частично упорядоченных множеств). Любое утверждение, истинное в ч.у. множестве остаётся истинным в ч.у. множестве, дуальном к нему. Определение 2.3. Элемент u ∈ P ч.у. множества h P, v i называют: 1) максимальным, если u v x ⇒ u = x, 2) минимальным, если u w x ⇒ u = x, 3) наибольшим, если x v u, 4) наименьшим, если x w u для любых x ∈ P . Из определений ясно, что элемент наибольший, если все другие элементы меньше его, и он максимальный, если нет элементов, больших его (аналогично для наименьшего и минимального элементов). Легко видеть, что ч.у. множество может иметь не более, чем по одному наибольшему и наименьшему элементу. Их называют соответственно единицей и нулём, а также универсальными гранями данного ч.у. множества. Для них мы будем использовать обозначения ι и o. Ч.у. множество с универсальными гранями называется ограниченным или, короче, ограниченным порядком. Понятно, что наибольший [наименьший] элемент есть одновременно и единственный максимальный [минимальный]. С другой стороны, максимальных или минимальных элементов может быть несколько, а может и не быть совсем. Пример 15. 1. Рассмотрим ч.у. множество h Nf1 , 4 i, где Nf1 — множество единичных наборов монотонной булевой функции f (x1 , x2 , x3 , x4 , x5 ) = x1 ∨ x2 x3 ∨ x3 x4 x5 . Для Nf1 нижние единицы (1, 0, 0, 0, 0), (0, 1, 1, 0, 0) и (0, 0, 1, 1, 1) функции f будут минимальными элементами, ˜1 = (1, 1, 1, 1, 1) — максимальным элементом, а наименьший элемент в Nf1 отсутствует. 30

2. Ч.у. множество h { 1, 2, 3, 4, 5, 6 }, | i имеет следующую диаграмму Хассе: 4

[[

[[  [[  [[  2 [ 3 5 [  AAAA [[  AA AAAA 1 6

Здесь 1 — наименьший элемент, 4, 5 и 6 — максимальные, а наибольшего элемента нет. 3. В ограниченном ч.у. множестве h P(A), ⊆ i наименьшим элементом является пустое подмножество, ∅, а наибольшим — само множество A. Будем обозначать через P ∗ (A) совокупность всех непустых подмножеств множества A. В ч.у. множестве h P ∗ (A), ⊆ i при |A| > 2 нет наименьшего элемента, а минимальными являются все одноэлементные подмножества. Будем обозначать через P0 (A) совокупность всех конечных подмножеств бесконечного множества A. В ч.у. множестве h P0 (A), ⊆ i наименьшим элементом будет пустое подмножество, а максимальных (следовательно, и наибольшего) элементов нет. Если ч.у. множество имеет наименьший элемент, то элементы, непосредственно следующие за ним называют атомами. Понятно, что таковых может и не оказаться. Данное определение атома ч.у. множества совпадает с определением 1.4 атома булевой алгебры, def если в ней принять x v y = (x = x u y). Двойственно определяются дуальные атомы или коатомы: это элементы, непосредственно предшествующие наибольшему элементу (предполагается, что таковой существует). Пример 16. В ч.у. множестве h { 0, 1, . . . }, | i наименьшим элементом является 1, наибольшим — 0, атомы суть простые числа, а коатомы отсутствуют. Определение 2.4. Пусть h P, v i — ч.у. множество и A ⊆ P . Множества AM и AO определяемые условиями def

AM =

©

x ∈ P | ∀ a ( a v x)

ª

A

def

и AO =

©

x ∈ P | ∀ a ( x v a)

ª

A

называются верхним и нижним конусами множества A , а их элементы — верхними и нижними гранями множества A соответственно. Верхним и нижним конусами пустого подмножества элементов P считают само множество P . Ясно, что любая верхняя грань подмножества A элементов некоторого ч.у. множества содержит любой из элементов A, и если A имеет наибольший элемент, то он одновременно является и наименьшим элементом AM . Аналогично для нижних граней. Теорема 2.2 (Свойства верхнего и нижнего конусов). Верхний и нижний конусы обладают следующими свойствами. 1. A ⊆ B влечёт B O ⊆ AO и B M ⊆ AM . 31

2. A ⊆ AMO ∩ AOM . 3. AM = AMOM . 4. AO = AOMO . 5. (A ∪ B)M = AM ∩ B M . 6. (A ∪ B)O = AO ∩ B O . Доказательство. 1. Это свойство вытекает непосредственно из определения. 2. Так как для любых x ∈ A и y ∈ AM справедливо x v y, то A ⊆ AMO . Аналогично проверяется, что A ⊆ AOM . 3, 4. В приводимом ниже соотношении первое включение следует из свойства (2), а последнее — из (2) и (1). AM ⊆ (AM )OM = (AMO )M ⊆ AM , откуда вытекает свойство (3). Аналогично для (4). 5, 6. Эти свойства вытекает непосредственно из определения верхнего и нижнего конусов ч.у. множества. Определение 2.5. Если в AM существует наименьший элемент, то он называется точной верхней гранью множества A и обозначается sup A. Если в AO существует наибольший элемент, то он называется точной нижней гранью множества A и обозначается inf A. В частности, точной верхней [нижней] гранью пустого множества является наименьший [наибольший] элемент ч.у. множества. Пример 17. 1. Пусть P = { a, b, c, d } и два различных порядка на P задаются следующими диаграммами Хассе: d4

a

4 hhh 44 hhh  c [[444  [4 hh

d4

a

b

h 44 h hhh c [ 444 h  [[44 hh

b

Для A = { a, b } имеем AM = { c, d } в обоих случаях, но в первом случае sup A отсутствует, а во втором sup A = c.12 ˜ ч.у. множества h B n , 4 i имеем 2. Для элемента α α ˜ M = B(˜ α, ˜1),

α ˜ O = B(˜0, α ˜ );

sup α ˜ = inf α ˜ = α ˜,

˜ — подкуб B n , натянутый на вершины α ˜ где B(˜ α, β) ˜ и β. 12

Строго говоря, вторая диаграмма не есть диаграмма Хассе: линии, соединяющие элемент d с элементами a и b здесь излишни.

32

Непосредственно из определений вытекает также справедливость следующих соотношений. 1. Если a v b, то sup { a, b } = a, inf { a, b } = b. 2. Пусть h P, v i — ч.у. множество и A ⊆ B ⊆ P . Если существуют sup A и sup B ( inf A и inf B ), то sup A v sup B (inf A w inf B ). 3. Если A ⊆ P(M ), то sup A совпадает с пересечением всех надмножеств A, а inf A — с объединением всех подмножеств A. Определение 2.6. Частичный порядок v на множестве P называется линейным, если любые два элемента из P сравнимы. В этом случае ч.у. множество h P, v i называется линейно упорядоченным или цепью. На рис. 4a ) приведена диаграмма Хассе четырёхэлементной цепи. Ч.у. множество может содержать цепи в качестве ч. у. подмножеств. Цепь в ч.у. множестве называется максимальной, если её объединение с любым не принадлежащим ей элементом цепью не является. В ч.у. множестве h N, | i для любого M ⊆ N цепью является, например, подмножество { 2n | n ∈ M }; при M = N имеем максимальную цепь. 2.1.3

Изотонные отображения и порядковые идеалы

Определение 2.7. Пусть P и P 0 — ч.у. множества. Отображение ϕ : P → P 0 называется порядковым гомоморфизмом или изотонным отображением, если следование x v y ⇒ ϕ(x) v ϕ(y), и обратно изотонным отображением, если следование ϕ(x) v ϕ(y) ⇒ x v y выполняются для любых x, y ∈ P . Если ϕ изотонно, обратно изотонно и инъективно, то его называют вложением или ϕ мономорфизмом ч.у. множества P в ч.у. множество P 0 , что обозначают P ,→ P 0 . Сюръективный мономорфизм ч.у. множеств называют порядковым изоморфизмом. Если ч.у. множества P и P 0 (порядково) изоморфны, то пишут P ∼ = P 0. Пример 18. 1. Ч.у. множество a ) изображённое на рис. 4 является изотонным образом ч.у. множества b ), если в качестве отображения взять функцию ϕ(x) = |x|. Это отображение не инъективно и, следовательно, вложением не является. 2. Тождественное отображение какого-либо подмножества ч.у. множествва h N, | i во множество натуральных чисел с естественным порядком изотонно, но не обратно изотонно и, следовательно, вложением также не является. 3. Если Q — неодноэлементное ч.у. множество с тривиальным порядком, а Q 0 — то же самое множество с нетривиальным порядком, то тождественное отображение Q на себя является изотонным и взаимнооднозначным, но не обратно изотонным и, следовательно, не изоморфизмом между данными ч.у. множествами. 4. Естественное вложение nZ в Z, где n ∈ N0 , есть их вложение как ч.у. множеств с естественным порядком 6. Пусть P и P 0 — ч.у. множества. Отображение ϕ : P → P 0 называется антиизотонным, если следование x v y ⇒ ϕ(x) w ϕ(y) выполняется для любых x, y ∈ P . Отображение ϕ булеана непустого множества X в себя такое, что для A ⊆ X ϕ(A) = X, есть антиизотонное отображение. Легко видеть, что для ч.у. множеств P и P 0 биекция ϕ : P → P 0 есть порядковый изоморфизм, если и только если для любых a, b ∈ P имеет место a v b ⇔ ϕ(a) v ϕ(b). 33

Теорема 2.3. Любое ч.у. множество может быть вложено в булеан подходящего множества, упорядоченный по включению. Доказательство. Пусть h P, v i — ч.у. множество. Сопоставим каждому x ∈ P его нижний конус xO . Объединение всех нижних конусов элементов P образует множество U ∈ P(P ). Понятно, что введённое соответствие ϕ есть биекция между P и U . С другой стороны, по свойству нижнего конуса, x v y ⇔ xO ⊆ y O и ϕ есть изоморфизм между h P, v i и h U, ⊆ i. Таким образом, показано h P, v i ,→ h P(P ), ⊆ i. К ч.у. множествам можно применять различные операции. Рассмотрим некоторые из них. Определение 2.8. Если P = h P, vp i и Q = h Q, vq i — два ч.у. множества с непересекающимися носителями, то их прямой суммой или дизъюнктивным объединением P + Q называется множество P ∪ Q с частичным порядком v таким, что x v y когда либо x vp y, либо x vq y. Ч.у. множество, не являющийся прямой суммой некоторых двух других ч.у. множеств называется связанным. Если P = h P, vp i и Q = h Q, vq i — два ч.у. множества, то их прямым или декартовым произведением P × Q называется множество P × Q с частичным порядком v таким, что (x, y) v (x 0 , y 0 ) только когда x vp x 0 и y vq y 0 . Прямое произведение n экземпляров ч.у. множеств P обозначают Pn . Для того, чтобы нарисовать диаграмму Хассе прямого произведения конечных ч.у. множеств P и Q рисуют диаграмму Хассе ч.у. множества P , отбрасывая соединения между элементами P заменяют каждый элемент x ∈ P копией Qx ч.у. множества Q и соединяют соответствующие элементы множеств Qx и Qy , если элементы x и y были соединены в диаграмме Хассе ч.у. множества P . Пример 19. На рис. 5 показан пример прямого произведения двух ч.у. множеств вида “зигзаг”. Из определения ясно, что для ч.у. множеств P и Q справедливо P × Q ∼ = Q × P, хотя соответствующие диаграммы Хассе обычно выглядят совершенно не похожими друг на друга. Легко убедиться, что для операций + и × над ч.у. множествами (с точностью до изоморфизма) выполняются законы ассоциативности и коммутативности и первый дистрибутивный закон: P × (Q + R) ∼ = (P × Q) + (P × R) . Здесь предполагается, что Q + R существует. Если P = h P, vp i и Q = h Q, vq i — два ч.у. множества, то обозначим через QP множество всех изотонных отображений из P в Q. Введём на QP порядок v, положив f v g, если f (x) vq g(x) для всех x ∈ P . Таким образом, h QP , v i есть ч.у. множество. Можно проверить, что для +, × и введенной выше операции “возведения в степень” над ч.у. множествами выполняются соотношения RP +Q ∼ = RP × RQ ;

(RQ )R ∼ = RQ×R

(здесь также предполагается, что Q + R существует). Определение 2.9. Пусть h P, v i — ч.у. множество. Подмножество I элементов P называется порядковым идеалом, если из x ∈ I и y v x следует y ∈ I. Подмножество F элементов P называется порядковым фильтром, если из x ∈ F и x v y следует y ∈ F . 34

 [[[  ◦

◦

◦

◦

[[ ◦ [

◦

◦

Z3

Z4

◦[

A A ◦

A A A AAA [[



A A AAA ◦ AAA ◦ ◦

◦

◦ ◦[ [[ AAAA AAA A



[[[



AA AAAA A A ◦ ◦ ◦ ◦

Z3 × Z4 Рис. 5: Диаграммы Хассе двух ч.у. множеств и их прямого произведения Таким образом, порядковые идеалы [фильтры] ч.у. множества суть такие его подмножества, которые вместе с каждым своим элементом a содержат все элементы, предшествующие [следующие за] a. Ясно, то ∅ есть порядковый идеал любого ч.у. множества множества h P, v i. Если x — элемент ч.у. множества, то xO и xM являются порядковыми идеалом и фильтром соответственно. Такие идеалы и фильтры называют главными; мы будем обозначать их J(x) и F (x) соответственно. Множество всех порядковых идеалов ч.у. множества P , упорядоченное по включению, образует ч.у. множество, которое мы будем обозначать J(P ). Теорема 2.3 утверждает, что ϕ P ,→ J(P ) и ϕ(x) = xO = J(x). Антицепь есть подмножество A ч.у. множестве P , в котором все элементы попарно несравнимы. Например, в ч.у. множестве h N, | i антицепью является произвольное подмножество взаимно некратных чисел, а в множестве h B n , 4 i — совокупности верхних нулей либо нижних единиц некоторой монотонной булевой функции. Если h P, v i — конечное ч.у. множество, то существует взаимнооднозначное соответствие между его анитцепями и порядковыми идеалами. Действительно, с одной стороны, S множество M максимальных элементов идеала I есть антицепь, а с другой — I = a∈M aO . Если некоторое подмножество A ч.у. множества P и его идеал I связаны таким соотношением, то говорят, что A порождает I. В случае A = { a1 , . . . , ak } пишут I = h a1 , . . . , ak i; например, J(a) = h a i. Пример 20. На рис. 6 показаны диаграммы Хассе четырёхэлементного ч.у. множества P и множества его порядковых идеалов J(P ). Каждому порядковому идеалу из J(P ) соответствует антицепь P .

35

hdi

[[ [

ha, ci

hhh

a

hhh

d

[[

[[

hhh

c

hai

   ha, bi [  [[  

hbi [[ [  

  

hci

∅

b

J(P )

P

Рис. 6: Диаграммы Хассе ч.у. множеств P и J(P ). Главные идеалы выделены 2.1.4

Вполне упорядоченные множества и смежные вопросы

В ходе исследований ч.у. множеств были сформулированы следующие утверждения. Лемма Куратовского-Цорна. Если в ч.у. множестве P любая цепь имеет верхнюю грань, то каждый элемент из P содержится в некотором максимальном. Принцип Хаусдорфа. Всякая цепь любого ч.у. множества может быть вложена в максимальную цепь. Оказалось, что эти утверждения эквивалентны. Более того, они также эквивалентны фундаментальной теоретико-множественной аксиоме выбора и аксиоме о полном упорядочении. Аксиома выбора (AC). Для любого непустого множества A существует отображение f , сопоставляющая каждому непустому подмножеству B множества A элемент из B : f (B) ∈ B для любого B ∈ P ∗ (A). Таким образом, аксиома выбора утверждает, что для любого всюду определённого соответствия можно построить вложенное в него функциональное. Для формулировки следующей аксиомы нам потребуются новое понятие. Определение 2.10. Линейный порядок P называется полным, если каждое его непустое подмножество содержит наименьший элемент. В этом случае множество P называют вполне упорядоченным, а его элементы — трансфинитами.

36

Во вполне упорядоченном множестве каждый элемент, если только он не является наибольшим, имеет единственный непосредственно следующий и может иметь не более одного непосредственно предшествующего. Элемент вполне упорядоченного множества не имеющий предшествующего, если только он не является наименьшим, называется предельным. Пример 21. 1. Очевидно, вполне упорядочены все конечные цепи, а так же цепь N с естественным порядком. Множество целых чисел Z не является вполне упорядоченным относительно естественного порядка, поскольку оно не имеет наименьшего элемента. Если же на Z задать порядок 0 @ 1 @ 2 . . . @ n . . . @ −n . . . @ −2 @ −1 , то получим цепь, в которой не все подмножества будут иметь наименьшие элементы, и поэтому это ч.у. множество не приобретёт свойства полной упорядоченности. 2. Множество {m −

1 n

| m, n ∈ N } = { 0, 12 , 23 , 34 , . . . , 1, 1 + 21 , 1 + 23 , . . . , . . . , m, m + 12 , m + 23 , . . . }

с естественным порядком является вполне упорядоченным. Его предельные элементы суть натуральные числа. Аксиома о полном упорядочении. Любое непустое множество можно вполне упорядочить. Пример 22. Множество целых чисел Z можно вполне упорядочить считая, например, что 0 @ 1 @ −1 @ 2 @ −2 @ 3 . . . или 1 @ 2 @ . . . @ 0 @ −1 @ −2 @ . . . . В последнем случае 0 — предельный элемент. Покажем, к примеру, как аксиому выбора можно получить из аксиомы о полном упорядочении. Пусть A — непустое множество; по аксиоме о полном упорядочении его можно считать вполне упорядоченным. Тогда в качестве f можно взять отображение, ставящее в соответствие каждому непустому подмножеству A его наименьший элемент. Отметим, что известны и другие предложения, эквивалентные приведённым, например, о равномощности множеств X и X × X. Доказательство эквивалентности всех упомянутых утверждений можно найти в [13]. Таким образом, истинными или ложными все эти утверждения могут быть только одновременно. Что же имеет место “в действительности”? Ответ на поставленный вопрос зависит от того, какими свойствами мы наделяем понятие «множество». В наиболее общей форме проблема выражена в аксиоме выбора, предложенной Э. Ц´ермело в 1904 г. при разработке аксиоматической теории множеств. Для конечных множеств её справедливость очевидна. Однако при рассмотрении бесконечных совокупностей бесконечных множеств эта очевидность теряется. Все же попытки свести указываемое утверждение к фундаментальным принципам теории множеств оказались безуспешными: в аксиоматике ZF Цермело-Френкеля теории множеств13 не выводимы ни отрицание аксиомы выбора 13

См., например, Френкель А., Бар-Хиллел И. Основания теории множеств. — М.: Мир, 1966.

37

(К. Гёдель, 1939), ни она сама (П. Коэн, 1963). Таким образом, аксиома выбора является независимым от ZF утверждением, и добавление к ZF как самой этой аксиомы, так и её отрицания порождает две равноправные непротиворечивые аксиоматики теории множеств.14 Поэтому в практической работе можно как принять аксиому выбора, так и отказаться от неё. Исследования показали, что, с одной стороны, имеются “отрицательные” последствия принятия аксиомы выбора. Выяснилось, что её принятие влечет существование объектов с парадоксальными, на первый взгляд, свойствами: неизмеримого по Лебегу множества действительных чисел; такого разбиения шара на конечное число частей, что из них движениями в пространстве оказывается возможным составить два таких же шара и др. Отметим, что все рассматриваемые утверждения неконструктивны и являются теоремами чистого существования.15 С другой стороны, отклонение аксиомы выбора существенно обедняет содержание конкретных исследований, не связанных с вопросами оснований математики и теории множеств. Например, без её привлечения не удается доказать ни наличия базиса у произвольного векторного пространства, ни эквивалентности двух определений непрерывности функции в точке (на языке ε-δ и через пределы последовательностей), ни некоторых других важных и привычных свойств различных математических объектов. За принятие аксиомы выбора говорит и следующий, весьма сильный, аргумент. Как отмечалось выше, К. Гёдель показал, что присоединение аксиомы выбора к системе ZF не увеличивает опасности впасть в противоречие, т.е. если в полученной системе встретилось противоречие, то причина его в ZF , а не в аксиоме выбора. Более того, из доказательства Гёделя вытекает, что всякое свойство натуральных чисел, которое можно доказать с помощью аксиомы выбора, можно доказать и без неё. В силу этого, по крайней мере в теории натуральных чисел, аксиому выбора можно рассматривать как вспомогательное средство, нужное лишь для упрощения доказательств. Указанные соображения обычно перевешивают, и при конкретных математических исследованиях аксиому выбора (или эквивалентное ей утверждение, если это более удобно), как правило, принимают. Заметим, что в данном пособии мы будем оставаться в рамках т.н. наивной теории множеств, которая позволяет рассматривать любое множество, точно определяемое каким-либо свойством. Последовательное применение этого принципа, как известно, может привести к противоречиям (парадоксам), однако мы не встретимся с ним в ходе наших рассмотрений. def Для вполне упорядоченного множества определяют множество [o, a) = aO r {a}, которое называют начальным отрезком a (при этом [o, o) есть пустое множество). Справедлива Теорема 2.4 (О сравнении вполне упорядоченных множеств). Пусть A и B — два вполне упорядоченных множества. Тогда имеется лишь одна из следующих возможностей: 1)

A ∼ = B;

2)

A изоморфно начальному отрезку B ;

3)

B изоморфно начальному отрезку A.

14

Естественно, при условии непротиворечивости самой системы ZF , что, как известно, является открытым вопросом. 15 Обычно используемое выражение «чистая теорема существования» является неточным переводом с немецкого.

38

Доказательство этой теоремы имеется, например, в [14]. Если между множествами A и B существует биекция, назовем их равномощными, что будем обозначать A = B. В противном случае будем говорить, что они неравномощны и писать A 6= B. Здесь под X понимается новый объект, связанный с множеством X; он называется кардинальным числом X или кардиналом. Используя теорему 2.4, теорему Кантора-Шрёдера-Бернштейна (1.18) и аксиому о полном упорядочении, легко доказать справедливость следующего утверждения. Теорема 2.5 (О сравнении множеств). Для любых множеств A и B имеется лишь одна из следующих возможностей: 1) A = B; 2) A = B 0 для некоторого B 0 ⊆ B, но B 6= A0 для любого A0 ⊆ A; 3)

B = A0 для некоторого A0 ⊆ A, но A 6= B 0 для любого B 0 ⊆ B.

Данная теорема лежат в основе учения о мощности множеств. Она позволяет ввести порядок на множестве кардинальных числе, а именно считать, что A < B и A > B соответственно в случаях 2) и 3) данной теоремы. Важно отметить, что на вполне упорядоченные множества можно обобщить метод математической индукции. Утверждение 2.1 (Принцип трансфинитной индукции). Пусть P — вполне упорядоченное множество с каждым элементом α которого связано утверждение Sα , образующие совокупность S. Тогда, если из справедливости Sβ для всех β ∈ [o, α) следует справедливость Sα , то верны все утверждения из S. Доказательство. Пусть среди S имеется неверное утверждение. Тогда непусто множество E неверных утверждений. Пусть α — наименьший элемент E, который всегда существует в силу полного порядка на P . Но тогда, поскольку Sβ справедливо для всех β ∈ [o, α), то справедливо и Sα . Противоречие.

2.2 2.2.1

Алгебраические решётки Решёточно упорядоченные множества и решётки

Определение 2.11. Ч.у. множество, в котором для любых элементов a и b существуют inf { a, b } и sup { a, b } называют решёточно упорядоченным. Ясно, что в решёточно упорядоченном множестве точные верхние и нижние грани существуют для любого конечного подмножества элементов. Пример 23. 1. Модели, изображённые на рис. 4 (см. c. 30) суть решёточно упорядоченные множества. 2. Любая цепь решёточно упорядочена. Модели h R, 6 i, h N, | i и h P(A), ⊆ i суть решёточно упорядоченные множества. Операциями объединения будут здесь max, ∨ (НОК) и ∪, а операциями пересечения — min, ∧ (НОД) и ∩ соответственно. 3. На рис. 7 представлены два ч.у. множества, причем лишь первое из них является решетчато упорядоченным, т.к. во втором не существуют sup { a, b } и inf { c, d }.

39

ι

[[

[[

[[ [  [[[ [[  c b [ d [[  AAAA A AAA a

[[   [  c

AA d A A

A A

AA a[ b [  [[   ι

o

o

Рис. 7: Диаграммы Хассе двух ч.у. множеств с 6-ю элементами Мы ввели понятие решёточно упорядоченного множества, отталкиваясь от отношения порядка. Однако возможен другой, эквивалентный данному, подход, опирающийся на алгебраические операции. Определение 2.12. (Алгебраической) решёткой L называется непустое множество L с заданными на нём двумя бинарными операциями: объединения (t ) и пересечения ( u ), подчиняющимися двойственным парам законов коммутативности, ассоциативности, идемпотентности и поглощения (см. с. 4). Отметим, что раньше вместо термина «решётка» часто употреблялся термин структура. Теперь под структурой обычно понимают алгебраическую систему. Приведённое выше определение утверждает, что алгебраическая решётка есть AC L = h L, t, u i, двуместные операции t и u которой удовлетворяют указанным законам. Следствием их двойственности является Принцип двойственности (для решёток). Любое утверждение, истинное в некоторой решётке, остаётся истинным, если в нём произвести замены символов u ↔ t. В п. 1.1.1 было показано, что, например, законы идемпотентности вытекают из законов поглощения, и, поэтому, указанная система аксиом избыточна. Использование именно такой системы аксиом традиционно. Для универсальных граней o и ι решёток выполняются законы t o, u ι (см. определение 1.1). Ясно, что бесконечная решётка может содержать, а может и не содержать универсальных граней, а конечная решётка их обязательно содержит. Пример 24. 1. Очевидно, любая булева алгебра есть алгебраическая решётка. С другой стороны, любая цепь есть решётка, являясь булевой алгеброй лишь при числе элементов, равном 2. 2. На рис. 8 изображены диаграммы Хассе всех, за исключением линейного порядка, решёток с пятью элементами. Последние две решётки называют “пятиугольник” и “ромб” и обозначают, соответственно, N5 и M3 . 3. Ч.у. множество h E(A), ⊆ i всех отношений эквивалентности на множестве A, рассмотренное в примере 14.2 есть решётка с универсальными гранями o =MA и

40

 [[ ι

ι

 [  c [ b [  [  

 [[  a

o

[  c b [ [[  

a)

b)

ι4 4  4  4

ι [  [[   a[ c b [[  

a

c

a



o

4

4 44

hhh h

[[

o

b

h h [ h h o

c) N5

d) M3

Рис. 8: Диаграммы Хассе всех решёток с 5-ю элементами (линейный порядок опущен).

41

ι = OA . Здесь для эквивалентностей α и β в качестве α t β выступает их эквивалентное замыкание (случае перестановочности α и β совпадающее с их произведением и объединением — см. на c. 20 следствие 2 утверждения 1.2), а в качестве u — теоретико-множественное пересечение α ∩ β. Эту решётку называют также решёткой всех разбиений множества A. 4. Множество Sub (G) всех подгрупп группы G с операциями xty = hx, yi (подгруппа порожденная объединением подгрупп x и y ) и xuy = x∩y (это множество, как известно, всегда является группой) есть решётка. Здесь o = E (единичная группа) и ι = G. В ч.у. множестве L = h N, | i для любой пары натуральных чисел m и n существуют наименьшее общее кратное m ∨ n и наибольший общий делитель m ∧ n, из определений которых следует, что m∨n = sup { m, n } и m∧n = inf { m, n }. Таким образом, L — решёточно упорядоченное множество. С другой стороны, операции ∨ и ∧ удовлетворяют законам коммутативности, ассоциативности и идемпотентности, и поэтому h N, ∨, ∧ i — алгебраическая решётка. Наконец, если в данной решётке ввести отношение δ по праdef вилу mδn = m ∧ n = m, то δ оказывается отношением «делит», и, таким образом, h N, δ i = L — ч.у. множество. Данное рассмотрение наводит на мысль, что алгебраические решётки и частично упорядоченные множества тесно связаны. Это действительно так, и данная связь устанавливается нижеследующей теоремой. Теорема 2.6. 1. Пусть h P, v i — решёточно упорядоченное множество. Если для любых элементов x и y из P положить def

x t y = sup {x, y} ,

def

x u y = inf {x, y} ,

то h P, t, u i будет алгебраической решёткой. 2. Пусть h L, t, u i — алгебраическая решётка. Если для любых элементов x и y из P положить def

xvy = xuy =x

def

(или x v y = x t y = y) ,

то h L, v i будет решёточно упорядоченным множеством. Доказательство. Доказательство (1) сводится к проверке законов коммутативности, ассоциативности и поглощения в полученной АС h P, t, u i. Доказательство (2) сводится к проверке рефлексивности, антисимметричности и транзитивности у введённого отношения v и установлению, что sup { x, y } = x t y, а inf { x, y } = x u y. Теорема 2.6 устанавливает взаимнооднозначное соответствие между решёточно упорядоченными множествами и алгебраическими решётками: из одной АС всегда можно получить другую. Поэтому термин «решётка» применяют для обоих понятий, имея в виду, что любую решётку можно представить либо как ч.у. множество, либо как алгебру. Например, решёточно упорядоченные множества h R, 6 i, h N, | i и h P(A), ⊆ i из примера 23 можно записать в виде алгебраических решёток соответственно как h R, max, min i, h N, ∨, ∧ i и h P(A), ∪, ∩ i. Возможность такого рассмотрения решёток позволяет вводить в них как порядковые, так и алгебраические операции, что приводит к богатой и многообразной в приложениях теории. Отметим очевидную изотонность решётчатых операций t и u: если a1 v b1 и a2 v b2 , то a1 t a2 v b1 t b2 и a1 u a2 v b1 u b2 . 42

2.2.2

Основные свойства решёток

Теорема 2.7. Элементы x, y и z любой решётки удовлетворяют следующим неравенствам полудистрибутивности Dtr1 w : (x t y) u z w (x u z) t (y u z) ; Dtr2 v : (x u y) t z v (x t z) u (y t z) ; и полумодулярности M od v : M od w :

x v y ⇒ x t (y u z) v y u (x t z) = (x t y) u (x t z) ; x w y ⇒ x u (y t z) w y t (x u z) = (x u y) t (x u z) .

Доказательство. Имеем xuz v x v xty xuz v z и

yuz v y v xty yuz v z

¾ ⇒ x u z v (x t y) u z ¾ ⇒ y u x v (x t y) u z .

Таким образом (x t y) u z есть верхняя грань для x u z и y u z. Это означает, что (x u z) t (y u z) v (x t y) u z , и следование Dtr1 w доказано. Второе неравенство дистрибутивности следует из только что доказанного по принципу двойственности. Неравенства полумодулярности есть частный случай неравенств дистрибутивности. Определение 2.13. Отображение ϕ решётки L в решётку L0 называется алгебраическим или решёточным гомоморфизмом, если для любых x, y ∈ L справедливы равенства ϕ(x t y) = ϕ(x) t ϕ(y) и ϕ(x u y) = ϕ(x) u ϕ(y) , что записывают ϕ = Hom (L, L0 ). Биективный решёточный гомоморфизм есть решёточный изоморфизм. Изоморфизм решётки в себя называется автоморфизмом. Инъективные и сюръективные решёточные гомоморфизмы называют решёточными (или алгебраическими) мономорфизмами и эпиморфизмами соответственно. Порядковые гомоморфизмы решёток как ч.у. множеств, вообще говоря, не являются ϕ алгебраическими: отображение P0 (M ) → N0 , ϕ(X) = |X| являясь изотонным, не сохраняет ни одну из решёточных операций. Напротив, алгебраический гомоморфизм решёток будет и их порядковым гомоморфизмом. Действительно, если ϕ — алгебраический гомоморфизм решётки h A, t, u i на некоторую другую решётку, то, поскольку ϕ сохраняет пересечение, для любых x, y ∈ A имеем x v y ⇔ x = xuy

⇒ ϕ(x) = ϕ(x u y) = ϕ(x) u ϕ(y) ⇔ ϕ(x) v ϕ(y) , (2.1)

и, значит, ϕ изотонно. Аналогично изотонность ϕ следует и из сохранения объединения. Поэтому можно сказать, что алгебраический гомоморфизм решёток, “сильнее” порядкового. В случае изоморфизма проблемы снимаются. 43

Теорема 2.8. Две решётки алгебраически изоморфны, если и только если они изоморфны как порядки. Доказательство. (⇐) Пусть ϕ — алгебраический изоморфизм решётки h A, t, u i на некоторую другую решётку. Так как отображение ϕ взаимнооднозначно и изотонно, остаётся показать его обратную изотонность. Обратная изотонность устанавливается обращением следования в (2.1) что можно сделать, поскольку ϕ взаимнооднозначно. (⇒) Пусть A и B — две решётки, изоморфные как порядки. Докажем устойчивость операции u относительно порядкового изоморфизма ϕ, т.е. что ϕ(x u y) = ϕ(x) u ϕ(y). Устойчивость операции t относительно ϕ будет справедлива по двойственности. Для произвольных элементов x, y ∈ A в силу изотонности ϕ в решётке B справедливым ϕ(x u y) ∈ { ϕ(x), ϕ(y) }O . Пусть b есть элемент { ϕ(x), ϕ(y) }O . Тогда, в силу сюръективности ϕ, в A найдется элемент a, такой, что ϕ(a) = b. Но тогда ϕ(a) v ϕ(x) ∧ ϕ(a) v ϕ(y) ⇒ a v x ∧ a v y ⇒ a v (x u y) ⇒ ϕ(a) v ϕ(x u y) (первое следование здесь возможно в силу обратной изотонности ϕ ). Таким образом, ϕ(x u y) = inf { ϕ(x), ϕ(y) }, или ϕ(x u y) = ϕ(x) u ϕ(y). Данная теорема позволяет не различать типы изоморфизма решёток и использовать для него традиционный символ ∼ =. Имея исходные решётки, можно строить новые, используя их гомоморфные образы и операции + и × над ч.у. множествами. При этом можно показать, что для построения диаграммы Хассе декартова произведения конечных решёток остается верным способ её построения для них, как для ч.у. множеств. Определение 2.14. Подрешёткой решётки L называется решётка L0 такая, что L0 — устойчивое относительно операций t и u подмножество L. При этом используется обозначение L0 6 L. Пример 25. 1. Каждое подмножество решётки L является подрешёткой, если и только если L — цепь. 2. Пересечение подрешёток либо пусто, либо является подрешёткой. Для любых элементов x и y решётки L интервал [ x, y ] либо пуст, либо является подрешёткой L. В силу этого, оказывается удобным считать подрешёткой и пустое множество. Тогда пересечение любой совокупности подрешёток и любой интервал решётки оказываются подрешёткой. 3. Если ϕ = Hom (L, L0 ), то Im ϕ 6 L0 . 4. Обозначим через N◦ множество натуральных чисел, свободных от квадратов (см. пример 3.4). Тогда h N◦ , ∨, ∧ i 6 h N, ∨, ∧ i. 5. С помощью теоремы 2.8 устанавливается, что решётка N◦ изоморфна решётке P0 (A) всех конечных подмножеств счётного множества A (считая, что 1 свободно от квадратов). Рассмотрим любую биекцию ϕ между множеством простых чисел (которые все содержатся в N◦ , и множество которых, как показал Евклид, счётно) и A. Таким образом, определено частичное инъективное отображение ϕ для простых чисел из N◦ в A. Полагаем ϕ(1) = ∅. Далее, для остальных элементов n = p1 . . . pk , k > 1 из N◦ , 44

где p1 , . . . , pk — различные простые числа, положим ϕ(n) = { ϕ(p1 ), . . . , ϕ(pk ) }. Нетрудно проверить, что полученное отображение ϕ есть изоморфизм указанных решёток. Легко проверяется, что прямое произведение решёток является решёткой. Ясно также, что совокупность Sub(L) подрешёток решётки L является ч.у. множествм (упорядоченным по включению). Определение 2.15. Пусть h L, t, u i — решётка. Подмножество I элементов L называется решёточным идеалом, если x∈I ∧ yvx ⇒ y∈I

и

x, y ∈ I ⇒ x t y ∈ I .

Подмножество F элементов L называется решёточным фильтром, если x∈F ∧ xvy ⇒ y∈F

и

x, y ∈ F ⇒ x u y ∈ F .

Очевидно, идеалы [фильтры] решёток суть их устойчивые относительно операций t [ u ] порядковые идеалы [фильтры]. Непустое подмножество I [ F ] оказывается идеалом [фильтром] решётки L, если и только если для любых её элементов x и y справедлива эквивалентность x, y ∈ I ⇔ x t y ∈ I

[x, y ∈ F ⇔ x u y ∈ F ] .

Легко видеть, что если L — решётка, а I и F — соответственно идеал и фильтр на ней, то для произвольного её элемента x если y ∈ I, то x u y ∈ I, а если y ∈ F , то x t y ∈ F . Сама решётка L всегда будет своим идеалом и фильтром. Все другие идеалы [фильтры] L называют собственными. Если L имеет наименьший o [наибольший ι] элемент, то он будет идеалом [фильтром] L. В случае, когда в решётке нет наименьшего [наибольшего] элемента, то в число её идеалов [фильтров] договариваются включать пустое подмножество. Если x — элемент решётки, то главные порядковые идеал J(x) = xO и фильтр F (x) = xM являются, очевидно, также и (главными) решёточными идеалом и фильтром. В конечной решётке все решёточные идеалы и фильтры — главные. Для бесконечных решёток это не так. Например, для бесконечного множества A совокупность P0 (A) всех его конечных подмножеств будет неглавным идеалом в решётке P(A). Если ϕ — гомоморфизм решётки L на решётку с нулём [единицей], то полный прообраз нуля [единицы] является идеалом [фильтром] в L. Такой идеал [фильтр] называется ядерным. Не всякий идеал [фильтр] является ядерным: например, идеал { o, a, b, e } решётки, изображённой на рис. 9, ядерным не является. Диаграммы Хассе дают удобный способ описания решёток. Однако, если решётка устроена слишком сложно, такие диаграммы становятся мало наглядными. Следующая теорема даёт другие возможности представления решёток. Теорема 2.9. Всякую решётку можно с сохранением всех точных нижних граней вложить в булеан подходящего множества. Доказательство. Пусть A — произвольная решётка. Рассмотрим отображение ϕ, сопоставляющее каждому элементу x ∈ A главный идеал J(x) ∈ P(A). Необходимо показать, что отображение ϕ: (1) взаимнооднозначно, (2) изотонно, (3) обратно изотонно и (4) сохраняет пересечения. Будем устанавливать свойства ϕ в указанном порядке. 1) Пусть ϕ(x) = ϕ(y). Так как ϕ(x) = J(x) и всегда, в силу рефлексивности порядка, x ∈ J(x), то x ∈ J(y) и y ∈ J(x). Значит одновременно x v y и y v x, т.е., в силу антисимметричности, x = y. 45

[ [[    c b [ d  [  [     a[ e [[   ι

o

Рис. 9: Решётка с неядерным идеалом hbi 2) Пусть x v y или x ∈ J(y). В этом случае z ∈ J(x) влечёт z v x v y и, по транзитивности, z ∈ J(y). Таким образом ϕ(x) = J(x) ⊆ J(y) = ϕ(y). 3) Если ϕ(x) ⊆ ϕ(y) или, что то же J(x) ⊆ J(y), то x ∈ J(y) (поскольку x ∈ J(x) ), и, значит, x v y. 4) Поскольку в тотальной алгебре множеств P(A) точная нижняя грань двух элементов (подмножеств A ) совпадает с их теоретико-множественным пересечением, нам надо показать, что ϕ(x u y) = ϕ(x) ∩ ϕ(y). В самом деле, z ∈ ϕ(x u y) ⇔ z ∈ J(x u y) ⇔ z v (x u y) ⇔ ⇔ z v x ∧ z v y ⇔ z ∈ J(x) ∧ z ∈ J(y) ⇔ ⇔ z ∈ (J(x) ∩ J(y)) ⇔ z ∈ (ϕ(x) ∩ ϕ(y)) . Теорема доказана. Данная теорема позволяет представлять элементы любой решётки подмножествами некоторого множества A, а операцию пересечения отождествить с теоретикомножественным пересечением в A. Это, в свою очередь, даёт возможность пользоваться аналогами диаграмм Эйлера-Венна. При этом наибольшему элементу решётки ι (если он существует) соответствует само множество A, а наименьшему o (если он есть) договариваются сопоставлять пустое подмножество A (хотя по теореме 2.9 ϕ(o) = J(o) = {o}, но точка, соответствующая o, содержится во всех идеалах решётки, и её можно удалить без нарушения отношения включения идеалов). Отличие от ситуации с булевой алгеброй будет в представлении объединения подмножеств: можно показать, что отображение ϕ, описанное в теореме 2.9 обладает свойством включения ϕ(x) ∪ ϕ(y) в ϕ(x t y), но не их равенства (которое будет иметь место только в случае сравнимости x и y ). Поэтому при обозначении объединения элементов, изображаемых в виде связных выпуклых областей, необходимо рисовать выпуклую область, покрывающую “с запасом” области, соответствующие данным элементам (см. рис. 10).

2.3

Специальные виды решёток

Далее мы рассмотрим некоторые специальные типы решёток, представляющие особый интерес. 46

$ ' '$ ¿

x

y

ÁÀ x t y&% & %

ι Рис. 10: Обозначение объединения элементов решётки 2.3.1

Модулярные решётки

Определение 2.16. Решётка L = h L, t, u i называется модулярной, если для любых x, y, x ∈ L в ней выполняется следующий модулярный закон M od : x v y ⇒ x t (y u z) = y u (x t z) . Ясно, что смысл модулярного закона состоит в выполнении следования, обратного утверждаемому в M od v. Двойственный к модулярному закон x w y ⇒ x u (y t z) = y t (x u z) ему эквивалентен. Поэтому для модулярных решёток принцип двойственности остается справедливым. Пример 26. 1. Модулярными являются все цепи, решётка h N, | i, булевы алгебры и их подрешётки. Впоследствии мы увидим, что для этих решёток справедливо более сильное условие дистрибутивности. 2. Решётка N Sub (G) всех нормальных подгрупп группы G образует модулярную решётку. Действительно, пусть X, Y, Z — произвольные нормальные подгруппы группы G и X ⊆ Y . Известно, что объединение X ∪ Z двух нормальных подгрупп def X и Z группы G совпадает с их произведением XZ = { g ∈ G | ∃ x ∃ z ( g = xz ) }, X

Z

а пересечение подгрупп всегда есть подгруппа. Поэтому нам нужно показать справедливость включения Y ∩ XZ ⊆ X(Z ∩ Y ). В самом деле, всегда найдутся такие x ∈ X и z ∈ Z, что g ∈ Y ∩ XZ ⇒ g ∈ Y ∧ g = xz ⇒ g = xz ∧ z ∈ Y ∩ Z ⇒ g ∈ X(Z ∩ Y ) . Второе следование справедливо, поскольку xz = g влечёт z = x−1 g ∈ Y . Модулярные решётки часто называют дедекиндовыми по имени Р. Дедекинда, обнаружившего в 1900 г. указанное свойство нормальных подгрупп. 3. Другим важным примером модулярной решётки является решётка всех подпространств векторного пространства. Под объединением подпространств понимается наименьшее подпространство, их содержащее. Доказательство этого факта полностью аналогично доказательству модулярности решётки N Sub (G). Точно также доказывают, что решётка всех идеалов любого кольца модулярна. Решётка всех эквивалентностей на данном множестве в общем случае не модулярна. Действительно, рассмотрим множество M = { 1, 2, 3, 4 }. Среди E(M ) имеются эквивалентности a, b и c со смежными классами a = { {1}, {2}, {3, 4} }, 47

b = { {1}, {2, 3}, {4} } и c = { {1, 2}, {3, 4} } соответственно. Вместе с диагональным отношением в качестве o и аморфной эквивалентностью в качестве ι они образуют решётку N5 (см. рис. 8). Однако, она немодулярна, поскольку a v c, но a t (c u b) = a t o = a 6= c u (a t b) = c u ι = c . Таким образом, решётка h E(M ), ⊆ i содержит немодулярную подрешётку, и, следовательно немодулярна сама. Немодулярность N5 оказывается ключевой: справедлива Теорема 2.10 (Критерий модулярности решётки). Решётка модулярна, если и только если никакая её подрешётка не изоморфна пятиугольнику N5 . Доказательство. (⇐) Поскольку пятиугольник не модулярен, то никакая решётка, содержащая изоморфную ему подрешётку, не может быть модулярной. (⇒) Покажем, что немодулярная решётка L содержит подрешётку, изоморфную пятиугольнику N5 . Немодулярность L означает существование таких её элементов x, y и z , что x v y , но x t (y u z) @ y u (x t z). Покажем, что элементы y u z, x t (y u z), y u (x t z), z, x t z образует подрешётку в L, изоморфную N5 . В самом деле, должны иметь место соотношения yuz @z @xtz

и

y u z @ x t (y u z) @ y u (x t z) @ x t z ,

поскольку, заменив первый, второй третий или пятый знак @ на =, получим x v z или z v y, откуда сразу следует модулярный закон. Далее x t y = (x t z) t z v (x t (y u z)) t z v (y u (x t z)) t z v (x t y) t z = x t z . Это означает, что элементы x t (y u z) и y u (x t z) оба дают в объединении с z элемент x t z. Кроме того, y u y = (y u z) u z v (x t (y u z)) u z v (y u (x t z)) u z = y u ((x t z) u z) = y t z . Это означает, что элементы x t (y u z) и y u (x t z) оба дают в пересечении с z элемент y u z. Данный критерий влечет справедливость условия Жордана-Дедекинда для цепей: если в конечной решётке две максимальные цепи между элементами a v b имеют разную длину, то интервал [ a, b ] содержит подрешётку, изоморфную N5 , и, следовательно, данная решётка немодулярна. Пример 27. Решётка, изображённая на рис. 11 немодулярна: длины её максимальных цепей не совпадают и, как следствие, она содержит подрешётку, изоморфную N5 (например, { o, a, b, ι, g } ). Теорема 2.11. Решётка h L, t, u i модулярна, если и только если для любых её элементов x, y и z имеет место соотношение x t ((x t y) u z)) = (x t y) u (x t z) или эквивалентное двойственное ему x u ((x u y) t z)) = (x u y) t (x u z) . 48

[[   e [ b [  g f [[  a[ d [  ι

o

Рис. 11: Немодулярная решётка Доказательство. Если решётка L модулярна, то первое тождество следует из “неравенства” x v x t y, если в модулярном законе заменить y на x t y. Обратно, при x t y, или, что то же, при x t y = y, первое тождество превращается в x t (y u z) = y u (x t z), что является заключением модулярного закона. Справедливость второго тождества следует из принципа двойственности. 2.3.2

Дистрибутивные решётки

Определение 2.17. Решётка называется дистрибутивной, если в ней выполняется дистрибутивные законы Dtr1 : (x t y) u z = (x u z) t (y u z) ; Dtr2 : (x u y) t z = (x t z) u (y t z) . Ясно, что смысл дистрибутивных законов состоит в выполнении следований, обратных утверждаемым в Dtr1 w и Dtr2 v. Так же понятно, что для дистрибутивных решёток принцип двойственности остается справедливым. Более того, легко видеть, дистрибутивные законы для решёток эквивалентны. Действительно, для любых элементов x, y, z решётки имеем Dtr1

(x t z) u (y t z) = (x u (y t z)) t (z u (y t z))

Abs1, Dtr1

=

Abs2

= (x u y) t (x u z) t z = (x u y) t z . т.е. доказано следование Dtr1 ⇒ Dtr2. Двойственно показывается, что Dtr2 ⇒ Dtr1. Так что достаточно было потребовать выполнения лишь одного из дистрибутивных законов (обычно постулируют выполнение Dtr1 ). В дистрибутивных решётках и только в них справедливо следующее правило. Утверждение 2.2 (Правило сокращения). Решётка L дистрибутивна, если только если для любых x, y, z ∈ L справедливо следующее правило сокращения ½ xty =xtz Abbr : ⇒ y = z. xuy =xuz Доказательство. (⇐) Пусть в дистрибутивной решетке для некоторых элементов x, y и z справедливы равенства x t y = x t z и x u y = x u z. Тогда имеем: Abs1

Dtr1

y = y u (y t x) = y u (z t x) = (y u z) t (y u x) = Dtr1

Abs1

= (y u z) t (x u z) = (y t x) u z = (x t z) u z = z . 49

Мы видим, что справедливость Abbr есть следствие законов коммутативности, поглощения и дистрибутивности. (⇒) Доказательство достаточности может быть найдено в [13]. Пример 28.

1. Все цепи, булевы алгебры и их подрешётки дистрибутивны.

2. Покажем дистрибутивность решётки h N, | i, т.е., что для любых натуральных чисел x, y, z справедливо соотношение x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) , где x ∧ y — наибольший общий делитель, а x ∨ y — наименьшее общее кратное x и y. Воспользуемся каноническим представлением натуральных чисел в виде произведений их простых сомножителей x =

s Y

piαi ,

y =

i=1

s Y

piβi ,

i=1

z =

s Y

piγi ,

i=1

считая, что некоторые показатели могут быть равны 0. Тогда x ∧ (y ∨ z) =

s Y

min{ αi , max{ βi , γi } }

pi

,

i=1

(x ∧ y) ∨ (x ∧ z) =

s Y

max{ min{ αi , βi }, min{ αi , γi } }

pi

,

i=1

и требуемое равенство min { αi , max { βi , γi } } = max { min{ αi , βi }, min{ αi , γi } } представляет собой дистрибутивный закон для цепи неотрицательных целых чисел. 3. Решётка всех подпространств векторного пространства, упомянутая выше в качестве примера модулярной решётки, не является дистрибутивной. 4. Непустая совокупность подмножеств некоторого множества, содержащая вместе с двумя подмножествами их объединение и пересечение называется решёткой или кольцом множеств (ср. с определением поля множеств на с. 5). Всякая решётка множеств дистрибутивна, поскольку дистрибутивны теоретико-множественные операции объединения и пересечения. 5. Решётка Sub (C) всех подгрупп циклической группы C дистрибутивна. Заметим, что, однако, Sub (C) не является решёткой множеств, поскольку объединение её элементов (в отличие от пересечения) не совпадает с теоретико-множественным. Пятиугольник N5 недистрибутивен: действительно, (см. рис. 8d) (a t b) u c = ι u c = c 6= (a u c) t (b u c) = a t o = a . Поэтому справедливо Утверждение 2.3. Всякая дистрибутивная решётка модулярна. Это утверждение так же следует из того, что модулярный закон представляет собой ослабленную форму первого дистрибутивного закона: если x v y, то x t y = y и Dtr1

x t (y u z) = (x t y) u (x t z) = y u (x t z) . 50

[[  [  a[ c b [[    V4 = ι

E=o

Рис. 12: Решётка Sub (V4 ). Решётка N Sub (G) всех нормальных подгрупп группы G модулярна (см. пример 26.2) но, в общем случае, не дистрибутивна. Действительно, рассмотрим четверную группу Клейна V4 = h x, y i, x2 = y 2 = e, xy = yx. Собственные её подгруппы суть a = hxi, b = hyi и c = hxyi. Все они нормальны, поскольку V4 абелева. Решётка Sub (V4 ) её подгрупп (см. рис. 12) изоморфна M3 и модулярна, но не дистрибутивна, т.к. не дистрибутивен ромб M3 : (a t b) u c = ι u c = c 6= (a u c) t (b u c) = o t o = o . Недистрибутивность M3 , оказывается ключевой: справедлива Теорема 2.12. Модулярная решётка является дистрибутивной, если и только если никакая её подрешётка не изоморфна ромбу M3 . Доказательство. (⇐) Поскольку ромб M3 не дистрибутивен, то никакая решётка, содержащая изоморфную ему подрешётку, не может быть дистрибутивной. (⇒) Пусть решётка L модулярна и не содержит M3 в качестве подрешётки. Для произвольных x, y, z ∈ L рассмотрим следующие пять элементов a b c u v

= = = = =

(z u (x t y)) t (x u y) , (y u (x t z)) t (x u z) , (x u (y t z)) t (y u z) , (x u y) t (y u z) t (z u x) , (x t y) u (y t z) u (z t x) .

Покажем сначала, что atb = btc = cta = v

и

a u b = b u c = c u a = u.

Имеем (z u (x t y)) t (y u (x t z)) = (x t y) u ((y u (x t z)) t z) = = (x t y) u ((x t z) u (y t z)) = v . Вывод сделан с учётом модулярного закона, а также следований y u (x t z) v x t z и z v x t z для первого и второго равенств соответственно. Отсюда получаем, что a t b = v и, в силу симметрии, что b t c = c t a = v.

51

Учитывая модулярный закон и очевидное следование x u y v x t z получаем другое, двойственное к исходному, выражение для a: a = (z t (x u y)) u (x t y) . Аналогично b = (y t (z u x)) u (z t x) , c = (x t (y u z)) u (y t z) . Используя теперь принцип двойственности для модулярных решёток и учитывая, что u двойственно v, получим a u b = b u c = c u a = u. Таким образом, если все элементы a, b и c попарно различны, то подрешётка { u, a, b, c, u } в L изоморфна ромбу M3 . Это невозможно, и, значит, u = a = b = c = u, но тогда (x t y) u z v a = u v (x u z) t (y u z) , и, следовательно, в L выполняется дистрибутивный закон. Следствие (Критерий дистрибутивности решётки). Решётка дистрибутивна, если и только если никакая её подрешётка не изоморфна ни пятиугольнику N5 , ни ромбу M3 . Пусть I — идеал дистрибутивной решётки L. Отношение θI = { (a, b) ∈ L2 | ∃ x (a t x = b t x) } I

является, как нетрудно видеть, эквивалентностью на L. Кроме того, легко устанавливается, что ½ (x1 t x2 )θI (y1 t y2 ) . x1 θI x2 ∧ y1 θI y2 ⇒ (x1 u x2 )θI (y1 u y2 ) Это позволяет корректно определить операции объединения и пересечения классов на фактормножестве L/θI (поскольку их результат не будет зависеть от выбранных элементов в соответствующих классах). Таким образом, L/θI есть решётка (с нулём). Гомоморфизм ϕ : L → L/θI , определяемый естественным отображением ϕ = nat(L, θI ) имеет своим ядром данный идеал I. Решётка дистрибутивна если и только если каждый её идеал ядерный, т.е. является ядром подходящего гомоморфизма (ср. рис. 9). Два разных гомоморфизма дистрибутивной решётки на одну и ту же решётку могут иметь совпадающие ядерные идеалы. В дальнейшем нам понадобятся некоторые леммы, которые, впрочем, представляют и самостоятельный интерес. Лемма 2.13. Совокупность J(P ) порядковых идеалов элементов ч.у. множества P есть дистрибутивная решётка. Доказательство. Пусть P — ч.у. множество и J(P ) — совокупность порядковых идеалов P . Введём на J(P ) операции объединения и пересечения как соответствующие теоретико-множественные. Поскольку объединение и пересечение порядковых идеалов есть порядковый идеал, а теоретико-множественные операции дистрибутивны, то J(P ) есть дистрибутивная решётка.

52

В соответствии с данной леммой, решётка J(P ), построенная в примере 20, дистрибутивна. Укажем алгоритм построения диаграммы Хассе для решётки порядковых идеалов J(P ) по данной диаграмме Хассе конечного ч.у. множества P . Ненулевой элемент z решётки назовём элемент неразложимым в объединение, если из z = x t y следует z = x или z = y. Очевидно, в этом случае элемент z нельзя записать в виде объединения строго содержащихся в нём элементов. Например, атомы любой решётки неразложимы, и в атомной булевой алгебре нет других неразложимых элементов, а в конечной цепи ни один элемент не является разложимым. Пусть множество I минимальных элементов P имеет мощность m. 1. Построим диаграмму Хассе конечной булевой алгебры, изоморфной J(I). 2. Выберем некоторый минимальный элемент x множества P r I и присоединим к J(I) неразложимый в объединение элемент, содержащий порядковый идеал J(x) r {x}. 3. Добавим все необходимые объединения элементов, содержащих идеал J(x) r {x}, чтобы они образовывали булеву алгебру. 4. Если существуют элементы, содержащие множество J(x)r{x} и покрывающие элементы которых не имеют объединений, то изобразим последние так, чтобы образовалась булева алгебра. Продолжая таким образом до тех пор, пока каждое множество элементов, содержащее данный элемент не будет иметь объединения, получим диаграмму Хассе дистрибутивной решётки J(I ∪ {x}). 5. Выберем некоторый минимальный элемент y множества (P rI)rx и присоединим к J(I ∪ {x}) неразложимый в объединение элемент, содержащий порядковый идеал J(x) r {y}. 6. Повторяя шаги 3 и 4, получим диаграмму Хассе дистрибутивной решётки J(I ∪ {x, y}). 7. Продолжаем аналогично, пока не получим диаграмму Хассе решётки J(P ). Пример 29. Построим по приведённому алгоритму решётку порядковых идеалов ч.у. множества Z5 вида “зигзаг”, изображённого на рис. 13. e [ [ [  [  d

a

b

c

Рис. 13: Ч.у. множество Z5 вида “зигзаг” Полученная решётка изображена на рис. 14. Известно, что n-элементное ч.у. множество вида “зигзаг” имеет Fn+2 ( (n+2)-е число Фибоначчи) порядковых идеалов. В нашем случае |J(Z5 )| = F7 = 13. Лемма 2.14. В конечной решётке каждый ненулевой элемент может быть представлен в виде объединения неразложимых элементов.

53

[[ [[

hd, ei



 hc, di  [[

   hdi [ [[ [

[ [

ha, ei



[[

   ha, b, ci [  [[  [ 

[[

  

[[ ha, ci[[ hb, ci [[ [[    

ha, bi

hai

hei

[[

hbi

[[  

hci

∅

Рис. 14: Решётка J(Z5 ) Доказательство. Если элемент b неразложим, то b = b t b. Пусть b = b1 t b2 и b1 6= b 6= b2 . Если и b1 , и b2 неразложимы, то лемма доказана. В противном случае представляем b1 и/или b2 в виде объединения строго содержащихся в них элементов, и т.д. В силу конечности решётки указанный процесс закончится, и исходный элемент b будет представлен в виде объединения неразложимых элементов. Множество неразложимых в объединение элементов решётки L будем обозначать Irr L. На этом множестве можно ввести порядок, наследуемый от L и рассматривать Irr L как ч.у. множество. Лемма 2.15. Если P — ч.у. множество, то Irr J(P ) ∼ = P. Доказательство. Пусть P — ч.у. множество. Тогда J(P ) — дистрибутивная решётка его порядковых идеалов. Ясно, что порядковый идеал решётки неразложим, если и только если он является главным. Поэтому между неразложимыми в объединение элементами из J(P ) и элементами P существует взаимнооднозначное соответствие. Ранее же был показан изоморфизм между ч.у. множеством и совокупностью его главных идеалов. Пример 30. 1. Рассмотрим ч.у. множество P , заданное диаграммой Хассе на рис. 15 a). Множество её идеалов J(P ) представлено на на рис. 15 b), где выделены неразложимые элементы J(P ). 2. Для ч.у. множества P , заданного диаграммой Хассе на рис. 16 a), решётка J(P ) и ч.у. множество Irr J(P ) приведены на b) и c). 54

[[ [

hb, ci

b

[[



   J(b) [[ [

c

[[   a



J(c)



J(a)

∅

a) P

b) J(P )

Рис. 15: Диаграммы Хассе ч.у. множества P и множества его идеалов J(P ) (элементы Irr J(P ) выделены)

[[ [

hc, di

c4

h h 4 h 4 hhh44

4

a

d

4

hhh

44 b

   J(c) [[ [

J(d)

   ha, bi [[  [  [[

J(a)



J(c)

4

4

J(d)

4

4

hhh

hh4h4

J(b)

hh 44

J(a)

J(b)

 [  ∅

a) P

b) J(P )

c) Irr J(P )

Рис. 16: Диаграммы Хассе ч.у. множества P , J(P ) и Irr J(P ) Для дистрибутивных решёток справедлива Теорема 2.16 (Биркгофа). Всякая дистрибутивная решётка вложима в решётку всех подмножеств подходящего множества. Мы докажем эту теорему для класса конечных решёток, где она допускает следующее 55

усиление. Теорема 2.17. Всякая конечная дистрибутивная решётка изоморфна решётке порядковых идеалов подходящего ч.у. множества. Доказательство. Пусть h L, t, u i — конечная дистрибутивная решётка, Irr L — подмножество неразложимых в объединение элементов J(L) (дистрибутивная в силу леммы 2.13) и J(Irr L) — соответствующая подрешётка J(L). В силу леммы 2.15 достаточно показать, что L ∼ = J(Irr L). Ясно, что J(x) ∈ J(Irr L), O где J(x) = x — главных идеал x ∈ L и отображение ϕ : x 7→ J(x) есть изотонное и обратно изотонное вложение L в J(Irr L) (см. доказательство теоремы 2.9). Следовательно, нам осталось показать, что ϕ сюръективно. Пусть I — некоторый идеал из J(Irr L). Теорема будет доказана, если будет установлено, что идеал I главный. Обозначим x = sup { y | y ∈ I }. Ясно, что I ⊆ J(x) и x = sup { y | y ∈ I } = sup { y | y ∈ J(x) } . Пусть z — некоторый элемент J(x). Вычислим x u z. В силу дистрибутивности, имеем sup { y u z | y ∈ I } = sup { y u z | y ∈ J(x) } .

(2.2)

Правая часть (2.2) есть в точности z, т.к. один из элементов J(x) есть z, а все другие элементы J(x) в z содержатся. Поскольку z ∈ Irr L, то z неразложим. Отсюда из (2.2) следует, что некоторый элемент y ∈ I удовлетворяет условию y u z = z, т.е. z v y. Так как I — порядковый идеал и z ∈ I, то J(x) ⊆ I, откуда I = J(x), т.е. I — главный идеал. Пример 31. Для конечной дистрибутивной решётки, представленной на рис. 17 a) ч.у. множество Irr J(L) и решётка J(Irr L) приведены на b) и c). ι [ [[   [  c b [  [[  [  a

b

[[



[[   a

o

a) L

[[ [

hb, ci

c

   J(b) [[ [

  

J(c)

J(a)

∅

b) Irr L

b) J(Irr L)

Рис. 17: Диаграммы Хассе решётки L, ч.у. множества Irr L и дистрибутивной решётки J(Irr L)

56

Теорема Биркгофа позволяет представлять элементы любой дистрибутивной решётки подмножествами некоторого множества A и пользоваться диаграммами Эйлера-Венна. Из теоремы также вытекает интересное Следствие. Всякая конечная дистрибутивная решётка вложима в упорядоченную делимостью решётку натуральных чисел. Доказательство. Из теоремы Биркгофа следует, что конечная дистрибутивная решётка L вкладывается в булеан P(S) некоторого конечного множества S. С другой стороны, пример 25.5 показывает, что h P(S), ⊆ i вложима в h N◦ , ∨, ∧ i. Таким образом, L вкладывается в h N◦ , ∨, ∧ i, и, следовательно, в h N, | i. Покажем, как конечная дистрибутивная решётка L может быть вложена в h N, ∨, ∧ i. Наименьшему элементу o решётки L сопоставляется число 1, а её атомам p1 , . . . , pn — первые n простых чисел. Пусть состоялось приписывание всем элементам множества xO r x элемента x решётки L. Если элементу x непосредственно предшествует единственный элемент, которому сопоставлено число k, то сопоставляем x число kp, где p — первое из ещё не использованных простых чисел. Если элементу x непосредственно предшествуют несколько элементов, то сопоставляем x наименьшее общее кратное всех чисел, им соответствующих. Такое сопоставление для решёток из примера 31 и J(P ) из примера 20 приведён на рис. 18. 210

   6 [ [[

30

2

[[ [   

10

1

30 [  [[   6 [ 15  [[      2 [ 3 [[   1

a)

b)

Рис. 18: Вложения конечных дистрибутивных решёток в решётку h N, | i

2.3.3

Решётки с дополнениями

Определение 2.18. Если в решётке h L, t, u i с универсальными гранями для элемента x существует элемент y такой, что x u y = o, x t y = ι, то последний называется дополнением элемента x.

57

Решётка называется решёткой с дополнениями, если в ней каждый элемент имеет хотя бы одно дополнение. Если каждый элемент решётки обладает в точности одним дополнением, то её называют решёткой с единственными дополнениями. Ясно, что если y — дополнение x, то и x — дополнение y, и что в любой ограниченной решётке o и ι являются единственными дополнениями друг для друга. Пример 32. 1. В решётке алгебры подмножеств множества A каждый элемент X ⊆ A имеет единственное дополнение X = A r {X}. Это классический пример решётки с единственными дополнениями. 2. В решётке, представленной на рис. 18 a) элемент 2 не имеет дополнения. 3. Пятиугольник N5 — решётка с дополнениями. В ней (см. рис. 8.c) ) дополнениями a и c будет элемент b, а дополнениями b — элементы a и c. Следствием того, что в дистрибутивной решётке справедливо правило сокращения Abbr (см. утверждение 2.2) является Утверждение 2.4. Если решётка дистрибутивна, то каждый её элемент имеет не более одного дополнения. Доказательство. Допустим, что элемент x решётки имеет два дополнения — y1 и y2 . Тогда ½ x t y1 = x t y2 = ι Abbr ⇒ y1 = y2 . x u y1 = x u y2 = o Из теоремы Биркгофа 2.16 следует, что каждая дистрибутивная решётка вложима в дистрибутивную решётку с единственными дополнениями. Вопрос о связи свойств дистрибутивности и наличия единственного дополнения у решёток является, как оказалось, достаточно глубоким и трудным. В начале XX века при формулировке систем аксиом для булевой алгебры естественной была попытка определить её как решётку, имеющую единственное дополнение. Это оказалось бы возможным, если единственность дополнения у элементов решётки влекло бы её дистрибутивность. В связи с этим Э. Хантингтоном (см. с. 5) было высказано предположение о том, что все решётки с единственными дополнениями дистрибутивны. Вопрос о том, верна ли эта гипотеза и составлял знаменитую проблему Хантингтона. К концу 30-х годов XX в. было исследовано значительное количество конкретных решёток с единственными дополнениями, все они оказались дистрибутивными, в силу чего справедливость данного предположения практически не вызывала сомнений у математиков. Поэтому большой неожиданностью было опубликование в 1945 г. работы американского математика Р. Дилуорса16 в которой была доказана Теорема 2.18 (Дилуорса). Всякая решётка может быть вложена в подходящую решётку с единственными дополнениями. В частности, можно взять пятиугольник N5 , и тогда теорема Дилуорса даст немодулярную и, тем более, недистрибутивную решётку с единственными дополнениями. Таким образом было доказано, что существуют недистрибутивные решётки с единственными дополнениями.17 Отметим однако, что данный объект в доказательстве теоремы Дилуорса появляется лишь в результате некоторого предельного перехода, и до сих 16 17

Dilworth R.P. Lattices with unique complements. — Trans. Amer. Math. Soc., 1945, 57, p. 123-154. Современное доказательство данной теоремы имеется в [12].

58

пор нет ни одного явного примера недистрибутивной решётки с единственными дополнениями. Решётка называется полной, если любое подмножество её элементов имеет точные верхнюю и нижнюю грани (ср. с определением полной булевой алгебры на с. 12). Например, отрезок [ 0, 1 ] с обычным порядком и произвольная алгебра множеств являются полными решётками. В классе полных решёток проблема Хантингтона до сих пор не имеет разрешения. Определение 2.19. Если [ a, b ] — интервал решётки L, x ∈ [ a, b ], и элемент y решётки L таков, что x u y = a и x t y = b, то y называется относительным дополнением элемента x в интервале [ a, b ]. Если в некоторой решётке все интервалы суть решётки с дополнениями, то она называется решёткой с относительными дополнениями. Легко видеть, что если y — относительное дополнение элемента x в интервале [ a, b ], то y ∈ [ a, b ] и x, в свою очередь, также будет относительным дополнением элемента y в интервале [ a, b ]. Пример 33. На рис. 19 изображена диаграмма Хассе решётка с относительными дополнениями. Дополнениями элемента b в интервале [e, ι] являются элементы c и d, а элементы a и e служат друг для друга единственными дополнениями в интервале [0, b].

[[  [  c b [ d [   [   a[ e [[   ι

o

Рис. 19: Решётка с относительными дополнениями

2.4 2.4.1

Булевы алгебры (продолжение) Безатомные булевы алгебры. Булевы гомоморфизмы, кольца и структуры

Определение 2.20. Дистрибутивная решётка с дополнениями называется булевой алгеброй. Согласно утверждению 2.4 в булевой алгебре каждый элемент имеет одно и только одно дополнение. Нетрудно видеть, что оба определения — данное выше и на с. 4 эквивалентны. До сих пор мы рассматривали только атомные булевы алгебры. Приведём примеры булевых алгебр, не имеющих атомов. 59

Пример 34. Рассмотрим множество A, элементами которого являются подмножества действительных чисел, представимые в виде объединения конечного числа полуинтервалов вида (x, y], содержащихся в промежутке (0, 1]. Это множество, очевидно, устойчиво относительно теоретико-множественных операций объединения, пересечения и дополнения до (0, 1], т.е. представляет собой булеву алгебру. Единицей в ней будет интервал (0, 1], а нулём — пустое множество, представляемое в виде (x, x]. Легко видеть, что эта алгебра не имеет атомов: любой интервал (x, y] при 0 < x < y 6 1 содержит в себе ненулевой подынтервал такого же вида. Пример 35. Рассмотрим h P(Z), ∪, ∩, − , ∅, Z i — тотальную алгебру над множеством целых чисел Z. Определим отношение ' над элементами P(Z): будем считать, что A ' B, если симметрическая разность множеств A и B конечна. Ясно, что ' есть отношение эквивалентности. Поэтому можно образовать фактормножество P(Z)/'. Все конечные (включая пустое) подмножества P(Z) будут, очевидно, эквивалентныж обозначим этот класс эквивалентности [∅]. Также будут эквивалентными все подмножества целых чисел, имеющих конечные дополнения до Z, включая само Z; этот класс эквивалентности обозначим [Z]. Далее, легко проверить, что введенное отношение является также и стабильным относительно теоретико-множественных операций, т.е. для любых A, B ∈ P(Z) из A ' A0 и B ' B 0 следует A ∪ B ' A0 ∪ B 0 , A ∩ B ' A0 ∩ B 0 и A ' A0 . Это означает, что к элементам фактор-множества P(Z)/' применимы операции сигнатуры алгебры множеств, и АС B = h P(Z)/ ', ∪, ∩, − , [∅], [Z] i будет являться булевой алгеброй. Легко убедиться, что данная булева алгебра не имеет атомов. Действительно, любой отличный от o элемент B — класс бесконечных множеств. Атом — элемент, непосредственно следующий за o, а таковые отсутствуют в B. Приведём без доказательства следующий критерий для атомных булевых алгебр. Теорема 2.19. Булева алгебра будет атомной если и только если её единичный элемент представляет собой точную верхнюю грань всех её атомов. В п. 1.1.3 было введено понятие изоморфизма булевых алгебр. Дадим теперь определение булева гомоморфизма и его ядра. Определение 2.21. Пусть B1 и B2 — две булевы алгебры. Решёточный гомоморфизм ϕ : B1 → B2 называется булевым гомоморфизмом, если для всех x из B1 справедливо ϕ(x 0 ) = ϕ(x)0 . def

Множество Ker ϕ = { x ∈ B1 | ϕ(x) = o }, связанное с булевым гомоморфизмом ϕ называют его ядром.18 Инъективные булевы гомоморфизмы называют булевыми мономорфизмами. Таким образом, булев гомоморфизм сохраняет все операции булевой алгебры и её выделенные элементы. Для того, чтобы булев гомоморфизм ϕ был булевым изоморфизмом необходима биективность отображения ϕ. Ясно, что произвольный гомоморфизм одной булевой алгебры в другую может не быть булевым гомоморфизмом. Пример 36. Если A ⊂ B, то естественное вложение P(A) в P(B) является решёточным мономорфизмом, но не булевым гомоморфизмом. 18

Здесь не надо путать ядро отображения (подмножество множества) с раннее рассмотренным ядерным отношением (подмножество декартова квадрата множества).

60

Определение 2.22. Булева алгебра B 0 называется подалгеброй булевой алгебры B, если B 0 6 B как решётки, имеют общие нули, единицы и дополнение элемента в B 0 совпадает с его дополнением в B. Пример 37. 1. Булева алгебра P2n логических функций от n переменных является подалгеброй алгебры P2 всех логических функций (см. пример 3). 2. Пусть A ⊆ B. Тогда P(A) P(B), поскольку эти булевы алгебры имеют, например, разные единичные элементы (что влечёт и несовпадение дополнений данного подмножества A в P(A) и в P(B) ). Непосредственно из определений следует простое Утверждение 2.5. Пусть ϕ : B1 → B2 — булев гомоморфизм. Тогда 1. ϕ(o) = o,

ϕ(ι) = ι;

2. x v y ⇒ ϕ(x) v ϕ(y) для любых x и y из B1 ; 3. ϕ(B1 ) — булева подалгебра в B2 . В булевой алгебре h B, t, u, 0 , o, ι i можно ввести производные операции взаимного дополнения или вычитания (r ) и симметрической разности (⊕ ): def

x r y = x u y0,

def

x ⊕ y = (x r y) t (y r x) .

При этом оказывается, что x 0 = x ⊕ ι и x t y = x ⊕ y ⊕ xy. Рассмотрим булеву алгебру B = h B, t, u, 0 , o, ι i. Образуем на её основе АС B∗ = h B, ⊕, ·, o, ι i, где ⊕ — симметрическая разность, а · — новое обозначение операции пересечения. Тогда B∗ является ассоциативно-коммутативным кольцом с единицей ι и нулём o, операциями сложения ⊕ и умножения ·, в котором для любого элемента x имеет место свойство Id t булевой алгебры или, в другой записи, x2 = x. Ассоциативно-коммутативное кольцо, обладающие свойством x2 = x называется булевым кольцом. Основным примером булева кольца является кольцо h P(A), ⊕, ∩, ∅, A i, получаемое указанным способом из тотальной алгебры множеств. Таким образом, построенная выше АС B∗ есть булево кольцо с единицей ι. Если же в некотором булевом кольце R = h R, +, ·, 0, 1 i с единицей 1 и нулём 0 положить x t y = x + y + xy,

и x0 = x + 1,

x u y = xy

то получим булеву алгебру R∗ = h R, t, u, 0 , 0, 1 i. Таким образом, любое булево кольцо с единицей может быть задано с помощью булевой алгебры и наоборот. При этом, как легко видеть, B∗∗ = B и R∗∗ = R. Тем самым устанавливается т.н. стоуновская двойственность между булевыми алгебрами и булевыми кольцами. Из теоремы 2.6 следует, что в булевой алгебре можно ввести отношение порядка v по правилу def def x v y = x u y = x или x v y = x t y = y . Легко показать, что тогда из x v y будут следовать соотношения x u y0 = o,

x0 t y = ι

и

x0 w y0

(последнее соотношение есть закон антиизотонности дополнения). 61

Теперь можно определить булеву структуру h B, t, u, 0 , v, o, ι i , где её редукт h B, t, u, 0 , o, ι i — булева алгебра. Для многих приложений удобнее рассматривать не булевы алгебры, а сразу булевы структуры. Аналогично можно ввести булеву структуру множеств h P(A), ∪, ∩, − , ⊆, ∅, A i , дополнив тотальную алгебру множеств отношением включения ⊆. Очевидно также, что любая булева структура множеств есть и булева структура. Теорема 2.20. Булева структура есть решётка с относительными дополнениями. Доказательство. Пусть B — булева структура, a v x v b, и x 0 — дополнение для x. Определим элемент def

M od

y = a t (b u x 0 ) = b u (a t x 0 )

(2.3)

и покажем, что y — относительное дополнение элемента x в интервале [ a, b ]. Действительно, x u y = x u (b u (x 0 t a)) = (x u b) u (x 0 t a) = = x u (x 0 t a) = (x u x 0 ) t (x u a) = a , и, двойственно, x t y = x t (b u (x 0 t a)) = (x t b) u (x t x 0 t a) = b u ι = b . Таким образом, в булевой алгебре относительные дополнения определяются легко — по формуле (2.3). Если на интервале [ a, b ] по (2.3) определить операцию взятия дополнения ¯, то АС h [ a, b ], t, u,¯, a, b i оказывается булевой алгеброй. Отметим, что полученная булева алгебра не будет (за исключением “собственного” случая a = o, b = ι ), являться подалгеброй исходной алгебры т.к.эти алгебры имеют, например, различные выделенные элементы. 2.4.2

Булевы идеалы и фильтры

Решётчатые идеалы [фильтры] в булевой алгебре B называют булевыми идеалами [фильтрами] в B. Для булева идеала в B используют обозначение I P B. Пример 38. Рассмотрим тотальную алгебру множеств P(M ) над множеством M . 1. Пусть A ⊆ M . Тогда совокупность всех подмножеств множества M , содержащихся в A есть идеал в P(M ), а содержащих A есть фильтр в P(M ). 2. Пусть M — бесконечное множество. Совокупность P0 (A) всех конечных подмножеств M есть идеал в P(M ), а совокупность подмножеств, имеющих конечное дополнение до M есть фильтр в P(M ). Фильтр указанного вида называют фильтром Фреше.

62

На булевы идеалы и фильтры переносятся понятия конечнопорождённых, собственных, несобственных и главных идеалов и фильтров (см. п. 2.2.2). Так, идеалы и фильтры, описанные в п. 1 предыдущего примера — главные. Идеал и фильтр, описанные в п. 2 предыдущего примера — не главные и даже не конечнопорождённые. Справедлива следующая простая Теорема 2.21. Пусть B — булева алгебра и X ⊆ B. Тогда в B множество X 0 = { x 0 | x ∈ X } будет идеалом, если X — фильтр в B и фильтром, если X — идеал в B. Булевы идеалы и фильтры связаны с булевыми гомоморфизмами. Теорема 2.22. Ядро булева гомоморфизма есть идеал. Прообраз единицы булева гомоморфизма есть фильтр. Доказательство. В силу принципа двойственности достаточно доказать только утверждение относительно идеалов. Пусть ϕ — гомоморфизм, определённый на булевой алгебре B, x, y ∈ Ker ϕ и b v x. Тогда ϕ(x t y) = ϕ(x) t ϕ(y) = o t o = o и ϕ(b) v ϕ(x). Поэтому x t y ∈ Ker ϕ и b ∈ Ker ϕ, т.е. Ker ϕ P B. Определение 2.23. Идеал [фильтр] на булевой алгебре называется максимальным, если он не содержится ни в каком другом собственном идеале [фильтре] на ней. Максимальные булевы идеалы и фильтры можно очень просто охарактеризовать. Теорема 2.23 (О максимальных булевых идеалах и фильтрах). Идеал [фильтр] X булевой алгебры B максимален, если и только если для любого b ∈ B в точности один из элементов b и b 0 принадлежит X. Замечание. Идеал или фильтры указанного вида называют простыми. Таким образом, в булевой алгебре простота и максимальность идеалов и фильтров суть совпадающие понятия. Доказательство. По принципу двойственности достаточно доказать данное утверждение относительно идеалов. (⇐) Пусть для любого элемента b булевой алгебры B либо b, либо b 0 содержится в её идеале X. Рассмотрим Y — идеал в B, строго содержащий X. Для него имеем: y ∈ Y r X ⇒ y 0 ∈ Y , откуда y t y 0 = ι ∈ Y , т.е. Y = B и идеал X — максимальный. (⇒) Пусть X — максимальный идеал в B и элемент b0 ∈ B таков, что ни b0 , ни b0 0 не лежат в X. Тогда Y = { x t b | x ∈ X, b v b0 ∈ B} — идеал, строго содержащий X, и, в силу максимальности X, совпадающий с B. Значит, существую такие x ∈ X, b ∈ B, что b v b0 и x t b = b0 . Отсюда в силу b0 0 u b v b0 0 u b0 = o получаем b0 0 = b0 0 u b0 0 = b0 0 u (b t x) = (b0 0 u b) t (b0 0 u x) = b0 0 u x . Таким образом, b0 0 v x, что означает b0 0 ∈ X, т.е. получено противоречие. Максимальные фильтры в булевых алгебрах называют ультрафильтрами. Справедлива следующая Теорема 2.24. Каждый собственный фильтр [идеал] булевой алгебры содержится в некотором максимальном идеале [фильтре]. 63

Доказательство. По принципу двойственности достаточно доказать данное утверждение относительно фильтров. Пусть 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

Пусть дано уравнение a(˜ x) · X(˜ x) = F , где a(˜ x) и X(˜ x) — формулы, реализующие соответственно известную и искомую булевы функции (для простоты указывают именно формулы, а не порождённые ими классы). Тогда решением данного уравнения будут любая функция, реализуемая формулами из главного идеала, порождённого формулой a(˜ x) в соответствующей алгебре ЛинденбаумаТарского. Например, пусть a(˜ x) = x1 x2 , т.е. дано уравнение x1 x2 X(x1 , x2 ) = F .

(∗)

Имеем x1 x2 = x1 ∨ x2 , и главный идеал в алгебре Линденбаума-Тарского L∗2 , порождённый классом формул [ x1 ∨ x2 ] составляют классы [ x1 ∨ x2 ], [ x1 ], [ x2 ], [ x1 x2 ∨ x1 x2 ], [ x1 x2 ], [ x1 x2 ], [ x1 x2 ] и F. На рис. 20 показана диаграмма Хассе данного идеала. Для каждого класса указан вектор значений соответствующей функции при стандартном расположении наборов переменных.

[ x1 ] (0, 0, 1, 1)

[ x1 x2 ] (0, 0, 0, 1)

AAA

A AA

[ x1 ∨ x2 ] (0, 1, 1, 1)

A

[ x1 x2 ∨ x1 x2 ] (0, 1, 0, 1)

[ x2 ] (0, 1, 1, 0)

[ x1 x2 ] (0, 0, 1, 0)

[ x1 x2 ] (0, 1, 0, 0)



AAA A AAA











F (0, 0, 0, 0)

AA

A A

A AA AA A A AAA

Рис. 20: Главный идеал в L∗2 , порожденный классом конъюнкции Решением уравнения (∗) будет любая булева функция, реализующаяся формулами из приведённых классов. В бесконечных булевых алгебрах, как следует из теоремы 2.24, существуют и неглавные (нетривиальные) ультрафильтры. Их также называют свободными, поскольку они не фиксированы ни в какой точке исходного множества. Пересечение всех элементов такого фильтра есть нулевой элемент. При доказательстве указанной теоремы используется лемма Куратовского-Цорна, эквивалентная, как мы знаем, аксиоме выбора. Заметим, что данная теорема является теоремой чистого существования, и, поэтому, в каждом конкретном случае ультрафильтр оказывается заданным неявно, как результат некоторого бесконечного итерационного процесса. Без помощи аксиомы выбора никаких неглавных ультрафильтров построить не удалось. 65

Пример 41. Покажем, как может быть построен неглавный ультрафильтр F над множеством натуральных чисел. На первом шаге рассмотрим в P(N) фильтр Фреше, который обозначим F0 . Он не является максимальным, поскольку, например, ни множество чётных чисел 2N, ни его дополнение (множество нечётных чисел) не принадлежат F0 . Поэтому надо принять решение, отнести 2N к конструируемому ультрафильтру F или нет. Пусть принято решение о том, что 2N ∈ F . Это будет означать, что некоторые другие множества (все множества, содержащие 2N ) также будут принадлежать F . Полученный фильтр обозначим F1 . Понятно, что он также не будет являться искомым ультрафильтром, поскольку относительно ряда множеств неопределённость останется: например, ни множество 3N, ни его дополнение не принадлежат F1 . Здесь снова нужно принять решение о вхождении одного из указанных множеств в F1 , построить F2 и т.д. Показано, что в результате выполнения “трансфинитного числа шагов” будет построен искомый ультрафильтр F . Хотя мы привели чрезвычайно грубый набросок способа построения фильтра F , надеемся, что читателю видна роль аксиомы выбора в данных рассуждениях: никакого способа указать, какое множество нужно рассматривать на каждом шаге для включения его или его дополнения в F , нет. Кроме того, на каждом шаге можно принять любую из указанных альтернатив. Мы видим, что процесс построения F существенно неоднозначен, и, на самом деле, до сих пор не указано ни одного конкретного неглавного ультрафильтра, даже в самой простой бесконечной булевой алгебре — со счетным числом атомов. Неглавные ультрафильтры над P(N) могут быть использованы, например, при построении поля гипердействительных чисел в нестандартном анализе. Пример 42. Множество гипердействительных чисел ∗ R, изучаемых в нестандартном анализе, представляет собой неархимедово упорядоченное поле, являющееся расширением поля R действительных чисел.20 Это означает, что ∗ R — цепь, в которую вложено множество R (образ R — стандартные гипердействительные числа) и содержащее, кроме того, множество т.н. нестандартных гипердействительных чисел. При этом в ∗ R выполняются все аксиомы поля, однако не выполняется справедливая в R аксиома Архимеда: «для любых двух положительных чисел A и B существует натуральное n такое, что nA > B». Согласно принципу наследования свойств при расширении, аксиома Архимеда может нарушаться лишь когда хотя бы одно из чисел A и B нестандартное. Среди нестандартных чисел выделяют бесконечно большие и бесконечно малые. Так, если числа ε и I суть положительные бесконечно малое и бесконечно большое гипердействительные, а x — положительное действительное, то неравенства ε| + .{z . . + ε} > x n раз

и

x . . + x} > I | + .{z n раз

не будут выполняться ни для какого натурального n. Поле гипердействительных чисел ∗ R можно построить, используя некоторый неглавный ультрафильтр F в P(N). Рассмотрим всевозможные последовательности обычных действительных чисел. Будем говорить, что последовательности a = a1 , a2 , . . . и b = b1 , b2 , . . .. эквивалентны, если равенство ai = bi нарушается на множестве, не принадлежащем F . 20 Элементарному введению в нестандартный анализ посвящена брошюра Успенский В.А. Нестандартный, или неархимедов, анализ. — М.: Знание, 1983, откуда взяты этот и предыдущий примеры.

66

Легко проверяется, что, в силу свойств F , введённое отношения действительно является отношением эквивалентности и, например, все последовательности, отличающиеся, в конечном числе членов, эквивалентны. Получающиеся классы эквивалентности назовём гипердействительными числами; они и будут являться элементами ∗ R. Действительному числу a соответствует класс эквивалентности [ a, a, . . . ], это — стандартное гипердействительное число. Арифметические действия производятся над последовательностями почленно. Будем считать, что a < b , если неравенство ai > bi выполняется на каком-либо множестве, не входящем в F . Нетрудно проверить, что получено упорядоченное поле. В этом поле, однако, аксиома Архимеда не выполняется: например, [ 1, 12 , 13 , . . . ] есть бесконечно малое, а [ 1, 2, 3, . . . ] — бесконечно большое гипердействительные числа. Именно при проверке этих свойств и требуется, чтобы F был неглавным ультрафильтром.

67

3 3.1 3.1.1

Алгебраические системы Модели и алгебры Основные определения

Мы уже пользовались одним из основных понятий современной математики — понятием алгебраической системы (АС). Неформально, АС — это некоторое множество с определёнными на нём операциями и отношениями. Для формального задания АС A определим сначала составляющие её элементы. Пусть Op и Rel — некоторые непустые одновременно и не имеющие общих элементов совокупности символов произвольных операций и отношений. Если указанные множества конечны, то соответствующая алгебраическая система называется АС конечного типа. Мы будем рассматривать только такие системы. Сигнатура σ есть упорядоченная пара h Op, Rel i. Записывают σ = sgnt A. Различают следующие частные случаи: Rel = ∅, и тогда АС называют (универсальной) алгеброй, и Op = ∅, и тогда АС называют реляционной системой или моделью. Мощности множеств Op и Rel обозначим N и M соответственно. Каждому элементу fi ∈ Op сопоставлено натуральное число ni > 0, i = 1, N , а элементу rj ∈ Rel — целое число mj > 0, j = 1, M , выражающее «арность» или «местность» соответствующего функционального или предикатного символа. Нульарные отношения не включают в сигнатуру, поскольку таковых только два: это логические константы 0 и 1, и они играют специальную роль, неявно присутствуя в каждой АС с непустым множеством Rel. Также часто АС содержит двуместный предикат, выражающий отношение эквивалентности, однако соответствующий символ в сигнатуре при практических математических исследованиях обычно явно не указывают. Сигнатурным операциям с нулевыми арностями соответствуют фиксированные элементы области значений соответствующих функций. Будем считать, что операции с ненулевыми арностями имеют номера с 1 по N 0 6 N . Арности сигнатурных операций и отношений записывают в виде кортежа τ = h n1 , . . . , nN 0 , m1 , . . . , mM , 0, . . . , 0 i , который называют типом АС (при N 0 = N заключительные нули и разделитель «,» отсутствуют). Если оговаривают, что задается алгебра или модель, то их типы записывают, перечисляя арности лишь элементов из Op или, соответственно, из Rel. При задании типа, последовательности арностей n1 , . . . , nN 0 и m1 , . . . , mM принято упорядочивать так, чтобы они оказались невозрастающими. Задавая сигнатуру, её элементы перечисляют в соответствии с выбранной упорядоченностью. Если необходимо явно указывать арности элементов, их записывают в качестве верхних индексов: m fini , i = 1, N 0 , rj j , j = 1, M . Рассмотрим теперь не имеющее общих элементов с Op и Rel непустое множество A. Оно будет называться носителем или основным множеством АС A, что записывают A = Supp A. Если A — конечно, то соответствующая алгебраическая система называется конечной. Совокупности всех операций и отношений, которые можно определить на A будем обозначать Op A и Rel A соответственно. Понятно, что это — очень мощные множества, состоящие из большого числа элементов, даже если A — конечное множество небольшой мощности. Определим далее понятие интерпретации данной абстрактной сигнатуры. Интерпре-

68

тация ω есть пара функций h ω1 , ω2 i, ω1 : Op → Op A

и

ω2 : Rel → Rel A ,

сопоставляющих каждому символу из Op и Rel соответственно конкретные операции или отношения на A той же арности. Упомянутому выше неявному отношению эквивалентности сопоставляют предикат равенства (=). Окончательно, алгебраическая система A задаётся пятёркой h A, Op, Rel, ω1 , ω2 i. Образами интерпретации являются совокупности функций Op A ⊆ Op A и предикатов Rel A ⊆ Rel A на множестве A. Алгебраические системы с одинаковыми абстрактными сигнатурами называют однотипными. Однотипные АС различаются носителями и интерпретациями. Операции и отношения однотипных АС, являющиеся образами разных интерпретаций соответствующих символов сигнатуры называют одноимёнными. При работе с конкретными АС их записывают короче, либо в общем виде как A = h A, Op A, Rel A i , либо перечислением конкретных операций и отношений n

mM , 0, . . . , 0 i . A = h A, f1n1 , . . . , fNN0 0 , r1m1 , . . . , rM

Элементы Op A ненулевой арности называют главными операциями, элементы Rel A — главными отношениями, а элементы Op A нулевой арности — главными элементами АС. Элемент носителя A, отмечаемый нульарной операцией fi0 будем обозначать fi0 (A0 ), опуская, возможно верхний и нижний индексы у символа функции. Приведём примеры21 алгебраических систем. Пример 43. Для сигнатуры σ = h f1 , f2 , f3 , r1 , c1 , c2 i типа h 2, 2, 1, 2, 0, 0 i построим различные однотипные АС, выбирая различные носители и по-разному задавая интерпретацию символов сигнатуры σ. A1 : supp A1 = { 0, 1, . . . }, а элементы сигнатуры интерпретируются следующим образом: f1 7→ + , f2 7→ · (с соответствующим переходом к инфексной записи), f3 (n) = n + 1 , r 7→ 6 , c1 7→ 0 , c2 7→ 1 . Ясно, что такая АС описывает арифметику неотрицательных целых чисел. A2 : supp A2 = supp A1 , но сигнатурные символы интерпретируются по-другому: f1 7→ 0 , f2 (m, n) = mn , f3 (n) = 2n , r(m, n) 7→ m ∧ n = 1 , c1 7→ 1 , c2 → 7 1. Эта экзотичная АС не имеет специального названия. A3 : supp A3 = P(A). Сигнатурные символы будем трактовать следующим образом: f1 7→ ∪ ,

f2 7→ ∩ ,

f3 7→

−

,

r 7→ ⊆ ,

c1 7→ ∅ ,

c2 7→ A .

Ясно, что мы получили тотальную булеву структуру множеств. 21

См. Пинус А.Г. Основы универсальной алгебры: Учебное пособие. — Новосибирск: Изд-во НГТУ, 1998.

69

A4 : Носитель АС A4 есть множество V всех векторов ~x трёхмерного пространства, а сигнатурные символы интерпретируются так: f1 7→ + ,

f2 7→ × (векторное умножение) , f3 (~a) = −~a , r(~a, ~b) 7→ «вектор ~a коллинеарен вектору ~b» , c1 , c2 7→ ~0 .

Операции и отношения во всех приведённых примерах, соответствующие сигнатурным символам f1 , f2 , f3 и r1 будут одноимёнными. Везде мы предполагали, что введенные операции и отношения имеют обычный математический смысл. Заметим, что в этих АС неявно присутствует предикат эквивалентности =, интерпретируемый как равенство. Приведём примеры конкретных алгебраических систем различной сигнатуры. Пример 44. 1. AC h A, f i, где f — одноместная операция на множестве A называется унаром. 2. Поле действительных чисел h R, +, ·, 0, 1 i есть алгебра типа h 2, 1, 0, 0 i. Кортеж h +, ·, −, −1 , 0, 1 i нельзя рассматривать, как сигнатуру поля, т.к. операция −1 не определена для нуля. Кольцо K с единицей есть алгебра сигнатуры σK h 2, 2, 1, 0, 0 i.

=

h ·, +, −, 0, 1 i типа

Группа есть алгебра типа h 2, 1, 0 i с носителем G и сигнатурой σG = h ◦,

−1

, e i.

3. Частично предупорядоченное множество h P, ≤ i есть модель типа h 2 i. 4. Если одна АС может быть получена из другой удалением некоторых операций, отношений или констант, то первая АС называется редуктом второй. Упорядоченная группа A есть АС с носителем A типа h 2, 1, 2, 0 i и сигнатурой h ◦, −1 ; v, e i, где редукт G = h A, ◦, −1 , e i есть группа, а редукт P = h A, v i — ч.у. множество. При этом считается, что x v y ⇒ a ◦ x ◦ b v a ◦ y ◦ b для любых x, y, a, b ∈ A. Если при этом P — цепь, то A есть линейно упорядоченная группа. Примером линейно упорядоченной группы будет структура h R, +, −, 6, 0 i. Во всех приведённых выше примерах считалось, что приведённые операции и отношения обладают известными свойствами. В общем случае эти свойства необходимо задавать. Совокупность АС фиксированной сигнатуры называется классом алгебраических систем. Класс M АС сигнатуры σ называется многообразием, если существует множество Σ тождеств сигнатуры σ такое, что АС сигнатуры σ принадлежит классу M если и только если в ней выполняются все тождества Σ. Например, полугруппы — это многообразия сигнатуры состоящей из единственной бинарной операции · (в инфексной записи, обычно опускается), удовлетворяющие тождеству (xy)z = x(yz). Ассоциативно-коммутативные кольца с единицей это многообразия сигнатуры h +, ·, −, 0, 1 i типа h 2, 2, 1, 0, 0 i удовлетворяющие следующим тождествам Σ: (x + y) + z = x + (y + z) x+0 = 0+x = x x + (−x) = 0 x+y = y+x (x + y)z = xz + yz x(y + z) = xy + xz (xy)z = x(yz) x1 = 1x = x xy = yx. 70

Отметим, что алгебре можно сопоставить соответствующую адекватную модель, если каждую операцию вида fin (x, . . . , xn ) заменить на отношение rin+1 (x, . . . , xn , xn+1 ) такое, что r n+1 (x, . . . , xn , y) ⇔ fin (x, . . . , xn ) = y. Такая модель называется представi ляющей. Пример 45. Пусть задана группа h Z, +, −, 0 i. Если def

r13 (m, n, k) = m + n = k ,

def

r22 (m, n) = m = −n ,

def

r31 (n) = n = 0 ,

то h Z, r13 , r22 , r31 i будет представляющей моделью для данной алгебры. 3.1.2

Подсистемы и прямое произведение алгебраических систем

Напомним, что множество X называется устойчивым относительно отображения f : X n → X, если f (x1 , . . . , xn ) ∈ X для любого кортежа (x1 , . . . , xn ) из области определения f . Пусть A = h A, Op A, Rel A i — алгебраическая система и B — непустое подмножество A. Назовём B устойчивым относительно операций из Op A, если оно устойчиво относительно сужений на B каждой операции из Op A. Определение 3.1. Пусть A = h A, Op A, Rel A i — АС и ∅ 6= B ⊆ A. АС B = h B, Op B, Rel B i , где Op B и Rel B — сужения Op A и Rel A на B, называется подсистемой A, если множество B устойчиво относительно операций из Op A. Подсистему алгебры называют подалгеброй, а подсистему модели — подмоделью. Если B ⊂ A, то соответствующую подсистему называют собственной. Тот факт, что АС B есть подсистема (собственная подсистема) АС A записывают B 6 A (B < A). Ясно, что любое подмножество носителя определяет подмодель, но не любое — подалгебру. Для последнего требуется устойчивость подмножества относительно всех операций сигнатуры, в том числе и нульарных, т.е. подсистема должна содержать все главные элементы исходной системы, если таковые имеются. Пример 46. 1. Поле рациональных чисел hQ, +, ·, 0, 1 i есть подалгебра поля действительных чисел (см. пример 44). 2. Если множество A — собственное подмножество множества B, то алгебра множеств P(A) не является подалгеброй P(B), поскольку такое сужение не сохраняет единицу P(A). 3. Пусть F — множество дифференцируемых действительных функций. Тогда унар d d h F, dx i, где dx — операция дифференцирования, есть алгебра. Множество полиномов будет её подалгеброй. 4. При любом натуральном n унар h Z, + i содержит подалгебру h nZ, + i. Совокупность всех подсистем АС A будем обозначать Sub (A). Ясно, что это ч.у. множество, упорядоченное по включению. Утверждение 3.1. Пусть A — АС и {Ai }i∈I — некоторая совокупность её подсистем. T Тогда i∈I Ai либо пусто, либо является подсистемой. Доказательство. Достаточно заметить, что пересечение носителей всех подсистем, если оно не пусто, устойчиво относительно всех операций всех подсистем. Следствие. Если АС A имеет главные элементы, то пересечение всех её подсистем непусто. Справедливость данного следствия вытекает из условия принадлежности главных элементов АС A любой её подсистеме. 71

Наименьшая подсистема АС называют её главной подсистемой. Главная подсистема, однако, существует не для любой АС: например, алгебра (кольцо целых чисел) h Z, +, ·, 0 i или модель h Z, 6 i наименьших подсистем, очевидно, не имеют. Если же исходная АС содержит главные элементы, то они обязательно будут присутствовать во всех её подсистемах, в т.ч. и в главной. Пусть дана АС A = h A, Op A, Rel A i и B ⊆ A. Обозначим через B = hBi пересечение всех подсистем из Sub (A), содержащих B. B называют подсистемой, порождённой множеством B , а элементы B — порождающими элементами. Поэтому B мы также будем записывать B = h [B], Op A, Rel Ai. Если B — конечное множество, то B есть конечнопорождённая система. Пример 47.

1. Подкольцо чётных в кольце целых чисел порождается элементом 2.

2. Пусть A = h { a0 , a1 , . . . , an−1 }, f11 i — унар, где f11 (ai ) = ai+1(mod n) . Тогда A порождается любым элементом своего носителя. 3. h N, + i = h [1], + i. 4. АС h N, · i не есть конечнопорождённая алгебра. Итак, непустое пересечение подсистем АС всегда является её подсистемой. Чтобы снять условие непустоты пересечения подсистем, обычно в качестве подсистемы допускают и систему с пустым носителем. Объединение же подсистем АС, вообще говоря, подсистемой не является, что показывает нижеследующий Пример 48. h nZ, + i и h mZ, + i при любых целых n и m суть подсистемы h Z, + i, однако множество nZ ∪ mZ при некратных друг другу n и m неустойчиво по отношению к сложению, и в этом случае h nZ ∪ mZ, + i даже не есть АС. Например, при n = 6 и m = 10 множество { 0, ±6, ±10, ±12, ±20, . . . } не содержит элемента 16=6+10. Ниже будет сформулировано условие, когда объединение подсистем будет являться подсистемой. Определение 3.2. Совокупность S подмножеств A называется локальной, если любое конечное подмножество A содержится в некотором элементе S. Примером локальной подсистемы множества R является совокупность интервалов вида (−n, n), n ∈ N. Теорема 3.1. Пусть A = h A, Op A, Rel A i — алгебраическая система и SS= { Ai ⊆ A | i ∈ I } — локальная совокупность подмножеств её носителя A. Тогда h i∈I Ai , Op A, Rel A i 6 A. Доказательство. Нам достаточно показать лишь устойчивость множества S относительно операций из Op A, поскольку все остальные свойства полученной системы будут наследоваться от исходной. S Обозначим U = i∈I Ai и рассмотрим произвольную n-местную операцию операцию f из Op A. Для произвольного набора (a1 , . . . , an ) = a имеем: с одной стороны, a ∈ U , а с другой — найдется такое множество Ai ∈ U , что a ∪ f (a) ∈ Ai . Это означает, что U — устойчиво относительно f . Таким образом, устойчивость на объединении элементов локальной совокупности следует из того, что операции определены над конечным множеством аргументов. Выше мы отмечали, что совокупность Sub (A) всех подсистем АС A есть ч.у. множество. Для того, чтобы Sub (A) оказалось решёткой, необходимо показать существование наименьшей подсистемы, содержащей объединение двух произвольных подсистем 72

A. Оказывается, это можно сделать и, таким образом, Sub (A) есть решётка. Более того, она оказывается полной решёткой (см. с. 59). Пример 49. Продолжая рассмотрение примера 48 отметим, что наименьшей подсистемой АС h Z, + i, содержащей её подсистемы h nZ, + i и h mZ, + i будет h [m ∧ n], + i. Например, для h 6Z, + i и h 10Z, + i это h 2Z, + i. Если A и B — две однотипные АС абстрактной сигнатуры σ с носителями A1 и A2 соответственно, то можно определить прямое произведение C = A × B этих АС. Сигнатура АС C будет состоять из такого же числа тех же символов операций и отношений, но местности соответствующих символов удваиваются. Пусть f1 и f2 — одноимённые операции, а r1 и r1 — одноимённые отношения из A и B соответственно. Соответствующие им операция f × и отношение r× в АС C = A × B определяются как f × (a, b) = ( f1 (a), f2 (b) ) и r× (a, b) = ( r1 (a), r2 (b) ) (здесь a ∈ A и b ∈ B — произвольные наборы элементов соответствующей арности.

3.2 3.2.1

Гомоморфизмы алгебраических систем Согласованность отображений АС с операциями и отношениями

Определение 3.3. Пусть h A, Op A, Rel A i и h A0 , Op A0 , Rel A0 i — две однотипные АС, ϕ — отображение из A в A0 , а f ∈ Op A и f 0 ∈ Op A0 — пара одноимённых операций арности n. Тогда говорят, что отображение ϕ согласовано с данными операциями, если ϕ(f (a1 , . . . , an )) = f 0 (ϕ(a1 ), . . . , ϕ(an ))

и

ϕ(f (A0 )) = f 0 (ϕ(A0 ))

(3.1)

для n > 0 или n = 0 соответственно. Пример 50. Для алгебр h R r {0}, · i и h R, + i отображение ϕa (x) = loga |x| при любом действительном a > 0, a 6= 1 согласовано с операциями · и + данных АС. Определение 3.4. Пусть h A, Op A, Rel A i и h A0 , Op A0 , Rel A0 i — две однотипные АС, ϕ — отображение из A в A0 , а r ∈ Rel A и r 0 ∈ Rel A0 — пара одноимённых отношений арности m. Тогда говорят, что отображение ϕ соответственно 1) согласовано с данными отношениями, если r(a1 , . . . , am ) ¡¢ r 0 (ϕ(a1 ), . . . , ϕ(am )) ,

(3.2)

2) сильно согласовано с данными отношениями, если r 0 (ϕ(a1 ), . . . , ϕ(am )) ¡¢ ¡¢ ∃ b , . . . , b 1 m A

£¡

ϕ(ak ) = ϕ(bk ), k = 1, m

¢

¤ ∧ r(b1 , . . . , bm ) , (3.3)

3) полностью (или тождественно) согласовано с данными отношениями, если r(a1 , . . . , am ) ≡ r 0 (ϕ(a1 ), . . . , ϕ(am )) . Если отображение ϕ окажется согласованным со всеми парами одноимённых операций [отношений] двух АС, то будем говорить, что ϕ согласовано с операциями [отношениями] этих АС.

73

Пример 51. Рассмотрим две модели типа h 1 i: h {a1 , a2 }, r i и h {b}, r 0 i. Единственное возможное отображение ϕ из A на B задаётся равенствами ϕ(a1 ) = ϕ(a2 ) = b. Пусть r 0 (b) = 1. Тогда: 1) если r(a1 ) = r(a2 ) = 0, то ϕ согласовано, 2) если r(a1 ) = 1 и r(a2 ) = 0, то ϕ сильно согласованно, 3) если r(a1 ) = r(a2 ) = 1, то ϕ тождественно согласованно с парой r, r 0 одноимённых отношений рассматриваемых моделей. 3.2.2

Типы гомоморфизмов АС

Определение 3.5. Пусть A = h A, Op A, Rel A i и B = h B, Op B, Rel B i — две однотипные АС. Отображение ϕ : A → B, согласованное с операциями этих АС называется соответственно 1) гомоморфизмом из A в B, если ϕ согласованно, 2) взаимнооднозначным (или биективным) гомоморфизмом между A и B, если ϕ — биекция, согласованная, 3) сильным гомоморфизмом из A в B, если ϕ сильно согласованно, 4) изоморфизмом между A и B, если ϕ — биекция, полностью согласованная с отношениями этих АС. Вместо термина «сильный» для гомоморфизма иногда употребляют термин строгий. Для алгебр понятия гомоморфизма и сильного гомоморфизма, очевидно, совпадают, а биективный (взаимнооднозначный) гомоморфизм есть изоморфизм. Пример 52. Модель A = h Z, < i не изоморфна, а лишь биективно гомоморфна модели B = h 2Z, 6 i: отображение ϕ(n) = 2 n есть взаимнооднозначный (не сильный) гомоморфизм из A в B, но ϕ “просто”, но не тождественно согласовано с отношениями < и 6. Замечание. Отметим важное свойство сильных гомоморфизмов, которое нам понадобится в дальнейшем. Соотношение (3.3) позволяет утверждать, что если (в введённых обозначениях) справедливо r 0 (ϕ(a1 ), . . . , ϕ(an )), то в A найдутся такие b1 , . . . , bm из ядра отображения ϕ, что справедливо r(b1 , . . . , bm ), и, таким образом, r 0 (ϕ(a1 ), . . . , ϕ(an )) ¡¢ r(b1 , . . . , bm ). Можно сказать, что мы сохранили истинность переходя от отношения r 0 к одноименному отношению r “при движении против отображения ϕ”. АС A и B называют изоморфными, если существует изоморфизм между A и B, что записывают как A ∼ = B. То, что ϕ — гомоморфизм из A в B записывают как ϕ ∈ Hom(A, B). Если ϕ ∈ Hom(A, B), то, как нетрудно проверить, Im ϕ 6 B. Понятно, что тождественное отображение любой АС на себя есть изоморфизм, если ϕ : A → B — изоморфизм, то и ϕ−1 : B → A — также изоморфизм и композиция гомоморфизмов (изоморфизмом) есть гомоморфизм (изоморфизм). Легко видеть, что отношение изоморфизма есть отношение эквивалентности на множестве алгебраических систем и, следовательно, все алгебраические системы распадаются на классы эквивалентности, содержащие изоморфные системы. Обычно изучают свойства алгебраической системы с точностью до изоморфизма. Такие свойства называют абстрактными. 74

Сюръективный гомоморфизм АС называют эпиморфизмом (или наложением), а инъективный гомоморфизм — мономорфизмом (или вложением), т.е. также, как и соответствующе отображения. Гомоморфизм АС в себя называется эндоморфизмом. Изоморфизм АС на себя называют автоморфизмом. С каждой АС A связаны моноид эндоморфизмов End (A) и группа автоморфизмов Aut (A) (группа обратимых элементов моноида End (A)). Класс алгебраических систем называется абстрактным, если если с каждой АС в нём лежат все системы, ей изоморфные. Теорема 3.2. Всякий сюръективный эндоморфизм конечной системы есть изоморфизм. Доказательство. Рассмотрим АС A = h A, Op A, Rel A i с конечным носителем A и наложение ϕ : A → A. Нам надо показать, что ϕ тождественно согласовано с отношениями A и ϕ(A). Пусть r — произвольное отношение арности m из Rel A. Поскольку ϕ — гомоморфизм, то для любого набора a1 , . . . , am из m элементов носителя A истина импликация r(a1 , . . . , am ) ¡¢ r(ϕ(a1 ), . . . , ϕ(am )), т.е. для её посылки и заключения могут иметь место только следующие пары истинностных значений посылки и заключения: (0, 0), (0, 1), (1, 1). Теорема будет доказана, если выяснится, что второй случай в наших условиях не реализуется. Наложение множества на себя является биекцией и, в силу конечности A, перестановкой его элементов конечной степени. Тогда существует натуральное d такое, что ϕd есть тождественная перестановка. Пусть отношение r(ϕ(a1 ), . . . , ϕ(am )) выполнено. Отсюда следует, что, поскольку ϕ — гомоморфизм, для любого натурального t выполнено r(ϕt (a1 ), . . . , ϕt (am )). При t = d получаем, что выполнено и r(a1 , . . . , am ). Таким образом, r(ϕ(a1 ), . . . , ϕ(am )) ¡¢ r(a1 , . . . , am ), и случай (0, 1) невозможен.

3.3 3.3.1

Конгруэнции и гомоморфные системы Конгруэнции и фактор-системы

Определение 3.6. Однородное отношение ρ на множестве A называется стабильным относительно операции f местности n на A, если при n > 0 для любых элементов a1 , a1 0 , . . . , an , an 0 ∈ A справедливо n ^

ai ρai 0 ⇒ f (a1 , . . . , an )ρf (a1 0 , . . . , an 0 ) ,

i=1

а при n = 0 — ρ рефлексивно. Аналогично может быть определено стабильное отношение произвольной арности. Стабильность отношения означает, что если наборы аргументов функции находятся в данном отношении, то и результаты операции также находятся в этом отношении. Однородное отношение ρ на АС h A, Op A, Rel A i называется стабильным на этой АС, если оно стабильно относительно любой операции из Op A. Например, полное O и диагональное M отношения стабильны на любой АС. Определение 3.7. Стабильная на АС эквивалентность называется конгруэнцией на ней. Ясно, что полное и диагональное отношения являются конгруэнциями на любой АС. С каждой АС A связана решётка конгруэнций Con(A), которая оказывается полной подрешёткой в решётке её подсистем Sub (A). Решётка Con(A) имеет универсальные 75

грани: это отмеченные выше диагональ и аморфная конгруэнция. Пересечение конгруэнций α и β совпадает с их теоретико-множественным пересечением α ∩ β, а объединение — с эквивалентным замыканием (α ∪ β) e их теоретико-множественного объединения (если α и β перестановочны, то как мы помним, (α ∪ β) e = α ∪ β = αβ ). Теорема 3.3. Если на алгебре A все конгруэнции перестановочны, то решётка Con(A) модулярна. Доказательство. Пусть α, β, γ ∈ Con(A) и α ⊆ β. Для того, чтобы в решётке конгруэнций выполняется модулярный закон, достаточно показать, что выполняется включение α ⊆ β ⇒ α ∪ (β ∩ γ) ⊇ β ∩ (α ∪ γ) ,

(∗)

обратное к неравенству полумодулярности. Заменив объединение конгруэнций на их произведение, для произвольных подалгебр A и B алгебры A имеем A(β ∩ (α ¦ γ))B ⇔ AβB ∧ ∃X ( AαX ∧ XγB ) ⇔ ∃X ( AβB ∧ AαX ∧ XγB ) . Здесь X — некоторая подалгебра A. Покажем теперь, что в данных условиях AβB можно заменить на XβB. Действительно, AαX в силу α ⊆ β влечёт AβX, что, в свою очередь, эквивалентно XβA в силу симметричности конгруэнций. Вместе с AβB это означает, что справедливо XβA ∧ AβB, т.е. Xβ 2 B или XβB. Таким образом, ∃X ( AβB ∧ AαX ∧ XγB ) ⇒ ∃X ( AαX ∧ XβB ∧ XγB ) ⇔ ⇔ ∃X ( AαX ∧ X(β ∩ γ)B ) ⇔ A[α ¦ (β ∩ γ)]B . С заменой ¦ 7→ ∪ это эквивалентно (∗). Теорема 3.4. Ядро гомоморфизма АС есть конгруэнция на ней. Доказательство. Пусть ϕ — гомоморфное отображение АС с носителем A. Поскольку ядро Ker ϕ есть эквивалентность, нам достаточно показать его стабильность относительно операций данной АС. Рассмотрим произвольную операцию f данной АС. Пусть местность f есть n. Если n > 0, то возьмём a1 , a1 0 . . . , an , an 0 ∈ A такие, что ai (Ker ϕ)ai 0 , иначе ϕ(ai ) = ϕ(ai 0 ) для всех i = 1, n. Поскольку ϕ — гомоморфизм, имеем: ϕ(f (a1 , . . . , an )) = f 0 (ϕ(a1 ), . . . , ϕ(an )) = = f 0 (ϕ(a1 0 ), . . . , ϕ(an 0 )) = ϕ(f (a1 0 , . . . , an 0 )) , т.е. f (a1 , . . . , an ) Ker ϕ f (a1 0 , . . . , an 0 ). Если n = 0, то заметим, что ядро гомоморфизма — рефлексивное отношение, стабильное по определению. Пусть на АС A = h A, Op A, Rel A i задана конгруэнция α. Легко видеть, что результаты операций из Op A и истинность отношений из Rel A не изменятся при замене элемента a на какой-либо другой из класса эквивалентности [a]α . Это позволяет корректно определить на фактор-множестве A/α одноимённые относительно sgnt A операции и отношения. Операция f ∗ , одноимённая операции f ∈ Op A арности n, задаётся равенством def

f ∗ ([a1 ]α , . . . , [an ]α ) = [f (a1 , . . . , an )]α 76

или

def

f ∗ ((A/α)0 ) = [f (A0 )]α

(3.4)

при n > 0 и n = 0 соответственно. Отношение r∗ , одноимённое отношению r ∈ Rel A арности m задаётся равенством £ ¤ def r∗ ([a1 ]α , . . . , [am ]α ) = ∃ a1 0 , . . . , am 0 ( ai αai 0 , i = 1, m ) ∧ r(a1 0 , . . . , am 0 ) . A

(3.5)

Полученные множества операций и отношений на A/α будем обозначать Op∗ A/α и Op∗ A/α соответственно. Таким образом, фактор-система A/α = h A/α, Op∗ A/α, Rel∗ A/α i будет корректно определённой АС, однотипной с A. При этом ясно, что естественное отображение nat(A, α) будет сильным гомоморфизмом из A в A/α с ядерной эквивалентностью α. Замечание. Из сказанного следует, что теорема 3.4 допускает обращение: если α — конгруэнция на АС A, то естественное отображение nat(A, α) есть гомоморфизм (на её фактор-систему). Пример 53. Если A — алгебра с носителем A, то A/ MA ∼ = A, а A/OA — одноэлементная алгебра. Таким образом, каждая алгебра имеет одноэлементную фактор-алгебру. Для алгебр справедлива Теорема 3.5 (Биркгофа). Класс алгебр является многообразием, если и только если он замкнут относительно взятия подалгебр, прямых произведений и гомоморфных образов. 3.3.2

Теоремы о гомоморфизмах и изоморфизмах АС

Нижеследующая теорема описывает ситуацию, когда в качестве конгруэнции на АС берётся ядро гомоморфизма. Теорема 3.6 (О гомоморфизмах алгебраических систем). Пусть ϕ — гомоморфизм из АС A = h A, Op A, Rel A i в АС B = h B, Op B, Rel B i . Тогда: 1) отображение ψ, задаваемое правилом ψ([a]Ker ϕ ) = ϕ(a), есть биективный гомоморфизм из A/Ker ϕ в Im ϕ ⊆ B; 2) если гомоморфизм ϕ сильный, то ψ — изоморфизм между A/Ker ϕ и Im ϕ. Доказательство. По теореме об основном свойстве отображений существует вложение ψ

A/Kerϕ ,→ B такое, что диаграмма

'' ') nat (Kerϕ) A

ϕ

wB [ ] [[ψ

A/Kerϕ

коммутативна. Это отображение задаётся правилом ψ([a]Ker ϕ ) = ϕ(a) .

(3.6)

Для доказательства утверждения 1) теоремы нам надо показать согласованность отображения ψ с операциями и отношениями АС A/Ker ϕ и B. 77

Рассмотрим произвольную тройку одноимённых операций f ∈ Op A, f 0 ∈ Op B и f ∗ ∈ Op∗ A/Ker ϕ. Пусть их арность равна n. При n > 0 имеем (3.4)

(3.6)

ψ(f ∗ ([a1 ]Ker ϕ , . . . , [an ]Ker ϕ )) = ψ([f (a1 , . . . , an )]Ker ϕ ) = (3.1)

(3.6)

= ϕ(f (a1 , . . . , an )) = f 0 (ϕ(a1 ), . . . , ϕ(an )) = = f 0 (ψ([a1 ]Ker ϕ ), . . . , ψ([an ]Ker ϕ )) , (3.7) для любого набора элементов a1 , . . . , an из A, а при n = 0 — (3.4)

(3.6)

(3.1)

ψ(f ∗ ((A/Ker ϕ)0 )) = ψ([f (A0 )]Ker ϕ ) = ϕ(f (A0 )) = f 0 (ϕ(A0 )) = f 0 (ψ([A0 ])Ker ϕ ) . Это означает согласованность ψ с f ∗ и f 0 , и, следовательно, со всем множеством операций систем A/Kerϕ и B. Теперь рассмотрим произвольную тройку одноимённых отношений r ∈ Rel A, r 0 ∈ Rel B и r∗ ∈ Rel∗ A/Kerϕ. Пусть их арность равна m. Для любого набора элементов a1 , . . . , am из A имеем: (3.5)

r∗ ([a1 ]Kerϕ , . . . , [am ]Kerϕ ) ⇔ ¢ ¤ (3.2) £¡ ⇔ ∃ a1 0 , . . . , am 0 ai 0 (Kerϕ)ai , i = 1, m ∧ r(a1 0 , . . . , am 0 ) ⇒ A

⇒ r 0 (ϕ(a1 0 ), . . . , ϕ(am 0 )) ⇔ (3.6)

⇔ r 0 (ϕ(a1 ), . . . , ϕ(am )) ⇔ r 0 (ψ([a1 ]Kerϕ ), . . . , ψ([am ]Kerϕ )) . (3.8) Это означает согласованность ψ с r∗ и r 0 , и, следовательно, со всем множеством отношений систем A/Ker ϕ и B. Итак, показано, что ψ есть мономорфизм из A/Kerϕ в B и, следовательно, биективный гомоморфизм в Im ϕ. Для доказательства утверждения 2) теоремы заметим, что если гомоморфизм ϕ силь(3.2)

ный, то следование ⇒ в (3.8) можно обратить (см. замечание на с. 74) и, следовательно, заменить на ⇔. В результате получим, что отображение ψ сильно согласовано с r∗ ∈ Rel A/Ker ϕ и r 0 ∈ Rel B и, следовательно, со всем множеством отношений систем A/Kerϕ и Im ϕ ⊆ B. Поскольку отображение ψ биективо, то сильная согласованность означает согласованность тождественную и ψ — изоморфизм между A/Kerϕ и Im ϕ. Было установлено, что если гомоморфизм ϕ — сильный, то Im ϕ ∼ = A/Ker ϕ, или, другими словами, образ сильного гомоморфизма АС изоморфен фактор-системе по его ядру. С учётом замечания на с. 77, полученный результат можно переформулировать и так: совокупность всех сильно гомоморфных образов АС с точностью до изоморфизма совпадает с множеством всех фактор-система по различным конгруэнциям. Ясно, что для алгебр уточнение «сильного» в обоих случаях можно опустить. Пример 54. 1. Рассмотрим две однотипные алгебры A = h N0 , + i, B = h {+1, −1}, · i и отображение ϕ носителя A на носитель B, задаваемое правилом ϕ(n) = (−1)n . Имеем: ϕ(m + n) = (−1)m+n = (−1)m · (−1)n = ϕ(m) · ϕ(n) , т.е. ϕ — гомоморфизм из A в B. Далее ψ

m(Ker ϕ)n ⇔ m ≡ 2 n , A/Ker ϕ = h {[0], [1]}, ⊕ i ,→ B , ψ([1]) = ϕ(1) = −1 , ψ([0]) = ϕ(0) = +1 . 78

2. Пусть ϕ : L → L0 — сюръективный гомоморфизм решётки L в решётку L0 . Тогда по теореме о гомоморфизмах существует такой изоморфизм ψ решёток L0 и L/Ker ϕ, что ψ(ϕ(a)) = π(a) для всех a ∈ L, где π — естественный гомоморфизм решётки L на её фактор-решётку L/Ker ϕ. Пусть α — однородное на множестве A отношение, то его сужение на подмножество B ⊆ A есть B 2 ∩ α. В этом случае легко видеть, что если α — конгруэнция на A и B 6 A, то B 2 ∩ α — конгруэнция на B. Следствием теорем о гомоморфизмах АС и о фактормножествах является полезная Теорема 3.7 (О факторсистемах). Пусть ϕ — гомоморфизм из АС A = h A, Op A, Rel A i в АС B = h B, Op B, Rel B i и ∼ — эквивалентность на A такая, что ∼ ⊆ Kerϕ. Тогда: 1) отображение χ, задаваемое правилом χ([a]∼ ) = ϕ(a), есть эпиморфизм из A/ ∼ на Imϕ ⊆ B; 2) если гомоморфизм ϕ сильный, то и χ — сильный гомоморфизм между A/ ∼ и Imϕ. χ

Доказательство. По теореме о фактормножествах существует отображение A/∼ → B такое, что диаграмма ϕ A B

w χ  

[[ [] nat (∼)

A/ ∼

коммутативна. Это отображение задаётся правилом ψ([a]∼ ) = ϕ(a) .

(3.9)

Для доказательства утверждения теоремы надо показать согласованность отображения χ с операциями и отношениями АС A/ ∼ и B. Это проводится аналогично доказательству теоремы 3.6. Пусть f ∈ OpA, f 0 ∈ OpB и f ∗ ∈ Op∗ A/ ∼ — тройка одноимённых операций арности n. Для любого набора элементов a1 , . . . , an из A при n > 0 будем иметь цепочку равенств, аналогичную (3.7) с заменами Kerϕ 7→ ∼ и (3.6) 7→ (3.9). Также и для n = 0. Это означает согласованность χ с f ∗ и f 0 , и, следовательно, со всем множеством операций систем A/ ∼ и B. Теперь рассмотрим произвольную тройку одноимённых отношений r ∈ RelA, 0 r ∈ RelB и r∗ ∈ Rel∗ A/ ∼ арности m. Для любого набора элементов a1 , . . . , am из A будем иметь цепочку соотношений, аналогичную (3.8) с заменами Kerϕ 7→ ∼ и (3.6) 7→ (3.9). Это означает согласованность χ с r∗ и r 0 , и, следовательно, со всем множеством отношений систем A/ ∼ и B. Итак, показано, что χ есть гомоморфизм из A/ ∼ в B и, следовательно, эпиморфизм в Imϕ. Если гомоморфизм ϕ сильный, то соответствующую импликацию в последних соотношениях можно обратить. В результате получим, что отображение χ сильно согласованно с r∗ ∈ Rel A/ ∼ и r 0 ∈ Rel B и, следовательно, χ — сильный гомоморфизм из A/Ker в Imϕ.

79

Теорема 3.8 (Первая об изоморфизмах алгебраических систем). Пусть АС A с носителем A имеет подсистему B с носителем B, α — конгруэнция на A, ϕ = nat(A, α) и β = B 2 ∩ α — конгруэнция на B. Тогда существует взаимнооднозначный гомоморфизм ψ фактор-системы B/β на Im ϕ 0 , где ϕ 0 — сужение ϕ на B. Доказательство. Рассмотрим диаграмму

u

w A/α

ϕ

A сужение

B

ϕ0

[[

nat (B, β)

сужение

[[] B/β

u w Im ϕ 0  ψ 

Сужение ϕ 0 сильного гомоморфизма ϕ = nat(A, α) на B ⊆ A есть гомоморфизм B. По теореме 3.6 о гомоморфизме АС отображение ψ, задаваемое правилом ψ([x]Ker β ) = ϕ 0 (x) — взаимооднозначный гомоморфизм B/Ker β на Im ϕ 0 . Замечание. При сужении области задания свойство гомоморфизма быть сильным может быть потеряно, так что гомоморфизм ϕ 0 , вообще говоря, не сильный. Поэтому, в общем случае нельзя утверждать, что ψ — изоморфизм, и в данной 1-й теореме об изоморфизме АС речь, строго говоря, идёт лишь о биективном гомоморфизме. Однако, если A — алгебра, то ψ будет изоморфизмом, с чем связано традиционное название теоремы. Пример 55. Рассмотрим АС A = h N0 , +, 6 i и её подсистему B = h 2N, +, 6 i. Пусть mαn ⇔ m ≡ 2 n. Ясно, что α — конгруэнция на A, A/α = h {[1], [0]}, ⊕, 6 i и ϕ = nat(A, α)(n) равно [1] при нечётном n и [0] при чётном. Далее пусть ϕ 0 — сужение ϕ на B. Тогда Im ϕ 0 = h {[0]}, ⊕, O i, β = (2N)2 ∩ α = O и B/β = h {[0]}, ⊕, 6 i ∼ = Im ϕ 0 . Вторая теорема об изоморфизмах АС связана с дробными эквивалентностями (см. c. 21). Теорема 3.9 (Вторая об изоморфизмах алгебраических систем). Пусть A — АС, а α и β — две конгруэнции на ней, причём β ⊆ α. Тогда ( A/β ) /(α/β) ∼ = A/α. Доказательство. Рассмотрим диаграмму A ' ''nat α [ [ '') [^[[ ε w A/α A/β '' [ ] ') [ nat (α/β) ' [^[ ψ nat β

(A/β)/(α/β)

Зададим отображение ε правилом ε([a]β ) = [a]α . Тогда ε — сильный гомоморфизм из A/β в A/α. По теореме 3.6 отображение ψ, задаваемое правилом ψ([[x]β ]α/β ) = ε(x), есть изоморфизм между ( A/β ) /(α/β) и A/α. 80

Приведём без доказательства ещё одну теорему. Теорема 3.10 (О соответствии). Если A — АС с носителем A и β ∈ Con(A), то решётка L = { α | α ∈ Con(A), β ⊆ α } изоморфна решётке Con(A/β), при этом изоморфизм ϕ задаётся равенством ϕ(α) = nat(α/β). Укажем только, что здесь L и Con(A/β) — полные решётки (см. с. 59).

3.4

Многоосновные системы

Понятие АС может быть расширено. Например, если операции из Op A — частичные, то говорят о частичной АС. Другим возможным направлений расширения понятия АС является задание элементов сигнатуры не на одном, а на нескольких носителях. Так появляется понятие многоосновной (многосортной, гетерогенной, полидоменной) системы. Рассмотрим некоторые примеры многоосновных алгебр. Действие группы на множестве. Пусть дана группа G = h G, ◦, e i. Действие α группы G на непустом множестве T (обозначение G : T ) обычно определяют как гомоα

морфизм из G в симметрическую группу Symm T преобразований T (заметим, что при заданных группе G и множестве T можно, вообще говоря, построить различные действия G на T ). Мы дадим иное, как представляется, более простое определение действия группы на множестве. Рассмотрим структуру из пяти элементов D = h G, T, ◦, ∗, e i , ∗

у которой редукт h G, ◦, e i есть группа G, а операция G × T → T подчиняется соотношениям e ∗ t = t , (g ◦ h) ∗ t = h ∗ (g ∗ t) для любых g, h ∈ G и t ∈ T . Легко видеть, что указанные соотношения гарантируют, что соответствующее отображение G в Symm T будет являться гомоморфизмом. Введённая структура D представляет собой пример двухосновной алгебры с двумя бинарными операциями. Она имеет два носителя: G и T , причём групповая операция ◦ определена парах элементов из G, а операция ∗ — на парах элементов (g, t), где g ∈ G, а t ∈ T . Константа e есть главный элемент D. Конечные автоматы. Конечном детерминированным автоматом с начальным состоянием называется шестёрка объектов A = h S, X, Y, ◦, ∗, s0 i , где S, X, Y — конечные непустые множества, называемые соответственно множествами ◦ состояний, входных и выходных сигналов, ◦ — функция переходов S × X → S, ∗ — ∗ функция выходов S × X → Y и s0 ∈ S — начальное состояние. Конечные автоматы являются примером трёхосновной алгебры, имеющей три носителя ( S, X и Y ), две бинарные функции (◦, ∗ ) и главный элемент (s0 ). Линейное пространство. Пусть L — непустое множество и M = h L, +, 0 i — абелева группа (модуль). Пусть K — поле с носителем K, операцию сложения в котором будем обозначать тем же символом +, что и у модуля M, а символ операции умножения — опускать при записи. Единицу поля K будем обозначать, как обычно, 1. Введем новую операцию ·, действующую из K × L в L и подчиняющуюся правилам: 81

1. 1 · x = x

(унитальность),

2. (µλ) · x = µ · (λ · x)

(ассоциативность),22

3. (λ + µ) · x = λ · x + µ · x, 4. λ · (x + y) = λ · x + µ · x

(дистрибутивные законы).

для любых λ, µ ∈ K, x, y ∈ L. Линейное пространство L элементов L над полем K можно определить как АС L = h L, +, {fλ (x)}λ∈K , 0 i . Это пример АС бесконечного типа. В то же время ясно, что L можно мыслить как двухосновную алгебру с носителями L и K конечного типа. Более формально, в качестве носителя в многоосновных системах выступают наборы множеств A = (Ai )i∈S , где Ai — множества, называемых иногда доменами, а S — множество сортов доменов. Будем называть такие наборы множеств комплектами. Заметим, что комплект множеств множеством не является. При фиксированном множестве S будем говорить о S-комплектах. Для S-комплекта покомпонентно (“посортно”) определяются понятие подкомплекта. Покомпонентно определяются декартово произведение, а также образ и прообраз при рассмотрении отображений ϕ : A → B S − комплектов A и B. Также покомпонентно определяется умножение отображений. Ядром рассмотренного отображения ϕ будет являться набор φ = (ϕi )i∈S ядер отображений ϕi : Ai → Bi . Набор эквивалентностей ² = (∼i )i∈S комплекта A = (Ai )i∈S определяет факторdef комплект A/² = (Ai /∼i )i∈S . Ясно, что при этом для комплектов оказывается справедливым аналог теоремы 1.20 об основном свойстве отображений. При определении многосортных алгебраических систем аналогом понятия арности операции или отношения служит их тип. Тип многосортной операции f есть кортеж элементов множества сортов S вида t = (s1 , . . . , sn ; s0 ). Операция f вышеуказанного типа t на комплекте A = (Ai )i∈S — это отображение f : As1 × . . . × Asn → As0 . Тип нульарной операции, выделяющая элемент во множестве As0 , есть t = (s0 ). Тип многосортного отношения r есть кортеж элементов множества сортов S вида t = (s1 , . . . , sm ). Отношение r вышеуказанного типа t на комплекте A = (Ai )i∈S — это отображение r : As1 × . . . × Asn → {1, 0} . Для данного комплекта A = (Ai )i∈S совокупности Op A и Rel A есть объединение непересекающихся совокупностей операций Op t A и Rel t A типов t. На многосортные алгебраических системы переносятся понятия согласованности отображений систем, с операциями и отношениями (аналог определения 3.4), фактор-систем и гомоморфизмов различных видов (аналог определения 3.5). При этом оказываются верны аналоги теорем о гомоморфизме и изоморфизмах систем, а также теорема Биркгофа 3.5.

22

Строго говоря, данный закон не есть закон ассоциативности, поскольку операции умножения поля и · различны.

82

Список литературы

1. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. — М.: Наука, 1997. 2. Биркгоф Г. Теория решёток. — М.: Наука, 1984. 3. Биркгоф Г., Барти Т. Современная прикладная алгебра. — М.: Мир, 1976. 4. Гретцер Г. Общая теория решёток. — М.: Мир, 1982. 5. Гуров С.И. Элементы теории упорядоченных множеств и универсальной алгебры: Учебное пособие. — М.: Издательский отдел ф-та ВМиК МГУ, 2002. 6. Кук Д., Бейз Г. Компьютерная математика. — М.: Наука, 1990. 7. Кон П. Универсальная алгебра. — М.: Мир, 1968. 8. Курош А.Г. Общая алгебра (лекции 1969–1970 учебного года). — М.: Наука, 1974. 9. Лидл Р., Пильц Г. Прикладная абстрактная алгебра: Учебное пособие. — Екатеринбург: Изд.-во Урал. ун.-та, 1996. 10. Мальцев А.И. Алгебраические системы. — М.: Наука, 1970. 11. Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. — М.: Наука, 1991. 12. Салий В.Н. Решётки с единственными дополнениями. — М.: Наука, 1984. 13. Скорняков Л.А. Элементы теории структур. — М.: Наука, 1970. 14. Скорняков Л.А. Элементы общей алгебры. — М.: Наука, 1983. 15. Стенли Р. Перечислительная комбинаторика. — М.: Мир, 1990. 16. Яглом И.М. Булева структура и её модели. — М.: Сов. радио, 1980.

83