Теория множеств

Введение
Дискретная математика представляет собой область математики, в которой изучаются свойства структур конечного характера, а также бесконечных структур, предполагающих скачкообразность происходящих в них процессов или отделимость составляющих их элементов. В отличие от дискретной математики классическая математика занимается изучением свойств структур непрерывного характера. Это деление достаточно условно, поскольку средства дискретной математики используются для изучения непрерывных моделей и наоборот.
Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, которые по своей природе являются структурами конечными.
В предлагаемом вниманию обучающихся пособии представлен теоретический материал, сопровождаемый примерами и пояснениями. Значком  в тексте обозначены замечания.
Глава 1 Элементы теории множеств

1. 
   Множества и их спецификация
   
   1. 
      Элементы и множества
      

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

1. 
   Можно рассматривать множества объектов любой природы: множество городов России, множество студенческих групп на факультете ИВТ, множество букв русского языка, множество натуральных чисел…
   

Сами объекты, из которых состоит множество, называются его элементами. Все элементы множества различны и отличимы друг от друга.

• 
  Множества обычно обозначают прописными буквами (А, В, С и т.д.), а их элементы – строчными (например: x, y, z).
  

Если элемент x принадлежит множеству А, то пишут x  A. Запись x  A означает, что элемент x не принадлежит множеству А.
Множества, как объекты, могут быть элементами других множеств. Множество, элементами которого являются другие множества, обычно называется семейством, или классом множеств.

• 
  Обычно семейства множеств обозначают рукописными буквами латинского алфавита для отличия их от обычных множеств.
  

Множество, не содержащее элементов, называется пустым множеством и обозначается символом .
Если все рассматриваемые множества (в конкретной задаче) являются подмножествами более широкого множества U, то множество U называется универсальным множеством, или универсумом.
Мощность множества M обозначается как |M| и для конечного множества равняется числу элементов в нем.

• 
  Заметим, что || = 0, но |{}| = 1.
  

Для числовых множеств здесь и далее будем использовать следующие обозначения: N – множество натуральных чисел, Z – множество целых чисел, R – множество действительных чисел, P – множество простых чисел, Q – множество рациональных чисел.

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

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)}.
   

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

3. 
   Контрольные вопросы
   

1. 
   Что такое множество? Могут ли в составе множества быть одинаковые элементы?
   
2. 
   Являются ли множествами следующие наборы: {a, b, c, d}? {Обь, Иртыш, Енисей, Лена}? {1, 2, 5, 1, 3, 2, 3}?
   
3. 
   Что такое семейство (или класс) множеств? Что является элементом класса множеств?
   
4. 
   Что такое пустое множество – ?
   
5. 
   Что будет являться универсумом для следующих трех множеств: {1, 3, 5, 7}, {2, 4, 6}, {8, 9, 10}?
   
6. 
   Что такое мощность множества? Чему равна ||? А |{}| ?
   
7. 
   Какое множество обозначают через R? А через N?
   
8. 
   Какие способы задания множеств Вы знаете?
   
9. 
   Какой способ использован при задании множества A = {y  Z | y < 10}? Что здесь является характеристическим предикатом?
   
10. 
    Что такое порождающая процедура?
    
11. 
    Какие способы использованы при задании множеств A, B, C, D, если A = {1, 2, 3, 4}, B = {x  Z | x = 3 или x = 3·x}, C = {A, B}, D={x | x = 2·y | y = 1, 2, 3, 4, 5}?
    

2. 
   Операции над множествами
   
   1. 
      Сравнение множеств
      

Если каждый элемент множества А является элементом множества В, то пишут А  В (А является подмножеством множества В). Считается, что   А для любого множества А.
Подмножество C множества B называется его собственным подмножеством, если C  В, но C  В. Обычно для обозначения этого факта используется символ : C  В.
Два множества равны, если они состоят из одних и тех же элементов. Равенство множеств обозначается как А = В. Если множества не равны, то пишут А  В.
Множество А равно множеству В, если А  В и В  А.
Для числовых множеств выполняется N  Z  R.

3. 
   Рассмотрим множества из примера 1.2: А = {2, 4, 6}; B = {1, 3, 5}; C = {A, B}. Очевидно, что А  C, но тем не менее А  C, поскольку ни один из элементов А не является элементом C (т.е. множество А является элементом множества C, но А не является подмножеством множества C.
   

Если |А| = |В|, то такие множества называются равномощными.

2. 
   Операции над множествами. Диаграммы Венна
   

Обычно рассматриваются следующие операции над множествами: