Операции над множествами

С такими операциями мы уже фактически имели дело, но они всегда были выражены через операции над парами множеств. Сейчас мы дадим общее определение. Задать операцию над множествами — это значит задать закон построения по набору из любых множеств однозначно определенного множества , причем вопрос о вхождении некоторого элемента в полностью определяется тем, в какие из множеств этот элемент входит, а в какие — нет.

Рис. 13

Положим при и при . Заметим, что множество состоит из всех элементов, входящих в , если , и не входящих в , если . Операцию будем, как и при , называть долькой, отвечающей набору . Долек существует столько, сколько существует двоичных видите разбиение на дольки при .

Из определения операции следует, что каждая операция является объединением некоторого числа долек. Для задания операции каждой дольке, закодированной двоичным набором , поставим в соответствие 1 или 0, смотря по тому, входит эта долька в или нет. В результате операции отвечает двоичный набор длины (столько имеется долек), а значит, существует различных операций над множествами. Поскольку во всех случаях является объединением долек, одновременно мы получаем, что каждая операция выражается через объединения, пересечения и дополнения. Другое представление мы получим, если рассмотрим довески — дополнения к долькам, они имеют вид . Всякая операция может быть представлена в виде пересечения довесков.

Итак, оказалось, что, во-первых, имеется конечное число операций над множествами, а, во-вторых, все эти операции могут быть выражены через операции над парами множеств — объединение, пересечение и дополнение. Этим и объясняется, что во многих вопросах теории множеств ограничиваются рассмотрением этих трех операций. Впрочем, учитывая (3), можно ограничиться двумя операциями: объединением и дополнением или пересечением и дополнением.

Существуют и другие возможности выбирать основные операции, через которые выражаются все остальные операции. Рассмотрим, например, операцию . Если взять в качестве и одно и то же множество , то мы получим . Проделав последовательно эти две операции, мы получим . Но через пересечение и дополнение можно выразить любую операцию. Значит, любую операцию можно выразить через единственную операцию . Проверьте, что и через операцию тоже можно выразить все операции. Эти две замечательные операции носят название операций Шеффера. Докажите, что в качестве систем основных операций можно выбрать , или , 0.