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

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

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

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

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

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

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

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

Формальное определение декартова произведения из теоретико-множественных принципов следует из определения упорядоченной пары . Наиболее распространенное определение упорядоченных пар — определение Куратовского — $(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 \times B$ не является коммутативным . $A\times B\neq B\times A,$ ^[4]потому что упорядоченные пары меняются местами, если не выполняется хотя бы одно из следующих условий: ^[8]

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

Например:

А = {1,2}

;

Б = {3,4}

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

B \times A = {3,4} \times {1,2} = {(3,1), (3,2), (4,1), (4,2)}

А = Б = {1,2}

А \times В = В \times А = {1,2} \times {1,2} = {(1,1), (1,2), (2,1), (2,2)}

А = {1,2}; Б = \emptyset

А \times В = {1,2} \times \emptyset = \emptyset

В \times А = \emptyset \times {1,2} = \emptyset

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

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

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

$А = [1,4]$ , $B = [2,5]$ и
$C = [4,7]$ , демонстрируя
$А \times (B \cap C) знак равно (А \times B) \cap (А \times C)$ ,
$А \times (B \cup C) знак равно (А \times B) \cup (А \times C)$ , и

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

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

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

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

Вот несколько правил, демонстрирующих дистрибутивность с другими операторами (см. крайнюю левую картинку): ^[8] ${\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.$ ^[9]

Мощность

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

А \times В = {(а,5), (а,6), (б,5), (б,6)}

.

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

| А \times Б | = | А | \cdot | Б |

. ^[4]

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

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

| А \times Б \times С | = | А | \cdot | Б | \cdot | С |

и так далее.

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

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

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

Декартово произведение можно обобщить до $n$ -арного декартова произведения по $n$ множествам $X 1, ..., 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 1 \times ... \times X n -1) \times X n$ . Если кортеж определен как функция на ${1, 2, ..., n$ }, которая принимает свое значение в $i$ в качестве $i$ -го элемента кортежа, то декартово произведение $X 1 \times ... \times 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. 2 знак равно Икс \times Икс$ .Примером может служить двумерная плоскость $R 2 = R \times R$ , где $R$ — множество действительных чисел : ^[1] $Р 2$ — это набор всех точек $(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\}\}.$

Примером этого является $Р. 3 = R \times R \times R$ , где $R$ снова представляет собой набор действительных чисел, ^[1] и в более общем плане $Р н$ .

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}$ . ^[11]

Для каждого $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 1, X 2, X 3, ...$ ), то некоторые авторы ^[12] решите сокращать декартово произведение просто $\times X i$ .

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

Если $f$ — функция от $X$ до $A$ , а $g$ — функция от $Y$ до $B$ , то их декартово произведение $f \times g$ — это функция от $X \times Y$ до $A \times 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 \times H$ , набор вершин которого является (обычным) декартовым произведением $V (G) \times V (H)$ и такой, что две вершины $(u, v)$ и $(u', v')$ смежны в $G \times H$ тогда и только тогда, когда $u = u'$ и $v$ смежны с $v$ ′ в $H$ , или $v = v'$ и $u$ смежны с $u$ ′ в $G$ . Декартово произведение графов не является произведением в смысле теории категорий. Вместо этого категориальное произведение известно как тензорное произведение графов .

См. также

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

Ссылки

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

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

[:1-1] Перейти обратно: ^а ^б ^с Вайсштейн, Эрик В. «Декартово произведение» . Математический мир . Проверено 5 сентября 2020 г.

[2] Уорнер, С. (1990). Современная алгебра . Дуврские публикации . п. 6.

[3] Никамп, Дуэйн. «Определение декартова произведения» . Математическое понимание . Проверено 5 сентября 2020 г.

[:2-4] Перейти обратно: ^а ^б ^с «Декартово произведение» . web.mnstate.edu . Архивировано из оригинала 18 июля 2020 года . Проверено 5 сентября 2020 г.

[5] «Картезианский» . Merriam-Webster.com . 2009 . Проверено 1 декабря 2009 г.

[6] Корри, С. «Очерк основ теории множеств» (PDF) . Проверено 5 мая 2023 г.

[7] Гольдберг, Сэмюэл (1986). Вероятность: Введение . Дуврские книги по математике. Курьерская компания. п. 41. ИСБН 9780486652528 .

[cnx-8] Перейти обратно: ^а ^б Сингх, С. (27 августа 2009 г.). Декартово произведение . Получено с веб-сайта Connexions: http://cnx.org/content/m15207/1.5/.

[9] Декартово произведение подмножеств. (15 февраля 2011 г.). ДоказательствоВики . Получено 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] Ф. Р. Дрейк, Теория множеств: введение в большие кардиналы , с. 24. Исследования по логике и основам математики, вып. 76 (1978). ISBN 0-7204-2200-0.

[12] Осборн М. и Рубинштейн А., 1994. Курс теории игр . МТИ Пресс.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v т и Теория множеств
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo