Глава I. Множества.

1.1. Определения и обозначения.

Множество – это собрание определённых и различимых между собой объектов, мыслимых как единое целое. Объекты, называемые элементами множества, могут иметь физическую природу (яблоки, песчинки, люди, звёзды) или быть продуктом нашего интеллекта (числа, фигуры, буквы).

Множества обозначаются большими латинскими буквами А, В, С, ... , а их элементы – малыми буквами, обычно одноимёнными. Запись А={a₁,...,a_n} означает, что множество А состоит из элементов a₁,...,a_n. Запись aА означает, что элемент a принадлежит множеству А. Множество, не содержащее ни одного элемента, называется пустым и обозначается  . Запись ВА означает, что множество В является подмножеством множества А, т. е. каждый элемент множества В является элементом множества А. Само множество А и  называются несобственными подмножествами множества А, все остальные подмножества – собственные.

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

Множество, состоящее из элементов, входящих хотя бы в одно из множеств А или В, называются объединением множеств А и В и обозначается А В.

Множество, состоящее из элементов, входящих в оба множества А и В, называются пересечением множеств А и В и обозначается А  В.

Множество, состоящее из элементов, входящих в А, но не входящих в В, называется разностью множеств А и В и обозначается А\В.

Если имеется некоторое универсальное множеств V такое, что все рассматриваемые множества являются его подмножествами, то может быть введена операция дополнения

Операции над множествами могут быть наглядно представлены с помощью диаграмм Эйлера-Венна:

V

ФА

V

V

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

Операции производимые над подмножествами некоторого множестваV, обладают следующими свойствами:

1. A A=A, AA=A -идемпотентность

2. AB=BA, AB=BA -коммутативность

3. (AB) C=A (B C),

(AB) C=A(BC) -ассоциативность

4. A(AB)=A, A (AB)=A -поглощение

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

A(BC)=(AB)  (AC) -дистрибутивность

6. A=, A= A=A -закон нуля

7. A =V, AV=V, AV=A -закон единицы

8. -правило де Моргана

9. =A -инволютивность.

Заметим, что система свойств не изменяется, если одновременно поменять местами операции  и  и множества  и V. Это есть проявление так называемого принципа двойственности.

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

Отметим, что, если - конечноеn – элементное множество, то любое его подмножество может быть задано с помощью двоичного набора .

При этом означает, чтоНаборназывается характеристическим вектором множестваА.

1.4. Мощность множества.

Мощность конечного множества – это число его элементов, обозначается . Если, то. Бесконечные множества считаются равномощными, если между их элементами может быть установлено взаимно однозначное соответствие. Определенная таким образом мощность называется также кардинальным числом. Если элементы множества могут быть поставлены во взаимно однозначное соответствие с членами натурального ряда, то говорят, что оно счетно. Множество рациональных чисел счетно.

Для бесконечных множеств мощности множества и его собственного подмножества могут совпадать, что в определенной степени нарушает привычные представления. Так множество натуральных чисел {1,2,3, ...} и множество квадратов натуральных чисел {1,4,9,...} имеют одинаковую мощность. Оба они счетны, что доказывается установлением между их элементами взаимно однозначного соответствия по правилу , но второе из множеств является подмножеством первого.

Множество действительных чисел не может быть поставлено во взаимно однозначное соответствие с натуральным рядом, поэтому оно имеет большую мощность, которая называется континуум. Множество действительных чисел, принадлежащих отрезку [a;b] или интервалу (a;b) при a<b также имеет мощность континуум.

Докажем, что множество действительных чисел из интервала (0;1) не является счетным, с помощью диагонального метода Кантора. Допустим противное, что это множество счетное. Тогда все числа из (0;1)могут быть выписаны в виде последовательности . Каждое из этих чисел можно представить в виде бесконечной десятичной дроби

Выпишем теперь число , руководствуясь следующим правилом:b₁ - любая десятичная цифра, не равная a₁₁; b₂- любая цифра, не равная a₂₂; b₃ - не равная a₃₃ и т.д. Тогда , но числаb нет в выписанной последовательности. Полученное противоречие и доказывает несчетность множества действительных чисел из интервала (0;1)