Легко видеть, что ¬A A=U и ¬A∩ A= . Операции объе-

динения и пересечения множеств обладают свойствами сочетательности и переместительности, т. е.

A B = B A,	(1.2.2)
A ∩ B = B ∩ A,	(1.2.3)
(A B) C = A (B C),	(1.2.4)
(A ∩ B) ∩ C = A ∩ (B ∩ C).	(1.2.5)

Операция пересечения обладает также свойством распределительности относительно объединения, т. е.

(A B) ∩ C = (A ∩ C) (B ∩ C).

(1.2.6)

§ 3. Эквивалентность множеств. Счетные и несчетные множества

Пусть даны два конечных множества A и B. Если A состоит из n элементов, а B — из m элементов, то между числами n и m возможно только одно из трех соотношений:

n = m, n > m, n < m.

Какое из этих соотношений имеет место, можно определить либо непосредственным подсчетом элементов в данных множествах, либо постановкой элементов данных множеств во взаимно однозначное соответствие. Суть второго метода заключается в возможности составления пар элементов (a, b), где a A, b B, причем так, чтобы элементы a A и b B ни в одной паре не повторялись и каждое a A и каждое b B входили бы только в единственную пару. Например, каждый палец правой руки можно положить на такой же по названию палец левой руки. Тот факт, что при этом все пальцы обеих рук будут составлять пары, непосредственно без счета пальцев показывает, что количества пальцев на обеих руках равны.

— 12 —

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

y = ax + b (a ≠ 0).

Здесь каждому действительному числу x X «ставится в пару» действительное число y Y: y = ax + b и наоборот, каждому действительному числу y Y «ставится в пару» действительное число

xX: x = (y – b)/a.

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

Если между элементами двух различных множеств A и B можно установить взаимно однозначное соответствие, то эти множества называются эквивалентными. Это записывается так:

A ≈ B.

Заметим, что эквивалентны — не значит равны, т. к. множества A и B не обязательно состоят из одних и тех же элементов (обратное верно!).

Из определения эквивалентности вытекают следующие ее свойства:

1)A ≈ A (рефлексивность);

2)если A ≈ B, то B ≈ A (симметричность);

3)если A ≈ B и B ≈ С, то A ≈ C (транзитивность).

Пусть дано произвольное множество A. Рассмотрим совокупность всех множеств, эквивалентных множеству A. Из свойства транзитивности следует, что все эти множества эквивалентны друг

— 13 —

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

1)если A не эквивалентно B, то никакие два представителя классов эквивалентности A и B не эквивалентны друг другу, т. е. различные классы эквивалентных множеств не пересекаются;

2)существует бесконечное количество различных классов эквивалентных множеств.

Чтобы отличать эти классы друг от друга, поставим каждому классу в соответствие некоторый символ α, который будем назы-

вать кардинальным числом или мощностью. Таким образом, мощ-

ность — это то общее, что присуще всем эквивалентным между собой множествам.

Естественно, что мощностью конечного множества служит количество его элементов, т. е. целое неотрицательное число.

Пусть N — множество натуральных чисел; обозначим его мощность α0 (алеф-ноль). Рассмотрим еще несколько бесконечных множеств: Z (целых чисел), Q (рациональных чисел). Будут ли эти множества принадлежать классу α0 ? На первый взгляд кажется,

что они как бы «больше», чем N. Однако между любым из них и N можно установить взаимно однозначное соответствие. Действи-

тельно для N и Z имеем z =(−1)n	n		(функция y = [x] — целая
2

часть числа x). Установить эквивалентность N и Q можно геометрически. Все рациональные числа, как известно, представимы в виде дроби p/q, где q — натуральное число, а p — целое число. Поставим в соответствие каждое такое число p/q узлам целочисленной координатной сетки, у которой абсциссы узлов соответствуют числителям дробей p/q, а ординаты — знаменателям их.

Тогда занумеровать узлы можно как, например, показано на рисунке. Поскольку каждый узел получил свой номер, значит, каждое рациональное число соответствует единственному натуральному.

Определение. Всякое множество, эквивалентное множеству натуральных чисел, называется счетным.

— 14 —

Таким образом, мощность α0 есть счетная мощность. Счетные

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

Существуют ли множества, мощность которых больше счетной? Для ответа на этот вопрос рассмотрим теорему.

Теорема. Множество действительных чисел интервала (0; 1) более чем счетно.

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

x1, x2 , x3 , ... xn , ...

(1.3.1)

Каждое число xn единственным образом представляется в виде десятичной дроби

xn =0,a1(n)a2(n)a3(n) ... an(n) ...

Теперь возьмем для каждого n отличное от an(n) число bn , равное либо 1, либо 2.

Это можно сделать так: bn = 1, если an(n) ≠ 1, bn = 2, если

a(n)	= 1.
n
Рассмотрим бесконечную десятичную дробь
	x =0,b1b2b3 ... bn ... ,	(1.3.2)

которая определяет некоторое число из интервала (0; 1). Поскольку по предположению последовательность (1.3.1) со-

держит все числа интервала (0, 1), то число (1.3.2) стоит в ней на каком-то месте, пусть на m-ом. Тогда

x =0, a(m)a(m)a(m)	... a(m) ...	(1.3.3)
1 2 3	n

— 15 —