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

Алгебра — это множество объектов с определенными на нем операциями, отвечающими некоторым свойствам. Обычно абстрактная алгебра задается как двойка A = < М, Σ >, где М — множество объектов алгебры (носитель алгебры), Σ — множество операций (сигнатура алгебры). Множество операций описывается своими свойствами, которые задаются системой аксиом данной алгебры. Мы будем рассматривать алгебру подмножеств некоторого универсального множества U. Для краткости в дальнейшем будем называть ее просто алгеброй множеств.

Определим алгебру множеств как четверку: < M, ∪, ∩, ′ >, где M — множество-степень универсального множества U, а множество операций состоит из операций объединения (∪), пересечения (∩) и дополнения (′) множества до множества U. В содержательной теории множеств с помощью отношения принадлежности элементов множеству можно доказать следующую теорему.

Теорема 1. Для любых подмножеств A, B и C некоторого универсума U следующие равенства являются тождествами:

1) A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C (ассоциативность);

2) A ∪ B = B ∪ A, A ∩ B = B ∩ A (коммутативность);

3) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)(дистрибутивность);

4) A ∪ ∅ = A, A ∩ U = A;

5) A ∪ A′ = U, A ∩ A′ = ∅.

Из этих тождеств, принятых как аксиомы, может быть выведена любая теорема алгебры множеств без использования понятия принадлежности. Из приведенных выше десяти тождеств видно, что каждое правое тождество получено из левого заменой символа ∪ на ∩ и наоборот, а также заменой ∅ на U и наоборот.

Равенство, полученное из исходного заменой всех символов U на ∅, ∅ на U, ∪ на ∩, ∩ на ∪, называется двойственным исходному. В приведенном выше списке тождеств 1—5 каждое тождество имеет двойственное ему тождество. Таким образом, мы приходим к принципу двойственности: для любой теоремы алгебры множеств двойственное ей утверждение также является теоремой.

Теорема 2. Для произвольных подмножеств A и B некоторого универсального множества U справедливы следующие утверждения:

6) если для всякого A A ∪ B = A, то B = ∅, если для всякого A A ∩ B = A, то B = U;

7) если A ∪ B = U и A ∩ B = ∅, то B = A′;

8) A′ ′ = A,

9) ∅ ′ = U, U′ = ∅;

10) A ∪ A = A, A ∩ A = A (законы идемпотентности);

11) A ∪ U = U, A ∩ ∅ = ∅;

12) A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A (законы поглощения);

13) (A ∪ B)′ = A′ ∩ B′, (A ∩ B)′ = A′ ∪ B′ (законы де Моргана)

Докажем некоторые утверждения, используя только тождества 1—5.

Утверждение 6. Доказательство. Поскольку по условию A ∪ B = A для всех A, то это верно и для A = ∅, т.е. ∅ ∪ B = ∅. Тогда из 2) следует: ∅ ∪ B = B ∪ ∅, т.е. B ∪ ∅ = ∅. С другой стороны, согласно 4), B ∪ ∅ = B. Отсюда следует, что B = ∅.

Утверждение 7. Доказательство (в скобках указаны номера применяемых аксиом и утверждений). B = (4) = B ∪ ∅ = (5) = B ∪ (A ∩ A′) = (3) = (B ∪ A) ∩ (B ∪ A′) = = (2) = (A ∪ B) ∩ (B ∪ A′) = (по усл.) = U ∩ (B ∪ A′) = (5) = = (A ∪ A′) ∩ (B ∪ A′) = (2) = (A′ ∪ A) ∩ (A′ ∪ B) = (3) = = A′ ∪ (A ∩ B) = (по усл.) = A′ ∪ ∅ = (4) = A′. Доказательство утверждения 8 следует из утверждения 7: аксиомы 5 можно переписать в виде: A′ ∪ A = U, A ∩ A′ = ∅ в силу коммутативности операций ∪ и ∩ (аксиомы 2). Тогда, по утверждению 7, A = A′ ′.

Доказательство остальных утверждений самостоятельно!