Прямое произведение множеств

Прямым (декартовым) произведением множеств X и Y называется множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X, а вторая принадлежит множеству Y.

Формально: X*Y = {<x,y>: x∈X, y∈Y}

Пример 2. Пусть X=<1,2>, Y=<1,3,4>

Тогда X*Y={<1,1>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4> } См. рис. а).

Пример 3. Пусть X и Y — отрезки вещественной оси. Прямое произведение X*Y изображается заштрихованным прямоугольником. См. рис. б).

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

X*Y ≠ Y*X

Прямое произведение множеств X₁, X₂,..., X_n — это множество, обозначаемое X₁*X₂*...*X_n и состоящее из всех тех и только тех кортежей длины n, правая компонента которых принадлежит X₁, вторая — X₂ и т.д.

Очевидно X*Y = ∅ ⇔ X = ∅ или Y = ∅.

Аналогично X₁*X₂*...*X_n = ∅ тогда и только тогда, когда хотя бы одно из множеств X₁, X₂,..., X_n является пустым.

Частным случаем прямого произведения является понятие степеней (декартовых) множества — прямое произведение одинаковых множеств

M^s=M*M*...*M, M¹=M, M⁰=∧.

Обычно R — множество вещественных чисел, тогда R²=R*R — вещественная плоскость и R³=R*R*R — трехмерное вещественное пространство.

Пример. A={a,b,c,d,e,f,g,h}, B={1,2,3,...,8}

Тогда A*B ={a₁, a₂, a₃,..., h7, h8} — множество обозначающее все 64 клеток шахматной доски.

Пример. Пусть A — конечное множество, элементами которого являются символы (буквы, цифры, знаки препинания и т.д.). Такие множества обычно называют алфавитами. Элементы множества a_n называются словами длины n в алфавите A. Множество всех символов в алфавите A — это множество A^* = ∪Aⁱ = A¹∪A²∪A³.... При написании слов не принято пользоваться ни запятыми, ни скобками, ни разделителями.

СЛОВО ⇔ <С,Л,О,В,О>

Теорема. Пусть a₁, a₂,..., a_n — конечные множества и |a₁| = m₁, |a₂|=m₂,..., |a_n|=m_n. Тогда мощность множества a₁*a₂*a₃*...*a_n равна произведению мощностей a₁, a₂,..., a_n