Декартово произведение множеств. Количество элементов в декартовом произведении конечных множеств

Определение 1.22. Декартовым произведением двух множеств X uY называется множество пар (х,у) таких, что х X, у Y. Обозначим это множество X × Y.
Итак X × Y = {(х,у) | х X, у Y} . Равенство элементов в множестве X × Y понимается следующим образом: (x1, y1) = (x2, y2) тогда и только тогда, когда x1 = х2 и у1 = у2. Очевидно, что X × Y ≠ Y × X, если X ≠ У.
Определение 1.23. Декартовым произведением п множеств {Х1,Х2, ...,Хп} называется множество
X1 × X2 × ... × Xn = {(x1,x2,...,xn) | xi Xi Vi= 1,...,n} ,
то есть множество упорядоченных строк из п элементов.
Заметим, что множество X × X × ... × X обычно обозначают Хп.
Теорема 1.24. Если X u Y - конечные множества, то X × Y - конечное множество и |Х × Y| = |Х| ∙ |Y|.
Доказательство. Зафиксируем в X нумерацию, то есть X = {х1,х2, ...,хп}. Тогда
X × Y = × Y и (xi × Y) (XJ × Y) = Ø, если i≠j.
По правилу суммы |Х × Y| = |xi × Y|. Так как отображение fi :xi × Y →Y такое, что fi((xi, y)) = y, является биекцией для любого i (i=1,…,n), то |xi × Y| = |Y| и |Х × Y| = |Х| ∙ |Y|.
Следствие. Если Х1,Х2, ...,Хп - конечные множества, то |Х1×Х2×...×Хп| = |Х1|∙|Х2|∙...∙|Хп|

Задача. Из города А в город В ведет 3 дороги, из города В в город С - 4 дороги. Сколько различных дорог ведет из города А в город С ?
Решение.
Обозначим через X множество дорог из А в В, Y - множество дорог из В в С. Тогда X = {х1,x2,хз} , Y = {y1,y2,yз}. Каждая дорога из А в С является парой (xi,yj), где xi X, yj Y. Таким образом множество всех дорог из А в С является декартовым произведением X ×Y. Следовательно |Х × Y| = |Х| ∙ |Y| = 12.

Powered by Drupal - Design by artinet