Классификация множеств. Мощность множества

Основной характеристикой множеств является количество элементов, содержащихся в этом множестве.

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

Следует отметить, что понятие «равномощные множества» не означает, что эти множества равны.

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

Если ― инъекция множества в , то будет справедливо неравенство , а если ― сюръекция множества на , то .

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

Множество, содержащее бесконечное число элементов называется бесконечным.

Бесконечное множество, эквивалентное множеству натуральных чисел называется счетным. В противном случае множество будет несчетным. Например, счетными являются множества целых и рациональных чисел. Георг Кантор в 1878 году доказал, что множество точек отрезка несчетно.

По определению Б. Больцано и Р. Дедекинда множество называется бесконечным, если оно равномощно одному из своих собственных подмножеств.

Для конечных множеств справедливо утверждение, которое называется основной теоремой о конечных множествах.

Теорема. Любое конечное множество не эквивалентно никакому его собственному подмножеству, кроме самого себя.

Следствие. Всякое непустое конечное множество эквивалентно одному и только одному отрезку натурального ряда чисел .

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

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

Для сравнения множеств применяются некоторые теоремы о мощности множеств:

1. Если .

2. Если .

3. Если и ― несчетно, то тоже несчетно.

 

Принцип Дирихле

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

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

Пример. Покажите, что какие бы пять цифр из 1,2,3,4,5,6,7,8 мы ни выбрали, найдутся хотя бы две из них, сумма которых равна 9.

Решение. Перечислим пары цифр в сумме дающих 9: .

Обозначим через множество произвольно выбранных 5 цифр, а через следующее множество пар . Ясно, что . Рассмотрим функцию , сопоставляющую каждой цифре из пятерки пару из множества , которая в ней содержится. Например, . По принципу Дирихле хотя бы две цифры из множества попадут в одну и ту же пару. Короче говоря, две из пяти цифр дадут в сумме 9.

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

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

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

.

Поскольку , то найдется три человека, которые либо все знакомы с , либо все трое его не знают.

Предположим теперь, что три человека знакомы с . Если все трое друг с другом не знакомы, то мы получили решение задачи. В противном случае, какая-то пара, например, и знают друг друга. Но они же знакомы и с . Стало быть, трое людей знают друг друга. Аналогично разбирается случай, когда три человека не знакомы с .