Элементы теории множеств

§1. Множества и их спецификация (способы задания)

Понятие множества - одно из основных понятий математики. Вообще говоря, это неопределяемое понятие, такое как точка или прямая в геометрии, как число в арифметике.

Ввел это понятие немецкий математик Георг Кантор(1849-1918). Он определил его так: множество есть многое мыслимое как единое целое.

Множество — это совокупность определенных различаемых объектов, собранных по какому-либо общему признаку. Объекты, из которых составлено множество, называются элементами множества.

Утверждения типа ”объект а есть элемент множества А” и “объект а принадлежит множеству А”, которые имеют один и тот же смысл, записывают а_А, а если объект а не является элементом множества А, то пишут а_А.

Единственным требованием к признаку, по которому составляется множество — это чтобы для любого объекта можно было сказать, принадлежит он множеству или нет.

Множество, которое подчиняется лишь такому требованию, может содержать элементы любой природы:

· множество зарезервированных слов языка Паскаль;

· множество натуральных чисел;

· множество символов, доступных данному компьютеру;

· множество левых ботинок.

Множества будем обозначать прописными буквами А, В, С,..., а элементы строчными а, b, с,...

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

Одно и то же множество можно описать по-разному, например:

1) множество всех четных натуральных чисел;

2) множество всех чисел вида 2n, где n - натуральное.

Как видим, эти два описания определяют одно и то же множество.

Поэтому нужно ответить на вопрос: когда два описания определяют одно и то же множество?

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

1. перечислить все его элементы: А={1, 2, 3, 4, 5}, B={begin, end, if, then, do, for, while, repeat, until,...}

2. записать признак, определяющий его элементы в виде высказывательной формы, то есть в виде {x| P(x) истинно}, где Р(х)— высказывательная форма или проще {x| P(x)} читается: множество состоит из таких элементов х, что истинно Р(х)(то есть множество определяется как множество истинности некоторой высказывательной формы).

Пример: А={a| a_ N)a< 6}, B={x| x-зарезервированное слово языка Паскаль}.

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

Приведем некоторые примеры.

Учитывая определение равенства множеств: {7, 8, 9} = {8, 9, 7} = {9, 8, 7} = ={7, 8, 9, 8, 9}, поскольку элемент каждого из выписанных здесь множеств является элементом другого. Однако если три первые спецификации можно как-то объяснить (например, требование какой-то задачи), то последнюю спецификацию следует считать неудачной, поскольку не все элементы можно отличить друг от друга.

Рассмотрим множество X={“Введение в Паскаль”, ”Основы структурных данных”, ”Введение в Паскаль”}. Что это: множество, состоящее из двух книг, записанных по невнимательности дважды, или это три книги, две из которых имеют одинаковое название? В последнем случае две книги “Введение в Паскаль” надо как-то разделить. Из данной информации нельзя извлечь правильный ответ. Поэтому со спецификациями надо быть осторожнее.

Элементами множества могут быть опять же множества:

А={1, {2, 3}} — множество, состоящее из двух элементов, а множество В={1, 2, 3} — из трех. C={{3, 5}, {5, 7}, {7, 9}} — оно состоит из трех элементов. D={3, 5, 7, 9} — из четырех. Конечно, С_D и A_B.

Задача 1: О писать словами рекурсивно заданное множество

X={x|x_ Z)(x=1*(x-2) _X)}.

Определение 1: Два множества А и В называют равными и пишут А=В, если А и В содержат одни и те же элементы.

Формально: два множества А и В равны, если " x (x_A + x_B).

Определение 2: Множество А называется подмножеством множества В, если каждый элемент множества А принадлежит множеству В (" х(х_А.х_В)).

Это записывают так: А_В, читаем: А содержится в В. Например: 3_{3, 5, 7}, {3}_{3, 5, 7}, аналогично {3, 7}_{3, 5, 7}. А вот для множества {1; {2, 3}} можно записать: {2, 3}_{1; {2, 3}}; 2_{1; {2, 3}}. Чтобы заработал знак включения надо записать элемент {2, 3} как множество, то есть {{2, 3}}_{1; {2, 3}}.

Другие примеры: 1. Q _ R. 2. Z _ Q, 3. N _ R, 4. A={x|0_x< 4) x_ R }, B={y|1_y< 3) y_ R }, тогда B_A.

Определение 3: Множество А называется собственным подмножеством множества В, если А _ В и А_В. В случае, если надо подчеркнуть, что А _ В или А=В будем писать А_ В.

Например, можно записать А_А, на самом деле будем использовать символ _, то есть А_А — почему?

Задача 2: Д оказать, что если А _В и В_С, то А_С.

По определению подмножества, если А_В и В_А, то А=В (объясните, почему).

Таким образом, чтобы доказать равенство двух множеств А и В надо доказать, что 1) А_В и 2) В_А. Фактически это означает, что любой элемент множества А является элементом множества В и любой элемент множества В является элементом множества А, что соответствует определению равенства двух множеств.

И в заключение введем еще два важных понятия.

Определение 4: Множество, не содержащее ни одного элемента, называется пустым множеством. Пустое множество обозначается символом Æ.

Формализуя: множество А пусто, если " x (x_A)— истинно.

Утверждение 1: Пустое множество единственно.

Доказательство:

Пусть C и D— пустые множества, тогда высказывание " x (x_С+x_D) истинно, поскольку x_С и x_D оба ложны. А по определению 1 это и означает, что С = D. Что и требовалось доказать.

Утверждение 2: Пустое множество является подмножеством любого множества.

Доказательство:

Действительно, для каждого x импликация x__.x_A истинна, так как посылка x__ ложна. Что и требовалось доказать.

Определение 5: Множество всех подмножеств множества X назовем степенью множества Х и будем обозначать Р ( X ).

Например, если X={1, 2, 3}, то P (X) ={ _, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, X}.