Понятие множества
Под множеством S будем понимать любое собрание определенных и различимых между собой объектов мыслимое как единое целое. Эти объекты называются элементами множества S.
∈ - обозначает отношение принадлежности. Запись x ∈ S означает, что элемент x принадлежит множеству S.
Множества А и В считаются равными, если они состоят из одних и тех же элементов. Записывают А = В, если А и В равны, а А ≠ В - в противном случае.
Понятие формы
Под формой от х будем понимать конечную последовательность, состоящую из слов и символа х, такую, что если каждое вхождение х в эту последовательность заменить одним и тем же именем некоторого предмета соответствующего рода, то в результате получится истинное или ложное предложение.
Любая форма Р(х) определяет некоторое множество А, а именно множество тех и только тех предметов а, для которых Р(а) - истинное предложение.
А = {х|Р(х)} {х|х - четное число}
Парадокс Бертрана Рассела
Назовем множество "обычным" в том случае, если оно не является элементов самого себя ("расселовское" - множество всех обычных множеств).
"Необычным" множеством, в свою очередь, назовем такое множество, которое само является собственным элементом.
- Пусть "расселовское" множество - обычное. если оно обычное, то должно включать себя в качестве элемента, ведь по определению оно состоит из всех "обычных" множеств. но в то же время, оно не может быть "обычным", т.к. включает самого себя.
- Пусть "расселовское" множество - необычное. Теперь оно не может включать себя в качестве элемента, ведь по определению оно состоит только из обычны множеств. Но если так, и оно не включает себя, оно само должно быть "необычным".
Операции над множествами
Множеством U называется универсальным, если все рассматриваемые входе данного рассуждения множества являются подмножествами некоторого множества U.
Объединением множества А и В называется множество A∪В, все элементы которого являются элементами множеств А или В: А∪В = {x|x ∈ A или x ∈ В}.
Пересечением множеств А и В называется множество A ⋂ B, элементы которого являются элементами обоих множеств А и В: A ⋂ B = {x|x ∈ A и x ∈ В}.
Следствие: A ⋂ B ⊆ A ⊆ A ∪ B и А ⋂ B ⊆ В ⊆ A ∪ B
Относительным дополнением (разностью Х и А) множества А до множества Х называется множество Х\А всех тех элементов множества Х, которые не принадлежат множеству А: Х\А = {x|x ∈ Х и x ∉ А}
Симметрической разность множества А и В называется множество А + В = (А\В)∪(В\А).
Абсолютным дополнение множества А называется множество Ǡ всех тех элементов х, которые не принадлежат множеству А: Ǡ = U\A.
Основные тождества алгебры множеств
Для любых подмножеств А, В и С универсального множества U выполняются следующие тождества:
- А ∪ В = В ∪ А; A ⋂ B = В ⋂ А (коммутативность);
- А ∪ (В ∪ С) = (А ∪ В) ∪ С; А ⋂ (В ⋂ С) = (А ⋂ В) ⋂ С (ассоциативность);
- А ∪ (В ⋂ С) = (А ∪ В) ⋂ (А ∪ С); А ⋂ (В ∪ С) = (А ⋂ В) ∪ (А ⋂ С) (дистрибутивность);
- А ∪ ∅ = А; А ⋂ U = А;
- А ∪ A = U; А ⋂ Ǡ = ∅;
- А ∪ А = А; А ⋂ А = А;
- А ∪ U = U; А ⋂ ∅ = ∅
- А ∪ В = А ⋂ В; А ⋂ В = А ∪ В (закон де Моргана);
- А ∪ (А ⋂ В) = А; А ⋂ (А ∪ В) = А; (закон поглощения).
Упорядоченные пары
Упорядоченная пара <x, y> интуитивно определяется как совокупность, состоящая из двух элементов х и y, расположенных в определенном порядке. Две пары <x, y> и <u, v> считаются равными тогда и только тогда, когда x = u, y = v.
Упорядоченная n-ка (кортеж) элементов х1,х2,...,хn обозначается <x1,x2,...,xn> и, по определению, есть <<x1,x2,....xn-1>,xn>.
Элементы x1,x2,....xn называются компонентами или координатами n-ки.
Прямым (Декартовым) произведением множеств Х и Y называется совокупность всех упорядоченных пар <x, y> таких, что х ∈ Х и у ∈ Y. Обозначается такое произведение множеств X x Y.
Пример
Пусть Х = {1,2,3}, Y = {0,1}
Тогда
X x Y = {<1,0>, <1,1>, <2,0>, <2,1>,<3,0>,<3,1>}
Y x X= {<0,1>, <0,2>, <0,3>, <1,1>, <1,2>, <1,3>}
