АЛГЕБРА МНОЖЕСТВ

— раздел множеств теории, изучающий операции над подмножествами (частями) заданного множества и поведение этих операций при отображениях множеств. А. м. применяется в теор. кибернетике и в технике. Идеи А. м. высказал Дж. Буль в 1847 г. Одновременно он дал первую формулировку современной (символической, или математической) логики.

Пусть Е — мн-во, фиксируемое при построении А. м. и называемое универсальным мн-вом. Рассмотрим все возможные подмножества Е: А, В, С, ..., включая все мн-ва Е и пустое мн-во 0. Если Е конечно и состоит из элементов, то число таких частей равно Для частей Е вводим операции объединения: , пересечения В и дополнения . Тем самым мн-во всех частей Е превращается в алгебр, систему. Пусть Е, F — два универсальных мн-ва и отображение. Тогда для любых имеем

В этом смысле любое отображение сохраняет структуру А. м. Соотношение верно для всех но в общем случае лишь если инъективно, то . Если биективно, имеем также . Для любого семейства справедливы соотношения

а также, в случае биективности соответствующие соотношения для . Эти соотношения можно отнести к А. м. лишь в случае конечного множества I, т. к. операции над бесконечным числом мн-в не принадлежат А. м. Однако такие операции важны в теории меры. Легко проверить, что введенные операции

обладают следующими свойствами:

Проверка состоит в том, что берут произвольный элемент левой части и доказывают, что он принадлежит и правой части, и наоборот. Можно провести аналогию (неполную) между перечисленными свойствами и свойствами сложения и умножения чисел: операции аналогичны сложению и умножению, (1) и (1) суть аналоги ассоциативных, (2) и (2) — коммутативных законов сложения и умножения, (3) — аналог дистрибутивного закона; 0 в (4) соответствует нулю, Е в (4) — единице. Не имеют аналогов операция С и, следовательно, а также «второй дистрибутивный закон» операции вполне равноправны (в отличие от операций в арифметике). С алгебр, стороны являются бинарными операциями на мн-ве всех подмножеств Е. Но несмотря на указанные выше аналогии с арифметикой, мн-во с любой из этих операций но составляет группа, поскольку и, следовательно, в А. м. не существует однозначно определенных обратных элементов для У и П (для U существует единичный элемент для П — единичный элемент Е). Если а (Е), а (F) — А. м. над универсальными мн-вами Е, F, то любое отображение определяет обратный гомоморфизм а (Е), сопоставляющий каждому подмножеству A a F, рассматриваемому как элемент а (F), подмножество с Е, рассматриваемое как элемент . При этом для тождественного отображения имеем гомоморфизм а (Е) на себя) и соотношение означает, что если то из следует Как и в арифметике законы (1), (2), (3) могут быть обобщены на любое число мн-в:

(общий ассоциативный закон, существует аналогичный закон и для пересечения);

для любой перестановки чисел (общий коммутативный закон, существует аналогичный закон и для пересечения);

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

Симметрия операций приводит к следующему принципу двойственности: пусть справедливо некоторое соотношение между подмножествами записанное с помощью знаков Тогда справедливо и «двойственное» соотношение, полученное из данного соотношения путем замены этих знаков, соответственно, на символа пустого мн-ва 0 на на 0, причем символы мн-в общего вида не меняются. В применении к соотношениям (1) — (5) принцип двойственности дает (1) — (5) и наоборот. Доказывают принцип по индукции, опираясь на проверяемые непосредственно. Примеры двойственных соотношений:

Законы (11), (11) обобщаются на любое число

(дополнение объединения равно пересечению дополнений, и наоборот). Следующие соотношения «самодвойственны», т. е. переходят сами в себя по принципу двойственности:

Заметим еще, что для утверждения равносильны друг другу. Операция разности в А. м. сводится к основным: . В некоторых случаях требуется ввести симметрическую разность (или дизъюнктивную

сумму) (общепринятого обозначения не существует). Эта операция обладает свойствами . (коммутативность),

Логическое истолкование А. м. Об элементах х мн-ва Е можно делать высказывания, истинные или ложные (см. Исчисление высказываний). Каждое высказывание может быть приведено к виду: х обладает свойством а. Пусть — мн-во всех элементов Е, обладающих этим свойством; тогда предыдущее высказывание равносильно высказыванию: . Тем самым устанавливается взаимно однозначное соответствие между высказываниями об элементах Е и подмножествами ; пусть высказывание, соответствующее А. Высказывания соединяются связками V («или»), перед высказыванием ставят знак отрицания Высказывание означает: , а это равносильно или (не исключая случая, когда . То же записывается в виде дизъюнкции Аналогично проверяют остальные тождества:

Следовательно, осн. операции А. м. эквивалентным образом описывают на языке логики. Заметим еще, что тождественно (для всех ) истинное высказывание, ложное, а включение А с В равносильно где связка «следует». И наоборот, исчисление высказываний исходит из некоторого мн-ва «элементарных высказываний» из которых все остальные высказывания получаются применением операций Пусть набор значений соответствующих высказываний где каждое значение есть или символ «истина» или символ «ложь». Такие всевозможные наборы составляют мн-во Е. Тогда любое «сложное» высказывание построенное из истинно для некоторого подмножества наборов и, следовательно, приводится к виду: в общем смысле состоит из некоторого семейства (не обязательно всех) частей Е, устойчивого относительно операций , т. е. такого, что если то Такие А. м. важны в ряде случаев, когда надо выделить подмножества или спец. вида, или обладающие «хорошими» свойствами, обеспечивающими возможность дальнейших построений. Рассмотрим, напр., на действительной оси R полуинтервалы открытые справа. Возьмем в качестве Е конечный замкнутый интервал. Тогда мн-ва вида (о любым к) представляют собой объединения конечного числа непересекающихся отрезков, лежащих в Е (правый из них может быть замкнут справа). Такие мн-ва образуют А. в общем смысле; обозначим Аналогичные А. м. можно построить в евклидовых пространствах любой размерности с помощью полуинтервалов

Проблема меры и -алгебры. Пусть Е конечно и — число элементов А. Тогда при Мерой на А. ф-цию с действительными значениями, определенную на мн-ве элементов алгебры и обладающую теми же свойствами. Для бесконечного Е введение меры наталкивается на трудности, связанные с «патологическими» свойствами бесконечных подмножеств (наиболее важен случай, когда или Е есть мн-во в ). Для преодоления этих трудностей рассматривают «суженные» А. например, ЗЛ (Е). За принимают сумму длин отрезков, составляющих Однако полученная А. м. с мерой для большинства целей слишком узка; ее расширяют до большей содержащей всех подмножеств Е, но «достаточно богатой» множествами (напр., до алгебры всех подмножеств измеримых по Борелю или по Лебегу). расширенные А. м. содержат уже все мн-ва, встречающиеся анализе и математики. Они обладают и важными дополнительными свойствами: если то с этими свойствами наз. а-алгебрами множеств. Мера, определенная на исходной распространяется на 21, причем получается вполне аддитивная мера: если то

Вероятностное истолкование. Случайно выбранная точка может с некоторой вероятностью Р (А) принадлежать мн-ву на стол бросают шарик, останавливающийся в какой-то части стола или вне ее). Из теоремы сложения вероятностей следует, что при т. к. события «же А» и в этом случае несовместимы. При этом множества должны быть «достаточно хорошими», чтобы соответствующие вероятности имели смысл. В ряде случаев удается определить А. м. на частей на которой обладает свойствами меры (даже вполне аддитивной). Такая вероятностная мера, кроме того, обладает свойством т. к. достоверному событию («попадание в Е») приписывается вероятность 1.

Связь с булевыми алгебра-м и. Если отвлечься от содержательного смысла символов мн-в и операций . представляет собой абстрактную алгебр, систему, подчиненную аксиомам (1) - (5), (1) - (5). Такую систему наз. булевой алгеброй. Все соотношения А. м. могут быть формально выведены из этих аксиом (при этом ассоциативные законы (1), (1) можно удалить из списка аксиом, т. к. они следуют из остальных аксиом). Формальный вывод соотношений, без т. н. интерпретаций, имеет, напр., то преимущество, что его выполняет машина.

И. И. Жегалкин предложил модификацию булевой алгебры, в которой вместо операции объединения используется операция сложения по модулю 2 (см. Жегалкина алгебра). В различных приложениях встречаются и другие модификации. С развитием А. м. значительная часть комбинаторики (теории конечных множеств) стала развиваться в рамках А. м. и ее начали рассматривать в более широком смысле — как алгебру, включающую, наряду с булевыми операциями или операциями, которые могут быть выражены через булевы, новые операции над мн-вами подмножеств и над отношениями (напр., операции проектирования, декартова произведения, «среза» и др.). В связи с этим были разработаны цилиндрические и полиадические алгебры, а также алгебры отношений. Эти направления в последнее время интенсивно развиваются, удовлетворяя запросы теор. кибернетики (теория автоматов, матем. лингвистика, кодирование, дискретный анализ и др.).

Лит.: Александров П. С. Введение в теорию множеств и теорию функций, ч. 1. М.- Л., 1948; Халмош П. Р. Теория меры. Пер. с англ. М., 1953 [библиогр. с. 283—285]; Столл P. P. Множества. Логика. Аксиоматические теории. Пер. с англ. М., 1968. А. В. Гладкий.