Декартово умножение множеств

Рассмотрим следующую задачу. Сколько можно составить слогов, состоящих из двух букв, из которых первая – любая согласная из П, Р, С, а вторая – любая гласная из А, О, У, Э? Чтобы выписать все возможные слоги составим таблицу (табл. 2).

Таблица 2

	А	О	У	Э
П	ПА	ПО	ПУ	ПЭ
Р	РА	РО	РУ	РЭ
С	СА	СО	СУ	СЭ

С точки зрения теории множеств из двух данных множеств
А = {П, Р, С}, В = {А, О, У, Э} образовано новое множество слогов, состоящее из пар элементов, входящих в множества А и В, причем на первом месте стоит элемент из А, а на втором – элемент из В. Множество таких пар называется декартовым (или прямым) произведением множеств А и B.

Определение. Декартовым произведением А ´ В двух множеств А и В называют множество, состоящее из всех пар элементов (а, в), таких, что а Î А, в Î В, т.е. А ´ B = {(а, в) | а Î А, в Î В}.

В частности, для любого множества А, А ´ Æ = Æ ´ А = Æ.

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

П р и м е р. А = {1, 2, 3}, В = {2, 3, 4, 5}, А ´ B = {(1, 2), (1, 3),
(1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 2), (3, 3), (3, 4), (3, 5)}.

Заметим, что порядок расположения элементов в парах существенен, например, (2, 3) ≠ (3, 2).

Если A и B – числовые множества, то А ´ В – это множество упорядоченных пар чисел, изображая каждую пару чисел в прямоугольной декартовой системе координат, получим фигуру на плоскости. Например на рис. 9 изображено А ´ В множеств А = [0, 2], B = [1, 2]. На рис. 10 изображено А ´ В множеств А = {0, 1, 2}, B = [1, 2].

у у

2 2

1 1

0 1 2 х 0 1 2 х

Рис. 9 Рис. 10

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

Декартово умножение множеств не подчиняется коммутативному закону, т.е. существуют множества А и В, для которых A´В ≠ В´А. Декартово умножение не подчиняется и ассоциативному закону, но связано с операциями объединения, пересечения и вычитания множеств дистрибутивными свойствами: для любых множеств А, В и С имеют место равенства:

(А В) ´ С = (A ´ С) (В ´ С), С ´ (А В) = (С ´ А) (С ´ В);

(А В) ´ С = (A ´ С) (В ´ С), С ´ (А В) = (С ´ А) (С ´ В);

(А \ В) ´ С = (A ´ С) \ (В ´ С), С ´ (А \ В) = (С ´ А) \ (С ´ В).

Эти свойства интуитивно ясны.

Проверим для множеств А = {1, 2}, B = {2, 3} и C = {a} равенство (А В) ´ С = (A ´ С) (В ´ С).

Тогда {1, 2, 3} и = {(1, a); (2, a); (3, a)}.

С другой стороны, {(1, a); (2, a)}, {(2, a); (3, a)} и {(1, a); (2, a); (3, a)}.

Как видно, этот пример подтверждает равенство. На этом примере можно проверить и все остальные равенства, приведенные выше.

Однако, пример, подтверждающий равенство, не может служить доказательством этого равенства. Приведем в качестве примера и общее доказательство рассмотренного выше равенства:

и ( или ) и ( и ) или ( и ) или .

Следовательно, . Обратное включение доказывается точно такой же цепочкой, рассматриваемой лишь с конца.

Можно найти декартово произведение нескольких множеств (двух, трех, …, n множеств).

Определение. Декартовым произведением A₁ ´ A₂ ´ … ´ A_n множеств A₁, A₂, …, A_n называют множество всех упорядоченных наборов вида (a₁, a₂, …, a_n), где а₁ Î А₁, а₂ Î А₂, …, а_n Î А_n. Каждый такой набор называют кортежем длины n, т.е.

A₁ ´ A₂ ´ … ´ A_n = {(а₁, а₂, …, а_n)| а₁ Î А₁, а₂ Î А₂, …, а_n Î А_n}.

Пример. А = {1, 2, 3}, В = {3, 5, 7}, C = {4, 6}. Найдите A´В´С.

A ´ В = {(1, 3), (1, 5), (1, 7), (2, 3), (2, 5), (2, 7), (3, 3), (3, 5), (3, 7)}.

A ´ В ´ С = {(1, 3, 4), (1, 5, 4), (1, 7, 4), (2, 3, 4), (2, 5, 4), (2, 7, 4),
(3, 3, 4), (3, 5, 4), (3, 7, 4), (1, 3, 6), (1, 5, 6), (1, 7, 6), (2, 3, 6), (2, 5, 6), (2, 7, 6), (3, 3, 6), (3, 5, 6), (3, 7, 6)}.