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

Прямое произведение (дека́ртово произведение) — множество, элементами которого являются все возможные упорядоченные пары элементов заданных двух непустых исходных множеств. Предполагается, что впервые «декартово» (в честь Рене Декарта) произведение двух множеств ввёл Георг Кантор^[1][2].

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

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

Произведение двух множеств

в	в	в	в	в	в	в	в
и	и	и	и	и	и	и	и
к	к	к	к	к	к	к	к
Произведение множества {в, и, к} на множество цветов радуги

Пусть даны два множества ${\displaystyle X}$ и ${\displaystyle Y}$. Прямое произведение множества ${\displaystyle X}$ и множества ${\displaystyle Y}$ есть такое множество ${\displaystyle X\times Y}$, элементами которого являются упорядоченные пары ${\displaystyle (x,y)}$ для всевозможных ${\displaystyle x\in X}$ и ${\displaystyle y\in Y}$. Упорядоченную пару, образованную из элементов ${\displaystyle a}$ и ${\displaystyle b}$, принято записывать, используя круглые скобки: ${\displaystyle (a,b)}$. Элемент ${\displaystyle a}$ называют первой координатой (компонентой) пары, а элемент ${\displaystyle b}$ — второй координатой (компонентой) пары.

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

Слово «упорядоченная» значит, что для ${\displaystyle x\neq y}$, ${\displaystyle (x,y)\neq (y,x)}$. Так, пары ${\displaystyle (a,b)}$ и ${\displaystyle (c,d)}$ равны в том и только том случае, если ${\displaystyle a=c}$ и ${\displaystyle b=d}$.

Важность «порядка» можно показать на примере обычной записи чисел: используя две цифры 3 и 5, можно записать четыре двузначных числа: 35, 53, 33 и 55. Несмотря на то, что числа 35 и 53 записаны с помощью одних и тех же цифр, эти числа различные. В том случае, когда важен порядок следования элементов, в математике говорят об упорядоченных наборах элементов.

В упорядоченной паре ${\displaystyle (a,b)}$ может быть, что ${\displaystyle a=b}$. Так, запись чисел 33 и 55 можно рассматривать как упорядоченные пары (3; 3) и (5; 5).

Отображения произведения множеств в его множители — ${\displaystyle \varphi \colon X\times Y\to X,\;\varphi (x,y)=x}$ и ${\displaystyle \psi \colon X\times Y\to Y,\;\psi (x,y)=y}$ — называют координатными функциями.

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

Строго говоря, тождество ассоциативности ${\displaystyle A\times (B\times C)=(A\times B)\times C}$ не имеет места, но в силу существования естественного взаимно однозначного соответствия (биекции) между множествами ${\displaystyle A\times (B\times C)}$ и ${\displaystyle (A\times B)\times C}$ этим различием можно зачастую пренебречь.

Декартова степень

000	001	002	010	011	012	020	021	022
100	101	102	110	111	112	120	121	122
200	201	202	210	211	212	220	221	222
{0, 1, 2}3, 33 = 27 элементов

${\displaystyle n}$-я декартова степень множества ${\displaystyle X}$ определяется для целых неотрицательных ${\displaystyle n}$, как ${\displaystyle n}$-кратное декартово произведение ${\displaystyle X}$ на себя^{[3] [4]}:

${\displaystyle {\begin{matrix}\underbrace {X\times X\times \ldots \times X} .\\n\end{matrix}}}$

Обычно обозначается как ${\displaystyle X^{n}}$ или ${\displaystyle X^{\times n}}$.

При положительных ${\displaystyle n}$ декартова степень ${\displaystyle X^{n}}$ состоит из всех упорядоченных наборов элементов из ${\displaystyle X}$ длины ${\displaystyle n}$. Так, вещественное пространство ${\displaystyle \mathbb {R} ^{3}}$ — множество кортежей из трех вещественных чисел — есть 3-я степень множества вещественных чисел ${\displaystyle \mathbb {R} .}$

При ${\displaystyle n=0}$, декартова степень ${\displaystyle X^{0},}$ по определению, содержит единственный элемент — пустой кортеж.

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

В общем случае, для произвольного семейства множеств (не обязательно различных) ${\displaystyle \{X_{i}\}_{i\in I}}$ (множество индексов может быть бесконечным) прямое произведение ${\displaystyle X=\prod _{i\in I}X_{i}}$ определяется как множество функций, сопоставляющих каждому элементу ${\displaystyle i\in I}$ элемент множества ${\displaystyle X_{i}}$:

${\displaystyle X=\prod _{i\in I}X_{i}=\{f\colon I\to \bigcup \limits _{i\in I}X_{i}\mid f(i)\in X_{i},i\in I\}.}$

Отображения ${\displaystyle \pi _{i}\colon X\to X_{i}\colon f\mapsto f(i)}$ называются проекциями, и определяются следующим образом: ${\displaystyle \pi _{i}\colon (a_{1},\dots a_{n})\mapsto a_{i}}$.

В частности, для конечного семейства множеств ${\displaystyle \{A_{1},\dots ,A_{n}\}}$ любая функция ${\displaystyle f:\{1,\dots ,n\}\to \bigcup \limits _{i=1}^{n}A_{i}}$ с условием ${\displaystyle f(i)\in A_{i}}$ эквивалентна некоторому кортежу длины ${\displaystyle n}$, составленному из элементов множеств ${\displaystyle \{A_{i}\}_{i=1}^{n}}$, так, что на ${\displaystyle i}$-ом месте кортежа стоит элемент множества ${\displaystyle A_{i}}$. Поэтому декартово (прямое) произведение конечного числа множеств ${\displaystyle \{A_{i}\}_{i=1}^{n}}$ может быть записано так:

${\displaystyle A_{1}\times \dots \times A_{n}=\{(a_{1},\dots ,a_{n})\mid a_{i}\in A_{i},i\in \{1,\dots ,n\}\}.}$

Теоретико-множественные операции с прямыми произведениями

Пусть заданы прямые произведения ${\displaystyle A=A_{1}\times \dots \times A_{n}}$ и ${\displaystyle B=B_{1}\times \dots \times B_{n}}$. Тогда

1. ${\displaystyle A\subseteq B}$, если и только если ${\displaystyle A_{i}\subseteq B_{i}}$ для всех ${\displaystyle i=1,2,\ldots ,n}$^[5];
2. ${\displaystyle A\cap B=(A_{1}\cap B_{1})\times \dots \times (A_{n}\cap B_{n})}$, при этом, если существует хотя бы один ${\displaystyle i}$, такой что ${\displaystyle A_{i}\cap B_{i}=\varnothing }$, то ${\displaystyle A\cap B=\varnothing }$ ^[5];
3. ${\displaystyle A\cup B\subseteq (A_{1}\cup B_{1})\times \dots \times (A_{n}\cup B_{n})}$, при этом равенство возможно лишь в следующих случаях^[6]:

${\displaystyle \quad \quad }$ — ${\displaystyle A\subseteq B}$ или ${\displaystyle B\subseteq A}$;

${\displaystyle \quad \quad }$ — для всех ${\displaystyle i=1,2,\ldots ,n\quad A_{i}=B_{i}\quad }$ за исключением одного из ${\displaystyle i}$.

${\displaystyle \quad \quad }$4. Дополнение прямого произведения ${\displaystyle A=A_{1}\times \dots \times A_{n}}$ можно вычислить^[7], если задан универсум ${\displaystyle U=X_{1}\times \dots \times X_{n}}$. Для упрощения выражений введем следующие обозначения. Обозначим прямое произведение в виде ограниченного квадратными скобками кортежа, в котором располагаются множества, из которых сформировано прямое произведение, например:

${\displaystyle A=A_{1}\times A_{2}\times \dots \times A_{n}=[A_{1}\quad A_{2}\quad \dots \quad A_{n}]}$.

В алгебре кортежей^[8] такое матрицеподобное представление прямых произведений названо C-кортежем.

С учетом этого объединение прямых произведений, заданных в одном и том же универсуме, можно выразить в виде матрицы, ограниченной квадратными скобками, в которой строки представляют прямые произведения, участвующие в объединении:

${\displaystyle A\cup B=(A_{1}\times A_{2}\times \dots \times A_{n})\cup (B_{1}\times B_{2}\times \dots \times B_{n})=\left[{\begin{array}{cccc}A_{1}&A_{2}&\dots &A_{n}\\B_{1}&B_{2}&\dots &B_{n}\end{array}}\right]}$.

Эта структура в алгебре кортежей названа C-системой.

Тогда дополнением прямого произведения ${\displaystyle A}$ будет следующая C-система, выраженная в виде матрицы размерности ${\displaystyle n\times n}$:

${\displaystyle {\overline {A}}=\left[{\begin{array}{ccccc}{\overline {A_{1}}}&X_{2}&\dots &X_{n-1}&X_{n}\\X_{1}&{\overline {A_{2}}}&\dots &X_{n-1}&X_{n}\\\dots &\dots &\dots &\dots &\dots \\X_{1}&X_{2}&\dots &{\overline {A_{n-1}}}&X_{n}\\X_{1}&X_{2}&\dots &X_{n-1}&{\overline {A_{n}}}\end{array}}\right]}$.

Диагональные компоненты этой матрицы ${\displaystyle {\overline {A_{i}}}}$ равны соответственно ${\displaystyle X_{i}\setminus A_{i}}$.

В алгебре кортежей диагональную C-систему ${\displaystyle {\overline {A}}}$, выражающую дополнение C-кортежа ${\displaystyle A}$, можно представить в сжатом виде как ограниченный перевернутыми квадратными скобками кортеж диагональных компонент:

${\displaystyle {\overline {A}}=]{\overline {A_{1}}}\quad {\overline {A_{2}}}\quad \dots \quad {\overline {A_{n}}}[}$.

Эта структура называется D-кортежем. Тогда дополнением C-системы ${\displaystyle R}$ будет структура ${\displaystyle {\overline {R}}}$, представленная матрицей той же размерности, ограниченной перевернутыми квадратными скобками, в которой все компоненты равны дополнениям компонент исходной матрицы ${\displaystyle R}$. Данная структура названа D-системой и вычисляется при необходимости как пересечение содержащихся в ней D-кортежей. Например, если задана C-система

${\displaystyle R_{1}=\left[{\begin{array}{cccc}A_{1}&A_{2}&\dots &A_{n}\\B_{1}&B_{2}&\dots &B_{n}\end{array}}\right]}$,

то ее дополнением будет D-система

${\displaystyle {\overline {R_{1}}}=\left]{\begin{array}{cccc}{\overline {A_{1}}}&{\overline {A_{2}}}&\dots &{\overline {A_{n}}}\\{\overline {B_{1}}}&{\overline {B_{2}}}&\dots &{\overline {B_{n}}}\end{array}}\right[}$.

Рассмотрим некоторые новые соотношения для структур с прямыми произведениями, полученные в процессе исследования свойств алгебры кортежей^[9]. Однотипными называются структуры, заданные в одном и том же универсуме.

Пересечение C-систем. Пусть даны однотипные C-системы ${\displaystyle P}$ и ${\displaystyle Q}$. Результатом их пересечения будет C-система, содержащая все непустые пересечения каждого C-кортежа из ${\displaystyle P}$ с каждым C-кортежем из ${\displaystyle Q}$.

Проверка включения C-кортежа в D-кортеж. Для C-кортежа ${\displaystyle P=[P_{1}\quad P_{2}\quad \cdots \quad P_{N}]}$ и D-кортежа и ${\displaystyle Q=]Q_{1}\quad Q_{2}\quad \cdots \quad Q_{N}[}$ справедливо ${\displaystyle P\subseteq Q}$, если и только если по крайней мере для одного ${\displaystyle i}$ соблюдается ${\displaystyle P_{i}\subseteq Q_{i}}$.

Проверка включения C-кортежа в D-систему. Для C-кортежа ${\displaystyle P}$ и D-системы ${\displaystyle Q}$ справедливо ${\displaystyle P\subseteq Q}$, если и только если для каждого D-кортежа ${\displaystyle Q_{i}}$ из ${\displaystyle Q}$ выполняется ${\displaystyle P\subseteq Q_{i}}$.

Прямое произведение отображений

Пусть ${\displaystyle f}$ — отображение из ${\displaystyle A}$ в ${\displaystyle B}$, а ${\displaystyle g}$ — отображение из ${\displaystyle X}$ в ${\displaystyle Y}$. Их прямым произведением ${\displaystyle f\times g}$ называется отображение из ${\displaystyle A\times X}$ в ${\displaystyle B\times Y}$: ${\displaystyle (f\times g)(a,\;x)=(f(a),\;g(x))}$.

Аналогично вышеизложенному, данное определение обобщается на многократные и бесконечные произведения.

Воздействие на математические структуры

Прямое произведение групп

Основная статья: Прямое произведение групп

Прямое (декартово) произведение двух групп ${\displaystyle (G,*)}$ и ${\displaystyle (H,\circ )}$ — это группа из всех пар элементов ${\displaystyle (g,h)}$ с операцией покомпонентного умножения: ${\displaystyle (g_{1},h_{1})\times (g_{2},h_{2})=(g_{1}*g_{2},h_{1}\circ h_{2})}$. Эта группа обозначается как ${\displaystyle G\times H}$. Ассоциативность операции умножения в группе ${\displaystyle G\times H}$ следует из ассоциативности операций перемножаемых групп. Сомножители ${\displaystyle G}$ и ${\displaystyle H}$ изоморфны двум нормальным подгруппам своего произведения, ${\displaystyle \{(g,1_{H})\mid g\in G\}}$ и ${\displaystyle \{(1_{G},h)\mid h\in H\}}$ соответственно. Пересечение этих подгрупп состоит из одного элемента ${\displaystyle (1_{G},1_{H})}$, который является единицей группы-произведения. Координатные функции произведения групп являются гомоморфизмами.

Это определение распространяется на произвольное число перемножаемых групп. В случае конечного числа прямое произведение изоморфно прямой сумме. Отличие возникает при бесконечном числе множителей.

В общем случае, ${\displaystyle {\overline {\prod _{i\in I}}}G_{i}=\{f\colon I\to \bigcup _{i\in I}G_{i}\}}$, где ${\displaystyle f(i)\in G_{i}}$ и ${\displaystyle (f_{1}\times f_{2})(i)=f_{1}(i)*f_{2}(i)}$. (Операция в правой части — это операция группы ${\displaystyle G_{i}}$). Единицей группы-произведения будет последовательность, составленная из единиц всех перемножаемых групп: ${\displaystyle (1_{i}),\;i\in I}$. Например, для счётного числа групп: ${\displaystyle {\overline {\prod _{i\in \mathbb {N} }}}\mathbb {Z} _{2}=(2^{\mathbb {N} },\;\operatorname {xor} )}$, где в правой части стоит множество всех бесконечных двоичных последовательностей.

Подгруппа на множестве всех ${\displaystyle f}$, носитель которых (то есть множество ${\displaystyle \mathrm {supp} \,(f)=\{i\in I\mid f(i)\neq 1_{i}\}}$) конечен, называется прямой суммой. Например, прямая сумма того же самого набора множеств ${\displaystyle \prod _{i\in \mathbb {N} }\mathbb {Z} _{2}\ =\ (\mathbb {N} ,\;\operatorname {xor} )}$ содержит все двоичные последовательности с конечным числом единиц, а их можно трактовать как двоичные представления натуральных чисел.

Декартово произведение индексированной системы групп есть её прямое произведение в категории Grp.

Прямая сумма индексированной системы групп есть её копроизведение в категории Grp.

Прямое произведение других алгебраических структур

Аналогично произведению групп можно определить произведения колец, алгебр, модулей и линейных пространств, причём в определении прямого произведения ${\displaystyle 1_{i}}$ (см. выше) следует заменить нулём. Определение произведения двух (или конечного числа) объектов совпадает с определением прямой суммы. Однако, вообще говоря, прямая сумма отличается от прямого произведения: например, прямое произведение счётного множества копий ${\displaystyle \mathbb {R} }$ есть пространство всех последовательностей действительных чисел, тогда как прямая сумма — пространство тех последовательностей, у которых только конечное число членов ненулевые (так называемых финитных последовательностей).

Прямое произведение векторных пространств

Декартово произведение ${\displaystyle U\times V}$ двух векторных пространств ${\displaystyle U}$ и ${\displaystyle V}$ над общим полем ${\displaystyle F}$ — это множество упорядоченных пар векторов ${\displaystyle \left\{\left(u,v\right)\mid u\in U\wedge v\in V\right\}}$, то есть теоретико-множественное декартово произведение множеств векторов из ${\displaystyle U}$ и ${\displaystyle V}$, с линейностью, заданной покоординатно: ${\displaystyle \left(a,b\right)+\left(c,d\right)=\left(a+c,b+d\right)}$, ${\displaystyle \mathrm {\alpha } \left(a,b\right)=\left(\mathrm {\alpha } a,\mathrm {\alpha } b\right)}$.

Данное определение распространяется на любую индексированную систему линейных (векторных) пространств: декартовым произведением индексированной системы векторных пространств над общим полем является теоретико-множественное декартово произведение множеств векторов сомножителей, на котором задана покоординатная линейность, то есть при суммировании суммируются все проекции, при умножении на число все проекции умножаются на это число: ${\displaystyle c=a+b\leftrightarrow \forall i:c_{i}=a_{i}+b_{i}}$, ${\displaystyle b=\mathrm {\alpha } a\leftrightarrow \forall i:b_{i}=\mathrm {\alpha } a_{i}}$.

Декартово произведение индексированной системы линейных пространств есть её прямое произведение в категории ${\displaystyle \operatorname {Vec} _{F}}$, где ${\displaystyle F}$ есть подлежащее поле системы.

Прямая сумма векторных пространств есть такое подмножество их декартова произведения, элементы которого имеют лишь конечное число отличных от нуля проекций ${\displaystyle \bigoplus {A}=\left\{a\in \prod {A}\mid \left\vert \left\{i\in \operatorname {dom} A\mid a_{i}\neq 0\right\}\right\vert <\aleph _{0}\right\}}$, где ${\displaystyle \operatorname {dom} A}$ есть индексное множество индексированной системы ${\displaystyle A}$. Для конечного числа слагаемых прямая сумма не отличается от декартова произведения.

Прямая сумма индексированной системы линейных пространств есть её копроизведение в категории ${\displaystyle \operatorname {Vec} _{F}}$, где ${\displaystyle F}$ есть подлежащее поле системы.

Прямое произведение топологических пространств

Основная статья: Произведение топологических пространств

Пусть ${\displaystyle X}$ и ${\displaystyle Y}$ — два топологических пространства. Топология декартова произведения ${\displaystyle X\times Y}$ задаётся на их теоретико-множественном произведении, как бесструктурных множеств, базой, состоящей из всевозможных произведений ${\displaystyle U\times V}$, где ${\displaystyle U}$ — открытое подмножество ${\displaystyle X}$ и ${\displaystyle V}$ — открытое подмножество ${\displaystyle Y}$.

Определение легко обобщается на случай произведения нескольких пространств.

Для произведения бесконечного набора сомножителей определение усложняется: пусть ${\displaystyle X}$ есть индексированная система топологических пространств, ${\displaystyle B=\prod {\overline {X}}}$ — бесструктурное произведение элементов ${\displaystyle X}$, как множеств. Определим цилиндр, восставленный над ${\displaystyle U\subseteq X_{i}}$, как множество всех точек из ${\displaystyle B}$, чьи ${\displaystyle i}$-е проекции лежат в ${\displaystyle U}$, то есть ${\displaystyle \operatorname {Cyl} \left(i,\;U\right)=\left\{x\in B\mid x_{i}\in U\right\}}$, где ${\displaystyle i\in \operatorname {dom} X}$ и ${\displaystyle \operatorname {dom} X}$ есть индексное множество индексированной системы ${\displaystyle X}$. Топология произведения будет задана на предбазе из цилиндров, восставленных надо всеми открытыми множествами всех топологий из набора ${\displaystyle X}$: ${\displaystyle \left\{\operatorname {Cyl} \left(i,\;U\right)\mid i\in \operatorname {dom} X\land U\in \operatorname {T} \left(X_{i}\right)\right\}}$, где ${\displaystyle \operatorname {T} \left(X_{i}\right)}$ есть совокупность всех отрытых множеств (топология) пространства ${\displaystyle X_{i}}$, то есть задаваться базой, составленной из всевозможных пересечений конечного числа открытых цилиндров. Данная топология является «контрвариантно» наведённой проекторами — это минимальная топология на теоретико­‑множественном декартовом произведении, при которой все проекторы непрерывны (такая топология аналогична компактно-открытой топологии пространств отображений, если считать индексное множество ${\displaystyle I}$ имеющим дискретную топологию).

Декартово произведение индексированной системы топологических пространств есть её прямое произведение в категории ${\displaystyle \operatorname {Top} }$.

Прямая сумма топологий строится на бесструктурной прямой сумме пространств, как множеств точек. Открытыми в ней являются все множества, пересечения которых со всеми слагаемыми открыты. Данная топология является «ковариантно» наведённой копроекторами — это максимальная топология на теоретико­‑множественной прямой сумме, при которой все копроекторы (то есть вложения слагаемых в сумму) непрерывны.

Прямая сумма индексированной системы топологических пространств есть её копроизведение в категории ${\displaystyle \operatorname {Top} }$.

Теорема Тихонова утверждает компактность произведений любого количества компактных пространств; однако для бесконечных произведений её не удаётся доказать без использования аксиомы выбора (или равносильных ей утверждений теории множеств).

Также теорема Александрова показывает, что любое топологическое пространство можно вложить в (бесконечное) произведение связных двоеточий, если только выполнена аксиома Колмогорова.

Прямое произведение графов

Основная статья: Прямое произведение графов

	—	
	—	
		
	—	

Множество вершин прямого произведения двух графов ${\displaystyle G}$ и ${\displaystyle H}$ задаётся как произведение вершин графов сомножителей. Рёбрами будут соединены следующие па́ры вершин:

• ${\displaystyle (g,\;h)(g',\;h)}$, где ${\displaystyle g}$ и ${\displaystyle g'}$ — соединённые ребром вершины графа ${\displaystyle G}$, а ${\displaystyle h}$ — произвольная вершина графа ${\displaystyle H}$;
• ${\displaystyle (g,\;h)(g,\;h')}$, где ${\displaystyle g}$ — произвольная вершина графа ${\displaystyle G}$, а ${\displaystyle h}$ и ${\displaystyle h'}$ — соединённые ребром вершины графа ${\displaystyle H}$.

Иначе говоря, множество рёбер произведения графов является объединением двух произведений: рёбер первого на вершины второго, и вершин первого на рёбра второго.

Вариации и обобщения

Идея прямого произведения получила дальнейшее развитие в теории категорий, где она послужила основой для понятия произведения объектов. Неформально, произведение двух объектов ${\displaystyle A}$ и ${\displaystyle B}$ — это наиболее общий объект в данной категории, для которого существуют проекции на ${\displaystyle A}$ и ${\displaystyle B}$. Во многих категориях (множеств, групп, графов, …) произведением объектов является именно их прямое произведение. Важно, что в большинстве случаев важно не столько конкретное определение прямого произведения, сколько указанное выше свойство универсальности. Различные определения будут давать при этом изоморфные объекты.

Примечания

1. Бурбаки, 2013, с. 307.
2. Cantor, 1932, с. 286—287.
3. Бурбаки, 2013, с. 115.
4. Эдельман, 1975, с. 10.
5. Бурбаки, 2013, с. 117.
6. Кулик, 2020, с. 77.
7. Кулик, 2020, с. 83.
8. Кулик, 2020, с. 67.
9. Кулик, 2020, с. 134—139.

Литература

• Бурбаки Н. Основные структуры анализа. Книга 1. Теория множеств. — М.: Книга по требованию, 2013. — 460 с.
• Кулик Б. А. Логика и математика: просто о сложных методах логического анализа. — СПб.: Политехника, 2020. — 141 с. — ISBN 978-5-7325-1166-6.
• Эдельман С. Л. Математическая логика. — М.: Высшая школа, 1975. — 176 с.
• Cantor G. Gesammelte Abhandlungen. — Berlin: Springer, 1932. — 486 с.