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

редактировать

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

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

A × B = {(a, b) ∣ a ∈ A и b ∈ B}. {\ displaystyle A \ times B = \ {\, (a, b) \ mid a \ in A \ {\ t_dv {and}} \ b \ in B \, \}.}A \ times B = \ {\, ​​(a, b) \ mid a \ in A \ {\ t_dv {и}} \ b \ in B \, \}.

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

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

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

Содержание

  • 1 Примеры
    • 1.1 Колода карт
    • 1.2 Двумерная система координат
  • 2 Наиболее распространенная реализация (теория множеств)
    • 2.1 Некоммутативность и неассоциативность
    • 2.2 Пересечения, объединения и подмножества
    • 2.3 Мощность
  • 3 Декартовы произведения нескольких множеств
    • 3.1 Декартово произведение n-мерного
    • 3,2 Декартово n-мерное значение
    • 3.3 Бесконечное декартово произведение
  • 4 Другие формы
    • 4.1 Сокращенная форма
    • 4.2 Декартово произведение функций
    • 4.3 Цилиндр
  • 5 Определения вне теории множеств
    • 5.1 Теория категорий
    • 5.2 Теория графов
  • 6 См. Также
  • 7 Ссылки
  • 8 Внешние ссылки

Примеры

Колода карт

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

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

Ranks × Suits возвращает набор вида {(A, ♠), (A, ♥), (A, ♦), (A, ♣), (K, ♠),..., (3, ♣), (2, ♠), (2, ♥), (2, ♦), (2, ♣)}.

Suits × Ranks возвращает набор вида {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10),..., (♣, 6), (♣, 5), (♣, 4), (♣, 3), (♣, 2)}.

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

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

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

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

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

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

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

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

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

A × B ≠ B × A, {\ displaystyle A \ times B \ neq B \ times A,}A \ times B \ neq B \ times A,

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

Для пример:

A = {1,2}; B = {3,4}
A × B = {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) }
A = B = {1,2}
A × B = B × A = {1,2} × {1,2} = {(1,1), (1,2), (2,1), (2,2)}
A = {1,2}; B = ∅
A × B = {1,2} × ∅ = ∅
B × A = ∅ × {1,2} = ∅

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

(A × B) × C ≠ A × (B × C) {\ displaystyle (A \ times B) \ times C \ neq A \ times (B \ times C)}(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).

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

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

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

A × (B \ C) = (A × B) \ (A × C) Примеры наборов.

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

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

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

(A ∩ B) × (C ∩ D) знак равно (A × C) ∩ (B × D) {\ displaystyle (A \ cap B) \ times (C \ cap D) = (A \ times C) \ cap (B \ times D)}(A \ cap B) \ раз (C \ крышка D) = (A \ раз C) \ cap (B \ times D)

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

(A ∪ B) × (C ∪ D) ≠ (A × C) ∪ (B × D) {\ displaystyle (A \ cup B) \ times (C \ cup D) \ neq (A \ times C) \ cup (B \ times D)}(A \ cup B) \ times (C \ cup D) \ neq (A \ times C) \ чашка (B \ times D)

На самом деле, мы имеем:

(A × C) ∪ (B × D) = [(A ∖ B) × C] ∪ [(A ∩ B) × (C ∪ D)] ∪ [(B ∖ A) × 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]}(A \ times C) \ чашка (B \ times D) = [(A \ setminus B) \ times C] \ cup [(A \ cap B) \ times (C \ cup D)] \ cup [(B \ setminus A) \ times D]

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

(A × C) ∖ (B × D) знак равно [A × (C ∖ D)] ∪ [(A ∖ B) × C] {\ displaystyle (A \ times C) \ setminus (B \ times D) = [A \ times (C \ setminus D)] \ cup [(A \ setminus B) \ times C]}(A \ раз C) \ setminus (B \ times D) = [A \ times (C \ setminus D)] \ cup [(A \ setminus B) \ times C]

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

A × (B ∩ C) = (A × B) ∩ (A × C), A × (B ∪ C) = (A × B) ∪ (A × C), A × (B ∖ C) = (A × B) ∖ (A × C), {\ Displaystyle {\ begin {выровнено} A \ times (B \ cap C) = (A \ times B) \ cap (A \ times C), \\ A \ times (B \ cup C) = (A \ times B) \ чашка (A \ times C), \\ A \ times (B \ setminus C) = (A \ times B) \ setminus (A \ times C), \ end {align}}}{\ displaystyle {\ begin {align} 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 {align}}}
(A × B) ∁ = (A ∁ × B ∁) ∪ (A ∁ × B) ∪ (A × B ∁), { \ Displaystyle (A \ times B) ^ {\ complement} = \ left (A ^ {\ complement} \ times B ^ {\ complement} \ right) \ cup \ left (A ^ {\ complement} \ times B \ right) \ чашка \ влево (A \ times B ^ {\ complement} \ right),}{\ displaystyle (A \ times B) ^ {\ complement} = \ left (A ^ {\ complement} \ times B ^ {\ complement} \ right) \ cup \ left (A ^ {\ complement} \ times B \ right) \ чашка \ left (A \ times B ^ {\ complement} \ right),}

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

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

Если A ⊆ B, то A × C ⊆ B × C; {\ displaystyle {\ text {If}} A \ substeq B {\ text {, then}} A \ times C \ substeq B \ times C;}{\ displaystyle {\ text {If}} A \ substeq B {\ текст {, затем}} A \ times C \ substeq B \ times C;}
если оба A, B ≠ ∅, то A × B ⊆ C × D ⟺ A ⊆ C и B ⊆ D. {\ displaystyle {\ text {если оба}} A, B \ neq \ emptyset {\ text {, then}} A \ times B \ substeq C \ times D \ iff A \ substeq C {\ text {and}} B \ substeq D.}{\ displaystyle {\ text {if both}} A, B \ neq \ emptyset {\ text {, затем}} A \ times B \ substeq C \ times D \ iff A \ substeq C {\ text {и}} B \ substeq D.}

Мощность

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

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

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

| A × B | = | A | · | B |.

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

Аналогично

| A × B × C | = | A | · | B | · | C |

и так далее.

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

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

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

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

X 1 × ⋯ × X n = {(x 1,…, xn) ∣ xi ∈ X i для любого i ∈ {1,…, n}}. {\ Displaystyle X_ {1} \ times \ cdots \ times X_ {n} = \ {(x_ {1}, \ ldots, x_ {n}) \ mid x_ {i} \ in X_ {i} \ {\ text {для каждого}} \ i \ in \ {1, \ ldots, n \} \}.}{\ displaystyle X_ {1} \ times \ cdots \ раз X_ {n} = \ {(x_ {1}, \ ldots, x_ {n}) \ mid x_ {i} \ in X_ {i} \ {\ text {для каждого}} \ i \ in \ {1, \ ldots, n \} \}.}

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

{x: {1,…, n} → X 1 ∪… ∪ X n | x (i) ∈ X i для любого i ∈ {1,…, n}}. {\ displaystyle \ {x: \ {1, \ ldots, n \} \ к X_ {1} \ cup \ ldots \ cup X_ {n} \ | \ x (i) \ in X_ {i} \ {\ text {для каждого}} \ i \ in \ {1, \ ldots, n \} \}.}{\ displaystyle \ {x: \ { 1, \ ldots, n \} \ в X_ {1} \ cup \ ldots \ cup X_ {n} \ | \ x (i) \ in X_ {i} \ {\ text {для каждого}} \ i \ in \ {1, \ ldots, n \} \}.}

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

Декартов квадрат множества X равен декартово произведение X = X × X. Примером является двумерная плоскость R= R× R, где R - это набор действительных чисел, :R- это набор всех точек ( x, y), где x и y - действительные числа (см. декартова система координат ).

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

X n = X × X × ⋯ × X ⏟ n = {(x 1,…, xn) | x i ∈ X для любого i ∈ {1,…, n}}. {\ displaystyle X ^ {n} = \ underbrace {X \ times X \ times \ cdots \ times X} _ {n} = \ {(x_ {1}, \ ldots, x_ {n}) \ | \ x_ { i} \ in X \ {\ text {для каждого}} \ i \ in \ {1, \ ldots, n \} \}.}{\ displaystyle X ^ {n} = \ underbrace {X \ times X \ times \ cdots \ times X } _ {n} = \ {(x_ {1}, \ ldots, x_ {n}) \ | \ x_ {i} \ in X \ {\ text {для каждого}} \ i \ in \ {1, \ ldots, n \} \}.}

Примером этого является R= R× R× R, с R снова набор действительных чисел, и в более общем смысле R.

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

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

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

∏ i ∈ IX i = {f: I → ⋃ i ∈ IX i | (∀ я) (е (я) ∈ Икс я)}, {\ Displaystyle \ prod _ {я \ в I} X_ {я} = \ left \ {\ left.f: я \ к \ bigcup _ {я \ в I} X_ {i} \ \ right | \ (\ forall i) (f (i) \ in X_ {i}) \ right \},}{\ displaystyle \ prod _ {я \ in I} X_ {i} = \ left \ {\ left.f: I \ to \ bigcup _ {i \ in I} X_ {i} \ \ right | \ (\ forall i) (f (i) \ in X_ {i}) \ right \},}

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

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

π j: ∏ i ∈ IX i → X j, {\ displaystyle \ pi _ {j}: \ prod _ {i \ in I} X_ { i} \ to X_ {j},}{ \ displaystyle \ pi _ {j}: \ prod _ {i \ in I} X_ {i} \ to X_ {j},}

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

Декартова степень - это декартово произведение, где все множители X i являются одним и тем же набором X. В этом случае

∏ i ∈ IX i = ∏ i ∈ IX {\ displaystyle \ prod _ {i \ in I} X_ {i} = \ prod _ {i \ in I} X}\ prod _ {i \ in I} X_ {i} = \ prod _ {i \ in I} X

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

∏ n = 1 ∞ R = R × R × ⋯ {\ displaystyle \ prod _ {n = 1} ^ {\ infty} \ mathbb {R} = \ mathbb {R} \ times \ mathbb {R} \ times \ cdots}\ prod _ {n = 1} ^ {\ infty} \ mathbb {R} = \ mathbb {R} \ times \ mathbb {R } \ times \ cdots

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

Другие формы

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

Если несколько наборов умножаются вместе (например, X 1, X 2, X 3,…), то некоторые авторы предпочитают сокращать декартово произведение как просто ×Xi.

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

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

(f × g) (a, x) = (f (a), g (x)). {\ displaystyle (f \ times g) (a, x) = (f (a), g (x)).}{\ displaystyle (f \ раз g) (a, x) = (f (a), g (x)).}

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

Цилиндр

Пусть A {\ displaystyle A}A будет набором, а B ⊆ A {\ displaystyle B \ substeq A}{\ displaystyle B \ substeq A} . Тогда цилиндр B {\ displaystyle B}B относительно A {\ displaystyle A}A является декартовым произведением B × A {\ displaystyle B \ times A}{\ displaystyle B \ times A} из B {\ displaystyle B}B и A {\ displaystyle A}A .

Обычно A {\ displaystyle A }A считается юниверсом контекста и не учитывается. Например, если B {\ displaystyle B}B является подмножеством натуральных чисел N {\ displaystyle \ mathbb {N}}\ mathbb {N} , то цилиндр B {\ displaystyle B}B is B × N {\ displaystyle B \ times \ mathbb {N}}{\ 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. Декартово произведение графов не является произведением в смысле теории категорий. Вместо этого категориальный продукт известен как тензорное произведение графов.

См. Также

Ссылки

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

Последняя правка сделана 2021-05-14 10:36:30
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте