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

«Декартов квадрат» перенаправляется сюда. О декартовых квадратах в теории категорий см. Декартов квадрат (теория категорий).

Декартово произведение ${\displaystyle \scriptstyle A\times B}$ наборов ${\displaystyle \scriptstyle A=\{x,y,z\}}$ и ${\displaystyle \scriptstyle B=\{1,2,3\}}$

В математика, конкретно теория множеств, то Декартово произведение из двух наборы А и B, обозначенный А × B,^[1] это набор всех заказанные пары (а, б) куда а в А и б в B.^[2] С точки зрения обозначение построителя множеств, то есть

${\displaystyle A\times B=\{\,(a,b)\mid a\in A\ {\mbox{ and }}\ b\in B\,\}.}$^[3][4]

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

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

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

Примеры

Колода карт

Стандартная колода из 52 карт

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

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

Костюмы × Ранги возвращает набор вида {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10), ..., (♣, 6), (♣, 5), (♣, 4), (♣, 3), (♣, 2)}.

Эти два множества различны, даже не пересекаются.

Двумерная система координат

Декартовы координаты примерных точек

Главный исторический пример - Декартова плоскость в аналитическая геометрия. Чтобы представить геометрические формы в числовом виде и извлечь числовую информацию из числовых представлений форм, Рене Декарт каждой точке на плоскости назначается пара действительные числа, назвал его координаты. Обычно первая и вторая составляющие такой пары называются ее Икс и у координаты соответственно (см. рисунок). Множество всех таких пар (т.е. декартово произведение ℝ × ℝ, где ℝ обозначает действительные числа), таким образом, назначается набору всех точек на плоскости.^{[нужна цитата ]}

Наиболее распространенная реализация (теория множеств)

Основная статья: Применение математики в теории множеств

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

Некоммутативность и неассоциативность

Позволять А, B, C, и D быть наборами.

Декартово произведение А × B не является коммутативный,

${\displaystyle A\times B\neq B\times A,}$^[5]

поскольку заказанные пары отменяются, если не выполняется хотя бы одно из следующих условий:^[7]

• А равно B, или же
• А или же B это пустой набор.

Например:

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

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

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

А = B = {1,2}

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

А = {1,2}; B = ∅

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

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

Строго говоря, декартово произведение не ассоциативный (если один из задействованных наборов не пуст).

${\displaystyle (A\times B)\times C\neq A\times (B\times C)}$

Если например А = {1}, тогда (А × А) × А = { ((1,1),1) } ≠ { (1,(1,1)) } = А × (А × А).

Пересечения, объединения и подмножества

Примеры наборов

А = {у ∈ ℝ  : 1 ≤ у ≤ 4}, B = {Икс ∈ ℝ: 2 ≤Икс ≤ 5},
и C = {Икс ∈ ℝ: 4 ≤Икс ≤ 7}, демонстрируя
А × (B∩C) = (А×B) ∩ (А×C),
А × (B∪C) = (А×B) ∪ (А×C), и

А × (B \ C) = (А×B) \ (А×C)

Примеры наборов

А = {Икс ∈ ℝ: 2 ≤Икс ≤ 5}, B = {Икс ∈ ℝ: 3 ≤Икс ≤ 7},
C = {у ∈ ℝ: 1 ≤у ≤ 3}, D = {у ∈ ℝ: 2 ≤у ≤ 4}, демонстрируя

(А∩B) × (C∩D) = (А×C) ∩ (B×D).

(А∪B) × (C∪D) ≠ (А×C) ∪ (B×D) можно увидеть на том же примере.

Декартово произведение удовлетворяет следующему свойству относительно перекрестки (см. средний рисунок).

${\displaystyle (A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)}$^[8]

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

${\displaystyle (A\cup B)\times (C\cup D)\neq (A\times C)\cup (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]}$

Вот несколько правил, демонстрирующих распределенность с другими операторами (см. Крайний левый рисунок):^[7]

${\displaystyle {\begin{aligned}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{aligned}}}$

${\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)\!,}$^[8]

куда ${\displaystyle A^{\complement }}$ обозначает абсолютное дополнение из А.

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

${\displaystyle {\text{if }}A\subseteq B{\text{, then }}A\times C\subseteq B\times C;}$

${\displaystyle {\text{if both }}A,B\neq \emptyset {\text{, then }}A\times B\subseteq C\times D\!\iff \!A\subseteq C{\text{ and }}B\subseteq D.}$^[9]

Мощность

Смотрите также: Кардинальная арифметика

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

А × B = {(a, 5), (a, 6), (b, 5), (b, 6)}.

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

|А × B| = |А| · |B|.^[5]

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

по аналогии

|А × B × C| = |А| · |B| · |C|

и так далее.

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

Декартовы произведения нескольких наборов

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

Декартово произведение можно обобщить на п-арное декартово произведение над п наборы Икс₁, ..., Икс_п как набор

${\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\}\}.}$

из п- пары. Если кортежи определены как вложенные упорядоченные пары, его можно отождествить с (Икс₁ × ... × Икс_п-1) × Икс_п. Если кортеж определен как функция на {1, 2, ..., п} что имеет ценность в я быть яth элемент кортежа, то декартово произведение Икс₁×...×Икс_п это набор функций

${\displaystyle \{x:\{1,\ldots ,n\}\to X_{1}\cup \ldots \cup X_{n}\ |\ x(i)\in X_{i}\ {\text{for every}}\ i\in \{1,\ldots ,n\}\}.}$

п-арная декартова степень

В Декартов квадрат набора Икс декартово произведение Икс² = Икс × ИксПримером может служить двумерный самолет р² = р × р куда р это набор действительные числа:^[2] р² это множество всех точек (Икс,у) куда Икс и у являются действительными числами (см. Декартова система координат ).

В п-арная декартова степень набора Икс, обозначенный ${\displaystyle X^{n}}$,^[1] можно определить как

${\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\}\}.}$

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

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

Бесконечные декартовы произведения

Можно определить декартово произведение произвольного (возможно бесконечный ) индексированная семья наборов. Если я есть ли набор индексов, и ${\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)(f(i)\in X_{i})\right\},}$

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

Для каждого j в я, функция

${\displaystyle \pi _{j}:\prod _{i\in I}X_{i}\to X_{j},}$

определяется ${\displaystyle \pi _{j}(f)=f(j)}$ называется jth карта проекции.

Декартова степень - декартово произведение, в котором все факторы Икс_я тот же набор Икс. В этом случае,

${\displaystyle \prod _{i\in I}X_{i}=\prod _{i\in I}X}$

это набор всех функций из я к Икс, и часто обозначается Икс^я. Этот случай важен при изучении кардинальное возведение в степень. Важный частный случай - это когда набор индексов ${\displaystyle \mathbb {N} }$, то натуральные числа: это декартово произведение представляет собой набор всех бесконечных последовательностей с яth член в соответствующем наборе Икс_я. Например, каждый элемент

${\displaystyle \prod _{n=1}^{\infty }\mathbb {R} =\mathbb {R} \times \mathbb {R} \times \cdots }$

можно представить как вектор со счетно бесконечным вещественным числом компонентов. Этот набор часто обозначают ${\displaystyle \mathbb {R} ^{\omega }}$, или же ${\displaystyle \mathbb {R} ^{\mathbb {N} }}$.

Другие формы

Сокращенная форма

Если несколько наборов перемножаются (например, Икс₁, Икс₂, Икс₃,…), Затем некоторые авторы^[11] выберите для сокращения декартово произведение просто ×Икс_я.

Декартово произведение функций

Если ж это функция от А к B и грамм это функция от Икс к Y, то их декартово произведение ж × грамм это функция от А × Икс к B × Y с

${\displaystyle (f\times g)(a,x)=(f(a),g(x)).}$

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

Цилиндр

Позволять ${\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} }$.

Определения вне теории множеств

Теория категорий

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

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

Теория графов

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

Смотрите также

• Бинарное отношение
• Конкатенация наборов строк
• Копродукт
• Перекрестное произведение
• Прямое произведение групп
• Пустой товар
• Евклидово пространство
• Экспоненциальный объект
• Финитарное отношение
• Соединение (SQL) § Перекрестное соединение
• Заказы на декартово произведение полностью упорядоченных множеств
• Аксиома власти (чтобы доказать существование декартова произведения)
• Продукт (теория категорий)
• Топология продукта
• Тип продукта
• Ультрапродукт

Рекомендации

1. «Исчерпывающий список символов теории множеств». Математическое хранилище. 11 апреля 2020 г.. Получено 5 сентября, 2020.
2. Вайсштейн, Эрик В. «Декартово произведение». mathworld.wolfram.com. Получено 5 сентября, 2020.
3. Уорнер, С. (1990). Современная алгебра. Dover Publications. п. 6.
4. Никамп, Дуэйн. «Декартово определение произведения». Math Insight. Получено 5 сентября, 2020.
5. «Декартово произведение». web.mnstate.edu. Получено 5 сентября, 2020.
6. "Декартово". Merriam-Webster.com. 2009. Получено 1 декабря, 2009.
7. Сингх, С. (27 августа 2009 г.). Декартово произведение. Получено с веб-сайта Connexions: http://cnx.org/content/m15207/1.5/
8. «Декартов продукт». PlanetMath.
9. Декартово произведение подмножеств. (15 февраля 2011 г.). ProofWiki. Получено 05:06, 1 августа 2011 г. из https://proofwiki.org/w/index.php?title=Cartesian_Product_of_Subsets&oldid=45868
10. Питер С. (1998). Ускоренный курс математики бесконечных множеств. Сент-Джонс Ревью, 44(2), 35–59. Получено 1 августа 2011 г. из http://www.mathpath.org/concepts/infinity.htm
11. Осборн, М., Рубинштейн, А., 1994. Курс теории игр. MIT Press.

внешняя ссылка

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