Множество YX, и количество элементов |YX| в этом множестве

Определение 1.25. Пусть X и Y - непустые множества. Множество всех отображений из X в Y назовем множество степень и обозначим YX, то есть YX = {f | f : X → Y} .
Теорема 1.26. Пусть X uY - конечные непустые множества. Тогда |YX| = |Y||X|.
Доказательство. Для доказательства теоремы применим индукцию по количеству элементов в множестве X. Пусть |Х| = 1, то есть X = {х}, Y = {y1,y2,…,ym}. Каждое отображение f : X → Y определяется тем, куда попадет элемент х. В этом случае все различные отображения из множества X в множество Y можно просто перечислить: f1 - такое отображение, что f1(x) = y1; f2 - такое, что f2 (x) = у2; ...; fm - такое, что fm(x) = уm. Ясно, что все эти отображения разные и |YX| = m1 = |Y||X|. Предположим далее, что для любого множества X такого, что |Х| < п. Пусть теперь |Х| = п, то есть X = {x1,x2 ,…,xn}. Множество YX разобьем на непересекающиеся подмножества: YX = A1 A2 ... Am, где m = |Y|, Y = {y1, y2,…,ym}. Aj = {f : X → Y | f(x1) = yj }. Ясно, число Aj ∩ Ak = Ø, если j ≠ k. По правилу суммы |YX| = |А1| + |А2| + ... + |Ат|. Посчитаем теперь количество элементов в каждом множестве Aj. При любом отображении f Aj образ элемента х1 фиксирован (f(x1) = yj), следовательно отображение f определяется только тем, куда попадут элементы множества Х \ {x1}. Таким образом отображение f однозначно определяется своим ограничением на Х \ {х1}, поэтому для любого j количество элементов в множестве Aj совпадает с количеством всех различных отображений из множества Х \ {х1} в множество Y. По предположению индукции |Aj| = |Y X\{x1}| = mn−1.
Тогда |Y X| = m • mn−1 = mn = |Y ||X|, что и требовалось доказать.
Задача. В кабину лифта девятиэтажного дома вошли 4 пассажира, каждый из которых может выйти на любом из 8 этажей. Сколько существует способов разгрузки лифта?
Решение. Обозначим через X множество пассажиров, через Y - множество этажей, на которых они могут выйти. Тогда каждая разгрузка лифта - это некоторое отображение f : X —> Y (каждому пассажиру поставлен в соответствие этаж, на котором он выходит при этой разгрузке). Следовательно число различных способов разгрузки лифта совпадает с числом различных отображений из множества X в множество Y, то есть равно |YX| = 84 = 4096.
Задача. Пусть X - конечное множество. Найти количество всех различных подмножеств множества X.
Решение. Пусть Е2 = {0,1}. Для любого подмножества А X определим отображение
fA : X —> Е2 следующим образом: fA(х) = 1, если х A; fA(х) = 0, если х А. Заметим, что множество всех таких отображений совпадает с множеством Е2X. Действительно, очевидно, что { fA | А X} Е2X. С другой стороны, если f : X → Е2 - произвольное отображение, то f = fA, где А = {х X | f(x) = 1}. Очевидно, что отображение φ: {А | А X} → Е2X такое, что φ(А) = fA, является биекцией. Следовательно количество всех различных подмножеств множества X равно |Е2X| = 2|X|.
Заметим,что множество всех подмножеств множества X обозначают 2Xl и мы доказали, что
|2Х| = 2|X|.

Powered by Drupal - Design by artinet