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

«Декартовский квадрат» перенаправляется сюда. Чтобы узнать о декартовых квадратах в теории категорий, см. Декартов квадрат (теория категорий) .

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

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

$A\times B=\{(a,b)\mid a\in A\ {\mbox{ and }}\ b\in B\}.$

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

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

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

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

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

$$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, ♥ ), (А, ♦ ), (А, ♣), (К, ♠), …, (3, ♣), (2, ♠), (2, ♥ ), (2,  ♦ ), (2, ♣)}.

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

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

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

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

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

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

Основная статья: Реализация математики в теории множеств

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

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

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

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

$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)}

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} = ∅

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

$(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 ) .

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

См. Также: Список установленных личностей и отношений.

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

А = [1,4], B = [2,5] и
C = [4,7], демонстрируя
А × ( B ∩ C ) знак равно ( А × B ) ∩ ( А × C ),
А × ( B ∪ C ) = ( А × B ) ∪ ( А × C ), и

А × ( B \ C ) знак равно ( А × B ) \ ( А × C )

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

А = [2,5], Б = [3,7], С = [1,3],
D = [2,4], демонстрируя

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

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

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

$(A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)$

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

$(A\cup B)\times (C\cup D)\neq (A\times C)\cup (B\times D)$

Фактически у нас есть следующее:

$(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]$

Для разности множеств мы также имеем следующее тождество:

$(A\times C)\setminus (B\times D)=[A\times (C\setminus D)]\cup [(A\setminus B)\times C]$

Вот несколько правил, демонстрирующих дистрибутивность с другими операторами (см. крайнюю левую картинку):

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

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

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

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

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

Кардинальность

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

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

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

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

| А × Б | = | А | · | Б |.

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

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

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

и так далее.

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

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

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

Декартово произведение можно обобщить до n -арного декартова произведения над n множествами X ₁ , ..., X _n как множество

$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 равно набор функций

$\{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. ² знак равно Икс × Икс .Примером может служить двумерная плоскость R ² = R × R , где R — множество действительных чисел : Р ² — это набор всех точек ( x , y ), где x и y — действительные числа (см. декартову систему координат ).

-арная n декартова степень множества X , обозначаемая $X^{n}$, можно определить как

$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 снова представляет собой набор действительных чисел, и в более общем плане Р ^н .

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

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

Основная статья: Прямой продукт

Можно определить декартово произведение произвольного (возможно, бесконечного ) индексированного семейства множеств. Если I — любой набор индексов и $\{X_{i}\}_{i\in I}$ является семейством множеств, индексированных I , то декартово произведение множеств в $\{X_{i}\}_{i\in I}$ определяется как

$\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 непусто, декартово произведение может быть пустым, если не предполагается аксиома выбора , которая эквивалентна утверждению, что каждое такое произведение непусто. $\prod _{i\in I}X_{i}$ также может быть обозначено ${\mathsf {X}}$${}_{i\in I}X_{i}$.

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

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

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

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

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

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

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

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

Другие формы

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

Если перемножаются несколько наборов (например, X ₁ , X ₂ , X ₃ , …), то некоторые авторы решите сокращать декартово произведение просто × X _i .

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

Если f — функция от X до A , а g — функция от Y до B , то их декартово произведение f × g — это функция от X × Y до A × B с

$(f\times g)(x,y)=(f(x),g(y)).$

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

Цилиндр

Позволять $A$ быть набором и $B\subseteq A$. Тогда цилиндр ​ $B$ относительно $A$ это декартово произведение $B\times A$ из $B$ и $A$.

Обычно, $A$ считается вселенной контекста и опускается. Например, если $B$ является подмножеством натуральных чисел $\mathbb {N}$, то цилиндр $B$ является $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]
• Как найти декартово произведение, Education Portal Academy