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

 

В повседневных разговорах мы часто употребляем понятие пары: пара обуви, танцевальная пара, «сладкая парочка» (Twiks) и т.д.

Рассмотрим, например, число 68. Это число записывается при помощи двух цифр 6 и 8, которые необходимо записывать в определенном порядке: сначала 6, а затем 8. Если эти цифры переставить, то получаем другое число 86.

В таком случае, когда важен порядок расположения элементов множества, в математике говорят об упорядоченных наборах элементов.
В данном примере мы имеем дело с упорядоченными парами.

Пусть дано некоторое множество Х. Упорядоченной парой называют два элемента множества, взятые в определенном порядке.

Упорядоченную пару, образованную из элементов х и у множества Х, обозначают (х, у); элемент  называют первой компонентой (координатой), а элемент  — второй компонентой (координатой) этой пары.

В упорядоченной паре может быть, что х = у. Например, число 55 можно рассматривать, как упорядоченную пару (5, 5).

Две упорядоченные пары называются равными, если их соответствующие компоненты равны, т.е. (х, у) = (z, t), если х = z и y = t. Отсюда следует, что если x ¹ y, то (х, у) ¹ (y, x).

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

Рассмотрим два множества X = {1, 2, 3}, Y = {2, 5}. Найдем всевозможные упорядоченные пары, первой компонентой которых является элемент множества Х, а второй компонентой — элемент множества Y. Получим следующее множество упорядоченных пар:

{(1,2), (1,5), (2,2), (2,5), (3,2), (3,5)}.

Это множество называют декартовым (прямым) произведением множеств Х и Y.

Определение. Пусть Х и Y — два множества. Декартовым (или прямым) произведением множеств Х и Y называется множество Х  ´ Y, состоящие из всех упорядоченных пар (x, y), в которых первая компонента х принадлежит Х, а вторая компонента у принадлежит Y.

Таким образом, .

Пример 1. Составить всевозможные маршруты от Минска и Киева до Варшавы, Будапешта, Праги.

Для этого введем множество Х = {Минск, Киев} и Y = {Варшава, Будапешт, Прага}. Задача будет решена, если найдем декартовое произведение множеств Х и Y:

Х ´ Y = {(Минск, Варшава), (Минск, Будапешт), (Минск, Прага),
(Киев, Варшава), (Киев, Будапешт), (Киев, Прага)}.

Пример 2. Пусть Х = {1, 2, 3}, Y = {k, l}. Декартовое произведение Х ´ Y состоит из шести элементов:

Х ´ Y = {(1, k), (2, k), (3, k), (1, l), (2, l), (3, l)}.

Выпишем теперь декартовое произведение

Y ´ Х = {(k, 1), (k, 2), (k, 3), (l, 1), (l, 2), (l, 3)}.

 

Таким образом, Х ´ Y ¹ Y ´ Х. Результат декартового произведения зависит от порядка сомножителей.

С помощью примера легко показать, что для операции декартового произведения не выполняется ассоциативный закон

Х ´ (Y ´ Z) ¹ (Х ´ Y) ´ Z.

Для операции декартового произведения относительно операции объединения множеств справедлив дистрибутивный закон:

Х ´ (Y È Z) = Х ´ Y È Х ´ Z.

Доказательство равенства двух множеств, как известно, состоит из двух частей.

1. Пусть х Î Х ´ (Y È Z). Докажем, что х Î Х ´ Y È X ´ Z .
По определению декартового произведения, х является упорядоченной парой , где ,  или .

Если , , то пара  и, следовательно,
х Î Х ´ Y È X ´ Z . Аналогично, если , , то  и, следовательно, .

2. Пусть . Нужно доказать, что . Доказательство предоставляем читателю.

Для операции декартова произведения относительно операции вычитания и пересечения множеств также справедлив дистрибутивный закон:

.

Доказательство этих равенств предлагаем читателю.

Элементы декартового произведения двух конечных множеств Х, Y удобно записывать в виде прямоугольной таблицы, где по вертикали записывают элементы множества Х, а по горизонтали — элементы множества Y. На пересечении соответствующих строк и столбиков записываются элементы множества Х ´ Y.

Пример 3. Найдем декартовое произведение множеств Х и Y, если
Х = {1, 2, 3, 4} и Y = {а, b, c}.

 

Y       Х	а	b	с
1	(1, а)	(1, b)	(1, с)
2	(2, а)	(2, b)	(2, с)
3	(3, а)	(3, b)	(3, с)
4	(4, а)	(4, b)	(4, с)

 

Таким образом,

Х ´ Y = {(1, a), (2, a), (3, a), (4, a), (1, b), (2, b), (3, b), (4, b),

(1, c), (2, c), (3, c), (4, c)}.

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

Пусть даны множества Х₁, Х₂, …, Х _n . Возьмем элемент х₁ Î Х₁, х₂ Î Х₂, …, х _n Î Х _n,  и образуем упорядоченную систему из  элементов
(х₁, х₂, …, х _n) которую называют кортежем длины . Кортежи длины 2 называются парами, длины 3 — тройками и т.д., длины  — энками ( –ками). Два кортежа называются равными, если они имеют одинаковую длину и одинаковые компоненты с одинаковыми номерами.

При помощи понятия кортежа можно определить понятие декартового произведения  множеств.

Определение. Декартовым произведением  множеств Х₁, Х₂, …, Х _n называется множество всевозможных кортежей (х₁, х₂ , …, х _n) длины n таких, что

х₁ Î Х₁, х₂ Î Х₂, …, х _n Î Х _n.

.

Так, например, декартовым произведением Х ´ Y ´ Z множеств Х = {1, 2}, Y = {3, 4, 5} и Z = {4, 6} является множество

Х ´ Y ´ Z = {(1, 3, 4), (1, 3, 6), (1, 4, 4), (1, 4, 6), (1, 5, 4), (1, 5, 6),
                       (2, 3, 4), (2, 3, 6), (2, 4, 4), (2, 4, 6), (2, 5, 4), (2, 5, 6)}.

 

Упражнения

 

1. Пусть А={а, о, у}, В={к, н}. Перечислите элементы множеств А ´ В и
В ´ А.

2. Даны множества А = {м, а, в}, В = {л, о}. Является ли множество С декартовым произведением множеств А и В, если:

а) С={(м, л), (м, о), (а, л), (а, о), (л, в), (в, о)};

б) С={(м, л), (м, о), (а, л), (а, о), (в, л), (в, о)};

в) С={(м, о), (а, о), (в, о), (м, л), (а, л)}?

3. Известно, что Х ´ Y = {(1,2), (2,1), (3,1), (4,1), (5,1), (6,1), (7,1), (7,2), (4,2), (6,2), (3,3), (6,3), (1,1), (1,3), (2,3), (3,2), (4,3), (5,2), (5,3), (7,2), (7,3)}.

Запишите множества Х, Y, Y ´ X.

4.

 

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: