Мощность множества. Счетные множества

Если множество X – конечное, то любое эквивалентное ему множество Y тоже конечное, причем оба эти множества равночисленные. С другой стороны, назвав какое-либо натуральное число, мы выражаем численность не одного какого-нибудь множества, а любого из множеств, принадлежащих одному и тому же классу эквивалентности из классов, определяемых отношением X ~ Y.

Если множество X бесконечное, то Y, такое что X ~ Y, тоже бесконечное. Чем же характеризуется класс бесконечных множеств, эквивалентных множеству Х ? Возникла потребность в таком обобщении понятия «число элементов», чтобы это новое, более общее понятие служило характеристикой класса попарно эквивалентных множеств и в том случае, когда эти множества бесконечные. Таким обобщением явилось понятие «мощность» множества, введенное основоположником теории множеств Г. Кантором.

Определение. Множества имеют одну и ту же мощность, если они эквивалентны.

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

Если X конечное множество, то его мощность воспринимается как число элементов этого множества и выражается целым неотрицательным числом (кардинальным числом).

Рассмотрим 2 бесконечных множества: N – множество всех натуральных чисел и В – множество положительных четных чисел
(B Ì N) и отображение F, состоящее из пар (х, у) таких, что у = 2х,
x Î N, у Î В.

Нетрудно заметить, что F – биекция. Следовательно, N ~ B, т.е. эти множества равномощны. Равномощность множества своему подмножеству нам кажется парадоксальной потому, что это противоречит принципу «целое больше своей части» в привычной нам области конечных множеств.

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

Из этого определения непосредственно следует, что любые два счетных множества равномощны. В самом деле, пусть X ~ N, Y ~ N, тогда X ~ NÙ N~ Y Þ X~ Y (в силу симметричности и транзитивности). Примером счетного множества является рассмотренное выше множество положительных четных чисел. Аналогично устанавливается, что и множество положительных нечетных чисел эквивалентно N, т.е. является счетным множеством. Легко доказать, что и множество всех целых чисел Z ~ N, хотя NÌ Z. Можно построить, например, следующую биекцию

N:						…	2n	2n+1	…
Z:			-1		-2	…	n	-n	…,

доказывающую эквивалентность Z ~ N, т.е. счетность множества Z.

Вопросы и задания для самопроверки

1.Соответствие R между множествами X = {1, 3, 5, 7} и Y = {2, 4, 6} задано перечислением пар:{(1, 2), (3, 2), (5, 2), (5, 4), (7, 4), (7, 6)}.Покажите, что R Ì X ´ Y. Задайте перечислением пар соответствия обратное и противоположное данному.

2. Какой частный случай соответствия называется отношением?

3. Определите свойства отношения «равно» в множестве N натуральных чисел.

4. Почему в математике среди отношений выделили два класса: отношения эквивалентности и отношения порядка?

5. Какой частный случай соответствия называется отображением?

6. С каким видом отображений связаны понятия равномощности и счетности множеств?

ГЛАВА III

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

И ТЕОРИИ ВЕРОЯТНОСТЕЙ

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

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