1.4.4. Свойства конечных множеств

Множество Xназываетсяконечным, если существует биекция , т.е. множествоXможно взаимно однозначно отобразить на отрезок натурального ряда {1,2,…,n}; при этомX= n.

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

Пустое множество принято относить к конечным множествам и обозначать =0.

Сформулируем свойства конечных множеств в виде теорем (не все теоремы будут строго доказаны).

Теорема(правило суммы). Пусть множествоXявляется объединениемrнепересекающихся конечных множеств. Тогда.

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

Шаг 1. Покажем, что теорема справедлива при. Пусть и множества конечны, т.е. существует биекция и . Установим биекцию следующим образом: всем элементам множестваоставим прежние номера, а номера элементов множестваувеличим на число. Полученное отображение

является биекцией в силу биективности и. Следовательно,. Основание индукции доказано.

Шаг 2 . Индукционный переход заключается в следующем: предположим, что теорема справедлива при числе блоков разбиения; докажем, что в этом случае она будет справедлива и при числе блоковr.

Предположение: множества , конечны и образуют разбиение множестваY. Тогда

Рассмотрим разбиение множества Xнаrконечных множеств. Тогдапо закону ассоциативности объединения. ОбозначимОпираясь на основание индукции (шаг 1), имеем , а по индукционному предположениюИндукционный переход доказан.

Заключение. Согласно методу математической индукции, теорема справедлива для любого натурального числаr блоков разбиения.

Теорема(правило произведения). Пусть конечное множествоXпредставлено в виде декартова произведенияrконечных множеств . Тогда.

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

Теорема( о мощности булеана конечного множества). Пусть множествоXконечно и. Тогда.

Напомним, что B(X)есть булеан множестваX, т.е. множество всех подмножеств множестваX. При построении булеана в 1.1.8 мы использовали эту теорему без доказательства.

Доказательство. МножествоXконечно, значит, существует биекция. Зафиксируем порядок элементов множестваи рассмотрим множествоVвсех упорядоченных наборов длиныn, состоящих из нулей и единиц:

.

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

Теорема(правило включения – исключения). Пустьиконечные множества. Тогда.

Доказательство теоремы опирается на правило суммы. Представим множество в виде объединения непересекающихся множеств, где, , (рис. 1.23). Тогда по правилу суммы, но , поэтому, . Имеем,отсюда

.