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

Упорядоченной последовательностью элементов (кортежем) называют строку символов, в которой каждому символу отведено фиксированное место. Число символов последовательности называется ее длиной. Примерами кортежей являются телефонные номера, государственные номера автомашин, номера команд микропроцессора. Из этих примеров следует, что элементами кортежа могут быть элементы разных множеств. Например, автомобильные номера содержат арабские цифры и буквы русского алфавита. Для множеств определена операция, порождающая такого рода элементы. Эта операция называется прямым или декартовым произведением множеств.

Декартовым произведением n множеств А₁, А₂,..., А_n называется множество, элементами которого являются упорядоченные последовательности элементов длины n (a₁, a₂,..., a_n), в каждой из которых присутствует ровно один элемент каждого из перемножаемых множеств.

Декартово произведение обозначается следующим образом:

А₁ х А₂ х... х А_n= {(a₁,a₂,..., a_n)| a₁ ÎA₁, a₂ Î A₂,..., a_n Î А_n)}.

Декартово произведение множества А на себя n раз называется n-ой декартовой степенью множества А., обозначается Аⁿ. Например, если R - множество действительных чисел, то R² - множество точек действительной плоскости.

Если n=0, то по определению А⁰ = {Æ}.

Декартово произведение не коммутативно. Например, если А={1, 2}, B={a, b}, то

А ´ В ={(1,a), (1,b), (2,a), (2,b)}, а B ´ A = {(a,1), (a,2), (b,1), (b,2)}.

Основное свойство упорядоченных последовательностей длины n (упорядоченных n-ок) состоит в том, что они равны тогда и только тогда, когда их элементы равны между собой. Например, (a₁, a₂ ,..., a_n)=(b_1, b₂,..., b_n) тогда и только тогда, когда a₁=b₁, a₂=b₂,..., a_n=b_n.

Упорядоченные двойки называются парами, тройки - тройками и т.д.

Упорядоченные множества, элементами которых являются вещественные числа, называются точками пространства или векторами. В этом смысле можно говорить о проекции точек на координатные оси. Проекция упорядоченной n-ки на i-ю координату определяется следующим образом:

Пр_i(a₁, a₂,..., a_n) = a_i.

Проекция упорядоченной последовательности более, чем на одну координату есть вектор. Например,

Пр_i,j,k(a₁, a₂,..., a_n)= (a_i, a_j, a_k).

Проекция кортежа на пустое множество координат называется пустым кортежем и обозначается

Пр _Æ (а₁, a₂,..., a_n) = L.

Кортеж длины n будем обозначать а⁽ⁿ⁾.

Если элементами множества являются кортежи фиксированной длины, то к такому множеству может быть применена операция проектирования. При этом проекция множества кортежей одинаковой длины на одну или более координат есть множество проекций кортежей исходного множества на эти координаты. Например, если М ={(1,2,3,4), (2,4,1,3), (3,2,4,5)}, то проекции этого множества на одну и две координаты имеют вид:

ПР₃M = {3,1,4}, ПР _1,3M = {(1,3), (2,1), (3,4)}.

Если М=А х В, то ПР ₁М = А, ПР₂М = В.

Если М Í А х В, то ПР₁М Í А, ПР₂М Í В.

Свойства декартова произведения:

(М₁ È М₂) х М₃ = (М₁ х М₃) È (М₂х М₃),

(М₁ Ç М₂) х М₃ = (М₁ х М₃) Ç (М₂х М₃),

(М₁\М₂) х М₃ = (М₁ х М₃) \ (М₂ х М₃),

(Т₁ х М₂) Ç (М₁ х Т₂) = Т₁ х Т₂, если T_i Í М_i.

Если в произведении один из сомножителей есть пустое множество, то впроизведение по определению пусто.