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

Математическое множество, образованное из двух заданных множеств

Декартово произведение множеств { x , y , z } и {1,2,3}

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

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

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

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

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

Строгое определение декартова произведения требует указания домена в нотации конструктора множеств . В этом случае домен должен содержать само декартово произведение. Для определения декартова произведения множеств и , с типичным определением Куратовским пары как , подходящим доменом является множество , где обозначает множество мощности . Тогда декартово произведение множеств и будет определяться как ^[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, ♣)}.

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\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]}$$

Вот некоторые правила, демонстрирующие дистрибутивность с другими операторами (см. крайний левый рисунок): [ 8 ^] где обозначает абсолютное дополнение A. $${\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)\!,}$$ ${\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 = {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) § Перекрестное объединение
• Порядки декартового произведения полностью упорядоченных множеств
• Внешний продукт
• Продукт (теория категорий)
• Топология продукта
• Тип продукта

Ссылки

1. Weisstein, Eric W. "Декартово произведение". MathWorld . Получено 5 сентября 2020 г. .
2. Уорнер, С. (1990). Современная алгебра . Dover Publications . стр. 6.
3. Найкамп, Дуэйн. «Определение декартового произведения». Math Insight . Получено 5 сентября 2020 г.
4. "Декартово произведение". web.mnstate.edu . Архивировано из оригинала 18 июля 2020 г. Получено 5 сентября 2020 г.
5. "Cartesian". Merriam-Webster.com . 2009. Получено 1 декабря 2009 .
6. Корри, С. "A Sketch of the Rudiments of Set Theory" (PDF) . Получено 5 мая 2023 г.
7. Голдберг, Сэмюэл (1986). Вероятность: Введение. Dover Books on Mathematics. Courier Corporation. стр. 41. ISBN 9780486652528.
8. Singh, S. (27 августа 2009 г.). Декартово произведение . Получено с веб-сайта Connexions: http://cnx.org/content/m15207/1.5/
9. Декартово произведение подмножеств. (15 февраля 2011 г.). ProofWiki . Получено 05:06, 1 августа 2011 г. с https://proofwiki.org/w/index.php?title=Декартово_произведение_подмножеств&oldid=45868
10. Питер С. (1998). Ускоренный курс математики бесконечных множеств. St. John's Review, 44 (2), 35–59. Получено 1 августа 2011 г. с сайта http://www.mathpath.org/concepts/infinity.htm
11. FR Drake, Теория множеств: Введение в большие кардиналы , стр. 24. Исследования по логике и основаниям математики, т. 76 (1978). ISBN 0-7204-2200-0.
12. Осборн, М. и Рубинштейн, А., 1994. Курс теории игр . MIT Press.

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

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