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

В математике , в частности в теории множеств , декартово произведение двух множеств A и B , обозначаемое A × B , представляет собой множество всех упорядоченных пар ( a , b ) , где a принадлежит A , а b принадлежит B. ^[1] В терминах нотации конструктора множеств это выглядит следующим образом: ^{[2] [3]}$${\displaystyle A\times B=\{(a,b)\mid a\in A\ {\mbox{ и }}\ b\in B\}.}$$

Таблицу можно создать, взяв декартово произведение набора строк и набора столбцов. Если взять декартово произведение строк × столбцов , ячейки таблицы будут содержать упорядоченные пары вида (значение строки, значение столбца) . ^[4]

Аналогично можно определить декартово произведение n множеств, также известное как n -кратное декартово произведение , которое может быть представлено n -мерным массивом, где каждый элемент является n - кортежем . Упорядоченная пара — это 2-кортеж или пара . Еще более общим образом можно определить декартово произведение индексированного семейства множеств.

Декартово произведение названо в честь Рене Декарта ^[5] , чья формулировка аналитической геометрии дала начало этой концепции, которая далее обобщается в терминах прямого произведения .

Строгое определение декартова произведения требует указания домена в нотации конструктора множеств . В этом случае домен должен содержать само декартово произведение. Для определения декартова произведения множеств и , с типичным определением Куратовским пары как , подходящим доменом является множество , где обозначает множество мощности . Тогда декартово произведение множеств и будет определяться как ^[6]${\displaystyle А}$${\displaystyle Б}$${\displaystyle (а,б)}$${\displaystyle \{\{а\},\{а,б\}\}}$${\displaystyle {\mathcal {P}}({\mathcal {P}}(A\cup B))}$${\displaystyle {\mathcal {P}}}$${\displaystyle А}$${\displaystyle Б}$$${\displaystyle A\times B=\{x\in {\mathcal {P}}({\mathcal {P}}(A\cup B))\mid \exists a\in A\ \exists b\in B:x=(a,b)\}.}$$

Иллюстративный пример — стандартная колода из 52 карт . Стандартные игральные карты {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2} образуют набор из 13 элементов. Масти карт {♠, ♥ , ♦ , ♣ } образуют набор из четырех элементов. Декартово произведение этих наборов возвращает набор из 52 элементов, состоящий из 52 упорядоченных пар , которые соответствуют всем 52 возможным игральным картам.

Ранги × Масти возвращают набор в форме {(A, ♠), (A,  ♥ ), (A,  ♦ ), (A, ♣), (K, ♠), ..., (3, ♣), (2, ♠), (2,  ♥ ), (2,  ♦ ), (2, ♣)}.

Suits × Ranks возвращает набор в виде {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10), ..., (♣, 6), (♣, 5), (♣, 4), (♣, 3), (♣, 2)}.

Эти два множества различны, даже не пересекаются , но между ними существует естественная биекция , при которой (3, ♣) соответствует (♣, 3) и так далее.

Основным историческим примером является декартова плоскость в аналитической геометрии . Для того чтобы представить геометрические фигуры численным способом и извлечь числовую информацию из числовых представлений фигур, Рене Декарт назначил каждой точке плоскости пару действительных чисел , называемых ее координатами . Обычно первый и второй компоненты такой пары называются ее координатами x и y соответственно (см. рисунок). Таким образом, множество всех таких пар (т. е. декартово произведение , с обозначением действительных чисел) назначается множеству всех точек плоскости. ^[7]${\displaystyle \mathbb {R} \times \mathbb {R} }$${\displaystyle \mathbb {R} }$

Формальное определение декартова произведения из теоретико-множественных принципов следует из определения упорядоченной пары . Наиболее распространенное определение упорядоченных пар, определение Куратовского , таково: . Согласно этому определению, является элементом , а является подмножеством этого множества, где представляет оператор множества мощности . Следовательно, существование декартова произведения любых двух множеств в ZFC следует из аксиом спаривания , объединения , множества мощности и спецификации . Поскольку функции обычно определяются как частный случай отношений , а отношения обычно определяются как подмножества декартова произведения, определение декартова произведения двух множеств обязательно предшествует большинству других определений.${\displaystyle (x,y)=\{\{x\},\{x,y\}\}}$${\displaystyle (x,y)}$${\displaystyle {\mathcal {P}}({\mathcal {P}}(X\cup Y))}$${\displaystyle X\times Y}$${\displaystyle {\mathcal {P}}}$

Пусть A , B , C и D — множества.

Декартово произведение A × B не является коммутативным , ^[4] поскольку упорядоченные пары меняются местами, если не выполняется хотя бы одно из следующих условий: ^[8]$${\displaystyle A\times B\neq B\times A,}$$

• A равно B , или
• A или B — пустое множество .

Например:

А = {1,2} ; В = {3,4}

А × В = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}

В × А = {3,4} × {1,2} = {(3,1), (3,2), (4,1), (4,2)}

А = В = {1,2}

А × В = В × А = {1,2} × {1,2} = {(1,1), (1,2), (2,1), (2,2)}

А = {1,2}; В = ∅

А × В = {1,2} × ∅ = ∅

В × А = ∅ × {1,2} = ∅

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

Декартово произведение удовлетворяет следующему свойству относительно пересечений (см. средний рисунок).$${\displaystyle (A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)}$$

В большинстве случаев приведенное выше утверждение неверно, если заменить пересечение на объединение (см. крайний правый рисунок).$${\displaystyle (A\чашка B)\times (C\чашка D)\neq (A\times C)\чашка (B\times D)}$$

На самом деле, у нас есть вот что:$${\displaystyle (A\times C)\cup (B\times D)=[(A\setminus B)\times C]\cup [(A\cap B)\times (C\cup D)]\cup [(B\setminus A)\times D]}$$

Для разности множеств мы также имеем следующее тождество:$${\displaystyle (A\times C)\setminus (B\times D)=[A\times (C\setminus D)]\cup [(A\setminus B)\times C]}$$

Вот некоторые правила, демонстрирующие дистрибутивность с другими операторами (см. крайний левый рисунок): [ 8 ^] где обозначает абсолютное дополнение A.$${\displaystyle {\begin{align}A\times (B\cap C)&=(A\times B)\cap (A\times C),\\A\times (B\cup C)&=(A\times B)\cup (A\times C),\\A\times (B\setminus C)&=(A\times B)\setminus (A\times C),\end{align}}}$$$${\displaystyle (A\times B)^{\complement}=\left(A^{\complement}\times B^{\complement}\right)\cup \left(A^{\complement}\times B\right)\cup \left(A\times B^{\complement}\right)\!,}$$${\displaystyle A^{\complement}}$

Другие свойства, связанные с подмножествами :

$${\displaystyle {\text{если }}A\subseteq B{\text{, то }}A\times C\subseteq B\times C;}$$

$${\displaystyle {\text{если оба }}A,B\neq \emptyset {\text{, то }}A\times B\subseteq C\times D\!\если и только если \!A\subseteq C{\text{ и }}B\subseteq D.}$$^[9]

Мощность множества — это количество элементов множества. Например, определим два множества: A = {a, b} и B = {5, 6} . Оба множества A и B состоят из двух элементов каждое. Их декартово произведение, записанное как A × B , дает новое множество, которое имеет следующие элементы:

А × В = {(а, 5), (а, 6), (б, 5), (б, 6)} .

где каждый элемент A парен каждому элементу B , и где каждая пара составляет один элемент выходного набора. Количество значений в каждом элементе результирующего набора равно количеству наборов, декартово произведение которых берется; в данном случае 2. Мощность выходного набора равна произведению мощностей всех входных наборов. То есть,

| А × В | = | А | · | В | . ^[4]

В этом случае | А × В | = 4

Сходным образом,

| А × В × С | = | А | · | В | · | С |

и так далее.

Множество A × B бесконечно , если либо A , либо B бесконечно, а другое множество не является пустым множеством. ^[10]

Декартово произведение можно обобщить до n -арного декартова произведения над n множествами X ₁ , ..., X _n как множество$${\displaystyle X_{1}\times \cdots \times X_{n}=\{(x_{1},\ldots ,x_{n})\mid x_{i}\in X_{i}\ {\text{for every}}\ i\in \{1,\ldots ,n\}\}}$$

из n -кортежей . Если кортежи определены как вложенные упорядоченные пары , их можно идентифицировать с помощью ( X ₁ × ... × X _{n −1} ) × X _n . Если кортеж определен как функция на {1, 2, ..., n }, которая принимает свое значение в i как i -й элемент кортежа, то декартово произведение X ₁ × ... × X _n является набором функций$${\displaystyle \{x:\{1,\ldots ,n\}\to X_{1}\cup \cdots \cup X_{n}\ |\ x(i)\in X_{i}\ {\text{for every}}\ i\in \{1,\ldots ,n\}\}.}$$

Декартов квадрат множества X — это декартово произведение X ² = X × X. Примером является двумерная плоскость R ² = R × R , где R — множество действительных чисел : ^[1] R ² — это множество всех точек ( x , y ) , где x и y — действительные числа (см. декартову систему координат ).

n- арная декартова степень множества X , обозначаемая , может быть определена как${\displaystyle X^{n}}$$${\displaystyle X^{n}=\underbrace {X\times X\times \cdots \times X} _{n}=\{(x_{1},\ldots ,x_{n})\ |\ x_{i}\in X\ {\text{for every}}\ i\in \{1,\ldots ,n\}\}.}$$

Примером этого является R ³ = R × R × R , где R снова является множеством действительных чисел ^[1] и, в более общем смысле, R ⁿ .

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

Можно определить декартово произведение произвольного (возможно, бесконечного ) индексированного семейства множеств. Если I — это любое индексное множество , а — семейство множеств, индексированных I , то декартово произведение множеств в определяется как множество всех функций, определенных на индексном множестве I, таких, что значение функции при определенном индексе i является элементом X _i . Даже если каждое из X _i непусто, декартово произведение может быть пустым, если не предполагается аксиома выбора , которая эквивалентна утверждению, что каждое такое произведение непусто. также может обозначаться . ^[11]${\displaystyle \{X_{i}\}_{i\in I}}$${\displaystyle \{X_{i}\}_{i\in I}}$$${\displaystyle \prod _{i\in I}X_{i}=\left\{\left.f:I\to \bigcup _{i\in I}X_{i}\ \right|\ \forall i\in I.\ f(i)\in X_{i}\right\},}$$ ${\displaystyle \prod _{i\in I}X_{i}}$${\displaystyle {\mathsf {X}}}$${\displaystyle {}_{i\in I}X_{i}}$

Для каждого j в I функция, определяемая как, называется j -й проекционной картой .$${\displaystyle \pi _{j}:\prod _{i\in I}X_{i}\to X_{j},}$$${\displaystyle \pi _{j}(f)=f(j)}$

Декартова степень — это декартово произведение, где все множители X _i являются одним и тем же множеством X . В этом случае — это множество всех функций от I до X , и часто обозначается как X ^I . Этот случай важен при изучении кардинального возведения в степень . Важным особым случаем является случай, когда множество индексов — это , натуральные числа : это декартово произведение — это множество всех бесконечных последовательностей с i -м членом в соответствующем множестве X _i . Например, каждый элемент из можно визуализировать как вектор со счетно бесконечными вещественными числовыми компонентами. Это множество часто обозначается как , или .$${\displaystyle \prod _{i\in I}X_{i}=\prod _{i\in I}X}$$${\displaystyle \mathbb {N} }$$${\displaystyle \prod _{n=1}^{\infty }\mathbb {R} =\mathbb {R} \times \mathbb {R} \times \cdots }$$${\displaystyle \mathbb {R} ^{\omega }}$${\displaystyle \mathbb {R} ^{\mathbb {N} }}$

Если несколько множеств умножаются вместе (например, X ₁ , X ₂ , X ₃ , ... ), то некоторые авторы ^[12] предпочитают сокращать декартово произведение просто как × X _i .

Если f — функция из X в A, а g — функция из Y в B , то их декартово произведение f × g — функция из X × Y в A × B, причем$${\displaystyle (f\times g)(x,y)=(f(x),g(y)).}$$

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

Пусть — множество и . Тогда цилиндр относительно является декартовым произведением и .${\displaystyle A}$${\displaystyle B\subseteq A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B\times A}$${\displaystyle B}$${\displaystyle A}$

Обычно считается вселенной контекста и не учитывается. Например, если является подмножеством натуральных чисел , то цилиндром является .${\displaystyle A}$${\displaystyle B}$${\displaystyle \mathbb {N} }$${\displaystyle B}$${\displaystyle B\times \mathbb {N} }$

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

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

В теории графов декартово произведение двух графов G и H — это граф, обозначаемый как G × H , множество вершин которого является (обычным) декартовым произведением V ( G ) × V ( H ) и таким, что две вершины ( u , v ) и ( u ′, v ′) смежны в G × H , тогда и только тогда, когда u = u ′ и v смежно с v ′ в H , или v = v ′ и u смежно с u ′ в G . Декартово произведение графов не является произведением в смысле теории категорий. Вместо этого категориальное произведение известно как тензорное произведение графов .

• Аксиома степенного множества (для доказательства существования декартова произведения)
• Прямой продукт
• Пустой продукт
• Финитное отношение
• Объединение (SQL) § Перекрестное объединение
• Порядки декартового произведения полностью упорядоченных множеств
• Внешний продукт
• Продукт (теория категорий)
• Топология продукта
• Тип продукта

• Декартово произведение в ProvenMath
• «Прямой продукт», Энциклопедия математики , EMS Press , 2001 [1994]
• Как найти декартово произведение, Образовательный портал Академии