1.2 Задание множеств. Парадокс Рассела

Пример. Рассмотрим несколько множеств:

1) А = {2, 4, 6}; 2) B = {1, 3, 5}; 3) C = {A, B};

4) D = { x Î R | x>0}; 5) E = {2·y | y=1, 2, …, n};

6) F = {x | x=1 или x=2·y, yÎ F } {степени двойки: 1, 2, 2², 2³, 2⁴, …}

В первом и втором пунктах примера множества заданы путем перечисления их элементов. В третьем пункте – тоже, но здесь элементами множества C являются множества. Заметим, что множество C имеет только два элемента и, в частности, 1  C, хотя 1  A  и A  C . Действительно: 1 A и 1 B,  1  C, т.к. только A и B являются элементами C.

В 4-м примере множество D задано путем его описания, т.е. задания неких свойств его элементов.

Множества E, F строятся согласно указанному способу порождения множества, т.е. с помощью задания некой процедуры построения, причем множество F определяется через его же элементы. Правило задания F является рекурсивным.

Задание множества путем указания его свойств может приводить к противоречиям. Например, один из наиболее типичных теоретико-множественных парадоксов носит название парадокса Рассела и состоит в следующем. Рассмотрим множество всех множеств, которые не содержат себя в качестве элемента: F = {X | XX}. Спрашивается, является ли само множество F элементом F? Возможны только два случая:

1) F F. Тогда для него выполняется условие содержания элемента в множестве, т.е. F F.

2) F F. Тогда для F не выполняется условие содержания элемента в множестве, т.е. F содержит само себя: F F.

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

Потому будут рассматриваться только те множества, которые могут быть явно записаны или построены путем четко определенных процессов. Для каждого множества должна быть определена его спецификация. Итак, множества могут быть заданы тремя основными способами:

1. Перечислением элементов множества (множества A, B, C) {1,2,3}.

Этот способ применим только для конечных множеств.

2. Указанием свойств элементов множества, или заданием т.н. характеристического предиката: D = {x | P(x)} (Другими словами – задание разрешающей процедуры).

Здесь P(x) обозначает некоторое условие, выраженное в форме логического утверждения; это условие может быть проверено для любого элемента.

3. Порождающей процедурой: E = {y | y:=f(x)}.

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

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

Множество A называется подмножеством множества B, если любой элемент множества A принадлежит множеству B. При этом пишут AÌB, где "Ì" есть знак вложения подмножества. Из определения следует, что для любого множества A справедливы, как минимум, два вложения A Ì A и A Ì U.

Если A Ì B и A ≠ B, A ≠ Ø, то A называется собственным подмножеством множества B. В этом случае B содержит хотя бы один элемент, не принадлежащий A.

В теории множеств, по определению, полагают, что пустое множество является подмножеством любого множества:   A.

Пустое множество и само множество A называются несобственными подмножествами множества A.

При графическом изображении множеств удобно использовать диаграммы Эйлера–Вейна , на которых универсальное множество обычно представляют в виде прямоугольника, а остальные множества в виде овалов, заключенных внутри этого прямоугольника (рис 1.1).

Определение. Объединением множеств A и B (обозначение A B) называется множество элементов x таких, что x принадлежит хотя бы одному из двух множеств A или B (рис 1.2). Символически это можно записать следующим образом:

A B = {xx  A или     x  B}.

Определение. Пересечением множеств A и B (обозначение A B) называется множество, состоящее из элементов x, которые принадлежат и множеству A и множеству B (рис. 1.3):

A B = {xx  A и    x  B}.

Определение. Разностью множеств A и B называется множество всех тех элементов множества A, которые не принадлежат множеству B (рис. 1.4):

A\B = {xx  A  и    x  B}.

Определение. Симметрической разностью множеств A и B называется множество A B = ( A\B )( B\A ) (рис. 1.5).

Определение. Абсолютным дополнением множества A называется множество всех элементов, не принадлежащих A, т.е. множество A = U\A, где U - универсальное множество (рис. 1.6).

В дальнейшем вместо термина "абсолютное дополнение" мы будем употреблять термин "дополнение".

Пример. Если U = { a,  b,  c,  d,  e,  f,  g,  h }, A = {  c,  d,  e }, B = { a,  c,  e,  f,  h }, то

A B = { a ,  c,  d,  e,  f,  h },   A B = { c,  e },   A\B = {d},

A  B = { a,  d,  f,  h },    A   = { a,  b,  f,  g,  h }.

Свойства операций

Для любых множеств A,B,C выполняются следующие тождества:

A B = B A,   A B = B A

(коммутативность объединения и пересечения);

A ( B C ) = ( A B ) C,   A ( B C ) = ( A B ) C

(ассоциативность объединения и пересечения);

A ( B C ) = ( A B ) ( AC ),

A ( B C ) = ( A B ) ( AC )

(дистрибутивность;

A A = A,   A A = A

(идемпотентность;

A U = U,   A U = A,   A  = A,   A  = ,

A A = U,   A A = 

(свойства универсального и пустого множеств);

- A   = A

(закон двойного отрицания);

A B   = - A    - B   ,    A B   = - A    - B

(законы де Моргана).