Декартово произведение множеств: примеры и формула

Декартово произведение - одна из базовых операций теории множеств, которая появляется в курсах дискретной математики, линейной алгебры и математического анализа уже на первом занятии. Её суть проста: берём два множества и собираем все возможные пары «по одному из каждого», причём порядок внутри пары важен. Именно из этой операции вырастает координатная плоскость, понятие отношения, функции и многое другое. Попробуйте калькулятор ниже, чтобы сразу увидеть, как из двух наборов элементов получается сетка пар, а затем разберём строгое определение и типичные задачи.

Определение и обозначение

Пусть $A$ и $B$ - два произвольных множества. Декартовым произведением $A \times B$ называется множество всех упорядоченных пар $(a, b)$, где $a \in A$ и $b \in B$:

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

Ключевое слово - «упорядоченная»: пара $(a, b)$ считается упорядоченной, если на первом месте всегда стоит элемент из $A$, а на втором - из $B$. Формально две упорядоченные пары равны тогда и только тогда, когда совпадают обе компоненты: $(a_1, b_1) = (a_2, b_2) \Leftrightarrow a_1 = a_2$ и $b_1 = b_2$.

Это отличает упорядоченную пару от неупорядоченного множества $\{a, b\}$, где $\{1, 2\} = \{2, 1\}$. В декартовом произведении $(1, 2) \neq (2, 1)$ - это разные пары, даже если числа одинаковые.

Термин «декартово» восходит к имени Рене Декарта: именно он ввёл систему координат, в которой каждая точка плоскости задаётся парой вещественных чисел $(x, y) \in \mathbb{R} \times \mathbb{R}$.

Рассчитать для своей задачи

Примеры декартова произведения

Рассмотрим конкретные примеры, начиная с самых простых.

Пример 1. Пусть $A = \{1, 2\}$, $B = \{a, b, c\}$. Тогда:

$$A \times B = \{(1,a),\, (1,b),\, (1,c),\, (2,a),\, (2,b),\, (2,c)\}.$$

Здесь $|A| = 2$, $|B| = 3$, и результат содержит ровно $2 \cdot 3 = 6$ пар.

Пример 2. $B \times A$ - произведение в обратном порядке:

$$B \times A = \{(a,1),\, (a,2),\, (b,1),\, (b,2),\, (c,1),\, (c,2)\}.$$

Мощность та же - $6$, но элементы разные: $(1, a) \in A \times B$, а $(a, 1) \in B \times A$. Значит, $A \times B \neq B \times A$ в общем случае.

Пример 3. Степень множества $A^2 = A \times A$. Для $A = \{0, 1\}$:

$$A^2 = \{(0,0),\, (0,1),\, (1,0),\, (1,1)\}.$$

Это четыре упорядоченные пары - все возможные двоичные строки длины 2. Заметьте, что $(0,1) \neq (1,0)$: порядок имеет значение.

Пример 4. $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$ - декартова плоскость. Каждая точка плоскости $(x, y)$ - это в точности элемент произведения $\mathbb{R} \times \mathbb{R}$. Так абстрактная операция над множествами становится привычной системой координат.

Рассчитать для своей задачи

Мощность декартова произведения

Если $A$ и $B$ - конечные множества, то мощность их произведения выражается простой формулой:

$$|A \times B| = |A| \cdot |B|.$$

Доказательство очевидно из принципа перемножения: для каждого из $|A|$ элементов первого множества можно выбрать любой из $|B|$ элементов второго, поэтому общее число пар равно $|A| \cdot |B|$.

Отсюда следует несколько свойств:

• Если $A = \varnothing$ или $B = \varnothing$, то $A \times B = \varnothing$ (нет пар, если хоть одно множество пусто).
• $|A \times B| = |B \times A|$, хотя сами множества в общем случае не равны.
• $|(A \times B) \times C| = |A \times B \times C| = |A| \cdot |B| \cdot |C|$ - операция ассоциативна по мощности.

Для тройного произведения $A \times B \times C$ элементами являются уже тройки $(a, b, c)$. Более общо, $A_1 \times A_2 \times \cdots \times A_n$ - это множество $n$-кортежей. Отдельный важный случай: $A^n = \underbrace{A \times \cdots \times A}_{n}$, мощность которого $|A|^n$. Именно так получают $\{0,1\}^n$ - множество всех двоичных строк длины $n$, удобное в комбинаторике и информатике.

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

Бинарное отношение между $A$ и $B$ - это любое подмножество $R \subseteq A \times B$. Декартово произведение играет роль «универсального» отношения: оно включает все возможные пары, а любое конкретное отношение выбирает из них нужные.

Например, отношение «меньше» на натуральных числах:

$${<} = \{(m, n) \mid m, n \in \mathbb{N},\ m < n\} \subseteq \mathbb{N} \times \mathbb{N}.$$

Функция $f: A \to B$ - частный случай отношения: каждому $a \in A$ соответствует ровно одна пара $(a, b) \in f \subseteq A \times B$. Таким образом, $A \times B$ - это фундамент, на котором строятся функции, графы и реляционные базы данных.

Связь с координатной плоскостью

Декартова плоскость $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$ - наглядная иллюстрация операции. Горизонтальная ось отвечает первой компоненте пары, вертикальная - второй. Точка $(3, -1)$ - это ровно та упорядоченная пара, где первый элемент $3 \in \mathbb{R}$, второй $-1 \in \mathbb{R}$.

Расширяя идею: $\mathbb{R}^3 = \mathbb{R} \times \mathbb{R} \times \mathbb{R}$ даёт трёхмерное пространство, $\mathbb{R}^n$ - $n$-мерное. Конечные случаи тоже важны: координатная сетка в калькуляторе выше - это именно такая визуализация конечного $A \times B$, где элементы расположены по осям.

Важный момент: на сетке хорошо видно, почему $A \times B \neq B \times A$ при $A \neq B$. Поменяв оси местами, мы получим транспонированную сетку - тот же набор элементов, но с переставленными компонентами.

Свойства декартова произведения

Сводная таблица основных свойств:

• Некоммутативность: $A \times B \neq B \times A$ при $A \neq B$ (хотя $|A \times B| = |B \times A|$).
• Дистрибутивность по объединению: $A \times (B \cup C) = (A \times B) \cup (A \times C)$.
• Дистрибутивность по пересечению: $A \times (B \cap C) = (A \times B) \cap (A \times C)$.
• Дистрибутивность по разности: $A \times (B \setminus C) = (A \times B) \setminus (A \times C)$.
• Произведение подмножеств: если $A_1 \subseteq A_2$ и $B_1 \subseteq B_2$, то $A_1 \times B_1 \subseteq A_2 \times B_2$.

Эти свойства позволяют упрощать выражения при доказательствах. Особенно часто в задачах встречается дистрибутивность по объединению: вместо перечисления пар из $(A \cup B) \times C$ удобно разбить на два случая.

Частые ошибки

• Путаница с порядком элементов. $(a, b)$ и $(b, a)$ - разные пары. Это принципиально: в отношении «отец–сын» $(Иван, Пётр)$ означает «Иван - отец Петра», а $(Пётр, Иван)$ - обратное.
• Считать $A \times B = B \times A$. Мощности совпадают, но сами множества отличаются, если $A \neq B$. Исключение - $A = B$: тогда $A \times A = A^2$ и симметрия формальна.
• Забыть, что пустое множество «уничтожает» произведение. $\varnothing \times B = \varnothing$ независимо от $B$. Часто путают с нулём при умножении - аналогия верная, но применять надо осознанно.
• Смешивать $A \times B$ с $A^2$. $A^2 = A \times A$, это частный случай. Если $A = \{1, 2\}$, то $A^2 = \{(1,1), (1,2), (2,1), (2,2)\}$ - здесь обе компоненты из одного и того же множества.
• Ошибка в мощности при тройном произведении. $|A \times B \times C| = |A| \cdot |B| \cdot |C|$, но не $|A|^3$ (кроме случая $A = B = C$). Каждый множитель - это своё множество со своей мощностью.

FAQ

Чем отличается декартово произведение от пересечения множеств? Пересечение $A \cap B$ содержит элементы, принадлежащие обоим множествам, - это подмножество $A$ и $B$ одновременно. Декартово произведение $A \times B$ - это совсем другой объект: множество упорядоченных пар, где первый элемент из $A$, второй из $B$. Пересечение «берёт общее», произведение «комбинирует всё со всем».

Что такое декартова степень $A^n$? $A^n = A \times A \times \cdots \times A$ ($n$ раз) - множество всех $n$-кортежей из элементов $A$. Мощность $|A^n| = |A|^n$. Частные случаи: $\{0,1\}^n$ - двоичные строки длины $n$ (применяется в теории кодирования), $\mathbb{R}^n$ - $n$-мерное евклидово пространство.

Почему порядок элементов в паре важен? Это соглашение нужно, чтобы пара однозначно задавала «роль» каждого элемента. В реляционных базах данных строка таблицы - это кортеж из фиксированных колонок: имя, возраст, город. Если бы порядок не важен, нельзя было бы отличить «имя Иван, возраст 25» от «имя 25, возраст Иван». Упорядоченность - основа формальных определений функций, отношений и структур данных.

Коротко

Декартово произведение $A \times B$ - это множество всех упорядоченных пар $(a, b)$ с $a \in A$, $b \in B$. Его мощность равна $|A| \cdot |B|$, операция некоммутативна, а геометрически соответствует координатной сетке. Из декартова произведения строятся отношения, функции, координатные пространства и реляционные базы данных. В калькуляторе выше можно задать любые размеры $|A|$ и $|B|$ от 1 до 5, подсветить «строку» пар для выбранного элемента и сразу увидеть весь список $A \times B$.