Свойства конечных множествМножество 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). Тогда по правилу суммы , но , поэтому , . Имеем , отсюда .
Теорема (обобщенное правило включения – исключения). Пусть конечное множество X является объединением r конечных множеств: Тогда
Теорема доказывается методом математической индукции по числу r блоков покрытия множества X.
|