Декартово произведение множеств А и В

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

Операцию нахождения декартова произведения множеств называют умножением множеств.

Умножение множеств не коммутативно и не ассоциативно, то есть существуют множества A, B и C такие, что справедливы следующие неравенства А В¹В А и А (В С)¹(А В) С.

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

Теорема 4. Число элементов в декартовом произведении двух произвольных конечных множеств равно произведению чисел элементов в каждом из них, то есть n (A B)=n (A) ∙ n (B).

ÿ Рассмотрим произвольные конечные множества А и В.

Пусть n(A)=k, n(B)=l. Без ограничения общности рассуждений можно считать, что А={х , х , … , х } и В={y ,y , … ,y }.

Запишем элементы А  В в виде таблицы:

(x ; y )	(x ; y )	(x ; y )	…	(x ; y )
(x ; y )	(x ; y )	(x ; y )	…	(x ; y )
…	…	…	…	…
(x ; y )	(x ; y )	(x ; y )	…	(x ; y ).

В этой таблице k строк и l столбцов. Следовательно, в ней содержится k∙ l элементов.

Таким образом, n(A B)=n(A) ∙ n(B). Теорема доказана.