Лекция 1 Множества и отношения. Логические связки 1 Множества

КУРС ЛЕКЦИЙ ПО МАТЕМАТИКЕ

ЭЛЕМЕНТЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

Лекция 1 Множества и отношения. Логические связки
1.1 Множества

Понятие множества является исходным не определяемым строго понятием. В математике понятие множество используется для описания совокупности объектов, отличающихся и друг от друга, и от объектов, не входящих в эту совокупность. Например, можно говорить о множестве всех вершин данного многоугольника, множестве всех натуральных чисел, множестве студентов некоторой группы и так далее. Множества обычно обозначаются большими буквами латинского алфавита а их элементы – малыми. Тот факт, что элемент a принадлежит множеству А, записывается в виде aА. Множество, не содержащее элементов, называется пустым, и его обозначают символом .

Обычно множество задается одним из двух способов:

перечислением (если число элементов достаточно невелико). Например, А = {1; 5; 7; 9}
указанием характеристического (коллективизирующего) свойства элементов множества, то есть свойства, которым обладают все элементы данного множества и только они. Чаще всего это свойство формулируется в виде высказывания. Например, множество точек плоскости, равноудаленных от двух данных точек

Замечание:

Не каждое высказывание выражает коллективизирующее свойство. Рассмотрим парадокс Рассела (парадокс брадобрея).

В некоторой деревне живет брадобрей, который по долгу службы должен брить тех и только тех, кто не бреет себя сам. Если брадобрей не будет себя брить, то тотчас окажется, что он должен себя брить (он должен брить всех, кто не бреет себя сам). Но если он будет себя брить, то он должен прекратить бриться ( брадобрей не бреет тех, кто бреется сам).

Запишем этот парадокс в формальном виде. Пусть Y – множество всех множеств, не являющихся элементами самого себя: Y = . Это множество Y не пусто. Действительно, такие множества X встречаются часто. Например, множество действительных чисел R не является действительным числом. Получаем противоречие. Если , то по определению Y . если же , то по определению Y .

Это противоречие показывает, что рассматриваемое высказывание не задает коллективизирующего свойства.
1.2 Логические операции (связки)

Для сокращения записи высказываний, задающих множество, будем пользоваться логической символикой. Под высказыванием понимают имеющее смысл языковое выражение, относительно которого можно утверждать, что оно истинно или ложно. Определим следующие логические операции (связки):

Дизъюнкция (логическая сумма): высказывание PQ (читается “P или Q”) истинно тогда и только тогда, когда истинно хотя бы одно из высказываний P или Q.
Конъюнкция (&) (логическое умножение): высказывание PQ (P&Q) (читается ”P и Q”) истинно тогда и только тогда, когда истинны оба высказывания P и Q .
Отрицание (): высказывание P () (читается “не P”) истинно тогда и только тогда, когда P ложно.
Импликация : высказывание PQ (читается “если P, то Q” или “P влечет Q”) истинно тогда и только тогда, когда истинно высказывание Q или оба высказывания ложны (PQ ложно только в том случае, когда P истинно, а Q ложно: “из истины не следует ложь” ).
Эквивалентность (равносильность) : высказывание PQ (читается “P равносильно Q”) истинно тогда и только тогда, когда оба высказывания P и Q либо одновременно истинны, либо одновременно ложны. Любые два высказывания P и Q, такие , что истинно PQ, называют логически эквивалентными или равносильными.

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

Рассмотрим множество всех высказываний. Введем на этом множестве операции сложения, умножения и дополнения, результаты которых также будут высказываниями. Тогда, как известно, множество высказываний будет алгеброй, которую называют алгеброй высказываний или булевой алгеброй в честь английского математика Джорджа Буля.
Замечание:

В 1854 году Джордж Буль публикует исследование «Законы мысли» (The Laws of Thought) в котором показывает, что законы формальной логики сами могут быть предметом исчисления. Эта алгебра логики (булева алгебра) – начало того направления, которое стремилось объединить логику и математику.
Каждому высказыванию можно приписать значение И (истина) или Л (ложь). Вместо этих символов будем применять числа 1 и 0 соответственно. Тогда операцию сложения высказываний введем как дизъюнкцию этих высказываний, операцию умножения – как конъюнкцию высказываний, операцию дополнения – как отрицание высказывания. Введенные связки проиллюстрируем таблицами истинности (таблицы 1.1 – 1.5).
Таблица 1.1 – Дизъюнкция (логическая сумма)

P	Q	PQ (P+Q)
0	0	0
0	1	1
1	0	1
1	1	1

Таблица 1.2 – Конъюнкция (логическое умножение)

P	Q	PQ (PQ)
0	0	0
0	1	0
1	0	0
1	1	1

Таблица 1.3 – Отрицание (логическое дополнение)

P	P
0	1
1	0

Таблица 1.4 – Импликация

P	Q	PQ
0	0	1
0	1	1
1	0	0
1	1	1

Таблица 1.5 – Эквивалентность

P	Q	PQ
0	0	1
0	1	0
1	0	0
1	1	1

Таблицы истинности можно применить для определения истинности или ложности входящих в него высказываний.

Пример: Составить таблицу истинности высказывания

Таблица 1.6

P	Q						A
0	0	1	0	1	0	0	1
0	1	1	1	0	0	1	0
1	0	0	0	1	1	1	1
1	1	0	0	0	0	0	1

Одна из основных целей изучения логики состоит в получении формального аппарата для доказательства того, является ли данное утверждение следствием других. Формула G называется логическим следствием формул F₁, F₂, …, F_k, если для любой интерпретации j из того, что j(F₁) = j(F₂) = … = j(F_k) = 1 следует, что j(G) =1.

Например, докажем, что формула G=YX не является логическим следствием формул F₁=X v Y, F₂=XY, F₃=Y. Для этого построим совместную таблицу истинности формул F₁, F₂, F₃ и G.

Таблица 1.7

X	Y	F₁=X v Y	F₂=XY	F₃=Y	G=YX
1	1	1	1	1	1
1	0	1	0	0	1
0	1	1	1	1	0
0	0	0	1	0	1

Мы видим (см. таблицу 1.7), что если взять интерпретацию j, для которой j(х) = 0, j(y) = 1, (т.е. взять третью строку таблицы), то j(F₁) =j(F₂) = j(F₃) = 1, но j(G) = 0. Следовательно, формула G не является логическим следствием формул F₁, F₂, F₃.

1.3 Предикаты

Предикат есть высказывание, содержащее одно или несколько переменных. Например, «х есть четное число», «х есть сын y», «x, y и z учатся в одной группе». Предикаты обозначаются P(x), Q(x, y), R(x, y, z). Подставляя вместо каждого переменного, входящего в предикат, конкретное значение, получаем истинное или ложное высказывание. Например, «4 есть четное число», «Иванов есть сын Петрова», «Ньютон, Эйнштейн и Вася Иванов учатся в одной группе».

Высказывание из предиката можно получить не только подстановкой значений его переменных, но и посредством кванторов. Вводят два квантора – существования ( ) и всеобщности (). Например, читается « для всех выполняется Р(х).
1.4 Операции над множествами

Для любых двух множеств А и В определены новые множества:

1.4.1 Объединение А и В есть множество, которое состоит из элементов, принадлежащих хотя бы одному из множеств А и В, то есть . Для пояснения некоторых свойств операций над множествами и различных соотношений между множествами можно использовать диаграммы Эйлера-Венна, на которых множества, подлежащие рассмотрению, изображаются в виде совокупности точек на плоскости. На рисунке 1.1 множество выделено штриховкой.

Рисунок 1.1 -

1.4.2 Пересечение А и В есть множество, которое состоит из элементов, принадлежащих каждому из множеств А и В, то есть . Множества А и В, имеющие пустое пересечение () называются дизъюнктными (непересекающимися). На рисунке 1.2 множество выделено штриховкой .

1.4.3 Разность множеств А и В есть множество, состоящее из таких элементов множества А, которые не принадлежат множеству В, то есть . На рисунке 1.3 множество A \ B выделено штриховкой.

Рисунок 1.2 -

Рисунок 1.3 – A \ B

1.4.4 Симметрическая разность множеств А и В представляет собой множество, состоящее из элементов, принадлежащих в точности одному из множеств А и В, то есть . На рисунке 1.4 множество АΔВ выделено штриховкой.

Рисунок 1.4 – АΔВ

1.4.5 Дополнение множества А – это множество всех элементов универсального множества U, не принадлежащих А, то есть . На рисунке 1.5 множество выделено штриховкой.

Рисунок 1.5 -
1.4.6 Говорят, что В есть подмножество А (имеет место включение ), если всякий элемент В есть элемент А.

Рисунок 1.6 -

Считают, что пустое множество есть подмножество любого множества, и каждое множество есть подмножество универсального множества U. Очевидно, что если А = {x: P(x)}, B = {x: Q(x)}, то тогда и только тогда, когда высказывание тождественно истинно. Но тогда множество А равно множеству В тогда и только тогда, когда А есть подмножество В и наоборот, то есть .

Последняя формула является основой для построения доказательств о равенстве множеств. Ее применение состоит в следующем. Чтобы доказать равенство двух множеств X и Y, достаточно доказать два включения и , то есть доказать , что из предположения (для любого х) следует, что , и, наоборот, из предположения следует, что . Такой метод доказательства равенств множеств называется методом двух включений.

1.4.7 Для всякого множества А может быть образовано множество всех подмножеств множества А. Его называют булеаном множества А и обозначают 2^А, то есть 2^А = {Х: ХА}. Например, для множества А = {a, b, c} булеан состоит из восьми множеств ,{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}. Вообще, число элементов множества 2^А равно 2ⁿ, где n – число элементов множества А.

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

Свойства операций над множествами (логических операций)

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

2 коммутативность: (; );

3 ассоциативность: ();

4 дистрибутивность: ; (; ).

Для применения закона дистрибутивности в преобразованиях формул удобно иметь в виду следующий аналог. Заменим формулы A, B и C соответственно буквами a, b и с, знак ^ заменим умножением *, а знак – сложением +. Мы получим известное числовое тождество a*(b+c) = a*b + a*c. Это тождество есть дистрибутивность умножения чисел относительно сложения. В школе применение этого равенства слева направо называется раскрытием скобок, а справа налево вынесением общего множителя. Отличие операций над высказываниями ^ и * от числовых операций и + состоит в том, что для высказываний выполняются обе дистрибутивности, а для чисел только одна. Сложение не дистрибутивно относительно умножения.

5 поглощение: ();

6 свойства нуля: А=А; А= ( ; );

7 свойства единицы: AU = U; A U = A ( A1 = 1; A ^ 1=A);

8 инволютивность (двойное отрицание): ;

9 законы двойственности (де Моргана): ; (;);

10 свойства дополнения: (закон исключения третьего: ); = (закон противоречия: );

11 выражение для разности: А \ В = А

12 запишем два свойства логических связок, не имеющих очевидных аналогов в действиях над множествами: ;

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

Пример: доказать равносильность формул F=[X&(ZY)][(XZ)&Y] и G=(XY)&(YZ).

а) В силу закона 12: F = [X&()] [()&Y];

б) Дважды применив дистрибутивность (закон 4) и пользуясь ассоциативностью связок & и (закон 3), получим, что

F = [Xv( (vZ)&Y )] & [ (vY) v ( (vZ)&Y) ] = [ (Xv(vZ) )&(XvY) ]&

( (vY)&( vZ) )& ( (vY) vY)] = (XvvZ)&(XvY)&( vYvvZ)&( vYvY);

в) В силу коммутативности дизъюнкции (закон 2), законов исключения третьего (закон 10) и идемпотентности (закон 1), получаем

F = (1vZ)&(XvY)&(1vYv)&(vY);

г) Применив теперь свойство единицы (закон 7) и коммутативность дизъюнкции, получим

F = 1&(XvY)&1 &( vY) = (XvY)&( vY) = G. Равносильность формул F и G доказана.
Кроме того, с помощью законов 1-12 можно доказывать равенство множеств, задавая множества с помощью предикатов.

Пример: Доказать равенство множеств

X = и Y = .

Очевидно, что множество X задается с помощью формулы F предыдущего примера, а множество Y – с помощью формулы G предыдущего примера. Поскольку формулы F и G равносильны, то на основании закона 12 (закон двух включений) делаем вывод о равенстве множеств: X = Y.

1.5 Соответствия множеств

1.5.1 Кортеж. Декартово произведение

Упорядоченная пара (a, b)на множествах А и В – это множество, определяемое элементами и порядком, в котором они записаны. Простейший и важнейший пример использования упорядоченных пар дает аналитическая геометрия. Если на плоскости введена некоторая прямоугольная система координат, то каждая точка плоскости однозначно задается упорядоченной парой действительных чисел – координатами этой точки. Очевидно, что порядок, в котором перечисляются координаты точки, является существенным: точка, заданная координатами (1, 3), совсем не то же самое, что точка с координатами (3, 1).

Обобщением понятия упорядоченной пары является упорядоченный n – набор, или кортеж. Кортеж (a₁, a₂, …, a_n) на множествах A₁, A₂, …, A_n характеризуется не только входящими в него элементами , но и порядком, в котором они перечисляются. Простейшим примером кортежа является вектор.

Множество всех кортежей длины n на множествах A₁, A₂, …, A_n называют декартовым (прямым) произведением этих множеств и обозначают A ₁ x A₂ x …x A_n, таким образом

.

Если все множества A_i равны между собой, то указанное декартовое произведение называют n-ой декартовой степенью множества А и обозначают Aⁿ. В частности, при n = 2 получаем декартов квадрат, а при n = 3 – декартов куб.По определению полагают, что первая декартова степень множества А есть само множество А.

Декартово произведение имеет следующие свойства:

1 ;

2 ;

3 А x = x A = .

Эти свойства нетрудно доказать методом двух включений.
1.5.2 Соответствия и бинарные отношения

Отображение f из множества А в множество В считается заданным, если каждому элементу xA сопоставлен единственный элемент yB. Отображение f из множества А в множество В обозначают записью f: A→B. Элемент yB, который отображением f сопоставляется элементу xA, называют образом элемента x ри отображении f и обозначают f(x).

Таким образом, каждое отображение однозначно определяет множество упорядоченных пар , является подмножеством декартова произведения A x B множества A на множество B и называемое графиком отображения f.

Отображение f множества А в себя называют тождественным, если f(x) = x при всех x из А.

В общем случае для отображения f: A→B может существовать несколько различных элементов множества А, образы которых совпадают. Множество всех элементов xA, для которых f(x) = y₀, называют прообразом элемента y₀ B при отображении f. Так, прообразом числа a при отображении y = 2x – 4 есть множество всех решений уравнения 2x – 4 = a, то есть множество {x: x = a/2 + 2}.

Множество всех yB, таких, что найдется xA, для которого y = f(x), называют областью значений отображения f. Область значений отображения f будем обозначать R(f).

Отображение f: A→B называют инъекцией, если каждый элемент из области его значений имеет единственный прообраз, то есть из f(x₁) = f(x₂) следует x₁ = x₂.

Отображение f: A→B называют сюръекцией, если его область значений совпадает со всем множеством В. Сюръективное отображение из А в В называют также отображением множества А на множество В.

Отображение f: A→B называют биекцией, если оно одновременно и инъективно и сюръективно. Таким образом, если отображение f: A→B биективно, то каждому элементу множества А отвечает единственный элемент множества В и наоборот. Тогда говорят, что множества А и В находятся между собой во взаимно однозначном соответствии.

Биекцию множества А на себя называют автоморфизмом множества А. Применяют также термин " подстановка множества".

Пусть задано отображение f: A→B и - некоторое множество. Множество f(C) элементов yB, таких что y = f(x), xC, называют образом множества С при отображении f. Например, при отображении y = sin x отрезок [0, 1] является образом множества (отрезка) [0, π], равно как и любого объединения отрезков вида [2πk, (2k + 1)π] (для произвольного целого k). При k = 0 это можно записать следующим образом: sin([0, π]) = [0, 1].

Если отказаться от однозначности отображения, полагая, что данному xA сопоставлен не один, а несколько образов (множество образов), то получим соответствие из множества А в множество В. Если задано соответствие p из А в В, будем использовать обозначение p(x) по аналогии с обозначением f(x) для отображений, понимая при этом, что p(x) есть уже не элемент множества В, а его подмножество.

Аналогично графику отображения можно определить график соответствия p из множества А в множество В как множество С_р упорядоченных пар (x, y), таких, что xA, yB и элементы x, y связаны соответствием p, то есть yp(x). Указанное множество C_p упорядоченных пар есть подмножество декартова произведения A x B.

Соответствие pA x A из множества А в себя, тоесть подмножество множества А², называют бинарным отношением на множестве А. Простейшим примером бинарного отношения является отношение нестрогого неравенства на множестве действительных чисел. Здесь каждому x поставлено в соответствие такое y, что x ≤ y.

Для наглядного изображения соответствий из А в В (бинарных отношений в частности) будем использовать два способа. Первый из этих способов состоит в интерпретации соответствия как подмножества декартова произведения, которое можно изображать примерно так же, как на плоскости можно изображать подмножества декартова квадрата числовых множеств. Второй способ, применяемый для конечных множеств А и В, - построение так называемого графа соответствия. В этом случае элементы множества А и В изображаются на плоскости кружочками. Если пара (x, y) принадлежит соответствию р, то в графе соответствия из кружочка, обозначающего элемент xA, проводим стрелку к кружочку, обозначающему элемент yB. Для бинарного отношения на конечном множестве А часто удобнее использовать граф другого вида. Элементы множества А изображаются кружочками только один раз, а стрелки проводятся по тем же правилам, что и в графе соответствия. Заметим, что при таком построении возможно соединение кружочка стрелкой с самим собой (петля).

Пример: а) Рассмотрим множество программистов А = {Иванов, Петров, Сидоров} и множество программ В = {пр1, пр2, пр3, пр4, пр5}. Зададим соответствие р из А в В:

р = {(Иванов, пр1), (Иванов, пр3), (Иванов, пр5), (Петров, пр2), (Петров, пр4), (Сидоров, пр2), (Сидоров, пр5) } A x B. На рисунке 1.7, а

изображены график и граф этого отношения.

б) Пусть А = {1, 2, 3, 4}. Бинарное отношение q на А определяется как множество всех упорядоченных пар (x, y), таких, что x ≥ y. Тогда

q = {(1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (4, 4)}.
График и два варианта графа отношения q изображены на рисунке 1.7, б.

а

Рисунок 1.7

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

1.6.1 Конечные и бесконечные множества

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

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

Посмотрим, как мы сравниваем между собой два конечных множества. Можно, например, сосчитать число элементов в каждом из них и, таким образом, эти два множества сравнить. Но можно поступить и иначе, именно, попытаться установить биекцию этих множеств, то есть такое соответствие, при котором каждому элементу одного множества отвечает один и только один элемент другого, и наоборот. Ясно, что взаимно однозначное соответствие между двумя конечными множествами можно установить только тогда, когда число элементов в них одинаково. Например, чтобы проверить, одинаково ли число студентов в группе и стульев в аудитории, можно, не пересчитывая ни тех, ни других, посадить каждого студента на определенный стул. Если места хватит всем и не останется ни одного лишнего стула, то есть если будет установлена биекция между этими двумя множествами, то это и будет означать, что число элементов в них одинаково. Заметим, что если первый способ (подсчет числа элементов) годится лишь для сравнения конечных множеств, второй (установление взаимно однозначного соответствия) пригоден и для бесконечных.
1.6.2 Счетные множества

Простейшим среди бесконечных множеств является множество натуральных чисел. Назовем счетным множеством всякое множество, элементы которого можно биективно сопоставить со всеми натуральными числами. Иначе говоря, счетное множество – это такое множество, элементы которого можно занумеровать в бесконечную последовательность: а₁, а₂, …, а_n, … Приведем примеры счетных множеств.

1 Множество всех целых чисел.

Установим соответствие между всеми целыми и всеми натуральными числами по следующей схеме:

0 -1 1 -2 2 …

1 2 3 4 5 …

То есть неотрицательному числу n ≥ 0 сопоставим нечетное число 2n + 1, а отрицательному n

n ↔ 2n + 1 при n ≥ 0;

n ↔ 2|n| при n

2 Множество всех четных положительных чисел.

Соответствие очевидно: n ↔ 2n.

3 Множество всех рациональных чисел.

Каждое рациональное число записывается в виде несократимой дроби х = p/q , q > 0. Назовем сумму |p| + q высотой рационального числа х. Ясно, что число дробей с данной высотой n конечно. Например, высоту 1 имеет только число 0/1, высоту 2 – числа 1/1 и -1/1, высоту 3 – числа 2/1, 1/2, -2/1, -1/2 и т. д. Будем нумеровать все рациональные числа по возрастанию высоты, то есть сначала выпишем высоты 1, потом – числа высоты 2 и т. д. При этом всякое рациональное число получит некоторый номер, то есть будет установлено взаимно однозначное соответствие между всеми натуральными и всеми рациональными числами.

Перечислим некоторые свойства счетных множеств:

1 Всякое подмножество счетного множества конечно или счетно.

2 Объединение любого конечного или счетного числа счетных множеств есть счетное множество.

3 Всякое бесконечное множество содержит счетное подмножество.

1.6.3 Эквивалентные множества

Сравнивая те или иные бесконечные множества с натуральным рядом, мы пришли к понятию счетного множества. Ясно, что множества можно сравнивать не только с множеством натуральных чисел; установление биекции позволяет сравнивать между собой любые два множества.

Два множества А и В называются эквивалентными, если между их элементами может быть установлено взаимно однозначное соответствие (биекция). Понятие эквивалентности применимо к любым множествам, как конечным, так и бесконечным. Два конечных множества эквивалентны между собой только тогда, когда число элементов у них одинаково. Определение счетного множества можно теперь сформулировать следующим образом: множество называется счетным, если оно эквивалентно множеству натуральных чисел. Ясно, что два множества, эквивалентные третьему, эквивалентны между собой; в частности, любые два счетных множества эквивалентны между собой.

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

1 А = [a; b], B = [c;d].

Из рисунка 1.8 ясно, как установить биекцию между отрезками [a; b] и [c; d]. Именно, точки p и q соответствуют друг другу, если они являются проекциями одной и той же точки r вспомогательного отрезка [e; f].

Таким образом, множества точек на любых двух отрезках эквивалентны между собой.

2 А – множество всех чисел в интервале (0, 1), В – множество всех точек прямой.

Эти множества эквивалентны, так как можно установить биекцию с помощью функции .

Рисунок 1.8

Рассматривая эти примеры, можно заметить, что иногда бесконечное множество оказывается эквивалентным своей части. Например, натуральных чисел оказывается "столько же", сколько и всех целых или даже всех рациональных; на интервале (0, 1) "столько же" сколько и на всей прямой, и т.д. Это явление характерно для всех бесконечных множеств. Действительно, по свойству 3 счетных множеств из каждого бесконечного множества М можно выбрать счетное подмножество; пусть А = {а₁, а₂, …, а_n, …}. Разобьем его на два счетных подмножества: А₁ = {а₁, а₃, а₅, …}, А₂ = {а₂, а₄, а₆, …} и установим между А и А₁ взаимно однозначное соответствие. Это соответствие можно затем продолжить до взаимно однозначного соответствия между множествами А U (М\A) = M и A₁ U (M\A) = М \ A₂, отнеся каждому элементу из М \ A сам этот элемент. Между тем множество М \ А₂ не совпадает с М , то есть является подмножеством множества М. Мы получили следующее предложение: Всякое бесконечное множество эквивалентно некоторому своему подмножеству. Это свойство можно принять за определение бесконечного множества.

1.6.4 Несчетность множества действительных чисел

Множество действительных чисел, заключенных между нулем и единицей, несчетно. Докажем это утверждение. Предположим, что дано какое-то счетное множество (всех или только некоторых ) действительных чисел х , лежащих на отрезке [0, 1]:

x₁ = 0, a₁₁ a₁₂ a₁₃ … a_1n …,

x₂ = 0, a₂₁ a₂₂ a₂₃ … a_2n …,

x₃ = 0, a₃₁ a₃₂ a₃₃ … a_3n …,

……

x_n = 0, a_n1 a_n2 a_n3 … a_nn …,

……

Здесь а _i _k – k-я десятичная цифра числа x _i. Построим дробь y = 0, b₁ b₂ b₃ … b_n … диагональной процедурой Кантора, а именно: за b₁ примем произвольную цифру, не совпадающую с а₁₁, за b₂ - произвольную цифру, не совпадающую с а₂₂, и т.д. Вообще, за b_n примем произвольную цифру, не совпадающую с а_nn. Эта десятичная дробь не может совпасть ни с одной дробью x _i. Действительно, от х₁ дробь y отличается по крайней мере первой цифрой, от х₂ – второй цифрой и т.д. Таким образом, дробь y не является элементом произвольно выбранного счетного множества. Иными словами, никакое счетное множество действительных чисел, лежащих на отрезке [0, 1], не исчерпывает этого отрезка, а значит это множество несчетно.

Приведем примеры множеств, эквивалентных отрезку [0, 1], а значит несчетных множеств:

1 Множество всех точек любого отрезка [a, b] или интервала (a, b)

2 Множество всех точек прямой

3 Множество всех прямых на плоскости

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

Если эквивалентны два конечных множества, то они состоят из одного и того же числа элементов. Если же эквивалентные между собой множества произвольны, то говорят, что они имеют одинаковую мощность. Таким образом, мощность – это то общее, что есть у любых двух эквивалентных между собой множеств. Для конечных множеств понятие мощности совпадает с привычным понятием числа элементов множества. Мы отметили выше, что счетные множества – это "самые маленькие" из бесконечных множеств, а затем показали, что существуют бесконечные множества, бесконечность которых имеет более "высокий порядок", - это множества, эквивалентные множеству всех действительных чисел отрезка [0, 1]. Про такие множества говорят, что они имеют мощность континуума. Возникает вопрос: существует какая-то "наивысшая" мощность или нет? Оказывается, верна следующая теорема.

Теорема: Булеан 2^А имеет мощность большую, чем мощность исходного множества А.

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

Пусть А и В – два произвольных множества, а m(A) и m(B) – их мощности. Тогда А и В либо эквивалентны (и тогда m(A) = m(B)), либо А содержит подмножество,, эквивалентное В (тогда m(A) > m(B)), либо В содержит подмножество, эквивалентное А (тогда m(A)

При решении задач удобно следующее утверждение.

Утверждение: Для любых конечных А и В справедливо равенство

m(A U B) = m(A) + m(B) – m(AB)

Докажем это утверждение. Число общих элементов множеств А и В равно m(AB). Объединение этих множеств образуется добавлением к элементам множества А всех тех элементов множества В, которые не входят в А. Число таких элементов равно m(B) – m(AB). Таким образом, m(A U B) = m(A) + m(B) – m(AB).
Пример: В школе 1400 учеников. Из них 1250 умеют кататься на лыжах, 952 – на коньках. Ни на лыжах, ни на коньках не умеют кататься 60 учеников. Сколько учеников умеют кататься и на лыжах, и на коньках?

Множество учеников школы будем считать основным множеством U, А и В – соответственно множества учеников, умеющих кататься на лыжах и на коньках. Ученики, не умеющие кататься ни на лыжах, ни на коньках, составляют множество , по условию m() = 60. По законам двойственности =, поэтому m(A U B) = m(U) – m() = 1400 – 60 = 1340. Применим формулу m(A U B) = m(A) + m(B) – m(AB): 1340 = 1250 + 952 - m(AB), откуда m(AB) = 862.