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

Mathematical set formed from two given sets

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

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

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

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

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

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

Теоретико-множественное определение

Строгое определение декартова произведения требует указания домена в нотации set-builder . В этом случае домен должен будет содержать само декартово произведение. Для определения декартова произведения множеств и с типичным определением Куратовского пары как , подходящей областью является набор где обозначает набор мощности . Тогда декартово произведение множеств и будет определяться как ^[6] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle (a,b)}$ ${\displaystyle \{\{a\},\{a,b\}\}}$ ${\displaystyle {\mathcal {P}}({\mathcal {P}}(A\cup B))}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle A}$ ${\displaystyle B}$

$${\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 карт.

Наглядным примером является стандартная колода из 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, ♣)}.

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

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

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

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

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

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

Формальное определение декартова произведения из теоретико-множественных принципов следует из определения упорядоченной пары . Наиболее распространенное определение упорядоченных пар — определение Куратовского — . Согласно этому определению, является элементом и является подмножеством этого набора, где представляет оператор набора мощности . Следовательно, существование декартова произведения любых двух множеств в 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 не является коммутативным .

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

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

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

Например:

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

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

B × A = {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} = ∅

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

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

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

Пересечения, союзы и подмножества

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

${\displaystyle (A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)}$

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

${\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)\!,}$

где обозначает абсолютное дополнение A . ${\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.}$^[8]

Мощность

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

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

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

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

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

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

| А × Б × С | = | А | · | Б | · | С |

и так далее.

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

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

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

Декартово произведение можно обобщить до 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\}\}.}$

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 , то декартово произведение наборов в определяется как ${\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\},}$

то есть набор всех функций, определенных в наборе индексов I, таких, что значение функции по конкретному индексу i является элементом X _i . Даже если каждое из X _i непусто, декартово произведение может быть пустым, если не предполагается аксиома выбора , которая эквивалентна утверждению, что каждое такое произведение непусто. также можно обозначить . ^[10] ${\displaystyle \prod _{i\in I}X_{i}}$ ${\displaystyle {\mathsf {X}}}$ ${\displaystyle {}_{i\in I}X_{i}}$

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

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

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

Декартова степень — это декартово произведение, в котором все факторы X _i представляют собой один и тот же набор X. В этом случае,

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

представляет собой набор всех функций от I до X и часто обозначается X ^I . Этот случай важен при изучении кардинального возведения в степень . Важным особым случаем является случай, когда набором индексов являются натуральные числа : это декартово произведение представляет собой набор всех бесконечных последовательностей с i-м членом в соответствующем наборе X _i . Например, каждый элемент ${\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 ₃ , …), то некоторые авторы ^[11] предпочитают сокращать декартово произведение как просто × 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) § Перекрестное соединение
• Заказы на декартово произведение полностью упорядоченных множеств
• Внешний продукт
• Продукт (теория категорий)
• Топология продукта
• Тип продукта

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

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

Внешние ссылки

• Декартово произведение в ProvenMath
• «Прямой продукт», Математическая энциклопедия , EMS Press , 2001 [1994]
• Как найти декартово произведение, Education Portal Academy