Покрытие и разбиение множеств

Разбиением множества А называется семейство А_i непустых и различных подмножеств А, таких, что и для всех (i ≠ j). Множества A_i называются классами разбиения.

Пример. Разбиения множества А = {1, 2, 3. 4}. {1, 2}, {3, 4} и {1}, {2, 4}, {3}. Все объединения разбиений дают множество А, а все их пересечения пусты.

Если все рассматриваемые множества являются подмножествами некоторого множества U, то это множество называют универсальным множеством.

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

Рассмотрим два конечных множества А и В с числом элементов т и п. Между этими числами возможно одно из трех соотношений: т = п; т < п; т > п. Вопрос о том, какое из них имеет место, решается просто: подсчетом количества элементов А и В. Однако можно поступить иначе, не считая эти элементы. Для этого между элементами множеств А, В необходимо попытаться установить взаимно однозначное соответствие, при котором каждому элементу множества А отвечает один и только один элемент множества В и, наоборот, каждому элементу множества В соответствует один и только один элемент множества А.

Иными словами, каждому элементу множества А необходимо «поставить в пару» элемент множества В. Такое соответствие можно установить тогда и только тогда, когда число элементов в этих множествах одинаковое, т.е. т = п. Когда же после «постановки в пару» остались элементы множества В, то т < п. Если же полностью исчерпаны элементы В и остались лишние элементы множества А, то т > п.

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

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

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

Приведем примеры эквивалентных бесконечных множеств. Множество всех натуральных чисел эквивалентно множеству всех четных чисел, так как каждому натуральному числу п соответствует одно и только одно четное число 2n, и каждому числу 2n соответствует его половина, являющаяся натуральным числом. Множество всех целых чисел эквивалентно множеству натуральных чисел. Соответствие между целыми и натуральными числами устанавливается по следующей схеме:

0,-1, 1.-2.2...

1, 2, 3, 4, 5,..., т.е. неотрицательному числу п > 0 ставится в соответствие нечетное число 2n + 1, а отрицательному п < 0- четное число 2 ׀ n ׀.

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

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

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

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

Пусть - некоторое семейство подмножеств множества M и . Семейство называется покрытием множества M, если каждый элемент его принадлежит хотя бы одному из :

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

Дизъюнктное покрытие называется разбиением множества M.