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

Если множество 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:	1	2	3	4	5	…	2 n	2 n +1	…
Z:	0	1	-1	2	-2	…	n	-n	…,

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

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

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